《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (3): 695-700.DOI: 10.11772/j.issn.1001-9081.2021040776

• 2021年中国计算机学会人工智能会议(CCFAI 2021) • 上一篇    

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

韩舒宁1, 徐敏2, 董学士1(), 林青1, 沈凡凡3   

  1. 1.青岛大学 计算机科学技术学院, 青岛 266071
    2.长江航道规划设计研究院, 武汉 430040
    3.南京审计大学 信息工程学院, 南京 211815
  • 收稿日期:2021-05-13 修回日期:2021-06-19 接受日期:2021-06-22 发布日期:2021-11-09 出版日期:2022-03-10
  • 通讯作者: 董学士
  • 作者简介:韩舒宁(1997—),女,山东青岛人,硕士研究生,主要研究方向:智能交通、智能计算
    徐敏(1989—),女,浙江金华人,博士,主要研究方向:航道规划、数据分析
    林青(1981—),男,山东泰安人,助理教授,博士,主要研究方向:智能交通、智能感知算法
    沈凡凡(1987—),男,湖北荆门人,副教授,博士,主要研究方向:嵌入系统、计算机体系结构。
  • 基金资助:
    国家自然科学基金资助项目(61902189);山东省软件工程重点实验室(山东大学)开放基金资助项目(2020SPKLSE0612)

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

Shuning HAN1, Min XU2, Xueshi DONG1(), Qing LIN1, Fanfan SHEN3   

  1. 1.College of Computer Science and Technology,Qingdao University,Qingdao Shandong 266071,China
    2.Changjiang Waterway Institute of Planning and Design,Wuhan Hubei 430040,China
    3.School of Information Engineering,Nanjing Audit University,Nanjing Jiangsu 211815,China
  • Received:2021-05-13 Revised:2021-06-19 Accepted:2021-06-22 Online:2021-11-09 Published:2022-03-10
  • Contact: Xueshi DONG
  • About author:HAN Shuning, born in 1997, M. S. candidate. Her research interests include intelligent transportation, intelligent computing.
    XU Min, born in 1989, Ph. D. Her research interests include waterway planning, data analysis.
    LIN Qing, born in 1981, Ph. D., assistant professor. His research interests include intelligent transportation, intelligent perception algorithm.
    SHEN Fanfan, born in 1987, Ph. D., associate professor. His research interests include embedded system, computer architecture.
  • Supported by:
    National Natural Science Foundation of China(61902189);Shandong Provincial Key Laboratory of Software Engineering(2020SPKLSE0612)

摘要:

着色旅行商问题(CTSP)是多旅行商问题(MTSP)与旅行商问题(TSP)的一种扩展,主要应用于含重复区域的多机工程系统(MES)等工程问题。CTSP是NP完全问题,尽管相关研究尝试采用遗传算法(GA)、模拟退火(SA)等方法求解该问题,但它们求解的问题尺度有限,且速度和求解质量上不尽人意。基于此,尝试采用一种基于均匀设计(UD)融合蚁群(ACO)算法和伊藤算法(IT?)的混合伊藤算法(UDHIT?)来求解该问题。UDHIT?采用UD来选择合适的参数组合,借助ACO的概率图模型来产生可行解,并利用伊藤算法的漂移和波动算子进行优化。实验的结果表明,UDHIT?求解多尺度CTSP的最优解和平均解比传统GA、ACO和IT?有所改善。

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

Abstract:

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.

Key words: IT? algorithm, Colored Traveling Salesman Problem (CTSP), Ant Colony Optimization (ACO), drift operator, volatility operator

中图分类号: