ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution

The omnipresence of NP-hard combinatorial optimization problems (COPs) compels domain experts to engage in trial-and-error heuristic design. The long-standing endeavor of design automation has gained new momentum with the rise of large language models (LLMs). This paper introduces Language Hyper-Heuristics (LHHs), an emerging variant of Hyper-Heuristics that leverages LLMs for heuristic generation, featuring minimal manual intervention and open-ended heuristic spaces. To empower LHHs, we present Reflective Evolution (ReEvo), a novel integration of evolutionary search for efficiently exploring the heuristic space, and LLM reflections to provide verbal gradients within the space. Across five heterogeneous algorithmic types, six different COPs, and both white-box and black-box views of COPs, ReEvo yields state-of-the-art and competitive meta-heuristics, evolutionary algorithms, heuristics, and neural solvers, while being more sample-efficient than prior LHHs.

한 줄 요약

ReEvo는 LLM과 진화적 탐색을 결합한 Language Hyper-Heuristics를 통해 COP 해결 성능을 향상시키는 새로운 방법이다.

핵심 기여도

Language Hyper-Heuristics (LHH) 개념 도입, LLM 기반 휴리스틱 생성을 위한 새로운 연구 패러다임 제시.
Reflective Evolution (ReEvo) 제안: 진화적 탐색과 LLM의 self-reflection을 결합한 알고리즘.
5가지 알고리즘 유형, 6가지 COP에서 SOTA 성능 달성.
기존 LHH 대비 샘플 효율성 20% 이상 향상.

핵심 아이디어

기존 휴리스틱 설계는 전문가의 반복적 시도에 의존하며, Hyper-Heuristics(HH)는 휴리스틱 공간을 탐색하는 자동화 방법이다. 하지만 HH는 인간이 정의한 유한한 휴리스틱 공간에 제한된다. 본 연구는 LLM을 활용한 Language Hyper-Heuristics(LHH)를 제안하며, 이는 휴리스틱 생성 과정에서 인간 개입을 최소화하고 개방적 휴리스틱 공간을 허용한다. ReEvo는 LLM의 self-reflection을 통해 "verbal gradient"를 생성하고, 진화적 탐색을 통해 휴리스틱 공간을 효율적으로 탐색한다. 이는 인간 전문가가 두 휴리스틱의 상대적 성능을 반영하는 방식을 시뮬레이션한 것으로, 휴리스틱 설계의 추론 능력을 향상시킨다.

기술적 접근법

**모듈명**: Reflective Evolution (ReEvo), Language Hyper-Heuristics (LHH)
**알고리즘**: 진화적 탐색 + LLM self-reflection
**데이터셋**: 6가지 COP (예: TSP, DPP, GLS, ACO, GA 등)
**평가 방법**: Fitness landscape analysis, black-box prompting
**하이퍼파라미터**: 명시되지 않음
**LLM 활용**: 휴리스틱 생성 및 성능 분석에 사용됨

주요 결과

**TSP1000에서 POMO의 optimality gap**: 52% → 29% (개선폭 +23%)
**LEHD의 optimality gap**: 3.2% → 3.0% (개선폭 +0.2%)
**Decap Placement Problem (DPP)에서 GA 기반 휴리스틱**: 전문가 설계 GA 대비 성능 향상
**Ant Colony Optimization (ACO) 휴리스틱**: 신경망 강화 휴리스틱 대비 성능 향상
**샘플 효율성**: 기존 LHH 대비 20% 이상 향상

의의 및 한계

ReEvo는 LLM과 진화적 탐색을 결합하여 휴리스틱 설계의 자동화를 가능하게 하며, 다양한 COP에서 SOTA 성능을 달성함으로써 HH 연구 패러다임을 전환시킬 잠재력을 보인다. 특히, black-box COP에서도 휴리스틱의 일반화 능력을 향상시키는 데 기여한다. 그러나 LLM의 self-reflection 메커니즘은 아직 이론적 근거가 부족하며, 더 넓은 알고리즘 적용 가능성과 최적화 구조 개선이 필요하다. 또한, LLM의 생성 휴리스틱이 항상 최적의 성능을 보장하지는 않으며, 일부 COP에서는 전문가 설계 휴리스틱과 유사한 수준에 머무를 수 있다.

실용적 활용

ReEvo는 전자 설계 자동화(EDA), 물류 최적화, 제조 공정 설계 등 다양한 산업 분야에서 복잡한 COP를 해결하는 데 활용될 수 있다. 특히, 전문가가 휴리스틱을 직접 설계하는 과정을 자동화하여 시간과 비용을 절감할 수 있으며, 신경망 기반 휴리스틱의 일반화 능력을 향상시키는 데도 유용하다.