Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model

Heuristics are widely used for dealing with complex search and optimization problems. However, manual design of heuristics can be often very labour extensive and requires rich working experience and knowledge. This paper proposes Evolution of Heuristic (EoH), a novel evolutionary paradigm that leverages both Large Language Models (LLMs) and Evolutionary Computation (EC) methods for Automatic Heuristic Design (AHD). EoH represents the ideas of heuristics in natural language, termed thoughts. They are then translated into executable codes by LLMs. The evolution of both thoughts and codes in an evolutionary search framework makes it very effective and efficient for generating high-performance heuristics. Experiments on three widely studied combinatorial optimization benchmark problems demonstrate that EoH outperforms commonly used handcrafted heuristics and other recent AHD methods including FunSearch. Particularly, the heuristic produced by EoH with a low computational budget (in terms of the number of queries to LLMs) significantly outperforms widely-used human hand-crafted baseline algorithms for the online bin packing problem.

한 줄 요약

EoH는 LLM과 EC를 결합해 휴리스틱을 자동 생성하며, 휴리스틱 아이디어와 코드를 진화시켜 효율적인 알고리즘 설계를 가능하게 한다.

핵심 기여도

EoH는 휴리스틱의 아이디어(Thoughts)와 코드를 진화시켜 자동 휴리스틱 설계(AHD)를 수행한다.
GPT-3.5-turbo를 사용한 LLM 쿼리 수가 적은 조건에서도, 온라인 바인 팩킹 문제에서 기존 수작업 휴리스틱을 크게 초과한다.
5가지 프롬프트 전략을 도입해 LLM이 더 다양한 휴리스틱을 생성하도록 유도한다.
FunSearch 대비 훨씬 적은 LLM 쿼리 수로 유사 또는 더 우수한 휴리스틱을 생성한다.

핵심 아이디어

EoH는 휴리스틱의 고수준 아이디어를 자연어로 표현한 'Thoughts'를 진화시키는 새로운 패러다임이다. 이 'Thoughts'는 LLM을 통해 실행 가능한 코드로 변환되며, 이 두 요소(Thoughts와 코드)가 진화적 탐색 프레임워크 내에서 동시에 진화함으로써 최적화된 휴리스틱을 생성한다. 이는 기존 AHD 연구에서 휴리스틱을 수작업하거나, LLM만을 사용하는 방식보다 훨씬 효율적이고 효과적이다. 특히, EoH는 휴리스틱의 아이디어와 코드를 병렬적으로 진화시킴으로써, 인간 전문가의 설계 과정을 모방한다. 이는 휴리스틱 설계의 자동화와 최적화를 동시에 달성하는 핵심 통찰이다.

기술적 접근법

EoH는 휴리스틱의 고수준 아이디어를 자연어로 표현한 'Thoughts'를 진화시킨다.
LLM(GPT-3.5-turbo)을 사용해 'Thoughts'를 실행 가능한 코드로 변환한다.
E1과 E2라는 두 가지 진화 전략과 M1, M2, M3 세 가지 수정 프롬프트 전략을 사용한다.
온라인 바인 팩킹 문제에서 실험 시, 인구 크기는 20, 부모 휴리스틱 수는 5개로 설정된다.
EoC는 'Thoughts' 없이 코드만 진화시키는 변형 버전이다.

주요 결과

온라인 바인 팩킹 문제에서 EoH는 수작업 휴리스틱 대비 훨씬 높은 성능을 보인다.
FunSearch 대비 훨씬 적은 LLM 쿼리 수로 유사 또는 더 우수한 휴리스틱을 생성한다.
EoC는 EoH보다 성능이 낮아, 'Thoughts' 부분이 EoH의 성능에 중요한 기여를 함을 보여준다.
EoH-e2는 EoH보다 성능이 떨어지지만, E1과 E2만 사용해도 EoC보다 우수함을 보인다.

의의 및 한계

EoH는 휴리스틱 설계의 자동화를 가능하게 하며, LLM과 진화 계산을 결합한 새로운 패러다임으로, 휴리스틱 개발의 효율성과 유연성을 동시에 향상시킨다. 특히, 휴리스틱 아이디어와 코드를 병렬적으로 진화시키는 방식은 기존 AHD 연구에서 볼 수 없던 혁신적인 접근법이다. 그러나 EoH는 LLM의 질에 크게 의존하며, LLM의 오류나 편향이 휴리스틱 생성에 영향을 줄 수 있다. 또한, 특정 문제에 최적화된 프롬프트 전략이 필요하기 때문에, 일반화 가능성에 한계가 있을 수 있다.

실용적 활용

EoH는 복잡한 최적화 문제를 해결하는 산업 분야(예: 물류, 제조, 네트워크 최적화)에서 휴리스틱 설계를 자동화할 수 있는 도구로 활용될 수 있다. 연구 분야에서는 휴리스틱 개발의 반복적이고 수작업적인 과정을 줄이고, 다양한 문제에 대한 효율적인 알고리즘을 자동으로 설계하는 데 유용하다.