An improved memetic genetic algorithm based on a complex network as a solution to the traveling salesman problem
An improved memetic genetic algorithm based on a complex network as a solution to the traveling salesman problem
A genetic algorithm (GA) is not a good option for finding solutions around in neighborhoods. The current study applies a memetic algorithm (MA) with a proposed local search to the mutation operator of a genetic algorithm in order to solve the traveling salesman problem (TSP). The proposed memetic algorithm uses swap, reversion and insertion operations to make changes in the solution. In the basic GA, unlike in the real world, the relationship between generations has not been considered. This gap is resolved using the proposed complex network to allow selection among possible solutions. The degree measure has been used for analysis the network. Different scenarios have been evaluated to solve seven TSPLib problems. For example, the results indicated that the memetic algorithm with a complex network, the memetic algorithm with the proposed local search and basic GA have 0.31%, 1.15% and 38% errors, respectively, when solving the TSP for 70 cities compared to the best solution in the TSPLib database. These results offered better performance of the memetic algorithm with a complex network compared to the memetic algorithm with the proposed local search and the basic GA. Also, the average run time of the algorithms showed their scalability.
___
- 1] Fuentes GEA, Gress ESH, Mora JCS, Marín JM. Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic. PLoS One 2018; 13 (8): 1-20. doi: 10.1371/journal.pone.0201868
- [2] Nagarani B, Nesamony J. Performance enhancement of photovoltaic system using genetic algorithm-based maximum power point tracking. Turkish Journal of Electrical Engineering & Computer Sciences 2019; 27 (4): 3015-3025. doi: 10.3906/elk-1801-189
- 3] Peker M, Sen B, Kumru PY. An efficient solving problem: the ant colony system having parameters optimized by the Taguchi method. Turkish Journal of Electrical Engineering & Computer Sciences 2013; 21 (1): 2015-2036. doi: 10.3906/elk-1109-44
- [4] Hekim M, Comert O, Adem K. A hybrid model based on the convolutional neural network model and artificial bee colony or particle swarm optimization-based iterative thresholding for the detection of bruised apples. Turkish Journal of Electrical Engineering & Computer Sciences 2020; 28 (1): 61-79. doi: 10.3906/elk-1904-180
- [5] Guvenc U, Yigit T, Isik AH, Akkaya I. Performance analysis of biogeography-based optimization for automatic voltage regulator system. Turkish Journal of Electrical Engineering & Computer Sciences 2016; 24 (3): 1150-1162. doi: 10.3906/elk-1311-111
- [6] Kalinli A. Simulated annealing algorithm-based elman network for dynamic system identification. Turkish Journal of Electrical Engineering & Computer Sciences 2012; 20 (4): 1150-1162. doi: 10.3906/elk-1012-942
- [7] Jemai M, Dimassi S, Ouini B, Mtibaa A. A metaheuristic based on the tabu search for hardware-software partition- ing. Turkish Journal of Electrical Engineering & Computer Sciences 2017; 25 (2): 901-912. doi: 10.3906/elk-1501-64
- [8] Rostami N. Particle swarm optimization approach to optimal design of an AFPM traction machine for different driving conditions. Turkish Journal of Electrical Engineering & Computer Sciences 2019; 27 (4): 3234 -3246. doi: 10.3906/elk-1805-176
- [9] Mollakhalili Meybodi MR, Meybodi MR. Extended distributed learning automata an automata-based framework for solving stochastic graph optimization problems. Applied Intelligence 2014; 41 (2): 923-940. doi: 10.1007/s10489- 014-0577-2
- [10] Zhang JW, Si WJ. Improved enhanced self-tentative PSO algorithm for TSP. In: IEEE 2010 Sixth International Conference on Natural Computation (ICNC) Conference; Yantai, China; 2010. pp. 2638-2641.
- [11] Zhou Tao Z. TSP problem solution based on improved genetic algorithm. In: IEEE 2008 Fourth International Conference on Natural Computation Conference; Jinan, China; 2008. pp. 686-690.
- [12] Zhang L, Xiao C, Fei T. Improved ant colony optimization algorithm based on RNA computing. Automatic Control and Computer Sciences 2017; 51 (5): 366-375. doi: 10.3103/s0146411617050108
- [13] Buriol LS, Moscato P, França PM. A new memetic algorithm for the asymmetric traveling salesman problem. Journal of Heuristics 2004; 10 (5): 483-506. doi: 10.1023/b:heur.0000045321.59202.52
- [14] Rezapoor Mirsaleh M, Meybodi MR. Balancing exploration and exploitation in memetic algorithms: a learning automata approach. Computational Intelligence 2018; 34 (1): 282-309. doi: 10.1111/coin.12148
- [15] Gao Y, Du W, Yan G. Selectively-informed particle swarm optimization. Scientific Reports 2015; 5 (1): 1-7. doi: 10.1038/srep09295
- [16] Matsushita H, Nishio Y, Saito T. Particle swarm optimization with novel concept of complex network. In: 2010 International Symposium on Nonlinear Theory and Its Applications Conference; Krakow, Poland; 2010. pp. 197-200.
- [17] Watts DJ, Strogatz SH. Collective dynamics of small-world networks. Nature 1998; 393 (6684): 440-442. doi: 10.1038/30918
- [18] Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D-U. Complex networks: structure and dynamics. Physics Reports 2006; 424 (4-5): 175-308. doi: 10.1016/j.physrep.2005.10.009
- [19] Mo H, Xu L. Biogeography based optimization for traveling salesman problem. In: IEEE 2010 Sixth International Conference on Natural Computation (ICNC) Conference; Yantai, China; 2010. pp. 3143-3147.
- [20] Simon D. Biogeography-based optimization. Transactions on Evolutionary Computation 2008; 12 (6): 702-713. doi: 10.1109/TEVC.2008.919004
- [21] Pham DT, Huynh TTB, Dang MC. An improving of migration operator in biogeography-based optimization for solving traveling salesman problem. In: IEEE 2017 International Conference on Computational Intelligence and Cybernetics Conference; Makassar, Indonesia; 2016. pp. 33-40.
- 22] Li M, Du W, Nian F. An adaptive particle swarm optimization algorithm based on directed weighted complex network. Mathematical Problems in Engineering 2014; 2014 (2): 1-7. doi: 10.1155/2014/434972
- [23] Liu C, Du1 WB, Wang WX. Particle swarm optimization with scale-free interactions. PLoS One 2014; 9 (5): 1-8. doi: 10.1371/journal.pone.0097822
- [24] Contreras-Bolton C, Parada V. automatic combination of operators in a genetic algorithm to solve the traveling salesman problem. PLoS One 2015; 10 (9): 1-25. doi: 10.1371/journal.pone.0137724
- [25] Thanh PD, Binh HTT, Lam BT. New mechanism of combination crossover operators in genetic algorithm for solving the traveling salesman problem. Knowledge and Systems Engineering 2015; 326 (1): 367-379. doi: 0.1007/978-3- 319-11680-8-29
- [26] Sabry D, Abdel-Moetty Asmaa M, Heakil O. Enhanced traveling salesman problem solving using genetic algorithm technique with modified sequential constructive crossover operator. IJCSNS International Journal of Computer Science and Network Security 2012; 12 (6): 134-139.
- [27] Xu Q, Wang N, Wang L. Enhancing performance of oppositional BBO using the current optimum (COOBBO) for TSP problems. International Journal of Intelligent Computing and Cybernetics 2016; 9 (2): 144-164. doi: 10.1108/ijicc-03-2016-0015
- [28] Xu Q, Wang L. A novel oppositional biogeography-based ptimization for combinatorial problems. In: IEEE 2014 10th International Conference on Natural Computation (ICNC) Conference; Xiamen, China; 2014. pp. 414-420.
- [29] Tizhoosh HR. Opposition-based learning: a new scheme for machine intelligence. In: IEEE 2005 International Conference on Computational Intelligence for Modelling International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC’06) Conference; Vienna, Austria; 2005; pp. 695-701.
- [30] Mitchell M. Complex systems: network thinking. Artificial Intelligence 2006; 170 (2006): 1194–1212. doi: 10.1016/j.artint.2006.10.002
- [31] Zelinka I, Chen G. Evolutionary algorithms. In: Zelinka I, Chen G (editors). Swarm Dynamics and Complex Networks Methodology Perspectives and Implementation. Berlin, Germany: Springer-Verlag Berlin Heidelberg, 2018.