论文标题
提高蚂蚁菌落优化效率以解决大型TSP实例
Improving Ant Colony Optimization Efficiency for Solving Large TSP Instances
论文作者
论文摘要
蚂蚁菌落优化（ACO）是一种受自然风格的元硫疗法的家族，通常用于寻找困难优化问题的近似解决方案。尽管高于精确方法的速度要快得多，但ACO仍然可以过慢地放慢速度，尤其是与基本问题特定的启发式方法相比。正如最近的研究所表明的那样，可以通过算法改进和仔细的并行实施从多核CPU和专用加速器中受益。在本文中，我们提出了一种新颖的ACO变体，即集中的ACO（FACO）。 FACO的核心元素之一是控制新构造和选定的先前解决方案之间差异数量的机制。该机制导致了更加集中的搜索过程，从而可以在保留现有解决方案的质量的同时找到改进。另一个好处是与特定于问题的本地搜索更有效地集成。 基于一系列旅行人员问题实例的计算研究表明，在求解大型TSP实例时，FACO的表现优于最先进的ACO。具体而言，对于从100000到200000节点不等的TSP ART实例，FACO需要不到8核商品CPU时间才能找到高质量的解决方案（距最著名的结果1％以内）。
Ant Colony Optimization (ACO) is a family of nature-inspired metaheuristics often applied to finding approximate solutions to difficult optimization problems. Despite being significantly faster than exact methods, the ACOs can still be prohibitively slow, especially if compared to basic problem-specific heuristics. As recent research has shown, it is possible to significantly improve the performance through algorithm refinements and careful parallel implementation benefiting from multi-core CPUs and dedicated accelerators. In this paper, we present a novel ACO variant, namely the Focused ACO (FACO). One of the core elements of the FACO is a mechanism for controlling the number of differences between a newly constructed and a selected previous solution. The mechanism results in a more focused search process, allowing to find improvements while preserving the quality of the existing solution. An additional benefit is a more efficient integration with a problem-specific local search. Computational study based on a range of the Traveling Salesman Problem instances shows that the FACO outperforms the state-of-the-art ACOs when solving large TSP instances. Specifically, the FACO required less than an hour of an 8-core commodity CPU time to find high-quality solutions (within 1% from the best-known results) for TSP Art Instances ranging from 100000 to 200000 nodes.
