기술 요약: LLM 지원 유연한 MCTS 를 통한 대규모 CVRP 솔버 설계 자동화

문제 정의

용량 제한 차량 경로 문제 (CVRP) 는 공급망 최적화의 핵심이지만, 수백에서 수천 개의 노드로 구성된 대규모 CVRP(LSCVRP) 인스턴스를 해결하는 것은 여전히 중요한 과제입니다. 문제의 NP-난해성으로 인해 탐색 공간은 인스턴스 크기에 따라 기하급수적으로 확장되어, 최첨단 솔버조차 대규모 데이터에서 성능 저하를 겪습니다.

'분할 정복' 전략, 즉 전역 문제를 관리 가능한 하위 문제로 분해하는 접근법은 효과적인 패러다임이지만, 실제 적용에는 두 가지 주요 장벽이 존재합니다:

1. 전문성 의존성: 효과적인 분해 로직을 설계하고 하위 솔버 매개변수를 보정하는 작업은 노동 집약적이며 도메인 전문 지식에 크게 의존합니다.
2. 현재 LLM 지원 알고리즘 설계 (LLMaAD) 의 한계: 기존 LLM 기반 접근법은 일반적으로 단일 '생각에서 코드'로 이어지는 단일 구조 (monolithic) 패러다임에 의존합니다. 이러한 방법들은 제한된 컨텍스트 창 내에서 LSCVRP 에 필요한 정교한 다중 구성 요소 아키텍처를 생성하는 데 어려움을 겪습니다. 또한, 대규모 인스턴스에서 후보 솔버를 평가하는 데 드는 막대한 계산 비용은 병목 현상을 초래하여 알고리즘적 가설 공간 내 탐색을 제한합니다.

방법론: LaF-MCTS

이러한 과제를 해결하기 위해 저자들은 LSCVRP 고성능 솔버 설계를 자동화하는 프레임워크인 LaF-MCTS(LLM 지원 유연한 몬테카를로 트리 탐색) 를 제안합니다. 이 방법론은 개발(최적 솔버 구성 탐색) 과 배포(발견된 최우수 솔버 적용) 의 두 단계로 운영됩니다.

1. 3 단계 의사결정 계층 구조

LLM 에게 단일 프롬프트로 전체 솔버를 생성하도록 강요하는 대신, LaF-MCTS 는 분해형 하이브리드 유전 알고리즘 (HGS) 에서 영감을 받은 계층적 접근법을 채택합니다. 이 계층 구조는 탐색 공간을 세 단계로 구성합니다:

• 1 단계 (전체 프레임워크 설계): LLM 은 메타휴리스틱 골격, 분해 세분성 (하위 문제 크기/수량), 실행 흐름 (예: 진화 사이클, 재통합 메커니즘) 을 정의하여 전역 알고리즘 아키텍처를 종합합니다.
• 2 단계 (분해 전략 설계): 프레임워크를 조건부로, LLM 은 대규모 그래프를 하위 문제로 분할하는 코드를 생성합니다. LLM 의 전문 도메인 지식 부족을 극복하기 위해, 이 단계는 11 가지 기존 CVRP 분해 코드 라이브러리를 활용한 퓨샷 프롬프팅(few-shot prompting) 전략을 사용하여 생성된 전략이 엄격한 도메인 제약 조건 (예: 하위 문제 동질성) 을 충족하도록 보장합니다.
• 3 단계 (하위 솔버 구성): 최하위 단계는 지역 적응에 중점을 둡니다. LLM 은 하이퍼휴리스틱 튜너 역할을 하여 각 분할의 특정 토폴로지와 규모에 맞춘 HGS 기반 하위 솔버의 매개변수 세트를 생성합니다.

2. 유연한 몬테카를로 트리 탐색 (MCTS)

이 프레임워크는 솔버 구성 요소의 조합 공간을 탐색하기 위해 토폴로지 유연한 MCTS 를 활용합니다. 탐색 과정은 다음을 포함합니다:

• 선택: 탐색과 활용의 균형을 맞추기 위해 트리 적용 상한 신뢰 구간 (UCT) 을 사용합니다.
• 확장: LLM 은 다음 단계에 대한 $K$개의 후보 코드 구성 요소를 생성합니다.
• 평가: 롤아웃 전략은 선택된 경로에서 완전한 솔버를 조립하여 고정된 훈련 인스턴스 세트에서 평가합니다. 보상은 최우수 알려진 해 (BKS) 에 대한 평균 간격으로 정의됩니다.
• 역전파: 보상은 방문 횟수와 가치 추정을 업데이트하기 위해 트리 위로 전파됩니다.

3. 시맨틱 가지치기 및 가지 재생성

LaF-MCTS 의 핵심 혁신은 코드 중복을 처리하고 다양성을 유지하는 메커니즘으로, LLM 이 구문적으로 다르지만 의미적으로 동일한 코드 (또는 그 반대) 를 생성하는 문제를 해결합니다.

• 시맨틱 가지치기: 중복 평가를 피하기 위해 시스템은 단어 및 문장 구조 이동자 거리 (WSMD) 를 사용합니다. 이 지표는 다음을 결합합니다:
  • 시맨틱 임베딩 정렬: 토큰 임베딩에 대한 단어 이동자 거리 (WMD) 사용.
  • 구조적 토폴로지 매칭: 제어 및 데이터 흐름 종속성을 포착하기 위해 자기 주의 행렬 (SAM) 에 대한 그로모프-워슈타인 거리 사용.
    두 코드 브랜치 간의 복합 거리가 임계값 미만이면 열등한 변형을 가지치기합니다.
