On Solving Travelling Salesman Problems by Genetic Algorithms
On Solving Travelling Salesman Problems by Genetic Algorithms
复制标题
DOI：
10.1007/bfb0029743
复制
发表时间：
1990-10
期刊：
影响因子：
--
通讯作者：
H. Braun
中科院分区：
文献类型：
--
作者：
H. Braun
我们提出了一个遗传算法来解决旅行商问题的遗传算法，通过遗传算法来优化旅行商问题，多达442个城市。Mühlenbein等人。[MGK 88]，[MK 89]提出了一种用于旅行商问题的遗传算法，该算法为442和531个城市的旅行商问题生成了非常好的但不是最优的解决方案。我们通过改进遗传算法的所有基本组成部分来改进这种方法。在实验研究中，我们使用了在[CP 80]，[GH 89]中得到最优解的旅行商问题TSP（i）（i= 137，202，229，318，431，442，666），在SUN工作站上，我们可以在平均不到3分钟的时间内解决多达229个城市的中型旅行商问题。此外，我们可以在可接受的时间限制内最优地解决多达442个城市的旅行推销员问题（例如，在SUN工作站上TSP（431）的平均运行时间约为30分钟）。666个城市的最大问题可以通过构建一个长度超过最优值0.04%的旅游来近似解决。
We present a genetic algorithm for solving the traveling salesman problem by genetic algorithms to optimality for traveling salesman problems with up to 442 cities. Mühlenbein et al. [MGK 88], [MK 89] have proposed a genetic algorithm for the traveling salesman problem, which generates very good but not optimal solutions for traveling salesman problems with 442 and 531 cities. We have improved this approach by improving all basic components of that genetic algorithm. For our experimental investigations we used the traveling salesman problems TSP (i) with i cities for i=137, 202, 229, 318, 431, 442, 666 which were solved to optimality in [CP 80], [GH 89].We could solve medium sized traveling salesman problems with up to 229 cities in < 3 minutes average runtime on a SUN workstation. Furthermore we could solve traveling salesman problems with up to 442 cities optimally in an acceptable time limit (e.g. the average runtime on a SUN workstation for the TSP (431) is about 30 minutes). The greatest examined problem with 666 cities could be approximately solved by constructing a tour with length 0,04% over the optimum.