求解旅行商问题的蚁群遗传混合算法

Solving Traveling Salesman Problem by Ant Colony Optimization Genetic Hybrid Algorithm

根据蚁群算法与遗传算法的特性,提出了求解旅行商问题的混合算法.该混合算法以遗传算法为整个算法的框架,根据旅行商问题的特点,给出了4种变异策略;针对遗传算法存在的过早收敛问题,加入2-Opt方法对问题求解进行了局部优化;利用蚁群算法根据信息素产生若干个路径,替代部分差的解.与模拟退火算法、标准遗传算法和标准蚁群算法进行比较,4种混合算法效果都比较好,策略D的混合算法效果最好.

By use of the properties of ant colony algorithm and genetic algorithm, a hybrid algorithm, whose framework of hybrid algorithm is genetic algorithm, is proposed to solve the traveling salesman problems. Four mutation strategies are put forward using the characteristic of traveling salesman problems. The hybrid algorithm with 2 -Opt lcr_al search can ef- fectively find better minimum beyond premature convergence. Ants choose several tours based on trail , and these tours will replace the worse solution. Compare with the simulated armealing algorithm, the standard genetic algorithm and the standard ant colony algorithm, all the 4 hybrid algorithms are proved effective. Especially the hybrid algorithm with strategy D is a simple and effective better algorithm than others.