기술 요약: CoupleEvo

문제 정의

실제 세계의 최적화 시스템은 종종 높은 전체 성능을 달성하기 위해 조율되어야 하는 여러 개의 긴밀하게 결합된 하위 문제로 구성됩니다. 이러한 결합된 문제들은 종종 재고 경로 문제 (IRP) 나 다중 로봇 다중 베이 단위 하중 사전 정리 문제 (MR-MUPMP) 와 같이 두 개 이상의 NP-하드 하위 문제를 결합합니다. 하위 문제를 고립적으로 최적화하는 것은 종종 비최적의 전역 결과를 초래하는 반면, 완전히 통합된 동시 최적화는 결합된 해 공간의 조합적 성장으로 인해 계산적으로 처리 불가능한 경우가 많습니다.

기존의 대규모 언어 모델 (LLM) 기반 자동 휴리스틱 설계 프레임워크는 현재 단일 문제 설정에 국한되어, 단일 목적을 위해 단일 휴리스틱을 진화시키는 데 그칩니다. 결합된 최적화 문제를 위한 여러 상호작용하는 휴리스틱의 체계적 설계에 관한 연구는 부재하며, 특히 하위 문제 간의 상호의존성을 관리하기 위한 진화적 조율 전략이 부족합니다.

방법론: CoupleEvo

저자들은 결합된 최적화 문제를 위한 자동 휴리스틱 설계의 첫 번째 LLM 기반 프레임워크인 CoupleEvo를 제안합니다. 이 프레임워크는 반복적 대형 이웃 탐색 (LNS) 컨텍스트 내에서 작동하며, 여기서 LLM 은 각 하위 문제에 대한 **파괴 휴리스틱 (destroy heuristics)**을 생성하도록 할당되고, 수리 휴리스틱은 결정론적으로 유지됩니다.

진화적 조율 전략

CoupleEvo 는 상호의존적인 하위 문제에 걸친 진화적 탐색을 지배하기 위해 세 가지 고유한 전략을 도입합니다:

1. 순차적 진화 (Sequential Evolution): 휴리스틱은 한 하위 문제에서 다른 하위 문제로 순차적으로 진화됩니다. 하위 문제 $k$의 진화는 고정된 세대 수 동안 진행되며, 다른 모든 하위 문제는 현재 가장 성능이 좋은 휴리스틱 (고정됨) 을 사용합니다. 이는 개념적 단순성을 제공하지만, 먼저 진화된 휴리스틱이 후속 하위 문제의 탐색 공간을 제한하는 조기 수렴의 위험이 있습니다.
2. 반복적 진화 (Iterative Evolution): 진화는 여러 제어 라운드에 걸쳐 하위 문제 간에 교차합니다. 각 라운드에서 알고리즘은 모든 하위 문제를 순환하며, 이전 라운드의 최성능자 (best performers) 를 기반으로 휴리스틱을 정제합니다. 이 전략은 단일 하위 문제에 대한 과적합을 방지하고 조율을 위한 유연성을 유지하는 것을 목표로 합니다.
3. 통합적 진화 (Integrated Evolution): 모든 하위 문제에 대한 휴리스틱이 동시에 진화됩니다. LLM 은 모든 하위 문제에 대한 전체 휴리스틱 튜플 (코드 및 사고 과정) 을 단일 단계에서 생성하도록 프롬프트됩니다. 이는 명시적으로 상호의존성을 모델링하지만, 탐색 복잡성을 증가시키고 LLM 의 생성 능력에 더 높은 요구를 부과합니다.

구현 세부 사항

• LLM: 이 프레임워크는 오픈 소스 Qwen3-coder:30b 모델을 활용합니다.
• 프롬프팅: 시스템은 초기화 (I1), 탐색 (E1, E2), 수정 (M1, M2) 프롬프트를 포함한 기존 작업 (EoH, ReEvo) 에서 적응된 일련의 프롬프트 전략을 사용합니다.
• 평가: 적합도 (Fitness) 는 결합된 문제 인스턴스의 목적 함수 값을 기반으로 계산됩니다. IRP 의 경우 적합도는 최첨단 HGS 기준 대비 상대적 격차이며, MR-MUPMP 의 경우 평균 목적 함수 값입니다.
• 실험 설정: 이 프레임워크는 두 가지 도메인에서 테스트되었습니다:
  • IRP: 재고 관리와 차량 경로 통합.
  • MR-MUPMP: 이동 탐색 (이동 시퀀싱) 과 우선순위가 있는 차량 경로 통합.
  • 모든 전략은 공정한 비교를 위해 동일한 진화 예산 (총 40 세대) 을 할당받았습니다.

주요 기여

