🤖 AI

Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation

이 논문은 LLM 유도 진화적 합성을 활용하여 구조적으로 현실적인 훈련 인스턴스를 생성하고 신경 솔버를 점진적으로 적응시킴으로써, 합성 데이터와 TSPLib 및 CVRPLib와 같은 실제 경로 최적화 벤치마크 사이의 일반화 격차를 크게 좁히는 프레임워크인 EvoReal을 소개한다.

원저자: Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li

게시일 2026-01-30

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Jianghan Zhu, Yaoxin Wu, Zhuoyi Lin, Zhengyuan Zhang, Haiyan Yin, Zhiguang Cao, Senthilnath Jayavelu, Xiaoli Li

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

큰 문제: "보조 바퀴" vs "실제 도로"

당신이 로봇에게 세계 최고의 배달 기사가 되는 법을 가르치고 있다고 상상해 보세요.

현재 상황:
현재 우리는 이 로봇들(이를 **뉴럴 솔버(Neural Solvers)**라고 부릅니다)을 "보조 바퀴"를 달고 가르칩니다. 우리는 컴퓨터를 이용해 집들이 체스판처럼 격자무늬로 완벽하게 배치된 수백만 개의 가짜 배달 경로를 생성합니다. 로봇은 이 완벽하고 격자 형태인 퍼즐을 푸는 데 매우 능숙해집니다.

문제점:
하지만 그 로봇을 실제 세상으로 데려가면, 로봇은 충돌하고 맙니다. 실제 도시는 격자 구조가 아닙니다. 실제 도시는 집들이 밀집해 있기도 하고, 구불구불한 도로가 있으며, 기묘한 패턴들을 가지고 있습니다. 완벽한 격자 구조에서만 훈련받은 로봇은 혼란에 빠져 엉망인 배달 경로를 만듭니다. 이를 **일반화 격차(generalization gap)**라고 부릅니다. 이는 마치 잔잔하고 빈 수영장에서 수영하는 법을 배운 사람을 파도와 조류가 치는 폭풍우 치는 바다에 던져놓는 것과 같습니다.

해결책: EvoReal ("스마트 시뮬레이터")

이 논문의 저자들은 EvoReal이라는 새로운 시스템을 만들었습니다. 로봇을 그냥 실제 바다에 던져 넣는 대신, 로봇이 수영장에서 떠나기 전에 폭풍을 다루는 법을 가르쳐 줄 "스마트 시뮬레이터"를 구축한 것입니다.

작동 방식은 다음과 같습니다.

1. "설계자" (LLM)

연구진은 거대언어모델(LLM)을 사용했습니다. 이것을 아주 똑똑하고 창의적인 설계자라고 생각하세요. 이 설계자의 역할은 트럭을 운전하는 것이 아니라, 훈련 코스를 설계하는 것입니다.

보통 우리는 그냥 무작위로 훈련 코스를 만듭니다. 하지만 LLM은 실제 세계의 배달 지도(유명한 TSPLib 및 CVRPLib 벤치마크 등)를 살펴보고 이렇게 말하도록 요청받습니다. "음, 실제 도시들은 이런 특정한 패턴을 가지고 있네. 어떤 구역은 붐비고, 어떤 구역은 흩어져 있고, 어떤 구역은 반복되는 모양을 가지고 있어."

2. "진화적 체육관" (생성기 진화)

LLM은 단 하나의 코스만 설계하는 것이 아니라, **진화적 체육관(evolutionary gym)**을 운영합니다.

생성(Generation): LLM은 실제 도시와 똑같이 보이는(밀집 지역, 빈 공간, 기묘한 모양 등을 가진) 가짜 배달 경로를 만드는 코드를 작성합니다.
테스트(Testing): 이 가짜 경로들을 로봇에게 테스트합니다.
성찰 및 개선(Reflection & Improvement): 만약 로봇이 특정 유형의 가짜 경로에서 어려움을 겪는다면, LLM은 코드를 살펴보고 *"아, 이 생성기는 클러스터(밀집 지역)를 충분히 촘촘하게 만들지 못했구나"*라고 판단한 뒤, 다음 배치(batch)의 가짜 경로가 훨씬 더 현실적이 되도록 코드를 다시 작성합니다.
결과: 시간이 흐름에 따라, LLM은 합성 데이터를 실제 세계와 통계적으로 유사하게 만드는 "생성기"를 진화시킵니다.

