TY - JOUR
T1 - Population-Based Incremental Learning Algorithm for a Serial Colored Traveling Salesman Problem
AU - Meng, Xianghu
AU - Li, Jun
AU - Zhou, Meng Chu
AU - Dai, Xianzhong
AU - Dou, Jianping
N1 - Funding Information:
Manuscript received February 18, 2016; revised April 30, 2016; accepted June 30, 2016. Date of publication August 5, 2016; date of current version January 15, 2018. This work was supported in part by the National Natural Science Foundation of China under Grants 61374069, 61374148, and 51575108, the Jiangsu Province Natural Science Foundation under Grant BK20161427, and Jiangsu Province Graduate Students Research and Innovation Program under Grant KYLX_0136. (Corresponding author: Jun Li.) This paper has supplementary downloadable multimedia material available at http://ieeexplore.ieee.org provided by the authors.
PY - 2018/2
Y1 - 2018/2
N2 - 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.
AB - 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.
KW - Colored traveling salesman problem (CTSP)
KW - combinatorial optimization
KW - computational complexity
KW - genetic algorithm (GA)
KW - modeling
KW - multiple traveling salesman problem (MTSP)
KW - population-based incremental learning (PBIL)
UR - http://www.scopus.com/inward/record.url?scp=85040714955&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85040714955&partnerID=8YFLogxK
U2 - 10.1109/TSMC.2016.2591267
DO - 10.1109/TSMC.2016.2591267
M3 - Article
AN - SCOPUS:85040714955
SN - 2168-2216
VL - 48
SP - 277
EP - 288
JO - IEEE Transactions on Systems, Man, and Cybernetics: Systems
JF - IEEE Transactions on Systems, Man, and Cybernetics: Systems
IS - 2
M1 - 7534819
ER -