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

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