基于递阶遗传算法的多旅行商问题优化  

Optimization of multiple traveling salesman problem based on hierarchical genetic algorithm

作　　者：周辉仁[1,2] 唐万生[1] 牛犇[1,2] 

机构地区：[1]天津大学系统工程研究所,天津300072 [2]山东建筑大学管理工程学院,济南250101

出　　处：《计算机应用研究》2009年第10期3754-3757,共4页Application Research of Computers

基　　金：中国博士后科学基金资助项目(20090450759)

摘　　要：旅行商问题是一个经典的NP问题,对多人旅行商问题的求解则更具有意义。为了解决所有旅行商路径总和最小为优化标准的多旅行商一类问题,提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点,采用一种递阶编码方案,此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题无须设计专门的遗传算子,操作简单,并且解码方法适于求解距离对称和距离非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化多旅行商问题。Traveling salesman problem is a classical nondeterministie polynomial problem. It is significance to solve multiple traveling salesman problems （MTSP）. In order to solve MTSP that employed total-path-shortest as the evaluating rule, this paper proposed a hierarchical genetic algorithm and decoding method with matrix. Its coding method is simple and can effectively reflect the traveling policy, and the methods of crossover and mutation are not special to design. By this method, symmetric and asymmetric multiple traveling salesman problems can be easily solved. The computational results suggest that the hierarchical genetic algorithm is efficient and fit for multiple traveling salesman problems.

关 键 词：递阶遗传算法 多旅行商问题 优化 解码方法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP18[自动化与计算机技术—计算机科学与技术]