Journal of Systems Engineering and Electronics ›› 2020, Vol. 31 ›› Issue (4): 751-760.doi: 10.23919/JSEE.2020.000050

• Systems Engineering • Previous Articles     Next Articles

Parallel discrete lion swarm optimization algorithm for solving traveling salesman problem

Daoqing ZHANG(), Mingyan JIANG*()   

  • Received:2019-09-29 Online:2020-08-25 Published:2020-08-25
  • Contact: Mingyan JIANG E-mail:zhang_dao_qing@163.com;jiangmingyan@sdu.edu.cn
  • About author:ZHANG Daoqing was born in 1994. He is currently working toward his M.E. degree in the School of Information Science and Engineering, Shandong University, China. His research interests include evolutionary computation and machine learning. E-mail: zhang_dao_qing@163.com|JIANG Mingyan was born in 1964. He received hisM.S. degree in 1992 and his Ph.D. degree in 2005 from ShandongUniversity. He finished his postdoctoral research in communicationsignal and system at Spain Telecommunications Technology Center ofCatalonia in 2007. Now he is a full professor and a doctoralsupervisor in the School of Information Science and Engineering, Shandong University, China. He has published more than 200professional papers and six books. His research interests includesoft computing, signal and image processing, computernetwork, artificial intelligence and data mining.E-mail: jiangmingyan@sdu.edu.cn
  • Supported by:
    the National Natural Science Foundation of China(61771293);the Key Project of Shangdong Province(2019JZZY010111);This work was supported by the National Natural Science Foundation of China (61771293) and the Key Project of Shangdong Province (2019JZZY010111)

Abstract:

As a typical representative of the NP-complete problem, the traveling salesman problem (TSP) is widely utilized in computer networks, logistics distribution, and other fields. In this paper, a discrete lion swarm optimization (DLSO) algorithm is proposed to solve the TSP. Firstly, we introduce discrete coding and order crossover operators in DLSO. Secondly, we use the complete 2-opt (C2-opt) algorithm to enhance the local search ability. Then in order to enhance the efficiency of the algorithm, a parallel discrete lion swarm optimization (PDLSO) algorithm is proposed. The PDLSO has multiple populations, and each sub-population independently runs the DLSO algorithm in parallel. We use the ring topology to transfer information between sub-populations. Experiments on some benchmarks TSP problems show that the DLSO algorithm has a better accuracy than other algorithms, and the PDLSO algorithm can effectively shorten the running time.

Key words: discrete lion swarm optimization (DLSO) algorithm, complete 2-opt (C2-opt) algorithm, parallel discrete lion swarm optimization (PDLSO) algorithm, traveling salesman problem (TSP)