Hybrid ITÖ Algorithm for Large-scale Colored Traveling Salesman Problem

DONG Xueshi

doi:10.23919/cje.2023.00.040

Article Contents

Article Navigation > Chinese Journal of Electronics > 2023 > Accepted Manuscript

DONG Xueshi, “Hybrid ITÖ Algorithm for Large-scale Colored Traveling Salesman Problem,” Chinese Journal of Electronics, in press, doi: 10.23919/cje.2023.00.040, 2023.

Citation:

DONG Xueshi, “Hybrid ITÖ Algorithm for Large-scale Colored Traveling Salesman Problem,” Chinese Journal of Electronics, in press, doi: 10.23919/cje.2023.00.040, 2023.

DONG Xueshi, “Hybrid ITÖ Algorithm for Large-scale Colored Traveling Salesman Problem,” Chinese Journal of Electronics, in press, doi: 10.23919/cje.2023.00.040, 2023.

Citation:

DONG Xueshi, “Hybrid ITÖ Algorithm for Large-scale Colored Traveling Salesman Problem,” Chinese Journal of Electronics, in press, doi: 10.23919/cje.2023.00.040, 2023.

PDF( 2916 KB)

Hybrid ITÖ Algorithm for Large-scale Colored Traveling Salesman Problem

doi: 10.23919/cje.2023.00.040

DONG Xueshi^{1, 2, 3
,}

1.
College of Computer Science and Technology, Qingdao University, Qingdao 266071, China
2.
Beijing Key Laboratory of Urban Spatial Information Engineering, Beijing 100038, China
3.
School of Computer Science, Wuhan University, Wuhan 430072, China

Funds: This work was supported in part by Shandong Provincial Natural Science Foundation of China under Grant No.ZR2023MF092, Beijing Key Laboratory of Urban Spatial Information Engineering, No.20220109, and Shandong Provincial Key Laboratory of Software Engineering (Shandong University).

More Information

Author Bio:
Xueshi DONG (corresponding author) is currently a distinguished professor/associate professor in College of Computer Science and Technology, Qingdao University. He obtained Ph.D degree in School of Computer Science, Wuhan University. His current research interests include intelligent computing, intelligent transportation, and simulation optimization. (Email: dxs_cs@163.com)
Available Online: 2023-08-31

Abstract

Abstract

In the fields of intelligent transportation and multi-task cooperation, many practical problems can be modeled by colored traveling salesman problem (CTSP). However, when solving large-scale CTSP with a scale of more than 1000 dimensions, their convergence speed and the quality of their solutions are limited. Therefore, this paper proposes a new hybrid ITÖ (HITÖ) algorithm, which integrates two new strategies, crossover operator and mutation strategy, into the standard ITÖ. In the iteration process of HITÖ, the feasible solution of CTSP is represented by the double chromosome coding, and the random drift and wave operators are used to explore and develop new unknown regions. In this process, the drift operator is executed by the improved crossover operator, and the wave operator is performed by the optimized mutation strategy. Experiments show that HITÖ is superior to the known comparison algorithms in term of the quality solution.
- ITÖ algorithm,
- Large scale optimization,
- Colored traveling salesman problem,
- Drift operator,
- Wave operator

FullText(HTML)

References(35)

References

[1]	J. Li, M. C. Zhou, Q. R. Sun, et al., “Colored traveling salesman problem,” IEEE Transactions on Cybernetics, vol.45, no.11, pp.2390–2401, 2015. doi: 10.1109/TCYB.2014.2371918
[2]	J. Li, Q. R. Sun, M. C. Zhou, et al., “A new multiple traveling salesman problem and its genetic algorithm-based solution,” in Proceedings of the 2013 IEEE International Conference on Systems, Man, and Cybernetics, Manchester, UK, pp.1–6, 2013.
[3]	W. Y. Dong, Y. L Cai, Y. F. Wang, et al., “Discrete ITÔ algorithm to the coloured travelling salesman problem,” International Journal of Wireless and Mobile Computing, vol.11, no.2, pp.157–165, 2016. doi: 10.1504/IJWMC.2016.080175
[4]	X. H. Meng, J. Li, M. C. Zhou, et al., “Population-based incremental learning algorithm for a serial colored traveling salesman problem,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol.48, no.2, pp.277–288, 2018. doi: 10.1109/TSMC.2016.2591267
[5]	X. S. Dong, H. Zhang, M. Xu, et al., “Hybrid genetic algorithm with variable neighborhood search for multi-scale multiple bottleneck traveling salesmen problem,” Future Generation Computer Systems, vol.114, pp.229–242, 2021. doi: 10.1016/j.future.2020.07.008
[6]	X. S. Dong, M. Xu, Q. Lin, et al., “ITÖ algorithm with local search for large scale multiple balanced traveling salesmen problem,” Knowledge-Based Systems, vol.229, article no.107330, 2021. doi: 10.1016/j.knosys.2021.107330
[7]	P. Stodola, P. Otřísal, and K. Hasilová, “Adaptive Ant Colony Optimization with node clustering applied to the Travelling Salesman Problem,” Swarm and Evolutionary Computation, vol.70, article no.101056, 2022. doi: 10.1016/j.swevo.2022.101056
[8]	Q. T. Guo, Q. S. Li, and X. S. Dong. “Hybrid genetic algorithms for large scale optimization problem,” in Proceedings of the 2022 6th International Conference on Electronic Information Technology and Computer Engineering, Xiamen, China, pp.1765–1770, 2022.
[9]	S. Mahdavi, M. E. Shiri, and S. Rahnamayan, “Metaheuristics in large-scale global continues optimization: A survey,” Information Sciences, vol.295, pp.407–428, 2015. doi: 10.1016/j.ins.2014.10.042
[10]	B. L. Ye, W. M. Wu, L. X. Li, et al., “A hierarchical model predictive control approach for signal splits optimization in large-scale urban road networks,” IEEE Transactions on Intelligent Transportation Systems, vol.17, no.8, pp.2182–2192, 2016. doi: 10.1109/TITS.2016.2517079
[11]	G. A. Trunfio, P. Topa, and J. Wąs, “A new algorithm for adapting the configuration of subcomponents in large-scale optimization with cooperative coevolution,” Information Sciences, vol.372, pp.773–795, 2016. doi: 10.1016/j.ins.2016.08.080
[12]	M. N. Omidvar, M. Yang, Y. Mei, et al., “DG2: A faster and more accurate differential grouping for large-scale black-box optimization,” IEEE Transactions on Evolutionary Computation, vol.21, no.6, pp.929–942, 2017. doi: 10.1109/TEVC.2017.2694221
[13]	Q. Yang, W. N. Chen, T. L. Gu, et al., “Segment-based predominant learning swarm optimizer for large-scale optimization,” IEEE Transactions on Cybernetics, vol.47, no.9, pp.2896–2910, 2017. doi: 10.1109/TCYB.2016.2616170
[14]	P. Wang, C. H. Shen, A. van den Hengel, et al., “Large-scale binary quadratic optimization using semidefinite relaxation and applications,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.39, no.3, pp.470–485, 2017. doi: 10.1109/TPAMI.2016.2541146
[15]	Y. F. Zhang and H. D. Chiang, “A novel consensus-based particle swarm optimization-assisted trust-tech methodology for large-scale global optimization,” IEEE Transactions on Cybernetics, vol.47, no.9, pp.2717–2729, 2017. doi: 10.1109/TCYB.2016.2577587
[16]	R. Cheng, Y. C. Jin, M. Olhofer, et al., “Test problems for large-scale multiobjective and many-objective optimization,” IEEE Transactions on Cybernetics, vol.47, no.12, pp.4108–4121, 2017. doi: 10.1109/TCYB.2016.2600577
[17]	X. Y. Zhang, Y. Tian, R. Cheng, et al., “A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization,” IEEE Transactions on Evolutionary Computation, vol.22, no.1, pp.97–112, 2018. doi: 10.1109/TEVC.2016.2600642
[18]	X. M. Hu, F. L. He, W. N. Chen, et al., “Cooperation coevolution with fast interdependency identification for large scale optimization,” Information Sciences, vol.381, pp.142–160, 2017. doi: 10.1016/j.ins.2016.11.013
[19]	T. Sattler, B. Leibe, and L. Kobbelt, “Efficient & effective prioritized matching for large-scale image-based localization,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.39, no.9, pp.1744–1756, 2017. doi: 10.1109/TPAMI.2016.2611662
[20]	Y. F. Wang, W. Y. Dong, and X. S. Dong, “A novel ITÖ Algorithm for influence maximization in the large-scale social networks,” Future Generation Computer Systems, vol.88, pp.755–763, 2018. doi: 10.1016/j.future.2018.04.026
[21]	X. S. Dong, W. Y. Dong, and Y. L. Cai, “Ant colony optimisation for coloured travelling salesman problem by multi-task learning,” IET Intelligent Transport Systems, vol.12, no.8, pp.774–782, 2018. doi: 10.1049/iet-its.2016.0282
[22]	X. S. Dong and Y. L. Cai, “A novel genetic algorithm for large scale colored balanced traveling salesman problem,” Future Generation Computer Systems, vol.95, pp.727–742, 2019. doi: 10.1016/j.future.2018.12.065
[23]	A. P. Engelbrecht, “Fitness function evaluations: A fair stopping condition?” in Proceedings of 2014 IEEE Symposium on Swarm Intelligence, Orlando, FL, USA, pp.1–8, 2014.
[24]	M. Mernik, S. H. Liu, D. Karaboga, et al., “On clarifying misconceptions when comparing variants of the artificial bee colony algorithm by offering a new implementation,” Information Sciences, vol.291, pp.115–127, 2015. doi: 10.1016/j.ins.2014.08.040
[25]	M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol.26, no.1, pp.29–41, 1996. doi: 10.1109/3477.484436
[26]	M. Dorigo and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol.1, no.1, pp.53–66, 1997. doi: 10.1109/4235.585892
[27]	B. Crawford, R. Soto, F. Johnson, et al., “A max–min ant system algorithm to solve the software project scheduling problem,” Expert Systems with Applications, vol.41, no.15, pp.6634–6645, 2014. doi: 10.1016/j.eswa.2014.05.003
[28]	B. R. Ke, M. C. Chen, and C. L. Lin, “Block-layout design using MAX–MIN ant system for saving energy on mass rapid transit systems,” IEEE Transactions on Intelligent Transportation Systems, vol.10, no.2, pp.226–235, 2009. doi: 10.1109/TITS.2009.2018324
[29]	X. S. Dong, Q. Lin, M. Xu, et al., “Artificial bee colony algorithm with generating neighbourhood solution for large scale coloured traveling salesman problem,” IET Intelligent Transport Systems, vol.13, no.10, pp.1483–1491, 2019. doi: 10.1049/iet-its.2018.5359
[30]	W. Y. Dong, X. S. Dong, and Y. F. Wang, “Improved artificial bee colony algorithm for large scale colored bottleneck traveling salesman problem,” Journal on Communications, vol.39, no.12, pp.18–29, 2018. doi: 10.11959/j.issn.1000-436x.2018284
[31]	X. H. Meng, J. Li, X. Z. Dai, et al., “Variable neighborhood search for a colored traveling salesman problem,” IEEE Transactions on Intelligent Transportation Systems, vol.19, no.4, pp.1018–1026, 2018. doi: 10.1109/TITS.2017.2706720
[32]	H. G. Zhang and J. Zhou, “Dynamic multiscale region search algorithm using vitality selection for traveling salesman problem,” Expert Systems with Applications, vol.60, pp.81–95, 2016. doi: 10.1016/j.eswa.2016.05.007
[33]	G. G. Wang and Y. Tan, “Improving metaheuristic algorithms with information feedback models,” IEEE Transactions on Cybernetics, vol.49, no.2, pp.542–555, 2019. doi: 10.1109/TCYB.2017.2780274
[34]	Z. K. Fan, G. S. Hu, X. Sun, et al., “Self-attention neural architecture search for semantic image segmentation,” Knowledge-Based Systems, vol.239, article no.107968, 2022. doi: 10.1016/j.knosys.2021.107968
[35]	H. R. Zhao, X. Sun, J. Y. Dong, et al., “Multi-instance semantic similarity transferring for knowledge distillation,” Knowledge-Based Systems, vol.256, article no.109832, 2022. doi: 10.1016/j.knosys.2022.109832