🤖 machine learning

HeatACO: A Heatmap-Guided Max--Min Ant System for Large-Scale Travelling Salesman Problems

이 논문은 예측기 불가지론적 디코더인 HeatACO를 소개하며, 이는 새로운 차수 인지 증거 요인을 통해 비자기회귀적 TSP 히트맵을 Max-Min 개미 시스템에 통합함으로써, 예측기별 튜닝을 요구하지 않고도 대규모 및 다양한 TSP 인스턴스에 대해 MCTS 및 표준 베이스라인보다 우수한 솔루션 품질과 효율성을 달성한다.

원저자: Bo-Cheng Lin, Yi Mei, Mengjie Zhang

게시일 2026-07-29

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Bo-Cheng Lin, Yi Mei, Mengjie Zhang

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

당신이 도시 지도를 들고 가야 할 경유지 목록을 가지고 있는 배달 기사라고 상상해 보세요. 당신의 목표는 모든 경유지를 정확히 한 번씩만 방문하고 집으로 돌아오는 것이며, 이 모든 과정을 가능한 가장 짧은 거리로 수행해야 합니다. 이것은 그 유명한 "외판원 문제(Traveling Salesman Problem)"입니다. 듣기에는 간단해 보이지만, 도시가 커짐에 따라 가능한 경로의 수는 너무나 빠르게 폭발적으로 증가하여 세계에서 가장 강력한 슈퍼컴퓨터조차 완벽한 경로를 찾기 위해 모든 옵션을 일일이 확인할 수 없습니다. 이 때문에 과학자들은 인공지능의 도움을 받기로 했습니다. 모든 경로를 계산하려고 노력하는 대신, 현대의 AI 모델은 숙련된 정찰대처럼 행동합니다. 이들은 지도를 보고 유망해 보이는 도로들을 빠르게 강조하여, 훌륭한 경로의 일부가 될 가능성이 높은 가장자리(edge)를 밝은 색상으로 보여주는 "히트맵(heatmap)"을 만들어냅니다.

하지만 여기에는 함정이 있습니다. 이 AI 정찰대들은 좋은 길을 찾아내는 데는 뛰어나지만, 그것들을 하나의 완전하고 유효한 여정으로 연결하는 데는 서툽니다. AI는 한 집에서 나가는 세 개의 서로 다른 도로를 강조할 수도 있지만, 실제 운전자는 오직 하나만 갈 수 있습니다. AI는 당신에게 엉망진창인 단서 더미를 던져주며, 당신은 루프에 빠지거나 경유지를 놓치지 않고 하나의 실행 가능한 투어를 만들기 위해 이를 정리할 똑똑한 디코더(decoder)가 여전히 필요합니다. 문제는 어떻게 하면 새로운 도시나 지도 크기에 맞춰 AI를 매번 다시 학습시키지 않고도, 이 모호하고 엉망인 히트맵을 빠르게 완벽한 경로로 바꿀 수 있느냐는 것입니다.

이것이 바로 HEATACO를 개발한 연구자들이 해결하고자 했던 문제입니다. 그들은 AI 히트맵을 위한 스마트한 교통 관제사 역할을 하는 새로운 범용 디코더를 개발했습니다. 단순히 밝은 색상을 맹목적으로 따르거나 느린 시행착오 방식을 사용하는 대신, HEATACO는 개미가 먹이를 찾는 방식에서 영감을 얻은 영리한 시스템을 사용합니다.

그 작동 방식은 이렇습니다. 개미 군집이 다리를 건설하려고 노력하는 상황을 상상해 보세요. 기존 방식에서는 만약 AI 히트맵이 "이 길은 정말 밝아요!"라고 말한다면, 디코더는 즉시 그 길을 잡았습니다. 하지만 때때로 그 밝은 길은 함정일 수 있습니다. HEATACO는 더 똑똑합니다. 이 모델은 히트맵을 보고 "이 길이 아직 시도해보지 않았더라도 선택할 만큼 다른 길들보다 훨씬 더 나은가?"라고 묻습니다. 이는 정말 확신이 드는 단서에만 주목하고 노이즈는 무시하는 방식입니다. 그런 다음, 이 모델은 자신의 "개미"(실제로는 컴퓨터 시뮬레이션)들이 경로를 구축하도록 합니다. 경로를 구축하면서 개미들은 자신이 사용하는 도로에 디지털 "향기"(페로몬이라고 불림)를 남깁니다. 만약 개미가 짧고 좋은 경로를 발견하면 향기가 더 강해지며, 이는 다른 개미들에게 다음번에 그 경로를 시도하라고 알려줍니다.

