Learning (Re-)Starting Solutions for Vehicle Routing Problems
원문 초록
A key challenge in solving a combinatorial optimization problem is how to guide the agent (i.e., solver) to efficiently explore the enormous search space. Conventional approaches often rely on enumeration (e.g., exhaustive, random, or tabu search) or have to restrict the exploration to rather limited regions (e.g., a single path as in iterative algorithms). In this paper, we show it is possible to use machine learning to speedup the exploration. In particular, a value network is trained to evaluate solution candidates, which provides a useful structure (i.e., an approximate value surface) over the search space; this value network is then used to screen solutions to help a black-box optimization agent to initialize or restart so as to navigate through the search space towards desirable solutions. Experiments demonstrate that the proposed ``Learn to Restart'' algorithm achieves promising results in solving Capacitated Vehicle Routing Problems (CVRPs).
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
로봇 내비게이션을 위한 최소 장애물 변위 계획의 호리즌 슬라이싱 접근법
A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation
본 논문에서는 로봇 동작 계획(motion planning) 관점에서 최소 장애물 변위 계획(Minimum Obstacle Displacement Planning) 문제를 다룬다. 이 문제는 처음에 충돌 없는 경로가 없을 때 이동 가능한 장애물을 변위시켜 목표 지점까지의 실행 가능한 경로를 찾는 것을 포함한다. 우리는 이 문제가 계산적으로 어렵고, 특히 장애물을 평면상의 다각형으로 모델링할 때 NP-hard임을 보인다. 문헌의 다른 문제들을 일반화하는 최소 장애물 변위 문제의 정확한 공식화와 이에 대응하는 최적해 외에, 본 논문은 계산 부담이 더 적은 근사해를 제안하며, 이는 최적해와 최적 비용의 일부만큼만 차이 나며, 경로 길이와 장애물 변위량 사이의 트레이드오프를 조절할 수 있다.
비일관적 A*의 평활 분석
Smoothed Analysis of Inconsistent A*
A* 탐색은 인공지능에서 기본적인 경로 탐색 알고리리즘이다. 허용 가능하고 일관적인 휴리스틱은 각 상태를 최대 한 번만 확장함으로써 효율적인 성능을 보장하지만, 현대 탐색 응용에서는 기계 학습, 무작위 평가 등에서 유도된 강력하지만 비일관적인 휴리스틱을 자주 사용한다. 이러한 비일관적 휴리스틱 사용에 대한 오랜 이론적 장벽은 치명적인 노드 재확장(re-expansion) 위험이며, 이는 최악의 경우 $\Omega(2^n)$의 지수적 시간 복잡도를 초래한다. 그러나 경험적 관찰은 이 비관적 상한과 모순되며, 비일관적 A*가 실제로는 매우 효율적으로 동작함을 보여 준다. 이론과 실무 사이의 이 큰 격차를 메우기 위해, 본 논문은 비일관적 휴리스틱을 사용하는 A* 알고리리즘에 대한 최초의 평활 분석(smoothed analysis)을 제시한다. 우리는 최악 경우 탐색 그래프의 간선 가중치에 미세한 무작위 perturbation을 적용하여 전형적인 실세계 노이즈를 모델링한다. 주요 결과는 비일관적 A*의 기대 평활 시간 복잡도가 다항식으로 bounded됨을 증명하며, 구체적으로 총 반복 횟수가 $O(n^2 m \kappa)$임을 보인다. 여기서 $n$은 노드 수, $m$은 간선 수, $\kappa$는 무작위 perturbation의 규모를 조절한다. 또한 이 결과가 음수 가중치 그래프에서의 Dijkstra 알고리리즘과 기능적으로 동등한 문제로 자연스럽게 확장됨을 보인다.
Key-Interval A*: 구조적 추상화를 통한 격자 경로 탐색 가속
Key-Interval A*: Accelerating Grid Pathfinding via Structural Abstraction
기존 4-연결 격자 경로 탐색을 위한 정확(exact) 방법들은 온라인 탐색을 줄이지만, 종종 세밀한 탐색 상태를 유지하거나 상당한 전처리(preprocessing)를 요구한다. 본 논문은 경량 전처리를 사용하여 자유 공간(free space)의 간결한 구간(interval) 수준 추상화를 구성하고 탐색하는 최적 경로 탐색 알고리즘인 Key-Interval A* (KIA*)를 제안한다. KIA*는 구간을 사용하여 자유 공간을 표현하며, 구간이란 통과 가능한 셀들의 최대 연속 구간(maximal contiguous runs)이다. 구조적 경계 변화를 포착하는 핵심 구간(key interval)을 추출하고, 연속적인 비핵심(non-key) 영역을 통해 이를 연결한다. KIA*는 이로부터 얻어진 핵심-구간(key-interval) 그래프에서 A* 스타일 탐색을 수행하고, 셀 수준의 지역 탐색 없이 구간 체인(interval chain)으로부터 격자 경로를 구성적으로 재구성한다. 4-연결 격자에서 KIA*의 완전성(completeness)과 최적성(optimality)을 증명한다. 표준 벤치마크(benchmark) 실험에서 KIA*는 정확한 최단 경로 길이를 유지하고 8개 벤치마크 그룹 중 7개에서 최고 실행 시간을 달성하며, 구조화된 맵과 게임 맵에서 가장 큰 성능 향상을 보인다.
SplatQ: 2차 선택을 통한 3D 가우시안 스플래팅의 상호작용 인지 가지치기
SplatQ: Interaction-Aware Pruning of 3D Gaussian Splatting via Quadratic Selection
기존의 3D 가우시안 스플래팅(3DGS) 가지치기(pruning) 방법들은 주로 독립적인 중요도 점수에 기반한 전역 Top-K 선택에 의존하여, 영역별 예산 제어가 부족하고 공동 삭제 효과를 무시합니다. 결과적으로 전체 장면에 걸쳐 균형 잡힌 재구성 품질을 보장하지 못합니다. 본 논문에서는 고정된 예산 하에서 영역별 예산 할당과 공동 가우시안 선택을 조율하는 조합 가지치기 알고리즘인 SplatQ를 제안합니다. SplatQ는 공간적 근접성과 외형 유사성을 기준으로 가우시안을 크기가 제한된 블록으로 분할하여, 전역 선택 문제를 특정 크기의 하위 문제들로 분해합니다. 그런 다음 중요도 기반의 블록 유지 할당량을 평활화하여 과도한 예산 집중을 방지합니다. 마지막으로 가우시안 불투명도 변화에 대한 대표 픽셀 색상의 반응을 활용하여 공동 삭제 효과의 2차 근사를 구성합니다. 개별 반응, 쌍별 상호작용 및 할당량 페널티는 2차 비제약 이진 최적화(QUBO) 목적 함수에 통합되며, 모의 담금질(SA) 또는 코히런트 이징 머신(CIM)을 사용하여 이를 해결함으로써 가우시안을 공동으로 선택합니다. 5개 벤치마크에 대한 실험을 통해 SplatQ가 종합적인 재구성 품질, 공간적 품질 균형, 렌더링 속도 측면에서 최신 가지치기 방법들보다 우수한 성능을 보임을 입증합니다. 절제 연구(ablation)를 통해 예산 평활화가 국소적인 세부 표현 재구성을 향상시키는 한편, 상호작용 모델링이 고정된 예산 하에서 가우시안 선택 품질을 향상시킴을 확인합니다.
MMAO: 연속 및 이산 최적화를 위한 내인성 자원 할당 기반 대사적 다중 에이전트 옵티마이저
MMAO: A Metabolic Multi-Agent Optimizer with Endogenous Resource Allocation for Continuous and Discrete Optimization
전통적인 메타휴리스틱은 흔히 고정된 개체군 크기, 수동으로 선택한 탐색 스케일, 외부에 부착된 파라미터 제어 모듈에 의존한다. 본 논문은 개별-공공 대사 자원 순환으로부터 적응이 내생적으로 도출되는 교차 도메인 최적화 프레임워크인 대사 다중 에이전트 최적화기(MMAO)를 제시한다. 각 에이전트는 내부 에너지, 연속적인 역할 상태, 이동 또는 구조 기억, 국소 탐색 이력을 지니며, 개체군은 공동 자원 풀을 공유한다. 적합도 향상은 강건한 진행 스케일과 최근 성공 통계를 통해 정규화된 대사 이득으로 변환되고, 동일한 폐루프가 감지 강도, 탐색 진폭, 역할 변동, 분기, 가지치기, 재생성, 엘리트 재투자를 조절한다. 연속 환경에서 MMAO는 에너지로 조절되는 대칭 영차 탐침과 역할 보간 이동을 사용한다. 이산 환경에서는 동일한 제어 법칙이 구조적 감지, 국소 경로 개선, 유도된 섭동, 에너지 가중 간선 재사용을 통해 구현된다. 본 논문은 구현에 충실한 정식화와 CEC2017 부분집합(10D/30D, 20개 시드) 및 5개의 TSPLIB 인스턴스(이산 실행 총 100회)에 대한 재현 가능한 실험 연구를 결합한다. 현재의 증거는 MMAO를 보편적으로 우월한 최적화기로서가 아니라, 주로 파라미터 부담이 적고 자기 보정하는 최적화 프레임워크로서 뒷받침하며, 그 주된 검증된 독창성은 이질적인 탐색 행동 전반에 걸친 대사적으로 내생적인 자원 할당에 있다.
Minimal MMAO: 적응형 메타휴리스틱 탐색을 위한 자원 폐쇄 루프 프레임워크
Minimal MMAO: A Resource-Closed-Loop Framework for Adaptive Metaheuristic Search
토론
이 논문과 연결된 포럼 글이 아직 없습니다.