Insights
AI가 자동으로 큐레이션·번역·정리하는 기술 동향 피드입니다.
대규모 라우팅 문제 해결을 위해 LLM 기반 자동 휴리스틱 설계(AHD)를 개선한 SpecAHD 프레임워크를 제안합니다. 이층 구조를 통해 인스턴스 내 전문화를 달성하며, 기존 AHD 대비 목적 함수 비용을 최대 57.7%까지 절감했습니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.AI의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기LLM 기반 자동 휴리스틱 설계 (Automated Heuristic Design, AHD)는 일반적으로 전체 인스턴스 또는 고정된 솔버 (Solver) 구성 요소 내에서 실행 가능한 프로그램을 평가합니다. 대규모 라우팅 문제 (Routing Problems)에서 국소적 재구성 (Localized Reconstruction)은 각 최적화 작업의 크기를 줄여주지만, 동일한 현재 최적해 (Incumbent) 내의 복구 영역 (Repair Regions)은 상당히 다른 구조를 보일 수 있습니다. 따라서 하나의 구성 규칙은 이들 사이에서 절충안을 찾아야만 합니다. 본 논문에서는 인스턴스 내 전문화 (Within-instance Specialization)를 위한 결합된 이층 구조 프레임워크 (Coupled Bilevel Framework)인 SpecAHD를 제안합니다. 상위 수준 (Upper-level) 탐색은 제한된 복구 영역을 노출할 위치를 학습하며, 하위 수준 (Lower-level) 탐색은 유도된 복구 작업 (Repair Tasks)에 대해 상호 보완적인 실행 가능 휴리스틱 레퍼토리 (Repertoire)를 진화시킵니다. 상위 수준 프로그램은 하위 수준에서 보는 복구 작업을 결정하며, 확인된 복구 결과는 상위 수준 프로그램이 어떻게 평가되는지를 결정합니다. 하위 수준의 목적 함수는 평균적으로 성능이 좋거나 현재 레퍼토리가 제대로 처리하지 못하는 작업을 해결하는 휴리스틱을 선호합니다. 고정된 상위 수준 프로그램과 고정된 하위 수준 후보 풀에 의해 유도된 복구 작업에 대해, 이 목적 함수는 단조 부가성 (Monotone Submodular)을 가지므로 (1-1/e) 근사 보장과 함께 탐욕적 레퍼토리 선택 (Greedy Repertoire Selection)이 가능합니다. 4가지 라우팅 문제와 여러 LLM 백본 (Backbones)에 대해, SpecAHD는 가장 강력한 경쟁 AHD 베이스라인 대비 홀드아웃 목적 함수 비용 (Held-out Objective Cost)을 최대 57.7%까지 줄였으며, 대부분의 공개 인스턴스에서 인스턴스별 베이스라인 엔벨로프 (Per-instance Baseline Envelope)를 능가했습니다.