混合伊藤算法求解多尺度着色旅行商问题  

Hybrid IT? algorithm for multi-scale colored traveling salesman problem

作　　者：韩舒宁 徐敏 董学士 林青 沈凡凡 HAN Shuning;XU Min;DONG Xueshi;LIN Qing;SHEN Fanfan(College of Computer Science and Technology,Qingdao University,Qingdao Shandong 266071,China;Changjiang Waterway Institute of Planning and Design,Wuhan Hubei 430040,China;School of Information Engineering,Nanjing Audit University,Nanjing Jiangsu 211815,China)

机构地区：[1]青岛大学计算机科学技术学院,青岛266071 [2]长江航道规划设计研究院,武汉430040 [3]南京审计大学信息工程学院,南京211815

出　　处：《计算机应用》2022年第3期695-700,共6页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61902189);山东省软件工程重点实验室(山东大学)开放基金资助项目(2020SPKLSE0612)。

摘　　要：着色旅行商问题(CTSP)是多旅行商问题(MTSP)与旅行商问题(TSP)的一种扩展,主要应用于含重复区域的多机工程系统(MES)等工程问题。CTSP是NP完全问题,尽管相关研究尝试采用遗传算法(GA)、模拟退火(SA)等方法求解该问题,但它们求解的问题尺度有限,且速度和求解质量上不尽人意。基于此,尝试采用一种基于均匀设计(UD)融合蚁群(ACO)算法和伊藤算法(IT?)的混合伊藤算法(UDHIT?)来求解该问题。UDHIT?采用UD来选择合适的参数组合,借助ACO的概率图模型来产生可行解,并利用伊藤算法的漂移和波动算子进行优化。实验的结果表明,UDHIT?求解多尺度CTSP的最优解和平均解比传统GA、ACO和IT?有所改善。Colored Traveling Salesman Problem(CTSP)is a variant of Multiple Traveling Salesmen Problem(MTSP)and Traveling Salesman Problem(TSP),which can be applied to the engineering problems such as Multi-machine Engineering System(MES)with overlapping workspace.CTSP is an NP complete problem,although related studies have attempted to solve the problem by Genetic Algorithm(SA),Simulated Annealing(SA)algorithm and some other methods,but they solve the problem at a limited scale and with unsatisfactory speed and solution quality.Therefore,a hybrid IT?algorithm combined with Uniform Design(UD),Ant Colony Optimization(ACO)and IT? algorithm was proposed to solve this problem,namely UDHIT?.UD was applied to choose the appropriate combination of parameters of the UDHIT?algorithm,the probabilistic graphic model of ACO was used to generate feasible solutions,and the drift operator and volatility operator of IT? were used to optimize the solutions.Experimental results show that the UDHIT? algorithm can demonstrate improvement over the traditional GA,ACO and IT? algorithm for the multi-scale CTSP problems in terms of best solution and average solution.

关 键 词：伊藤算法 着色旅行商问题 蚁群算法 漂移算子 波动算子 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]