arXiv:2409.13788

Quantum evolutionary algorithm for TSP combinatorial optimisation problem

Yijiang Ma, Tan Chye Cheah

제출 2024-09-20

원문 초록

This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA). We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA). The TSP is a well-established challenge in combinatorial optimization where the objective is to find the most efficient path to visit a series of cities, minimizing the total distance, and returning to the starting point. We chose the TSP to test the performance of both algorithms because of its computational complexity and importance in practical applications. We choose the dataset from the international standard library TSPLIB for our experiments. By designing and implementing both algorithms and conducting experiments on various sizes and types of TSP instances, we provide an in-depth analysis of the accuracy of the optimal solution, the number of iterations, the execution time, and the stability of the algorithms for both. The empirical findings indicate that the CGA outperforms the QGA in terms of finding superior solutions more quickly in most of the test instances, especially when the problem size is large. This suggests that although the principle of quantum computing provides a new way to solve complex combinatorial optimisation problems, the implementation of quantum phenomena and the setting of parameters such as the optimal angle for a quantum revolving gate is challenging and need further optimisation to achieve the desired results. Additionally, it is important to note that the QGA has not been tested on real quantum hardware, so its true performance remains unverified. These limitations provide rich opportunities for further research in the future.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.09708v1cs.AI공통 태그 Combinatorial Optimization, Traveling Salesman Problem

GES-TSP: TSP를 위한 그래프 엣지 희소화

GES-TSP: Graph Edge Sparsification for TSP

외판원 문제(TSP)의 대규모 인스턴스를 정확하게 푸는 것은 계산 비용이 많이 든다. 연구자들은 계산 효율성을 높이기 위해 그래프 희소화(sparsification) 방법을 자주 활용한다. 전통적인 희소화 방법은 주로 고정된 휴리스틱에 의존하며 인스턴스별 구조적 정보를 충분히 활용하지 못한다. 본 논문에서는 유클리드 TSP를 위한 학습 기반 희소화 접근법인 그래프 엣지 희소화(GES, Graph Edge Sparsification)를 제안한다. 기하학적 구조 정보와 조합 최적화 기술을 결합하여, 제안된 방법은 서로 다른 인스턴스에 대해 희소화 그래프를 적응적으로 생성하며, 그래프 크기를 크게 줄이고 풀이 과정을 가속화한다. 실험 결과, 본 희소화 방법은 MATILDA 데이터셋에서 엣지의 최대 95%를 가지치기하면서도 솔루션 갭을 최적값의 1% 이내로 유지함을 보여준다. 또한, 본 접근법은 TSPLIB 벤치마크에서 강력한 일반화 능력을 나타낸다. 일부 대규모 인스턴스에서는 가지치기 비율이 99%를 초과하면서도 최적성 갭이 1% 미만으로 유지된다.

arXiv:2610.13503v2cs.CV공통 태그 Combinatorial Optimization

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)를 통해 예산 평활화가 국소적인 세부 표현 재구성을 향상시키는 한편, 상호작용 모델링이 고정된 예산 하에서 가우시안 선택 품질을 향상시킴을 확인합니다.

arXiv:2606.28109v3cs.NE공통 태그 Combinatorial Optimization

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를 보편적으로 우월한 최적화기로서가 아니라, 주로 파라미터 부담이 적고 자기 보정하는 최적화 프레임워크로서 뒷받침하며, 그 주된 검증된 독창성은 이질적인 탐색 행동 전반에 걸친 대사적으로 내생적인 자원 할당에 있다.

arXiv:2606.31584v3cs.NE공통 태그 Combinatorial Optimization

공정 예산 연속 및 이산 벤치마크에서 MMAO의 대규모 실증 평가

A Large-Scale Empirical Evaluation of MMAO Under Fair-Budget Continuous and Discrete Benchmarks

본 논문은 프레임워크 자체를 다시 소개하는 대신, 더 엄격한 경험적 프로토콜 하에서 대사 다중 에이전트 최적화기(MMAO)를 평가한다. 연구는 MMAO의 폐루프 자원 할당 원리가 더 광범위하고 더 표준적이며 예산이 더 명시적으로 통제된 연속 및 이산 벤치마크에서도 신뢰성을 유지하는지를 묻는다. 완료된 주요 행렬은 각각 20개 시드를 갖는 10D와 30D의 CEC2017 함수 8개와 각각 20개 시드를 갖는 TSPLIB 인스턴스 5개를 다루며, PSO-lite, ES-lite, 반복 탐욕 2-opt 경로 기준선을 포함한 더 강력한 재현 가능 기준선과 함께 평가한다. 여기에 공동 예산, 성공률, 역할 진화, 개체군 교체에 대한 궤적 수준 진단을 추가하고, 이산 증거를 경로 문제 너머로 확장하기 위해 보조적인 OR-Library 다중 배낭 문제 일부도 더한다. 이 프로토콜 하에서 MMAO는 연속 영역과 TSPLIB 영역 모두에서 외부 기준선 집합을 뚜렷하게 능가하며, 제거 변형들은 외부 기준선보다 전체 방법에 훨씬 더 가깝게 유지된다. 결과는 시험한 영역 전반에서 내생적 자원 재분배를 뒷받침하지만, 더 정밀한 메커니즘 분리와 더 폭넓은 대회 수준 비교는 열린 과제로 남는다.

arXiv:2607.01551v3cs.NE공통 태그 Combinatorial Optimization

MMAO: 대사 폐루프 메타휴리스틱의 메커니즘 및 안정성 분석

MMAO: Mechanism and Stability Analysis of Metabolic Closed-Loop Metaheuristics

본 논문은 대사 다중 에이전트 최적화기(Metabolic Multi-Agent Optimizer, MMAO)를 구현이나 벤치마크 수준이 아닌 프레임워크 수준에서 연구한다. 핵심 질문은 개별 에너지, 공동 예산, 역할 변동, 생애주기 교체로 이루어진 대사 자원 순환이 서사적 비유를 넘어서는 프레임워크 수준의 해석을 가지는가이다. 도메인 특화 이동 연산자는 추상화하되 프레임워크를 규정하는 자원 장부 관리는 유지하는 일반적인 MMAO 상태 모델을 도입한다. 완만한 이득 유계 및 지출 유계 가정 하에서 개별 에너지, 공동 예산, 역할 상태, 활성 개체군 크기에 대한 유계성과 비음수성을 증명한다. 이어서 순환의 세 가지 내생적 행동 양상을 규명한다. 지속적인 자원 부족 하의 수축, 공동 축적 잉여 하의 재투자, 에이전트 또는 하위 집단 간 이질적인 한계 수익 하의 탐색 재분배가 그것이다. 이 분석은 의도적으로 보수적이다. 전체 적응 시스템의 전역 수렴, 전문 최적화기에 대한 보편적 우월성, 결과 과정의 완전한 정상상태 특성화를 주장하지 않는다. 대신 어떤 내부 조절 특성이 순환의 일반적 귀결이고 어떤 것이 구현에 따라 달라지는지를 식별한다. 대표적인 연속 및 이산 MMAO 구현에 대한 간결한 메커니즘 검증 패키지는 이러한 해석을 뒷받침하는 경험적 증거를 제공하지만 전체 벤치마크 연구를 대체하려는 것은 아니다. 이 분석은 MMAO에 대해 유계적, 재생적, 자원 조절적 해석을 제공하며, 구현 수준의 성능 문제는 열어 둔다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.