• 가지 재생성: 가지치기로 인해 탐색 공간이 너무 좁아지는 것을 방지하기 위해 시스템은 가지 재생성을 트리거합니다. 노드가 가지치기되면 LLM 은 유지된 노드와 논리적이고 구조적으로 구별되는 새로운 후보를 생성하도록 부정 제약을 부여받아 프롬프트를 받습니다. 이를 통해 탐색 다양성을 유지합니다.

주요 기여

1. 새로운 프레임워크: 3 단계 계층 구조를 통해 인간 전문가의 구축 방식을 모방하여 LSCVRP 를 위한 분해 강화 솔버 설계를 자동화하는 LaF-MCTS 도입.
2. 계층적 탐색 공간: 프레임워크, 분해, 하위 솔버의 플러그 앤 플레이 알고리즘 템플릿 제안으로, LLM 이 제한적이지만 표현력 있는 구조 내에서 전문 구성 요소를 생성할 수 있게 하여 단일 구조 코드 생성의 한계를 극복.
3. 효율적인 탐색 메커니즘: 시맨틱 가지치기(WSMD 를 통해) 및 가지 재생성 메커니즘 개발. 이러한 기술은 중복 평가의 계산 병목 현상을 효과적으로 줄이면서 탐색이 지역 최적점에 머무르지 않도록 보장.
4. 최첨단 성능: LaF-MCTS 가 기존 메타휴리스틱, 신경 조합 최적화 (NCO) 방법 및 기타 LLMaAD 접근법보다 우수한 솔버를 자율적으로 구성할 수 있음을 입증.

실험 결과

저자들은 $N=100$부터 $N=1000$까지의 노드 수를 포함하는 100 개의 인스턴스를 다루는 CVRPLib 벤치마크에서 LaF-MCTS 를 평가했습니다.

• 성능: OR-Tools, HGS, HGS+BS, 다양한 NCO 모델 (예: RF-POMO, CaDA) 및 기타 LLMaAD 방법 (예: FunSearch, ReEvo, EoH) 을 포함한 모든 베이스라인과 비교하여 모든 문제 규모에서 LaF-MCTS 가 가장 낮은 평균 목적 함수 값과 최적성 간격을 달성했습니다.
• HGS+BS 와의 비교: 분해 기반 메타휴리스틱인 HGS+BS 는 표준 HGS 보다 우수했지만, LaF-MCTS 는 인간의 개입 없이 HGS+BS 를 능가하는 분해 기반 솔버를 생성하여 $[100, 200)$ 노드 규모에서 평균 최적성 간격 0.05%, $[800, 1000]$ 규모에서 **1.39%**를 달성했습니다.
• 절대 실험 (Ablation Studies):
  • 계층 구조: 전체 통합 3 단계 변형이 부분 변형 (예: 프레임워크 전용 또는 분해 전용) 보다 일관되게 우수하여 전체 계층의 필요성을 입증했습니다.
  • 공동 최적화: 분해 전략과 매개변수를 동시에 최적화하는 것이 어느 하나를 고정하는 것보다 더 좋은 결과를 낳았으며, 매개변수 튜닝은 분해 전략에 결정적으로 의존함이 확인되었습니다.
  • 가지치기/재생성: 시맨틱 가지치기 또는 가지 재생성 중 하나를 제거하면 성능이 저하되어 효율성과 다양성 간의 균형을 유지하는 데 이들의 역할이 확인되었습니다.
  • WSMD 구성 요소: 가지치기 지표의 시맨틱 (임베딩) 및 구조적 (토폴로지) 구성 요소 모두 효과적인 중복 감지를 위해 필수적인 것으로 나타났습니다.

중요성 및 주장

이 논문은 LaF-MCTS 가 복잡한 조합 최적화 문제를 위한 자동화된 알고리즘 설계에서 중요한 진전을 이루었다고 주장합니다. LLM 의 추론 능력과 고전적 알고리즘의 실행 속도를 연결함으로써, 이 프레임워크는 대규모 경로 문제에서 기존에 LLMaAD 를 제한했던 구조적 복잡성과 평가 비용 장벽을 성공적으로 극복합니다.

저자들은 그들의 접근 방식이 단순한 구성 휴리스틱을 넘어 복잡하고 다중 구성 요소 아키텍처를 발견하는 것을 넘어선다고 강조합니다. 결과적으로 생성된 솔버는 최첨단 인간 설계 메타휴리스틱 (HGS+BS 등) 과 신경 접근법의 성능을 능가합니다. 이 연구는 수동 최적화가 점점 더 어려워지는 분야에서 정교한 솔버 설계를 자동화하기 위한 유망한 경로로서 계층적 가지치기 강화 탐색을 시사합니다.

참고: 저자들은 현재 한계, 즉 아키텍처 다양성을 제한하는 전문가 정의 HGS 워크플로우에 대한 의존성을 인정하며, 완전한 자율 워크플로우 진화 활성화 및 일반성 향상을 위한 분해 포트폴리오 생성을 향후 과제로 제시합니다.