3. "점진적 훈련" (사다리)

LLM이 이 완벽한 "실제 세계와 유사한" 훈련 코스를 구축하고 나면, 로봇은 곧바로 가장 어려운 단계로 뛰어들지 않습니다. 로봇은 사다리를 오릅니다.

1단계 (가교/Bridge): 로봇은 먼저 LLM의 새로운 현실적인 합성 데이터로 훈련을 받습니다. 로봇은 클러스터와 불규칙한 패턴을 다루는 법을 안전한 시뮬레이션 환경에서 배웁니다. 이는 인공 파도가 치는 수영장에서 연습하는 것과 같습니다.
2단계 (실전/The Real Deal): 로봇이 자신감을 얻으면, 실제 실제 세계의 벤치마크 문제들을 대상으로 짧은 최종 훈련 세션을 가집니다. 이미 1단계에서 실제 도시의 "분위기"를 배웠기 때문에, 로봇은 즉각적으로 적응합니다.

결과: "체스 고수"에서 "도시의 그랜드마스터"로

이 논문은 두 가지 유명한 실제 경로 문제 세트(TSPLib 및 CVRPLib)에 대해 테스트를 진행했습니다.

EvoReal 적용 전: 최고의 AI 모델들은 특정 유형의 수학 시험만을 위해 공부한 학생들과 같았습니다. 실제 문제를 마주했을 때, 이들의 점수는 크게 떨어졌습니다 (때로는 30% 이상).
EvoReal 적용 후: 이 방식으로 훈련된 모델들은 믿기 힘들 정도로 강력해졌습니다.
- TSPLib(외판원 문제) 벤치마크에서, 이들의 솔루션과 완벽한 해답 사이의 격차는 단 **1.05%**로 줄어들었습니다.
- CVRPLib(차량 경로 문제) 벤치마크에서, 격차는 **2.71%**로 줄어들었습니다.

핵심 요점:
이 논문은 LLM을 사용하여 (로봇 자체를 진화시키는 것이 아니라) 더 나은 훈련 데이터를 진화시킴으로써, 가짜와 진짜 사이의 간극을 메웠다고 주장합니다. 로봇은 "실제" 데이터와 똑같이 느껴지는 "가짜" 데이터를 통해 일반화하는 법을 배웠습니다.

요약 비유

기존 방식: 조종사에게 바람이 없는 시뮬레이터에서 비행하는 법을 가르친 다음, 허리케인 속으로 보내는 것.
EvoReal 방식: AI를 사용하여 허리케인의 난기류, 윈드시어(wind shear), 폭풍을 완벽하게 재현하는 시뮬레이터를 설계하는 것. 조종사는 이 초현실적인 시뮬레이터에서 훈련을 받은 후, 실제 비행기에 올라타 완벽하게 비행합니다.

이 논문은 (AI의 안내를 받는) 더 나은 훈련 데이터 생성이 단순히 로봇 자체를 미세 조정하는 것보다 로봇의 문제를 해결하는 데 더 강력한 방법임을 입증합니다.

기술 요약: LLM 유도형 인스턴스 생성 및 점진적 적응을 통한 합성 및 실제 라우팅 문제 간의 가교 형성

문제 정의

신경 조합 최적화(Neural Combinatorial Optimization, NCO) 방법론은 균등 분포된 노드를 가진 합성 차량 경로 문제(VRP)에서 최첨단 성능을 달 я성했습니다. 그러나 이러한 모델을 TSPLib 및 CVRPLib 벤치마크와 같은 실제 세계의 라우팅 시나리오에 적용할 때 상당한 일반화 격차가 지속적으로 발생합니다. 기존의 신경 솔버들은 실제 데이터셋에 내재된 이질적이고 비균일한 구조적 패턴을 처리하는 데 어려움을 겪습니다. 대규모 언어 모델(LLM)이 휴리스틱을 진화시키거나 조합 최적화 문제(COP)를 직접 해결하는 데 유망한 가능성을 보여주었지만, 컨텍스트 제한과 확장된 텍스트 설명 처리 시의 일관성 문제로 인해 중대형 인스턴스(예: 노드 50개 초과)를 처리하는 데는 종종 실패합니다. 결과적으로, 솔버의 아키텍처 변경을 요구하거나 단순한 직접 미세 조정(fine-tuning)에만 의존하지 않고도(이는 흔히 제한적인 개선만을 가져옴), 합성 학습 데이터와 실제 세계 벤치마크 사이의 분포 차이를 메울 수 있는 프레임워크가 필요합니다.

