一种基于基因库和多重搜索策略求解TSP的遗传算法

A Genetic Algorithm Based on Gene Bank and Multiple-Searching Method for TSP

TSP是组合优化问题的典型代表,该文在分析了遗传算法的特点后,提出了一种新的遗传算法(GB—MGA),该算法将基因库和多重搜索策略结合起来,利用基因库指导单亲遗传演化的进化方向,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际TSP库中多个实例的测试,结果表明:算法(GB—MGA)加快了遗传算法的收敛速度,也加强了算法的寻优能力。

Traveling salesman problem is a typical representative of combinatorial optimization problems. After analyzing the characteristic of genetic algorithm, a new genetic algorithm named GB-MGA is designed in this article. It combines gene bank and multiple-searching method, gene bank directs the slngle-parent evolution and enhances the evolutionary speed. Based on multiple-searching method, GB_ MGA aims on enhancing the ability of global search by using improved cross operator. The test results of some instances in TSP library show that proposed algorithm increases the convergence speed, and improves the chance of finding optimal solution.