基于改进遗传算法的TSP问题优化研究

Research on TSP of Optimization Based on Improved Genetic Algorithm

旅行商问题(TSP问题)已经被证明属于NP完全问题。遗传算法是一种模拟自然界中生物的进化机制的优化策略,是一种基于群体、隐并行搜索策略,是求解TSP问题效率相当高的一种算法。因此,本文提出使用改进的遗传算法,即用个体数量控制选择策略以保证群体的多样性,用顺序交叉算子和部分路径翻转变异算子来提高算法的收敛速度,较好地解决了群体的多样性和收敛速度的矛盾。算法的分析和测试表明,该改进算法的是有效的。

TSP can be proved that it belongs to total NP. Genetic algorithm is optimization game simulating the biology evolution system, which is searching game based on group and latent concurrent. And it is very high efficiency algorithm to solve TSP. Therefore, the paper proposes the improved genetic algorithm, which using individual amount control selection game in order to guarantee colony diversity, using order cross operator and partial route overturn mutation operator to improve convergent speed of algorithm so as to better solve the inconsistency between diversity and convergent speed. Algorithm analysis and test indicate the improved algorithm is effective.