求解多旅行商问题的改进分组遗传算法

摘要

In order to solve the total-path-shortest Multiple Traveling Salesman Problem (MTSP), an improved grouping genetic algorithm is proposed. This algorithm employs a new encoding scheme called ordered grouping encoding, which makes the adjusted individuals corresponding one by one to valid solutions of MTSP. According to the features of the encoding scheme, a fast crossover operator is constructed for the sake of reducing the running time of the algorithm. For enhancing its local search ability, the algorithm combines the greedy algorithm and the 2-opt algorithm to design a new local search operator. The comparison of results shows that the proposed algorithm can solve MTSP effectively and has an excellent search performance no matter in computing efficiency or convergence precision.%该文针对总路径长度最小的多旅行商问题，提出一种改进分组遗传算法。在该算法中，设计了一种有序分组编码，采用新编码方式的个体与多旅行商问题有效解之间具有一一对应的关系。为了减少算法的运行时间，根据编码的特点构造了一种快速交叉算子。同时，结合贪婪算法和2-opt 算法设计了一种新的局部搜索算子，以提高算法的收敛精度。实验结果分析表明，所提算法能够有效地解决多旅行商问题，具有可靠的全局收敛性，较高的计算效率。