利用基于分区搜索的自适应遗传算法求解TSP问题

Solving Traveling Salesman Problem by the Adaptive Genetic Algorithm Based on the Regional Search

为了提高用遗传算法求解旅行商问题(TSP)的收敛速度,结合自适应算子和父子竞争策略等优化思想,提出了基于分区搜索的自适应遗传算法.该算法将整个搜索区域分成若干个较小的搜索区域,先进行局部搜索,在得到局部较优的基因组合后,再进行全区域搜索,不但提高了遗传算法的收敛速度,而且改进了变异算子的操作性能.通过TSP问题的求解表明,基于分区搜索的自适应遗传算法是一种稳定、高效的优化算法.

To increase the convergence speed of the genetic algorithm in solving the traveling salesman problem （TSP）, combined with adaptive operators and competitive strategy between parents and their children, an adaptive genetic algorithm based on the regional search is proposed. This algorithm divides the global space into regional space and makes the regional search first. The global space search is carried out based on the better local gene sequences obtained from the regional search, so as to improve the search speed. Moreover, this algorithm improves the mutation performance at the same time. The TSP simulations show that the improved algorithm is a steady and efficient optimal search method.