用于求解TSP问题的遗传算法改进

李庆　魏光村　高兰　仇国华　肖新光

摘 要：TSP問题是一个著名的NP难问题，提出一种改进的遗传算法用来解决该问题。为了处理传统遗传算法中出现的早熟、收敛速度慢、收敛结果不准确等问题，分别在选择、交叉、变异3个阶段对算法进行优化。设计一个动态适应度函数;放弃轮盘赌策略，采用无放回式优良个体多复制原则，防止优良基因被破坏;按照群体适应度值分布，动态改变交叉率及变异率;引入相似度概念，避免出现近亲交配现象，影响种族进化;寻找并记忆优良基因簇，加快收敛过程。实验结果证明，改进遗传算法的优化性能提升了17.04%。

关键词：TSP问题;遗传算法;动态适应度函数;优良个体多复制;相似度;优良基因簇

DOI：10. 11907/rjdk. 192387

中图分类号：TP301   文献标识码：A                 文章编号：1672-7800（2020）003-0116-04

Improvement of Genetic Algorithm for Solving TSP Problem

LI Qing1， WEI Guang-cun1，2， GAO Lan1， QIU Guo-hua1， XIAO Xin-guang1

（1.College of Computer Science and Engineering， Shandong University of Science and Technology，Qingdao 266590，China;

2.Department of Informaion Engineering，Shandong University of Science and Technology，Taian 271019，China）

Abstract：TSP problem is a well-known NP-hard problem. This paper proposes an improved genetic algorithm to solve this problem. In order to solve the problems of premature ripening， slow convergence and inaccurate convergence results in traditional genetic algorithms， the algorithm is optimized in three stages： selection， crossover and mutation. This paper designs a dynamic fitness function， then abandons the roulette strategy and adopts the principle of non-return-type good multiple replication to prevent the destruction of good genes; and then dynamically changes the crossover rate and mutation rate according to the distribution of group fitness values. The concept of similarity is introduced to avoid the phenomenon of inbreeding and affect ethnic evolution. The algorithm finds and memorizes good gene clusters， and accelerates the convergence process to design a dynamic fitness function. It abandons the roulette strategy and adopts the principle of non-return-type good individual multiple replication to prevent good genes from being destroyed. According to the group fitness value distribution， the crossover rate and mutation rate are dynamically changed; the concept of similarity is introduced to avoid inbreeding that affects racial evolution. Finally， find and remember good gene clusters are found and remembered to speed up the convergence process. Experiments show that the optimization performance of the improved genetic algorithm is improved by 17.04%.

Key Words： TSP problem; genetic algorithm; dynamic fitness function; excellent individual multiple replication; the concept of similarity; good gene clusters