[논문리뷰] G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design

링크: 논문 PDF로 바로 열기

저자: Baoyun Zhao, He Wang, Liang Zeng

핵심 연구 목표

기존 LLM 기반 Automated Heuristic Design (AHD) 방법론이 고정된 휴리스틱 형태(구성 규칙 또는 매개변수화된 지역 탐색) 에 국한되어 탐색 공간을 제한하고 복잡한 조합 최적화 문제(COPs)에서 깊은 지역 최적해 를 탈출하기 어려운 문제를 해결하는 것이 목표입니다. 이 연구는 LLM 기반 AHD를 Large Neighborhood Search (LNS) 연산자의 자동 설계 로 확장하여 구조적 탐색 능력을 향상시키고자 합니다.

핵심 방법론

G-LNS는 LLM 을 활용하여 문제별 LNS 연산자를 자동으로 설계하는 생성적 진화 프레임워크 를 제안합니다. destroy 및 repair 연산자 를 위한 이중 모집단 아키텍처 를 유지하며, 적응형 LNS 프로세스 내에서 연산자 쌍을 공동으로 평가합니다. 시너지 행렬 을 통해 연산자 쌍의 협력적 성능을 명시적으로 포착하고 시너지 기반 교차(synergy-aware crossover) 를 통해 공동 진화를 유도하여 상호 보완적인 연산자 로직을 발견합니다.

주요 결과

Traveling Salesman Problem (TSP) 및 Capacitated Vehicle Routing Problem (CVRP) 벤치마크에서 G-LNS는 기존 LLM 기반 AHD 방법론 및 강력한 고전 솔버를 상당히 능가 했습니다. 특히, CVRP100/200 과 같은 대규모 인스턴스에서는 OR-Tools 솔버보다 우수한 솔루션을 식별했으며, CVRPLib Set F 에서 최적성 간극을 40.1%에서 15.9% 로 줄였습니다. 또한, MCTS-AHD(ACO) 대비 약 4.5배 빠른 70초 이내 에 거의 최적의 솔루션을 달성하며 계산 예산을 크게 절감했습니다.

AI 실무자를 위한 시사점

G-LNS는 LLM을 활용하여 알고리즘의 구조적 구성 요소 를 자동화하는 새로운 패러다임을 제시합니다. 이는 고정된 규칙이나 매개변수 최적화에서 벗어나 복잡한 위상 변환 을 가능하게 하여 NP-hard 문제 해결 의 효율성을 높입니다. AI 실무자들은 이 프레임워크를 통해 도메인 전문 지식에 덜 의존하면서도 고성능의 LNS 연산자 를 자동 생성하여 다양한 조합 최적화 문제에 적용할 수 있으며, 이는 시간 제약이 있는 애플리케이션 에서 특히 유용할 수 있습니다.

⚠️ 알림: 이 리뷰는 AI로 작성되었습니다.