New EAX Crossover for Large TSP Instances
New EAX Crossover for Large TSP Instances
复制标题
适用于大型 TSP 实例的新 EAX 交叉
DOI：
10.1007/11844297_38
复制
发表时间：
2006
影响因子：
2.6
通讯作者：
Y. Nagata
中科院分区：
文献类型：
--
作者：
Y. Nagata
提出了一种适用于旅行商问题的进化算法（EA）。EA使用边缘组装交叉（EAX），这是已知的高效和有效的解决tsp。近年来，人们提出了一种快速实现EAX和有效保护种群多样性的方法。这使得将EA与EAX进行比较成为可能，这与基于Lin-Karnighan启发式的最先进的TSP启发式相当。使用EAX进一步提高了ea的性能，特别是在超过1万个城市的大型实例中。我们的方法可以在一天内使用单个Itanium 2 1.3 ghz处理器为多达24978个城市的实例找到最佳解决方案。此外，我们的EA在合理的计算时间内为未解决的国家TSP实例找到了三个新的最佳旅行。
We propose an evolutionary algorithm (EA) that applies to the traveling salesman problem (TSP). The EA uses edge assembly crossover (EAX), which is known to be efficient and effective for solving TSPs. Recently, a fast implementation of EAX and an effective technique for preserving population diversity were proposed. This makes it possible to compare the EA with EAX comparable to state-of-the-art TSP heuristics based on Lin-Karnighan heuristics. We further improved the performance of EAs with EAX, especially for large instances of more than 10,000 cities. Our method can find optimal solutions for instances of up to 24978 cities within a day using a single Itanium 2 1.3-GHz processor. Moreover, our EA found three new best tours for unsolved national TSP instances in a reasonable computation time.
考虑多样性损失的EAX算法
DOI：
--
发表时间：
2004
期刊：
The 8th International Conference on Parallel Problem Solving from Nature (PPSN VIII)
影响因子：
--
作者：
Yuichi Nagata;Yuichi Nagata;Yuichi Nagata
通讯作者：
Yuichi Nagata