Population-Based Incremental Learning Algorithm for a Serial Colored Traveling Salesman Problem
Population-Based Incremental Learning Algorithm for a Serial Colored Traveling Salesman Problem
复制标题
基于群体的增量学习算法解决串行彩色旅行商问题
DOI：
10.1109/tsmc.2016.2591267
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
Jianping Dou
中科院分区：
文献类型：
--
作者：
Xianghu Meng;Jun Li;MengChu Zhou;Xianzhong Dai;Jianping Dou
彩色旅行商问题（CTSP）是对著名的多重旅行商问题的推广。本文研究了一类CTSP，称为串行CTSP （S-CTSP）。它的每个销售人员都有自己的专属城市，并以串行方式与邻居共享一些城市。该方法可用于求解机器线性排列的多机器工程系统的调度问题。S-CTSP是NP-hard。开发有效和高效的S-CTSP方法对于实现其工业应用至关重要。本文提出了一种基于群体的增量学习（PBIL）方法。在分析其解空间的基础上，建立了一些概率矩阵模型来指导算法的个体搜索。然后，在状态传递函数中引入距离惩罚，通过轮盘赌方法选择惩罚值较小的城市，形成一条良好的路线。通过在算法中加入强大的局部搜索操作2-opt，进一步增强了算法的搜索能力。仿真结果表明，增强后的PBIL算法是有效的，其性能优于遗传算法和CPLEX算法。
A colored traveling salesman problem (CTSP) is a generalization of the well-known multiple traveling salesman problem. This paper investigate a class of CTSP, called serial CTSP (S-CTSP). Each of its salesmen has his exclusive cities and shares some cities with its neighbor(s) in a serial manner. It can be used to model the scheduling problem of multimachine engineering systems with linearly arranged machines. S-CTSP is NP-hard. Developing effective and efficient approaches to S-CTSP is important to enable its industrial applications. This paper presents a population-based incremental learning (PBIL) approach to it. After analyzing its solution space, we set up some probability matrix models to guide the individual search of the algorithm. Then, a distance penalty is introduced into the state transfer function that can select the cities with small penalty values by the Roulette method to form a good route. By adding a powerful local search operation, 2-opt, to the algorithm, we can further enhance its search ability. Extensive simulation is conducted and its results show that the augmented PBIL is effective and well outperforms the genetic algorithms and CPLEX.