ImprovEvolve: AlphaEvolve를 활용하여 입력 솔루션을 개선하고, 추가적인 개선을 수행하는 방법

ImprovEvolve: Ask AlphaEvolve to Improve the Input Solution and Then Improvise

최근 LLM(대규모 언어 모델) 기반 진화 연산 분야, 특히 AlphaEvolve는 새로운 수학적 구조를 발견하고 어려운 최적화 문제를 해결하는 데 놀라운 성공을 거두었습니다. 본 논문에서는 LLM 기반 진화 방법, 특히 AlphaEvolve를 향상시키는 간단하면서도 효과적인 기법인 ImprovEvolve를 소개합니다. 최적화 문제에 대해, 일반적인 접근 방식은 실행 시 최적값에 가까운 솔루션을 생성하는 프로그램 코드를 진화시키는 것입니다. 우리는 최적 솔루션을 구성하는 능력을 유지하면서 LLM의 인지적 부담을 줄이는 대체 프로그램 매개변수화를 제안합니다. 구체적으로, 우리는 다음과 같은 기능을 제공하는 프로그램을 진화시킵니다: (1) 유효한 초기 솔루션을 제안, (2) 주어진 솔루션의 적합도(fitness)를 개선, (3) 특정 강도로 솔루션을 변경. 최적값을 도달하기 위해, improve() 및 perturb() 함수를 예약된 강도로 반복적으로 적용합니다. 우리는 ImprovEvolve를 AlphaEvolve 논문에 제시된 어려운 문제, 즉 육각형 패킹 문제(육각형 내 육각형 배치) 및 두 번째 자기 상관 부등식 문제에 대해 평가했습니다. 육각형 패킹 문제에서, 진화된 프로그램은 11, 12, 15, 및 16개의 육각형에 대해 새로운 최고 성능을 달성했습니다. 약간의 수동 편집을 거친 변형은 14, 17, 및 23개의 육각형에 대한 결과를 더욱 향상시켰습니다. 두 번째 자기 상관 부등식 문제에서, 수동 편집된 프로그램은 AlphaEvolve의 0.96102를 개선한 새로운 최고 성능의 하한인 0.96258을 달성했습니다.

Recent advances in LLM-guided evolutionary computation, particularly AlphaEvolve, have demonstrated remarkable success in discovering novel mathematical constructions and solving challenging optimization problems. In this article, we present ImprovEvolve, a simple yet effective technique for enhancing LLM-based evolutionary approaches such as AlphaEvolve. Given an optimization problem, the standard approach is to evolve program code that, when executed, produces a solution close to the optimum. We propose an alternative program parameterization that maintains the ability to construct optimal solutions while reducing the cognitive load on the LLM. Specifically, we evolve a program (implementing, e.g., a Python class with a prescribed interface) that provides the following functionality: (1) propose a valid initial solution, (2) improve any given solution in terms of fitness, and (3) perturb a solution with a specified intensity. The optimum can then be approached by iteratively applying improve() and perturb() with a scheduled intensity. We evaluate ImprovEvolve on challenging problems from the AlphaEvolve paper: hexagon packing in a hexagon and the second autocorrelation inequality. For hexagon packing, the evolved program achieves new state-of-the-art results for 11, 12, 15, and 16 hexagons; a lightly human-edited variant further improves results for 14, 17, and 23 hexagons. For the second autocorrelation inequality, the human-edited program achieves a new state-of-the-art lower bound of 0.96258, improving upon AlphaEvolve's 0.96102.