HEATACO의 마법은 AI의 초기 추측(히트맵)과 개미들의 자체 경험(페로몬) 사이의 균형을 맞추는 데 있습니다. 이 모델은 AI의 추측이 완전히 주도권을 잡도록 내버려 두지 않습니다. 대신, 그 추측을 시작 단계의 발판으로 삼은 뒤, 개미들이 진행하면서 경로를 정교하게 다듬도록 합니다. 이는 당신이 어떤 훈련된 AI 모델로부터 온 히트맵이라도—그것이 작은 마을을 대상으로 훈련되었든 거대한 도시를 대상으로 훈련되었든 상관없이—AI를 다시 학습시키거나 매번 설정을 조정할 필요 없이 HEATACO를 사용하여 훌륭한 경로로 바꿀 수 있음을 의미합니다.

연구진은 최대 10,000개의 경유지가 있는 거대한 도전 과제들을 통해 이를 테스트했습니다. 그들은 HEATACO가 많은 시간을 추측과 확인에 소비해야 했던 이전의 최선책들보다 더 빠르고 더 나은 경로를 찾아낸다는 것을 발견했습니다. 특히 AI의 엉망인 단서들을 본격적인 탐색을 시작하기도 전에 견고한 계획으로 바꾸는 데 탁월했습니다. 그러나 그들은 하나의 한계점도 발견했습니다. 경로가 이미 매우 훌륭하고 강력한 국소적 수정(예: 경로를 짧게 만들기 위해 몇몇 도로를 교체하는 작업)을 시작할 때, AI의 초기 히트맵은 도움이 덜 된다는 점입니다. 그런 경우에는 기존의 기하학적 기법들이 똑같이 잘 작동합니다.

요약하자면, HEATACO는 모호한 AI 예측과 완벽한 여행 계획 사이의 간극을 메우는 다재다능한 도구입니다. 이는 모든 AI 모델마다 별도의 디코더가 필요한 것이 아니라, "전문가의 말을 듣는 것"과 "경험으로부터 배우는 것" 사이의 적절한 균형만 있다면, 도시가 아무리 커지더라도 거대한 경로 문제를 빠르고 효율적으로 해결할 수 있음을 증명합니다.

기술 요약: HEATACO – 대규모 TSP를 위한 히트맵 가이드 Max–Min Ant System

1. 문제 정의

본 논문은 외판원 문제(Travelling Salesman Problem, TSP), 특히 비자기회귀(non-autoregressive, NAR) 신경망 솔버의 디코딩 단계에 초점을 맞춥니다. 이러한 솔버는 단 한 번의 순전파(forward pass)를 통해 에지 신뢰도 히트맵을 예측하여 잠재적 에지에 점수를 할당합니다. 그러나 히트맵은 유효한 투어(tour)가 아닙니다. 이는 종종 끊어진 사이클을 포함하거나, 차수 제약(노드에 두 개 이상의 인접 에지가 있는 경우)을 위반하거나, 가짜 양성(false positives)을 포함하기도 합니다.

핵심 과제는 히트맵-투어 디코딩 문제입니다. 즉, 고정된 밀집 히트맵( $O(n^2)$ 점수)을 전역 제약을 만족하는 유효한 해밀턴 사이클( $n$ 개의 에지)로 변환하는 것입니다. 기존 디코더들은 다음과 같은 트레이드오프에 직면해 있습니다:

탐욕적 병합(Greedy Merging): 빠르고 결정론적이지만, 초기 단계의 잘못된 에지 선택을 수정할 수 없기 때문에 낮은 품질의 투어를 생성합니다.
MCTS 가이드 k-opt 탐색: 더 높은 품질의 투어를 생성하지만, 계산 비용이 많이 들고, 예측기별 하이퍼파라미터(예: 탐색 상수) 튜닝이 필요하며, 인스턴스별 트리 탐색에 의존합니다.

저자들은 서로 다른 사전 학습된 모델의 히트맵을 재학습이나 특정 튜닝 없이 유효한 투어로 변환할 수 있으면서도, 계산 효율성과 높은 솔루션 품질을 유지할 수 있는 예측기 불가지론적(predictor-agnostic) 디코더가 필요하다고 주장합니다.

2. 방법론: HEATACO

저자들은 강력한 Ant Colony Optimization(ACO)의 변형인 **Max–Min Ant System(MMAS)**을 기반으로 하는 확장 가능한 디코더인 HEATACO를 제안합니다. HEATACO는 혁신적인 **캡핑된 차수 인식 증거 계수(capped, degree-aware evidence factor)**를 통해 고정된 히트맵을 MMAS 구축 규칙에 통합합니다.

