반성적 진화로 LLM을 활용한 초휴리스틱 자동 설계

한줄 요약

ReEvo는 LLM을 초휴리스틱으로 사용하여 조합 최적화 문제의 휴리스틱을 자동 생성하는 방법으로, 진화 탐색과 LLM 반성을 결합해 효율적으로 휴리스틱 공간을 탐색한다.

풀어야 하는 문제

NP-난해 조합 최적화 문제는 도메인 전문가의 시행착오 기반 휴리스틱 설계에 의존한다. 기존 자동 설계 방법은 수동 개입이 많거나 휴리스틱 공간이 제한적이다. LLM을 활용한 초휴리스틱(LHH)은 이러한 한계를 극복할 잠재력이 있지만, 효율적인 탐색 전략이 부족하다.

접근 방법

ReEvo는 진화 알고리즘을 통해 휴리스틱 공간을 탐색하고, 각 세대에서 LLM 반성(reflection)을 통해 생성된 휴리스틱의 성능에 대한 언어적 피드백(verbal gradient)을 제공한다. 이 피드백은 다음 세대의 휴리스틱 생성에 가이드로 사용된다. 다양한 COP(외판원 문제, 배낭 문제 등)와 알고리즘 유형(메타휴리스틱, 진화 알고리즘, 휴리스틱, 신경망 솔버)에 적용 가능하다.

결과·기여

다섯 가지 이기종 알고리즘 유형, 여섯 가지 COP, 화이트박스 및 블랙박스 설정에서 최첨단 또는 경쟁력 있는 성능을 달성했다. 기존 LHH보다 샘플 효율성이 높아 더 적은 평가로 좋은 휴리스틱을 찾는다. LLM 기반 초휴리스틱의 새로운 패러다임을 제시하며, 자동 휴리스틱 설계 분야에 중요한 기여를 한다.