新型模拟退火遗传算法在路径优化的应用  

Application of New Simulated Annealing Genetic Algorithm in Path Optimization

作　　者：李朝迁[1] 裴建朝 LI Chao-qian;PEI Jian-chao(School of Mathematics and Statistics,Yunnan University,Kunming 650504,China)

机构地区：[1]云南大学数学与统计学院,昆明650504

出　　处：《组合机床与自动化加工技术》2022年第3期52-55,共4页Modular Machine Tool & Automatic Manufacturing Technique

基　　金：云南省科技厅应用基础研究计划项目(2018FB001)。

摘　　要：针对路径优化中,遗传算法(GA)初始解质量低,变异能力差,以及易陷入局部最优解等问题,提出了一种新型模拟退火遗传算法。首先,采用混合策略生成初始解,将模拟退火算法引入遗传算法的变异算子,使用2-opt算子和单点最优插入算子增强局部搜索能力,使算法能够更加有效地避免陷入局部最优;其次,提出改进的锦标赛算法,对交叉、变异前后种群个体进行一一对比,选择较优个体进入下一代,目的是为了避免传统锦标赛法破坏种群多样性,同时改进方法可以在增强变异能力的情况下,维持种群稳定性;最后,用TSP问题实例进行试验。结果表明,所提算法在Dantzig42和Pr107实例的优化结果优于国际网站TSPLIB给出的最优结果。Aiming at the problems of genetic algorithm(GA)in path optimization,such as low initial solution quality,poor mutation ability and easy to fall into local optimal solution,a novel simulated annealing genetic algorithm was proposed.Firstly,a hybrid strategy is used to generate the initial solution.The simulated annealing algorithm is introduced into the mutation operator of the genetic algorithm,and the 2-opt operator and the single-point optimal insertion operator are used to enhance the local search ability,so that the algorithm can avoid getting into the local optimal more effectively.Then an improved tournament algorithm is proposed to compare the individuals of the population before and after crossover and mutation,and the better individuals are selected to enter the next generation.The aim is to avoid the destruction of population diversity by traditional tournaments method.At the same time,the improved method can maintain the population stability while enhancing the mutation ability.Finally,an example of TSP problem is used to test the algorithm,and The results show that the optimization results of the proposed algorithm in Dantzig42 and Pr107 examples are better than the optimal results given by the international website TSPLIB.

关 键 词：路径优化 改进遗传算法 模拟退火算法 2-opt算子 

分 类 号：TH16[机械工程—机械制造及自动化] TG506[金属学及工艺—金属切削加工及机床]