핵심 구성 요소:

후보 리스트 구축 (Candidate List Construction):
- 모든 $O(n^2)$ 에지를 고려하는 대신, 알고리즘은 노드당 $k=20$ 크기의 희소 후보 리스트로 구축을 제한합니다.
- 후보는 히트맵(신뢰도가 $\theta_h$ 보다 큰 에지)을 기준으로 선택되며, 히트맵이 희소할 경우 연결성을 보장하기 위해 최근접 이웃(nearest neighbors)으로 채워집니다.
차수 인식 증거 편향 ( $e_{ij}$ ):
- 히트맵은 보정된 확률이 아닌 서수적 증거(ordinal evidence)로 취급됩니다.
- 각 노드에 대해, $d^*$ 를 투어 차수(대칭 TSP의 경우 2, ATSP의 출사 방향의 경우 1)라고 할 때, $(d^*+1)$ 번째로 높은 신뢰도 에지를 기준으로 차수 베이스라인( $b_i$ )을 계산합니다.
- 에지에 대한 증거 계수 $e_{ij}$ 는 이 베이스라인에 대한 해당 에지의 신뢰도 비율이며, 최소 1로 캡핑됩니다. 이는 에지가 노드의 수용 능력을 초과하는 신뢰도를 가질 때만 편향된 부스트를 받도록 하여, 단순히 여러 유사한 옵션 중 가장 나은 것일 뿐인 "노이즈가 섞인" 고신뢰도 에지를 필터링합니다.
자동 스케일링 ( $\kappa$ ):
- 히트맵이 페로몬 피드백(인스턴스 특유의 구조를 학습함)을 영구적으로 압도하는 것을 방지하기 위해, 증거 편향의 강도( $\kappa$ )를 자동으로 조절합니다.
- $\kappa$ 는 페로몬 동적 범위( $\tau_{max}/\tau_{min}$ )와 증거 계수의 로그 마진(log-margins)의 90 백분위수를 통해 도출됩니다.
- 이 스케일링은 히트맵이 초기 샘플링에 영향을 미치게 하면서도, 탐색이 진행됨에 따라 페로몬 피드백이 오도된 안내를 수정할 수 있도록 보장합니다. 단일 설정이 재학습 없이 다양한 예측기에 걸쳐 작동합니다.
탐색 과정:
- 초기화: 최근접 이웃 투어가 페로몬 경계를 초기화합니다.
- 구축: $m$ 마리의 개미가 페로몬, 휴리스틱 거리, 히트맵 증거 계수를 결합한 의사 무작위 비례 규칙을 사용하여 병렬로 투어를 구축합니다.
- 업데이트: 페로몬이 증발하고 반복(iteration) 내의 최적 투어(또는 재시작/글로벌 최적값)에 의해 강화됩니다.
- 지역 탐색: 페로몬 업데이트 전에 투어를 정교화하기 위해 선택적으로 2-opt 또는 3-opt(대칭 TSP용) 또는 유향 2-opt(ATSP용)가 적용됩니다.

3. 주요 기여

예측기 불가지론적 디코더: HEATACO는 예측기를 재학습하거나 디코더를 모델별로 튜닝하지 않고도 다양한 사전 학습된 모델(AttGCN, DIMES, UTSP, DIFUSCO)의 히트맵을 디코딩합니다.
캡핑된 차수 인식 증거: 에지가 노드의 차수 용량을 초과할 때만 보상을 주는 메커니즘을 통해, 디코더가 밀집되고 변별력이 낮은 히트맵에 압도되는 것을 방und합니다.
자동 스케일링: 히트맵 편향을 페로몬 동적 범위에 맞춰 스케일링하여, 다양한 히트맵 품질과 인스턴스 규모에 걸친 견고함을 보장합니다.
포괄적 평가: 본 방법은 TSP500, TSP1K, TSP10K뿐만 아니라 분포 외(OOD) 벤치마크(Clustered, Gaussian, TSPLIB) 및 비대칭 TSP(ATSP)에서 평가되었습니다.

4. 실험 결과

본 논문은 네 가지 히트맵 소스에 대해 HEATACO를 표준 MMAS, 그리디 병합, MCTS 가이드 k-opt 탐색과 비교합니다.

