영팽창 가우시안 분포는 분포 추정 알고리즘에서 매개변수 공간 희소성을 가능하게 합니다
Zero-Inflated Gaussian Distributions Enable Parameter-Space Sparsity in Estimation-of-Distribution Algorithms
한국어 초록
분포 추정 알고리즘(EDAs)은 블랙박스 최적화를 위한 강력한 진화적 방법의 부류로, 특히 목적 함수의 구조에 대해 알려진 바가 거의 없을 때 유용합니다. 고전적 진화 알고리즘은 미지의 문제 구조에 대해 고안하기 어렵고 바이어스(bias)의 원인이 되는 수동으로 설계된 돌연변이 및 교차 연산자에 의존하는 반면, EDAs는 연산자 설계를 완전히 우회합니다. 즉, 최적 개체들에게 확률 분포를 적합시키고 이로부터 다음 세대를 샘플링합니다. EDAs는 연속 매개변수 공간에서 잘 정립되어 있지만, 좋은 해의 대부분의 계수가 정확히 0인 희소 공간으로는 이전에 일반화된 적이 없습니다. 따라서 기존 희소 블랙박스 최적화 도구는 EDAs가 피하도록 설계된 바로 그 요소, 즉 수작업으로 제작된 희소성 연산자, 서포트 집합과 활성 값 사이를 번갈아 가며 전환하는 이중 수준(bi-level) 스킴, 제로화 임계값 및 기타 내재된 가정을 다시 도입합니다. 우리는 다변량 영팽창 가우시안(ZIG) 분포를 EDA 샘플링 법칙으로 제안하여 이 격차를 해소합니다. 지표와 값 차원이 분리된 잠재 가우시안 모델(model)은 희소성 패턴, 활성 매개변수 간의 상관관계, 그리고 이 둘 사이의 상호작용을 나타내므로, 희소성 패턴과 활성 값이 계층 구조 없이 공동으로 최적화됩니다. 우리는 이 모델의 잠재 매개변수(parameter)가 관련 구조가 기원한 결측 데이터 설정과 달리 관측된 샘플로부터 식별 가능함을 보이고, 이를 위한 실용적인 아모티즈드(amortized) 역전 기반 추정기를 소개합니다. 해당 추정기는 잠재 상관 구조를 정확하게 복원하며, Lunar Lander 벤치마크에서 결과적인 ZIG-EDA는 밀집 가우시안 EDA, 수작업 희소 진화 알고리즘, 임시적(ad-hoc) 희소 EDA보다 더 빠르게 수렴하고 더 높은 최종 수익에 도달하는 동시에, 소수의 매개변수만 활성화된 컨트롤러를 찾아냅니다.
원문 초록
Estimation-of-distribution algorithms (EDAs) are a powerful class of evolutionary methods for black-box optimization, especially when little is known about the structure of the objective. Whereas classical evolutionary algorithms rely on hand-designed mutation and crossover operators, hard to devise for unknown problem structures, and a source of bias, EDAs sidestep operator design entirely: they fit a probability distribution to the best individuals and sample the next generation from it. EDAs are well established on continuous parameter spaces, but they have not previously been generalized to sparse ones, in which most coefficients of a good solution are exactly zero. Existing sparse black-box optimizers therefore reintroduce exactly what EDAs were designed to avoid: hand-crafted sparsity operators, bi-level schemes alternating between support set and active values, zeroing thresholds, and other baked-in assumptions. We close this gap by proposing multivariate zero-inflated Gaussian (ZIG) distributions as EDA sampling laws. A latent Gaussian model with separate indicator and value dimensions represents sparsity patterns, correlations among active parameters, and the interactions between the two, so sparsity patterns and active values are optimized jointly, hierarchy-free. We show that the latent parameters of this model are identifiable from observed samples, unlike in the missing-data settings where related constructions originate, and introduce practical amortized inversion-based estimators for them. The estimators accurately recover latent correlation structures, and on the Lunar Lander benchmark the resulting ZIG-EDA converges faster and reaches higher final returns than a dense Gaussian EDA, a hand-crafted sparse evolutionary algorithm, and an ad-hoc sparse EDA, while finding controllers with only a small fraction of parameters active.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.19369v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
대규모 언어 모델을 활용한 온라인 자동 알고리즘 설계
Online Automated Algorithm Design with Large Language Models
대규모 언어 모델(LLM)은 추론과 코드 합성을 통해 자동 알고리즘 설계(AAD)를 가능하게 한다. 그러나 기존의 LLM 기반 AAD 방법 대부분은 알고리즘 설계와 대상 최적화를 분리하여, 최적화 상태가 변화하는 동안에도 고정된 설계를 그대로 배포한다. 기존의 적응형 옵티마이저는 이러한 변화에 대응할 수 있지만, 그 조정은 사전에 정의된 파라미터, 연산자 또는 전략의 범위에 국한된다. 이러한 한계를 해결하기 위해, 본 논문은 알고리즘 자체를 상태 의존적 결정 변수로 취급하는 새로운 최적화 패러다임인 온라인 LLM 기반 AAD를 제안한다. 각 단계에서 LLM 에이전트는 현재의 최적화 상태로부터 새로운 동작 로직을 갖춘 알고리즘을 합성한다. 생성된 알고리즘을 실행하면 탐색이 진행되고 이후 설계를 위한 피드백이 제공되므로, 별도의 오프라인 알고리즘 사전학습 단계 없이도 알고리즘 설계와 대상 최적화가 결합된다. 이 패러다임을 구현하기 위해 본 논문은 상충하는 설계 관점을 조율하여 실행 가능한 알고리즘을 합성하고, 실행 피드백을 활용해 이후 설계를 위해 런타임 증거를 해석하는 방식을 개선하는 멀티 에이전트 프레임워크인 OnDesign을 제안한다. 우리는 두 가지 주류 블랙박스 최적화 패러다임에 걸친 세 가지 시나리오, 즉 베이지안 최적화, 진화적 연속 최적화, 진화적 혼합 변수 최적화에서 OnDesign을 평가한다. 여섯 개의 벤치마크 스위트와 하나의 공학 문제에 대해 다양한 문제 차원에서 수행한 광범위한 실험을 통해, 기존 옵티마이저와 오프라인 LLM 기반 AAD 방법보다 우수한 전반적 성능을 보임을 입증한다.
블랙박스 최적화에서 대리 모델로서의 인공 신경망
Artificial Neural Networks as Surrogate Models in Black Box Optimization
블랙박스 최적화(Black-Box Optimization, BBO)는 여러 공학 분야에서 흔히 적용되며, 수치 측정 및 시뮬레이션 기술의 발전을 활용할 수 있다. 이는 해석적 기술(analytical description)이 존재하지 않는 최적화 함수를 다룬다. 이 방법은 탐색 공간 내의 입력점과, 센서, 실험, 시뮬레이션 등 비해석적 수단을 통해 얻어진 해당 목적 함수 값의 쌍만을 필요로 하는 방법에 의존한다. 일반적인 접근법으로는 진화적 최적화(evolutionary optimization)와 기타 메타휴리스틱(metaheuristics)이 있다. BBO 방법은 목적 함수 값에만 의존하기 때문에 일반적으로 많은 평가(evaluation)를 필요로 하며, 이는 목적 함수를 평가하는 데 시간이 많이 걸리거나 비용이 많이 드는 경우 문제가 된다. 이로 인해 선택된 실제 목적값을 평가하고 탐색 공간 전체에 걸쳐 목적 함수를 근사하는 회귀 모델을 학습시키는 대리 기반 최적화(surrogate-based optimization)를 사용하게 된다. 대리 모델 지원 블랙박스 최적화는 소량 데이터 학습(small-data learning) 문제인데, 이는 옵티마이저가 제한된 평가로부터 비용이 큰 목적 함수를 근사해야 하기 때문이다. 대리 모델은 데이터 효율적인 회귀자(regressor) 역할을 하며, 제한된 평가 예산(evaluation budget) 하에서 유망하거나 정보성이 높은 지점으로 탐색을 유도한다. 본 논문에서는 목적 함수의 선택적 평가를 위해 인공 신경망을 사용하는 새로운 대리 모델인 적응적 충실도 넥서스 공분산 행렬 적응 진화 전략(Adaptive-Fidelity Nexus Covariance Matrix Adaptation Evolution Strategy, AFN-CMA-ES)을 제안한다. 실험 결과는 최신(state-of-the-art) 대리 모델 지원 BBO 방법들과 비교하여 경쟁력 있는 성능을 보여준다.
MEMENTO: 메모리 유도 멤틱 Code-as-Policy 진화
MEMENTO: Memory-Guided Memetic Code-as-Policy Evolution
장기 호라이즌(long-horizon) 체화(embodied) 태스크는 태스크 성공을 관찰하기 전에 많은 종속적 액션을 실행하는 정책(policy)이 필요하다. 정책을 실행 가능한 제어 프로그램(code-as-policy)으로 표현하면, 롤아웃 평가 후 의사결정 로직을 검사하고 수정할 수 있다. 수정된 프로그램은 롤아웃 성능으로 실행·비교될 수 있으며, 이는 정책 개선을 실행 유도 프로그램 탐색으로 규정한다. 대규모 언어 모델(LLM)이 구동하는 진화적(evolutionary) 방법은 변이를 생성하고 고성능 후보를 선택함으로써 이러한 탐색을 위한 자연스러운 메커니즘을 제공한다. 그러나 기존 접근법은 주로 독립적으로 생성된 변이들 중에서 선택하며, 순차적 국소 개선 단계가 부족하다. 우리는 code-as-policy 진화를 위한 메모리 유도 단일 엘리트(single-elite) 멤틱(memetic) 프레임워크인 MEMENTO를 제안한다. MEMENTO는 먼저 정책 롤아웃을 스칼라 적합도(fitness)와 구조화된 피드백 지표로 매핑하는 롤아웃 평가자(evaluator)를 진화시킨다. 적합도는 수락된 후보와 다음 엘리트를 선택하고, 피드백 지표는 메모리 유도 힐클라이밍(hill-climbing), 거시 돌연변이(macro-mutation), 교차(crossover)로 생성된 정책 제안을 조건화한다. 우리는 Robosuite Franka Tower-of-Hanoi 조작과 AI2-THOR 가정 내 상호작용이라는 두 장기 호라이즌 체화 도메인에서 MEMENTO를 평가한다. MEMENTO는 code-as-policy 진화 베이스라인으로 적용한 Eureka 및 REvolve를 태스크 성공과 보류(hold-out) Robosuite 객체 구성 및 미관측 AI2-THOR 장면에 대한 일반화(generalization) 면에서 능가한다. 소거 실험(ablation)은 제로샷(zero-shot) 생성과 미진화 평가자가 두 도메인 모두에서 해결에 실패하며, 정책 탐색 분기를 제거하면 성능이 저하됨을 보여준다. 마지막으로, 우리는 최고로 진화된 Robosuite 정책을 물리적 Franka 로봇에 배포하여, 진화된 code-as-policy의 sim-to-real 전이 가능성을 입증한다. 코드, 프롬프트(prompt), 동영상은 https://github.com/sygkounas/MEMENTO 에서 확인할 수 있다.
NeurGO: 메타 블랙박스 고비용 최적화를 위한 엘리트 후보 생성 학습
NeurGO: Learning to Generate Elite Candidates for Meta-Black-Box Expensive Optimization
과학과 공학에서 고비용 블랙박스 최적화는 함수 평가가 비용이 크고 평가 예산이 제한적인 상황에서 널리 사용됩니다. 전통적인 진화 알고리즘과 메타 블랙박스 최적화(MetaBBO) 접근법은 일반적으로 대부분의 평가를 후보 선택에 소비하며, 종종 열등한 해에 소중한 예산을 낭비합니다. 서로게이트 보조 진화와 베이지안 최적화는 서로게이트 모델을 통해 평가 횟수를 줄이는 것을 목표로 하지만, 제한된 데이터로부터 정확한 전역 모델을 구축하는 것은 여전히 어려우며, 모델 바이어스가 탐색을 지역 최적해에 쉽게 갇히게 할 수 있습니다. 이러한 한계를 극복하기 위해, 우리는 역사적 개체군 상태로부터 엘리트 후보를 직접 합성하는 생성형 MetaBBO 프레임워크인 NeurGO를 제안합니다. 구체적으로, 개체군 수준의 탐색 추세를 포착하기 위해 어텐션 기반 인코더를 사용하고, 이 표현을 조건으로 디코더를 작동시켜 고품질 후보를 생성함으로써 대규모 자손 풀의 고비용 평가를 피합니다. 그다음 탐색 전반에 걸쳐 해의 품질과 개체군 다양성을 유지하기 위해 품질-다양성 손실을 설계합니다. CEC 2008 및 COCO BBOB 테스트 스위트에 대한 광범위한 벤치마킹을 통해, 우리 방법은 동일한 평가 예산 하에서 더 나은 최적화 성능을 달성하고 더 빠른 수렴을 보입니다.
빠른 Diffusion Policy 추론을 위한 진화형 캐시 스케줄
Evolving Cache Schedules for Fast Diffusion Policy Inference
Diffusion policy는 action chunk를 반복적으로 denoising하여 강력한 visuomotor control을 달성하지만, 반복적인 denoising은 실시간 배포를 계산적으로 부담스럽게 만든다. 캐시 기반 방법은 중간 활성화를 재사용하여 추론 비용을 줄이지만, 기존의 학습 없는 스케줄은 일반적으로 블록 전체에 계산을 균등하게 할당하여 블록 간 이질적인 중복성을 무시하고, 이로 인해 성능-효율성 trade-off가 최적이 아니다. 이 격차를 메우기 위해, 우리는 진화 탐색을 통해 캐시 갱신을 전역적으로 스케줄링하는 학습 없는 가속 프레임워크인 Evolving Cache Schedules(EVO)를 제안한다. EVO는 각 후보를 block-timestep lattice에 대한 완전한 스케줄로 표현한다. 따라서 반복적 denoising 동안 중복된 트랜스포머 계산을 캐시 재사용을 통해 건너뛸 수 있으며, 폐루프 롤아웃 성능을 유지할 수 있다. 탐색을 실용적으로 만들기 위해, EVO는 유망한 스케줄로 개체군을 시드하는 중복성 인식 초기화와, 원하는 성능 목표에 도달하면 검증하고 종료하는 목표 조건부 조기 종료를 도입한다. 오프라인으로 최적화된 스케줄은 재학습 없이 사전학습된 diffusion policy에 직접 연결할 수 있다. 광범위한 manipulation 벤치마크에서 EVO는 거의 완전한 성능을 유지하면서 계산량을 대폭 줄이며, action generation 속도를 최대 8.05배 향상하고 FLOPs를 15.77G에서 최저 1.96G까지 감소시킨다. 소스 코드는 https://github.com/pillom/EVO 에서 이용 가능하다.
노이즈 블랙박스 최적화를 위한 적응형 샘플링 기반 신뢰도 순위화
Confidence-based Ranking with Adaptive Sampling for Noisy Black-Box Optimisation
현실 세계의 최적화 문제는 종종 블랙박스 함수와 평가 과정의 불확실성을 포함하며, 이는 널리 노이즈 최적화 문제(NOPs)로 불린다. 진화 알고리즘(EA)은 진화 전략(ES)과 유전 알고리즘(GA)을 포함하여, 최근 문헌에서 이러한 문제를 해결하기 위해 널리 채택되어 왔다. 지속적인 과제는 양질의 적합도(fitness) 추정과 순위화를 위해 필요한 평가 횟수로 인한 계산 비용이다. NOPs에서 적합도 추정에 흔히 사용되는 두 가지 기본 방법은 암시적 평균화(implicit averaging)와 명시적 평균화(explicit averaging)이다. 명시적 평균화는 추정치를 개선하기 위해 해(solution)의 재샘플링(resampling)을 사용하는 반면, 암시적 평균화는 일반적으로 재샘플링을 적게 하면서 큰 집단 크기를 사용한다. 암시적 평균화는 특정 경우에 이론적 장점이 있는 것으로 나타났으며, 이는 최근 일부 접근법이 이를 사용하도록 동기를 부여했다. 그러나 최근 연구는 그 성능이 함수의 급기(steepness)와 일정한 노이즈 수준과 같은 특정 가정에 크게 의존하며, 이는 대다수의 현실 문제에 적용되지 않을 수 있음을 보였다. 게다가 기존 알고리즘의 대부분은 탐색 공간 전체에 걸쳐 변동의 진폭이 균일한 등분산(homoscedastic) 노이즈만을 고려했으며, 더 일반적인 이분산(heteroscedastic) 노이즈의 경우와는 대조적이다. 이러한 문제를 해결하기 위해, 우리는 이분산 테스트 문제 집합을 도입하고 샘플링 예산 적응을 갖춘 계산적으로 효율적인 명시적 평균화 전략을 사용하는 새로운 신뢰도 기반 순위화 방법을 제안한다. 이를 공분산 행렬 적응 ES(CMA-ES)와 GA 프레임워크 내에 구현하여 그 효과와 범용성을 입증한다. 결과 알고리즘은 등분산 및 이분산 노이즈를 모두 갖는 다양한 문제에서 평가되었으며, 최신(state-of-the-art) 접근법과 비교하여 우수한 성능을 보였다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.