방법론: EvoReal

저자들은 솔버를 직접 해결하기보다 데이터 생성기를 진화시키는 데 LLM을 활용하는 데이터 중심 프레임워크인 EvoReal을 제안합니다. 이 프레임워크는 두 가지 주요 구성 요소인 LLM 유도형 진화 인스턴스 합성 모듈과 점진적 미세 조정 전략으로 구성됩니다.

1. LLM 유도형 진화 인스턴스 합성

EvoReal은 LLM에게 TSP 또는 CVRP 인스턴스를 풀도록 프롬프트를 주는 대신, 실제 세계의 분포를 모방하는 합성 인스턴스를 생성하는 코드 기반 데이터 생성기를 생성하도록 프롬프트를 제공합니다.

생성기 표현: 각 생성기는 함수 설명, 코드 구현(PyTorch 기반), 그리고 적합도 점수(fitness score)로 정의됩니다.
구조적 정렬: 진화 과정은 LLM이 생성한 합성 분포( $D(h_\phi(Z))$ )와 타겟 실세계 분포( $D_{real}$ ) 사이의 괴리를 최소화하는 것을 목표로 합니다. 이 괴리는 프록시 지표, 구체적으로는 검증 세트에서의 평균 최적성 갭(optimality gap)을 통해 측정됩니다.
모듈화 및 범주화: 다양한 구조적 패턴을 포착하기 위해, 검증 세트(TSPLib/CVRPLib)는 다음과 같은 통계적 특징을 기준으로 카테고리로 세분화됩니다:
- FFT 에너지: 전역적 주기성 또는 반복성을 측정합니다.
- NN-Ratio (변동 계수): 그리드 형태, 랜덤, 또는 클러스터링된 레이아웃을 구분하기 위해 최근접 이웃(nearest-neighbor) 거리의 변동을 측정합니다.
- 이러한 지표를 바탕으로 인스턴스는 유형(예: 반복 구조를 가진 S1, 약한 클러스터링/그리드 형태를 가진 S2, 국지적 집합을 가진 S3)으로 분류됩니다. 각 카테고리에 특화된 생성기가 진화됩니다.
진화 과정: 이 프레임워크는 ReEvo(Reflective Evolution) 접근 방식을 특정 수정 사항과 함께 적용합니다:
- 순위 기반 선택(Rank-based Selection): 수렴을 가속화하기 위해 적합도 순위에 따라 자손을 선택합니다.
- 지연된 선택(Delayed Selection): 다양한 후보가 조기에 제거되는 것을 방지하기 위해 교차(crossover)와 변이(mutation) 이후에 선택이 이루어집니다.
- 성찰 메커니즘(Reflection Mechanisms): 부모 쌍을 비교하는 단기 성찰과 변이를 가이드하기 위해 통찰력을 추출하는 장기 성찰을 사용하여 생성기를 반복적으로 정제합니다.

2. 점진적 미세 조정 전략

최적의 생성기가 식별되면, 사전 학습된 신경 솔버(POMO 및 LEHD)는 합성-실제 간의 격차를 메우기 위해 2단계의 점진적 미세 조정 과정을 거칩니다:

1단계 (구조적 적응): 모델을 LLM 유도형 생성기로 생성된 대규모 합성 데이터로 미세 조정합니다. 이 단계에서는 모델 아키텍처를 수정하지 않고도 다양한 TSPLib 스타일의 구조적 패턴(S1, S2, S3의 혼합 분포)에 모델을 노출시킵니다. 목표는 모델의 내부 표현을 실제 데이터의 구조적 사전 지식(structural priors)과 정렬하는 것입니다.
2단계 (직접 적응): 다양한 구조에 적응된 모델은 이제 실제 벤치마크 인스턴스(TSPLib/CVRPLib)에서 직접 미세 조정됩니다. 이 단계는 모델이 "쉬운" 합성 작업에서 "어려운" 실제 사례로 전환할 수 있도록 하여, 최종적인 성능 격차를 효과적으로 좁힙니다.

주요 기여

