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

Improvement of Genetic Algorithm for Solving TSP Problem

作　　者：李庆 魏光村 高兰[1] 仇国华 肖新光 LI Qing;WEI Guang-cun;GAO Lan;QIU Guo-hua;XIAO Xin-guang(College of Computer Science and Engineering,Shandong University of Science and Technology,Qingdao 266590,China;Department of Informaion Engineering,Shandong University of Science and Technology,Tai’an 271019,China)

机构地区：[1]山东科技大学计算机科学与工程学院,山东青岛266590 [2]山东科技大学信息工程系,山东泰安271019

出　　处：《软件导刊》2020年第3期116-119,共4页Software Guide

基　　金：山东省自然科学基金项目(ZR2018BF005);山东省重点研发计划项目(2018GGX101011)。

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]