旅行商问题的一种选择性集成求解方法  

A selective ensemble method for traveling salesman problems

作　　者：王立宏[1] 李强[2] 

机构地区：[1]烟台大学计算机与控制工程学院,山东烟台264005 [2]烟台大学经济管理学院,山东烟台264005

出　　处：《山东大学学报（工学版）》2016年第1期42-48,共7页Journal of Shandong University（Engineering Science）

基　　金：国家自然科学基金资助项目(71372122;61403328);山东省自然科学基金资助项目(ZR2013FM011)

摘　　要：针对大型TSP(traveling salesman problem)实例很难找到最优解的问题,提出了一种选择性集成求解方法。首先通过扩大路径法来选择集成多个较好解,构造出若干个极大路径;然后采用顶点插入法将剩余顶点和这些极大路径连接成一个哈密顿回路;最后使用2-opt方法对该回路进行提升。试验结果表明,算法在5个TSP实例上得出的最好解的最大偏差为1.69%,说明本算法可以有效求解TSP。To solve the problem of finding the optimum solution of very large TSP（ traveling salesman problem）,a selective ensemble method was proposed. Firstly,expanding path method was used to selective integrate some high quality solutions,and several maximum paths were obtained. And then vertex insertion method was employed to connect these paths and the remainder vertices to form a Hamiltonian tour. Finally,the tour was improved by 2-opt method. Experimental results on 5 TSP instances showed that the maximal bias was 1. 69%,and the effectiveness was proved.

关 键 词：人工智能 选择性集成学习 旅行商问题 极大路径 顶点插入 

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