그리디 병합 대비: HEATACO는 그리디 디코딩을 크게 능가하여, 최적성 갭(optimality gaps)을 10% 이상(대규모 인스턴스에서는 종종 30% 이상)에서 최적에 가까운 수준으로 줄입니다.
MCTS 대비: 인-디스트리뷰션(in-distribution) 벤치마크(TSP500, TSP1K, TSP10K)에서, 2-opt를 적용한 HEATACO는 동일한 고정 히트맵에 대해 발표된 MCTS 베이스라인보다 더 낮은 최적성 갭과 짧은 디코딩 시간을 달s합니다. 예를 들어, TSP1K에서 HEATACO+2-opt는 약 4~8초 만에 ~0.2–0.4% 갭에 도달하는 반면, MCTS는 ~0.5–1.5% 갭을 위해 ~100초가 소요됩니다.
표준 MMAS 대비:
- 구축 단계: 히트맵 가이드는 모든 예측기와 규모에 대해 초기 구축 품질을 크게 향상시켜, 지역 탐색 전의 갭을 몇 퍼센트 포인트 감소시킵니다.
- 지역 탐색과 함께 사용 시:
  - TSP500 및 TSP1K에서 HEATACO는 2-opt 및 3-opt와 함께 사용할 때도 여전히 유익하지만, 지역 탐색의 강도가 높아짐에 따라 한계 이득(marginal gain)은 감소합니다.
  - TSP10K에서는 강력한 지역 탐색(3-opt)이 수행된 후 히트맵 가이드의 이점이 감소하거나 역전됩니다. 논문은 이를 상호 보완성 감소 때문이라고 설명합니다. 즉, 강력한 기하학적 복구(3-opt)는 투어 구조를 독립적으로 복구할 수 있어, 히트맵의 기여가 중복되거나 히트맵이 탐색을 기하학적으로 최적인 경로로부터 멀어지게 유도할 경우 오히려 해로울 수 있습니다.
일반화:
- ATSP: HEATACO는 지역 탐색(유향 2-opt)이 약한 곳에서 상당한 이득을 보이면서 ATSP로 잘 전이됩니다.
- 분포 변화: OOD 데이터(Clustered, Gaussian, TSPLIB)에서의 성능은 히트맵의 신뢰도와 상관관계가 있습니다. 히트맵이 희소하고 변별력이 유지될 때(예: TSPLIB에 대한 DIFUSCO) HEATACO는 성공합니다. 히로가 너무 밀집되거나 변별력을 잃을 때(예: pr1002에 대한 DIMES) 성능은 저하됩니다.
- SoftDist 제어: 순수하게 거리 기반인 "SoftDist" 히트맵(학습되지 않은 히트맵) 실험 결과, 대규모 스케일에서 강력한 지역 탐색이 있을 때는 기하학적 사전 정보(geometric prior)만으로도 충분하다는 것을 보여줍니다. 이는 학습된 히트맵이 단순 근접성 이상의 구조를 제공할 때만 가치가 있음을 뒷편받습니다.

5. 의의 및 주장

본 논문은 HE-TACO가 다양한 사전 학습된 모델의 히트맵을 유효한 투어로 변환하는 공통의 자동 스케일링 절차를 제공한다고 주장합니다. 그 의의는 다음과 같습니다:

예측과 디코딩의 분리: 연구자들이 특정 디코더를 위해 재학습하거나 튜닝할 필요 없이 기존의 히트맵 예측기를 재사용할 수 있게 합니다.
효율성: MCTS와 비교했을 때 최첨단 디코딩 속도와 솔루션 품질을 달성합니다. MCTS는 대규모 문제에 대해 계산 비용이 매우 높습니다.
진단적 통찰: 본 연구는 학습된 히트맵의 가치가 두 가지 요인, 즉 히트맵 신뢰도(분포 변화 시)와 지역 탐색과의 상호 보완성(기하학적 복구가 강력한 대규모 스케일 시)에 의해 제한된다는 것을 밝혀냈습니다.
실용적 유용성: 특히 지역 탐색이 약하거나(예: ATSP) 빠른 디코딩이 필요한 경우, 신경망 조합 최적화 솔버를 위한 강력한 폴백(fallback) 또는 향상 도구를 제공합니다.

저자들은 신경망 히트맵이 강력하긴 하지만 항상 고전적 탐색보다 우월한 것은 아니며, 그 효용성은 에지 증거의 품질과 가용한 기하학적 복구 능력에 달려 있다고 결론짓습니다. 향후 연구로는 이러한 진단 도구들을 결합하여 HEATACO와 순수 MMAS 폴백 사이를 동적으로 선택하는 방법을 제안했습니다.