An improved genetic algorithm with a local optimization strategy and an extra mutation level for solving traveling salesman problem
An improved genetic algorithm with a local optimization strategy and an extra mutation level for solving traveling salesman problem
复制标题
具有局部优化策略和额外变异水平的改进遗传算法解决旅行商问题
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
V. Hashemi
中科院分区：
文献类型：
--
作者：
K. Borna;V. Hashemi
证明了旅行商问题（TSP）在大多数情况下是np完全的。遗传算法（GA）是解决这一问题最有用的算法之一。本文比较了传统遗传算法与改进混合遗传算法在求解TSP问题中的应用。改进遗传算法由传统遗传算法和两种局部优化策略组成。第一种策略是提取包含四个城市样本的所有序列组，并将两个中心城市相互改变。第二种局部优化策略类似于一个额外的突变过程。在此步骤中，以低概率选择样本。在这个示例中，定义了两个随机城市，这些城市之间的路径是相反的。计算结果表明，该方法在可接受的计算时间内也能找到比传统遗传算法更好的路径。
The Traveling salesman problem (TSP) is proved to be NP-complete in most cases. The genetic algorithm (GA) is one of the most useful algorithms for solving this problem. In this paper a conventional GA is compared with an improved hybrid GA in solving TSP. The improved or hybrid GA consist of conventional GA and two local optimization strategies. The first strategy is extracting all sequential groups including four cities of samples and changing the two central cities with each other. The second local optimization strategy is similar to an extra mutation process. In this step with a low probability a sample is selected. In this sample two random cities are defined and the path between these cities is reversed. The computation results show that the proposed method also finds better paths than the conventional GA within an acceptable computation time.