具有自识别能力的遗传算法求解旅行商问题

A Genetic Algorithm with Self-identify Capability to Solve TSP

为解决基本遗传算法求解旅行商(TSP)问题收敛速度慢、种群过早成熟和局部搜索能力差的问题,提出了一种具有自识别能力的遗传算法。算法的主要改进手段是,通过双向贪婪算法来构建初始种群,以提高寻找到最优解的速度;建立个体之间相似度的概念,用自识别交叉算子进行交叉操作,避免种群过早成熟。实验结果表明,与基本遗传算法相比,该算法很好地保持了群体的多样性,并具有较好的收敛速度。仿真结果验证了算法的良好性能。

To solve the problem of the slow convergence speed,the earliness group and the bad local searching ability in classical genetic algorithm for TSP,A kind of GA with self-identify capability is proposed.The improving methods of the algorithm are mainly composed of constructing an original group,by using the double greedy algorithm,to improve the speed of finding the best solution,proposing a concept of similitude degree between two individuals,and then using the self-identify crossover operator to avoid the earliness group.In contrast to the tradition GA,the experiment results in this paper show that the algorithm can keep the variety of group,and have better convergence speed.The simulation resuits show the excellent performance of the algorithm.