MuEvo: 대규모 언어 모델 기반 다중 휴리스틱 앙상블 진화

MuEvo: LLM-Driven Evolution of Multi-Heuristic Ensemble

대규모 언어 모델 기반 자동 휴리스틱 설계(LLM-AHD)는 조합 최적화 문제에 효과적인 휴리스틱을 발견하는 데 강력한 잠재력을 보여주었습니다. 그러나 기존 방법은 주로 단일 휴리스틱을 최적화하는 반면, 실제 최적화 프레임워크는 종종 여러 상호 작용 구성 요소에 의존합니다. 단일 휴리스틱 방법을 직접 확장하는 것은 어렵습니다. 왜냐하면 초기 구성 요소 선택은 늦게 잠재력이 있는 구성 요소를 간과할 수 있으며, 독립적인 진화는 구성 요소 간의 종속성을 무시하기 때문입니다. 본 논문에서는 앙상블 수준의 피드백을 통해 휴리스틱 앙상블을 진화시키는 LLM 기반 프레임워크인 MuEvo를 제안합니다. MuEvo는 검색 프로세스 전반에 걸쳐 구성 요소 우선 순위를 조정하는 데 사용되는 짧은 예산 탐색과 역전 가능 라이프사이클을 활용하는 동적 구성 요소 관리(Dynamic Component Management)와 다중 앙상블 평가, 상호 구성 요소 정보 공유, 관계 기반 쌍진화 및 적응적 예산 할당을 통해 구성 요소 개체군을 조정하는 LLM 기반 공동 진화(LLM-Driven Co-Evolution)를 결합합니다. MuEvo는 네 가지 조합 최적화 영역에서 선택형 하이퍼 휴리스틱과 모듈화된 蚁群 최적화에 대해 평가되었습니다. 결과적으로, MuEvo는 인간 설계 프레임워크보다 일관되게 성능이 향상되었으며, 최첨단 LLM-AHD 방법의 대표적인 다중 구성 요소 확장 방식보다 우수한 성능을 보였습니다. 이는 컨트롤러 기반 휴리스틱 풀과 기능적으로 분리된 알고리즘 구성 요소 모두에서 MuEvo의 효과를 입증합니다.

Large language model-based automated heuristic design (LLM-AHD) has shown strong potential in discovering effective heuristics for combinatorial optimization problems. However, existing methods primarily optimize a single heuristic, whereas practical optimization frameworks often rely on multiple interacting components. Directly extending single-heuristic methods is challenging because early component selection can overlook components with late potential, while independent evolution ignores inter-component dependencies. We propose MuEvo, an LLM-driven framework for evolving heuristic ensembles under ensemble-level feedback. MuEvo combines Dynamic Component Management, which uses short-budget probing and a reversible lifecycle to revise component priorities throughout the search, with LLM-Driven Co-Evolution, which coordinates component populations through Multi-Ensemble Evaluation, Cross-Component Information Sharing, Relation-Guided Pair Evolution, and Adaptive Budget Allocation. We evaluate MuEvo on selection hyper-heuristics and componentized ant colony optimization across four combinatorial optimization domains. Results show that MuEvo consistently improves human-designed frameworks and outperforms representative multi-component extensions of state-of-the-art LLM-AHD methods, demonstrating its effectiveness across both controller-mediated heuristic pools and functionally differentiated algorithmic components.