摘要
旅行商问题(traveling salesman problem,TSP)是一个易于描述但难于解决的著名难题之一。利用距离矩阵方差最小法(minimizing variance of distance matrix,MVODM)改进的贪婪算法得到遗传算法的初始种群;结合具有贪婪算法和淘汰机制的启发交叉算子引入双向三交叉的贪婪算子,对选择的父代进行充分交叉以提高种群多样性;变异算子采用2-opt局部优化算法,对基因进行改造,使变异子代向更优的方向进化。最后加入精英个体保留策略,使得最优基因结构得以延续。实验表明,该改进遗传算法在高质量的初始种群下进行充分的交叉,可以在较小的迭代次数内以及较小的种群数量下得到质量更高的全局最优解。
Traveling Salesman Problem(TSP)is one of the well-known problems that are to be described but difficult to be solved.The greedy algorithm improved by the minimum matrix variance variance method(MVODM)is used to obtain the initial population of genetic algorithm.Combining the greedy algorithm with greedy algorithm and elimination mechanism to introduce two-way three-crossing greedy operator,the choice of The fathers are fully crossed to improve the diversity of the population;the mutation operator uses the 2-opt local optimization algorithm to reform the genes and evolve the mutant offspring towards a better direction.Finally,the elite individual retention strategy is added when generating the next generation of populations,so that the most genetic structure can be continued.Experiments show that the improved genetic algorithm can fully cross under the high quality initial population,and the global optimal solution with higher quality can be obtained within a small number of iterations and a small population.
作者
王震
刘瑞敏
朱阳光
王枭
Wang Zhen;Liu Ruimin;Zhu Yangguang;Wang Xiao(Kunming University of Science and Technology,School of Information Engineering and Automation,Kunming,650504)
出处
《电子测量技术》
2019年第23期91-96,共6页
Electronic Measurement Technology
关键词
TSP问题
遗传算法
距离矩阵方差最小法
双向三交叉算子
2-opt优化
traveling salesman problem
genetic algorithm
minimizing variance of distance matrix
two-way three-crossing operator
2-opt optimization