EvoReal 프레임워크: 솔버를 진화시키는 것이 아니라 데이터 생성기를 진화시키는 새로운 프레임워크를 도입했습니다. 이 접근 방식은 실제 세계의 분포를 통계적으로 모방하는 구조적으로 현실적인 VRP 인스턴스를 합성하여, 일반화 격차의 근본 원인을 해결합니다.
점진적 미세 조정 전략: 먼저 LLM이 진화시킨 다양한 분포에 신경 솔버를 정렬한 다음, 실제 벤치마크 데이터로 이를 정제하는 2단계 적응 전략을 제공합니다. 이는 아키텍처 변경 없이도 효과적인 도메인 적응을 가능하게 하며, 실제 데이터에 대한 직접 미세 조정보다 우수한 성능을 보입니다.
최첨단 성능: 본 프레임워크는 TSPLib 및 CVRPLib 벤치마크의 광범위한 문제 규모에 걸쳐 일반화 성능의 유의미한 향상을 입증하며, 신경 솔버를 위한 새로운 최첨단(SOTA) 결과를 달성했습니다.

실험 결과

저자들은 70개의 TSPLib 문제와 100개의 CVRPLib SetX 문제에 대해 EvoReal을 평가하였으며, 클래식 솔버(Concorde, LKH-3, ORTools) 및 다양한 신경 베이스라인(POMO, LEHD, SGBS, CNF 등)과 비교하였습니다.

TSPLib 성능:
- 50회의 RRC 반복을 거친 **LEHD (본 연구)**는 TSPLib에서 **1.05%**의 전체 최적성 갭을 달성하여, 다른 학습 기반 방법들을 크게 앞질렀으며 Concord와의 격차를 좁혔습니다.
- **POMO (본 연구)**는 전체 갭을 **11.59%**로 줄였으며, 이는 사전 학습된 POMO(26.66%)에 비해 상당한 개선입니다.
- 이 방법은 전통적인 신경 솔버들이 성능이 급격히 저하되는 대규모 인스턴스(1000~5000 노드)에서 특히 강점을 보였습니다.
CVRPLib 성능:
- **LEHD (본 연구)**는 CVRPLib SetX에서 **2.71%**의 전체 갭을 달성하여, 모든 다른 신경 솔버를 능가하고 ORTools와 경쟁 가능한 수준을 유지했습니다.
- 점진적 미세 조정 전략은 소규모 인스턴스와 대규모 인스턴스 간의 성능 차이를 눈에 띄게 줄였습니다.
Ablation 연구:
- 미세 조정 전략의 1단계 또는 2단계를 제거하면 성능이 저하되었으며, 이는 점진적 접근 방식의 필요성을 확인시켜 줍니다.
- 진화된 생성기를 단순한 분포 생성기(Gaussian, Beta 등)와 비교했을 때, LLM이 진화시킨 생성기가 일관되게 더 낮은 최적성 갭을 달성하여 복잡한 구조적 특성을 포착하는 능력을 입증했습니다.
- 프레임워크는 다양한 LLM에 대해 견고함을 증명했으며, OpenAI o3가 가장 우수한 생성기 성능을 보였습니다.

의의 및 주장

본 논문은 솔버를 진화시키는 것에서 데이터 분포를 진화시키는 것으로 초점을 전환함으로써, EvoReal이 합성 및 실제 세계 라우팅 문제 사이의 일반화 격차를 성공적으로 메운다고 주장합니다. 저자들은 다음과 같은 점을 강조합니다:

자동 발견: 수동적인 휴리스틱 설계로는 달성하기 어려운, 실제 세계의 구조적 사전 지식과 일치하는 데이터 생성기의 자동 발견을 가능하게 합니다.
효율성: 기존의 SOTA 신경 솔버를 처음부터 다시 학습시키거나 아키텍처를 수정하는 비용이 들지 않고도 이러한 이득을 얻습니다.
확장성: 다양한 문제 규모에 효과적이며, 특히 기존의 신경 솔버들이 일반화에 실패했던 대규모 인스턴스 문제를 해결합니다.
직접 미세 조정보다 우월함: 진화된 합성 분포를 통해 모델을 적응시킨 후(1단계) 직접 미세 조정(2단계)하는 것이 실제 데이터에 직접 미세 조정하는 것보다 더 나은 일반화를 제공한다는 점을 입증하며, 구조적 적응을 위한 "커리큘럼"이 견고함에 결정적임을 시사합니다.

저자들은 결론적으로, 이 생성기 기반 적응 파이프라인이 NCO 방법론의 실제 물류 및 운송 시나리오 적용 가능성을 높이는 데 유망한 방향을 제시한다고 밝히고 있습니다.