1. CoupleEvo 프레임워크: 자동 휴리스틱 설계를 단일 문제 설정에서 여러 상호의존적인 NP-하드 하위 문제를 가진 결합된 최적화 문제로 확장하는 첫 번째 LLM 기반 프레임워크의 수립.
2. 진화적 전략: 상호작용하는 하위 문제에 대한 휴리스틱이 생성되고 정제되는 방식을 정의하는 세 가지 조율 전략 (순차적, 반복적, 통합적) 의 제안 및 체계적 조사.
3. 종합적 평가: 두 가지 대표적인 결합된 최적화 도메인에 대한 광범위한 실험적 평가를 통해 수렴 안정성, 탐색 복잡성, 그리고 해의 질 사이의 트레이드오프에 대한 경험적 통찰을 제공.

실험 결과

이 연구는 IRP 와 MR-MUPMP 모두에 대해 전략당 6 회 실행하여 세 가지 전략을 평가했습니다.

• 분해 vs 통합: 분해 기반 전략 (순차적 및 반복적) 은 통합 전략에 비해 일관되게 더 안정적인 수렴과 더 높은 해의 질을 보여주었습니다.
• 순차적 전략: 첫 번째 하위 문제를 진화시킬 때 초기 적합도 향상이 빠르게 나타났습니다. 그러나 두 번째 하위 문제로 전환할 때 수렴이 종종 느려지거나 정체되었으며, 이는 첫 번째로 진화된 휴리스틱이 탐색 공간을 제한했음을 시사합니다. 이는 MR-MUPMP 에 대해 가장 좋은 평균 성능을 달성했습니다.
• 반복적 전략: 더 점진적이지만 일관되게 개선되는 추세를 보였습니다. 초점을 교차시킴으로써 조기 과적합을 완화하고 적응력을 유지했습니다. 이는 MR-MUPMP 에 대해 가장 좋은 최소 및 중앙값 적합도 값을 달성했으며, IRP 에 대해 가장 안정적인 결과 (가장 작은 범위) 를 보였습니다.
• 통합적 전략: 증가된 탐색 복잡성과 높은 변동성으로 고통받았습니다. 일부 실행은 경쟁력 있는 결과를 달성했지만, 이 전략은 일반적으로 더 약한 성능과 더 큰 분산을 보였으며, 이는 결합된 문제에 대해 고품질 휴리스틱 튜플을 일관되게 정제하는 데 어려움을 나타냅니다.

벤치마킹

최고 성능을 보인 진화된 휴리스틱 (CoupleLNS) 은 기존 문헌과 비교되었습니다:

• IRP: CoupleLNS 는 기존 메타휴리스틱 (MH) 보다 평균 5.61% 더 우수한 성능을 보였습니다. 광범위한 문제 특화 엔지니어링에 의존하지 않고 최첨단 하이브리드 유전 탐색 (HGS) 과 경쟁력 있는 결과를 달성했으며, 평균 격차는 2.96% 였습니다.
• MR-MUPMP: 최적 A* 를 사용하는 단계별 순차적 접근 방식 (SBS) 과 비교했을 때, CoupleLNS 는 해결 가능한 인스턴스에서 약간 낮은 해의 질을 보였지만, SBS 가 일부 인스턴스에서 실패한 반면 시간 제한 내에 모든 인스턴스를 성공적으로 해결했습니다. LLM 기반 휴리스틱을 사용하는 적응형 SBS* 와 비교했을 때, CoupleLNS 는 평균 5.01% 더 우수한 성능을 보였습니다.

중요성과 주장

이 논문은 CoupleEvo가 복잡한 결합된 최적화 문제를 위한 LLM 기반 자동 휴리스틱 설계의 잠재력을 보여준다고 주장합니다. 주요 발견은 상호의존적인 하위 문제에 걸친 진화적 탐색을 조율하는 것이 결정적이라는 것이며, 이러한 특정 문제 유형에 대해서는 분해 기반 전략 (순차적 및 반복적) 이 현재 통합적 진화보다 더 효과적입니다.

저자들은 그들의 작업을 기존 방법의 대체가 아닌 보완적 접근으로 위치시킵니다. 그들은 LLM 기반 방법이 기존 LNS 와 같은 프레임워크를 강화할 수 있는 매우 적합하고 문제 특화된 휴리스틱 구성 요소를 진화시킬 수 있다고 제안합니다. 이 작업은 통합적 진화가 구성 요소 간 상호작용을 포착하는 이론적으로 매력적이지만, 현재 LLM 능력과 탐색 복잡성은 문제를 분해하면서 반복적 조율을 유지하는 전략을 선호함을 강조합니다.

저자가 식명한 향후 연구 방향으로는 두 개 이상의 하위 문제를 가진 문제에 프레임워크를 적응시키는 것, 통합적 전략의 안정성을 개선하는 것, 그리고 최적화 문제 간에 동적으로 전환하는 적응형 조율 전략을 개발하는 것이 포함됩니다.