Department of Statistics, Quaid-i-Azam University, Islamabad, Pakistan.
Department of Computer Science, Foundation University, Islamabad, Pakistan.
Comput Intell Neurosci. 2017;2017:7430125. doi: 10.1155/2017/7430125. Epub 2017 Oct 25.
Genetic algorithms are evolutionary techniques used for optimization purposes according to survival of the fittest idea. These methods do not ensure optimal solutions; however, they give good approximation usually in time. The genetic algorithms are useful for NP-hard problems, especially the traveling salesman problem. The genetic algorithm depends on selection criteria, crossover, and mutation operators. To tackle the traveling salesman problem using genetic algorithms, there are various representations such as binary, path, adjacency, ordinal, and matrix representations. In this article, we propose a new crossover operator for traveling salesman problem to minimize the total distance. This approach has been linked with path representation, which is the most natural way to represent a legal tour. Computational results are also reported with some traditional path representation methods like partially mapped and order crossovers along with new cycle crossover operator for some benchmark TSPLIB instances and found improvements.
遗传算法是一种根据适者生存的思想用于优化目的的进化技术。这些方法不能保证最优解；但是，它们通常可以在时间内给出很好的近似值。遗传算法对于 NP 难问题很有用，特别是旅行商问题。遗传算法取决于选择标准、交叉和变异算子。为了使用遗传算法解决旅行商问题，有多种表示方法，如二进制、路径、邻接、序数和矩阵表示。在本文中，我们提出了一种新的旅行商问题交叉算子，以最小化总距离。这种方法与路径表示法相关联，这是表示合法旅行的最自然方式。还报告了计算结果，并与部分映射和顺序交叉等一些传统的路径表示方法以及新的循环交叉算子进行了比较，针对一些基准 TSPLIB 实例进行了实验，并发现了改进。
