一种求解旅行商问题的基于外部存档的自适应遗传算法

An external archiving based self-adaptive genetic algorithm for solving Traveling Salesman Problem

旅行商问题是一类经典的组合最优化问题,在理论研究和实际应用领域具有重要的研究价值。本文提出了一种自适应遗传算法,通过变异率的自适应策略平衡算法的全局性和局部性,同时利用外部存档策略为种群进化提供具有全局指导信息的父代个体,提高了算法的收敛速度。通过对TSPLIB标准库中实例的测试,验证了算法的可行性和有效性。

Traveling Salesman Problem is a classical combinatorial optimization problem,which has important research value in theoretical research and practical application.In this paper,an adaptive genetic algorithm is proposed,which balances the global ability and local ability of the algorithm by adapting the self-adaptive mechanism of mutation probability.An external archiving strategy is used to provide better parent individuals which have global guiding information for the evolutionary process,to improve the convergence speed of the algorithm.The feasibility and effectiveness of the proposed algorithm are verified by the test on the instances in TSPLIB standard library.