잡음이 있는 QAOA 최적화를 위한 적응형 차분 진화 및 다중 시작 탐색
Adaptive Differential Evolution and Multistart Search for Noisy QAOA Optimization
한국어 초록
우리는 $N=12$, $p=3$, $D=6$ 조건에서 네 가지 비용 해밀토니안(cost-Hamiltonian) 계열에 걸쳐 고정된 저심도(low-depth) 양자 근사 최적화 알고리즘(Quantum Approximate Optimization Algorithm, QAOA) 앤자츠(ansatz)에 대한 고전적 최적화를 벤치마크한다. 10개의 옵티마이저를 10,000회 및 30,000회의 함수 평가(function evaluations, FEs)라는 공통 상한 하에서 25회의 독립 실행에 걸쳐 비교하며, 먼저 정확한 상태벡터(statevector) 목적함수로, 이후 두 가지 수준의 가산 관측 잡음(observation noise)을 적용하여 비교한다. 정확한 목적함수에서는 다중 시작(multistart) BFGS와 다중 시작 CMA-ES가 우세하다. 잡음이 있는 피드백 하에서는 적응형 개체군(population) 기반 방법들이 더 경쟁력을 갖게 되지만, 그 순위는 성능을 방문한 최적의 정확한 지점으로 측정하는지 아니면 잡음이 있는 관측값으로부터 선택된 지점으로 측정하는지에 따라 달라진다. 각 계열별로 사전 선별된 세 가지 인스턴스 전체에 대한 표적 확장 실험은 이러한 국면 전환(regime change)을 확인해주는 동시에, 명명된 적응형 차분 진화(adaptive-DE) 우승자들이 인스턴스에 따라 달라짐을 보여준다: 동일 인스턴스 요약에서 jSO-lite는 저잡음 오라클 탐색을, iL-SHADE는 고잡음 오라클 탐색을, L-SRTDE는 고잡음 선택 해(solution)를 각각 주도한다. 부트스트랩(bootstrap) 분석은 무시할 수 없는 수준의 고잡음 탐색-선택 격차(search-selection gap)를 정량화하며, 소급적 고정 예산 검증 프록시(retrospective fixed-budget verification proxy)는 최종 재평가를 위해 소량의 측정 예산을 남겨두는 것이 30,000 FEs에서 열 가지 방법 모두에 걸쳐 선택된 해의 품질을 향상시킴을 보여준다. 추가적인 구조 인식(structure-aware) 연구는 나아가 이러한 조건에서 QAOA의 교차 심도 제한(cross-depth restriction)과 연속적 분지 정제(continuous basin refinement)가 단독 몬테카를로 트리 탐색(Monte Carlo tree-search) 선택보다 더 유용함을 보여준다. 전반적으로 옵티마이저 선택은 지형 구조(landscape structure), 관측 잡음, 그리고 최종 지점 식별(final-point identification)에 공동으로 의존한다.
원문 초록
We benchmark classical optimization of a fixed low-depth Quantum Approximate Optimization Algorithm (QAOA) ansatz across four cost-Hamiltonian families at $N=12$, $p=3$, and $D=6$. Ten optimizers are compared over 25 independent runs under common ceilings of 10\,000 and 30\,000 function evaluations (FEs), first with exact statevector objectives and then with two additive observation-noise levels. Exact objectives favor multistart BFGS and multistart CMA-ES. Under noisy feedback, adaptive population methods become more competitive, but the ranking depends on whether performance is measured by the best exact point visited or by the point selected from noisy observations. A targeted extension over all three pre-screened instances per family confirms this regime change while showing that named adaptive-DE winners are instance dependent: jSO-lite leads low-noise oracle search, iL-SHADE high-noise oracle search, and L-SRTDE high-noise selected solutions in the equal-instance summaries. Bootstrap analysis quantifies a non-negligible high-noise search--selection gap, and a retrospective fixed-budget verification proxy shows that reserving a small measurement budget for final re-evaluation improves selected quality across all ten methods at 30\,000 FEs. A supplementary structure-aware study further shows that QAOA cross-depth restriction and continuous basin refinement are more useful in these conditions than standalone Monte Carlo tree-search selection. Overall, optimizer choice depends jointly on landscape structure, observation noise, and final-point identification.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.23180v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
평가 예산이 제한된 최적화를 위한 REMBGO: CEC2022 벤치마킹 및 EAF-STATCOM 일반화
REMBGO for Evaluation-Limited Optimization: CEC2022 Benchmarking and EAF-STATCOM Generalization
메타휴리스틱(metaheuristic) 비교는 비용이 큰 공학 시뮬레이션이 감당할 수 있는 수준보다 훨씬 더 큰 평가 예산에서 보고되는 경우가 많습니다. 본 논문에서는 EMBGO를 평가 예산 인식형으로 개선한 REMBGO를 제시합니다. 본 연구의 기여는 특정 단일 연산자가 아니라, 부모 대비 이점이 제한된 함수 평가 예산 하에 집중되는 개체군 보존, 척도 정규화 탐험(exploration) 및 복구 메커니즘들의 통합에 있습니다. REMBGO는 CEC2022에서 실제 응용에 맞춘 주요 예산인 1040회 함수 평가를 바탕으로 평가되었으며, 통제된 가설군이라기보다는 예산 의존성을 특성화하기 위해 주변 예산 래더(budget ladder)를 기술적으로 보고했습니다. 구성 요소 제거(component-removal) 연구 결과 다중성 보정(multiplicity correction)을 통과하는 개별 메커니즘은 발견되지 않았으며, 이는 단일 연산자가 아닌 통합적 기여라는 점과 일치합니다. 이후 이 알고리즘은 EAF-STATCOM 제어기 튜닝에 적용되었고, 도출된 고정 게인 벡터는 재튜닝 없이 사전에 지정된 20개의 미확인 확률적 아크 실현($210$회 고정 게인 시뮬레이션, 모두 실행 가능)으로 전이되었습니다. 선택된 게인 벡터 주효과는 교차 검증(validation) 변량의 $3.6$--$5.8\%$만을 설명하는 반면, 상호작용 및 잔차는 약 $61.4\%$를 차지했으며, 매칭된 REMBGO-EMBGO 쌍체 차이는 부호 면에서 제어기에 따라 달라졌고 통계적으로 유의미하지 않았습니다. 따라서 REMBGO는 보편적으로 우수한 옵티마이저(optimizer)라기보다는 평가 예산과 함께 이점이 명시되어야 하는 자원 인식형 개선 기법으로 제시됩니다.
SqueezeBench: 포화에 강건한 수학적 능력 평가
SqueezeBench: Saturation-Resilient Evaluation of Mathematical Capability
AI 시스템은 수학 분야에서 빠르게 발전하고 있지만, 이러한 발전을 측정하기는 어렵다. 이미 풀린 문제들로 구성된 벤치마크(benchmark)는 포화(saturate)되며, 미해결 문제들로 구성된 벤치마크에서는 각 문제가 최초로 단 한 번만 해결될 수 있다. 우리는 포화에 강건한 벤치마크인 SqueezeBench를 제시한다: 성공은 문제를 제거하는 대신 기준을 높인다. 각 문제는 작은 $n$에 대해서만 값이 알려진 정수 함수 $f(n)$을 고정하며, 벤치마크는 이에 대한 하한(lower) 기록과 상한(upper) 기록을 유지한다. 기록(record)은 $f$를 한정(bound)함을 기계 검증된 증명(machine-checked proof)으로 보인 계산 가능한 Lean 함수이다. 제출(submission)은 새로운 함수를 제안하고, 그 함수가 $f$를 한정하며, 모든 $n$에서 현재 기록보다 나쁘지 않고, 일부 $n$에서는 엄밀히 더 우수함을 증명한다. 채택되면 해당 제출은 다음 제출이 넘어서야 할 새로운 기록이 된다. 따라서 이 시스템은 한계값(bound)뿐 아니라 그 증명까지 선택하며, 단일 $n$에서의 기록을 개선할 수도 있고 성장률(growth rate)을 개선할 수도 있다. 모든 $n$에서 두 기록 사이의 간극은 인증된 한계값들이 $f(n)$을 결정하는 데에서 얼마나 떨어져 있는지를 보여준다. 모든 증명은 두 개의 독립적인 Lean 커널에 의해 검증되므로, 심판이 수학적 내용을 검토할 필요가 없다. 검증 과정은 또한 작은 $n$에서 전수 탐색(exhaustive search)으로 $f$를 계산하는 함수를 거부하며, 유지관리자(maintainer)는 제출자의 보고서만 읽고 더 큰 $n$에서 그러한 탐색이 있는지를 확인한다. 우리는 극단적 조합론(extremal combinatorics) 분야의 열 가지 문제를 스무 개의 증명된 초기 기록 및 승인 도구(admission tools)와 함께 공개한다. 기준선(baseline)으로서, 최신(frontier) 언어 모델(language model) 기반 에이전트(agent)는 기록당 최대 한 시간을 사용하여 82건의 제출을 승인받았고 모든 기록을 개선했으며, 이는 기존 발표된 문헌의 범위를 넘어서지는 않았다. 이후 두 개의 더 새로운 모델(model) 기반 에이전트들이 이 기록들로부터 시작하여 60건의 추가 제출을 승인받았고, 20개의 기록 중 19개를 다시 개선했다. 열 가지 문제 중 여덟 가지 문제에서는, 적어도 하나의 기록이 여전히 발표된 최선의 한계값(bound)에 비해 점근적으로(asymptotically) 뒤처져 있다.
LLM을 활용한 제로샷 교차 문제 일반화를 위한 다중 작업 진화
Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs
다양한 조합 최적화(combinatorial optimization) 문제를 위한 효과적인 휴리스틱(heuristic)을 설계하는 것은 상당한 전문성과 반복적인 탐색을 필요로 합니다. 대규모 언어 모델(LLM)은 휴리스틱 생성과 개선을 자동화하지만, 휴리스틱 탐색은 일반적으로 최적화 대상 문제의 평가 피드백에 의존합니다. 따라서 소스 작업 피드백만을 사용하여 새로운 문제 정의로 일반화하는 것은 여전히 핵심적인 과제로 남아 있습니다. 본 논문에서는 제로샷(zero-shot) 교차 문제 일반화를 위한 LLM 기반 다중 작업 진화 프레임워크인 MECo를 소개합니다. MECo는 작업 조건부 휴리스틱 개체군을 유지하며, 교차 작업 개체군 성능에 기반한 전이 격차(transfer gap)를 활용해 이들의 상호작용을 유도합니다. 이러한 상호작용은 휴리스틱의 전이와 재조합을 가능하게 합니다. 그런 다음 상호보완적 선택 기준을 통해 각 개체가 소스 조합에 대해 제공하는 추가적인 커버리지를 보상함으로써 간결한 휴리스틱 세트를 구성합니다. 선택된 세트는 추가적인 탐색이나 적응 과정 없이 타깃 문제에 바로 적용됩니다. 차량 경로 문제(VRP) 및 유연한 잡숍 스케줄링(FJSP) 전반에 걸친 32가지 변형 문제를 대상으로 한 실험에서, MECo는 동일한 예산 하에 8개의 자동화된 휴리스틱 설계(AHD) 기준선과 비교해 가장 낮은 평균 비용을 달성함을 보여줍니다. 도메인 외(OOD) 문제에서도 각 제품군에서 가장 강력한 기준선을 능가합니다. 나아가 MECo 프레임워크를 서로 다른 AHD 방법들과 통합했을 때 두 제품군 모두에서 ID 및 OOD 성능이 향상되어, 여러 방법 전반에 걸친 유효성을 뒷받침합니다.
CityDeploy-Bench: 다중 송신기 네트워크 배치를 위한 물리 기반 공간 집합 계획 벤치마킹
CityDeploy-Bench: Benchmarking Physics-Grounded Spatial Set Planning for Multi-Transmitter Network Deployment
도시 규모의 무선 배치 자동화는 복잡한 도심 전파 환경과 네트워크 전역의 간섭 속에서 여전히 어려운 과제로 남아 있다. 본 논문에서는 다중 송신기 배치 문제를 통합된 광선 추적(ray-tracing) 검증기 하에서 물리 기반 공간 집합 계획(physics-grounded spatial set planning) 문제로 재구성한 벤치마크인 CityDeploy-Bench를 소개한다. 이 벤치마크는 유틸리티(utility) 표현과 계획 다이내믹스를 분리함으로써, 다양한 플래너(planner)에 대해 직접적인 스칼라 보상, 관계형 모델, 그리고 고차 상호작용 구조 간의 통제된 비교를 가능하게 한다. 실험 결과, 물리적 결합(coupling)이 커질수록 계획 행동에서 명확한 전환이 나타난다. 배치 품질은 학습된 유틸리티가 송신기 간의 집합적 상호작용을 포착하는지에 점점 더 의존하게 되며, 반면 더 강력한 탐색만으로는 누락된 관계형 구조를 보완할 수 없다. 이는 다중 송신기 배치가 독립적인 공간적 의사결정들의 집합이 아니라, 물리적으로 상호작용하는 집합에 대한 조정(coordination) 문제임을 보여준다. 우리는 의사결정 학습(decision learning)과 물리 기반 무선 네트워크 설계를 연결하는 연구를 위한 재현 가능한 테스트베드로서 CityDeploy-Data와 벤치마크 프레임워크를 공개한다.
검증자가 정답을 유출할 수 있다: 폐루프 에이전트 디버깅에서 최적화에 앞선 진단 가능성
A Verifier Can Leak the Answer: Diagnosability Before Optimization in Closed-Loop Agent Debugging
에이전트(agent) 개발자들은 시뮬레이터 기반 검증자(verifier)를 통해 프롬프트, 도구, 정책 및 진단 알고리즘을 비교하는 방식을 점점 더 많이 활용하고 있습니다. 그러나 검증자는 솔버(solver) 비교를 무의미하게 만들 수도 있습니다. 즉, 검증자의 프로브(probe)나 술어(predicate)가 타깃의 식별 정보를 인코딩하고 있다면, 정확한 옵티마이저(optimizer)는 어떠한 실질적인 모호성도 해결하지 못한 채 효과적인 것처럼 보일 수 있습니다. 본 연구에서는 폐루프(closed-loop) 의사결정 에이전트를 위한 집계 트레이스 디버거에서 발생하는 이러한 실패 사례를 보고합니다. 정확한 최소 적중 집합(Minimum Hitting Set, MHS)과 전파 인식 탐욕 알고리즘(propagation-aware greedy method)은 12개 개발 사례 모두에서 동일한 지지 집합(support)을 반환했으며, 9/12 사례에서 동일한 주입 결함(planted fault) 복구를 달성했습니다. 후속 감사 결과, 정확한 앵커(exact-anchor) 술어가 9/9 사례에서 주입된 쌍을 생성한 것으로 확인되었습니다. 해당 앵커들을 제거한 후 전체 주입 쌍 복구율은 8/9였습니다. 그럼에도 불구하고 하드 프로브 싱글톤(hard-probe singleton) 쌍은 9/9 사례에서 주입된 쌍과 일치했으며, 전파 후 비어 있지 않은 잔여 충돌군(residual conflict family)이 유지된 사례는 전무했습니다(0/9). 옵티마이저는 올바르게 작동했으나, 검증자가 이미 정답을 노출하고 있었던 것입니다. 이에 본 논문에서는 솔버 우선 평가 방식을 지지 집합 기반 게이팅(support-gated) 검증 규약으로 대체합니다. 먼저 클린 참조 맵(clean reference map)을 통해 반복적인 컴포넌트 노출을 입증해야 하며, 그다음 일치된 참조/현재 게이트를 통해 비교 가능한 런타임 증거를 확립해야 하고, 그 이후에만 독립적으로 보정된 신호 규칙이 탐지 결과를 반환할 수 있습니다. 1,440개의 사례와 21,600개의 파티션 행으로 구성된 사전 등록된 홀드아웃(heldout) 평가에서, 55/72 체제-컴포넌트(regime-component) 단위가 참조 게이트를 통과했고, 54/55가 런타임 게이트를 통과했으며, 표현된 컴포넌트의 안정적 위허용(stable false admission)은 단측 정확 95% 상한선 0.1391과 함께 0/20을 기록했습니다. 승인된 단위 내에서는 영향을 받은 정상 트래픽이 공칭 결함 셀 비율(nominal fault-cell fraction)보다 탐지를 더 잘 예측했습니다. 본 연구의 핵심적인 구조적 교훈은 컴포넌트 선택기를 최적화하기 전에 증거의 적격성과 비공개성(non-revelation)을 먼저 검증해야 한다는 점입니다. 그렇지 않으면 더 강력한 솔버가 단지 더 강력한 검증자 아티팩트(artifact)를 인증하는 것에 불과할 수 있습니다.
유전 알고리즘을 이용한 통계적 품질 관리 절차 설계
Design of statistical quality control procedures using genetic algorithms
일반적으로, 거짓 기각 확률을 최소화하면서 명시된 확률로 중요한 무작위 및 체계적 분석 오류를 검출하도록 품질 관리(QC) 절차를 최적화하는 데 대수적 또는 열거적 방법을 사용할 수 없다. 유전 알고리즘(GA)은 최적화할 목적 함수에 대한 사전 지식을 요구하지 않고 대규모 매개변수 공간을 빠르게 탐색하므로 대안이 될 수 있다. 통계적 QC에서 GA의 적용 가능성을 탐구하기 위해, 주어진 분석 프로세스에 대해 새로운 근사 최적 QC 절차를 설계하는 GA 기반 대화형 컴퓨터 프로그램을 개발하였다. 이 프로그램은 결정론적 크라우딩(deterministic crowding) 알고리즘을 사용한다. 프로그램의 예시적 적용 결과, 임상 실험실에서 사용되는 45개의 대안적 QC 절차보다 유의미하게 우수한 QC 절차를 설계할 수 있는 잠재력이 있음을 보여준다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.