PyVRP$^+$: LLM 기반 메타인지 휴리스틱 진화 - 차량 경로 문제에서의 하이브리드 유전 알고리즘 검색

PyVRP$^+$: LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems

차량 경로 문제(VRP)와 같은 NP-hard 조합 최적화 문제에 대해 높은 성능을 보이는 메타휴리스틱을 설계하는 것은 여전히 중요한 과제이며, 종종 광범위한 도메인 전문 지식과 수동 튜닝이 필요합니다. 최근 연구에서는 대규모 언어 모델(LLM)이 진화적 검색을 통해 이 프로세스를 자동화할 수 있는 잠재력을 보여주었습니다. 그러나 기존 방법은 대부분 반응적이며, 즉, 성능 피드백에 의존하여 기본적으로 블랙박스 코드 변형을 안내합니다. 본 연구에서는 메타인지 진화 프로그래밍(MEP)이라는 프레임워크를 도입하여 이러한 패러다임에서 벗어나 LLM을 전략적 발견 에이전트로 끌어올립니다. MEP는 LLM이 단순히 성능 점수에 반응하는 것이 아니라, 구조화된 추론-행동-반성 주기를 통해 실패 원인을 명시적으로 진단하고, 설계 가설을 수립하며, 사전 제공된 도메인 지식을 기반으로 솔루션을 구현하도록 강제합니다. MEP를 사용하여 최첨단 하이브리드 유전 검색(HGS) 알고리즘의 핵심 구성 요소를 진화시켜, 원래의 기준 성능을 크게 능가하는 새로운 휴리스틱을 발견했습니다. LLM이 탐색-활용 균형에 대해 전략적으로 추론하도록 유도함으로써, 본 연구는 광범위한 VRP 변형에 적용 가능한 더 효과적이고 효율적인 휴리스틱을 발견합니다. 실험 결과, MEP는 원래의 HGS 기준 성능보다 상당한 성능 향상을 보이는 휴리스틱을 발견하며, 어려운 VRP 변형에서 솔루션 품질을 최대 2.70% 향상시키고 실행 시간을 45% 이상 단축했습니다.

Designing high-performing metaheuristics for NP-hard combinatorial optimization problems, such as the Vehicle Routing Problem (VRP), remains a significant challenge, often requiring extensive domain expertise and manual tuning. Recent advances have demonstrated the potential of large language models (LLMs) to automate this process through evolutionary search. However, existing methods are largely reactive, relying on immediate performance feedback to guide what are essentially black-box code mutations. Our work departs from this paradigm by introducing Metacognitive Evolutionary Programming (MEP), a framework that elevates the LLM to a strategic discovery agent. Instead of merely reacting to performance scores, MEP compels the LLM to engage in a structured Reason-Act-Reflect cycle, forcing it to explicitly diagnose failures, formulate design hypotheses, and implement solutions grounded in pre-supplied domain knowledge. By applying MEP to evolve core components of the state-of-the-art Hybrid Genetic Search (HGS) algorithm, we discover novel heuristics that significantly outperform the original baseline. By steering the LLM to reason strategically about the exploration-exploitation trade-off, our approach discovers more effective and efficient heuristics applicable across a wide spectrum of VRP variants. Our results show that MEP discovers heuristics that yield significant performance gains over the original HGS baseline, improving solution quality by up to 2.70\% and reducing runtime by over 45\% on challenging VRP variants.