A Novel Crossover based Discrete Artificial Algae Algorithm for Solving Traveling Salesman Problem
The Artificial Algae Algorithm (AAA) is a newly proposed metaheuristic algorithm that is inspired by microalgae behaviors. This algorithm has been proposed for solving continuous optimization problems and achieved good results for the continuous problems. In addition, binary versions of AAA are proposed in the literature. This paper presents a discrete version of AAA, which is named Discrete Artificial Algae Algorithm (DAAA). For discretization of AAA, Crossover operators (one-point and uniform) are used in the processes (helical movement, evolutionary process, and adaptation). In this study, in addition to crossover operators, transformation operators such as swapping, insertion, symmetry, and reversion are also used. DAAA’s performance was analyzed on a well-known discrete optimization problem called the Traveling Salesman Problem (TSP). DAAA was tested on thirty-two Benchmark instances of the TSP. These instances were small-sized, medium-sized, and large-sized. Firstly, the AAA processes (evolutionary process, adaptation, and helical movement) with the combination of nearest neighbor and transformation operators were tested for selected benchmark instances and this testing was called Process Analysis. After this process Analysis the best processes with which to continue were selected, and after this decision comparisons with other algorithms were started. The main comparison is between discrete Social Spider Algorithm (DSSA) and DAAA, and DAAA outperformed DSSA on most of the problems. Further, DAAA’s performance on some of the benchmark instances was compared with some of the well-known algorithms for TSP. In this comparison, DAAA has achieved better results than many other algorithms. Experimental results show that DAAA has the capability of solving discrete optimization problems and outperforming other algorithms.
[1] Akhand M., Ayon S., Shahriyar S., Siddique N., and Adeli H., “Discrete Spider Monkey Optimization for Travelling Salesman Problem,” Applied Soft Computing, vol. 86, pp. 105887, 2020. https://doi.org/10.1016/j.asoc.2019.105887
[2] Archetti C., Feillet D., Mor A., and Speranza M., “An Iterated Local Search for the Traveling Salesman Problem with Release Dates and Completion Time Minimization,” Computers and Operations Research, vol. 98, pp. 24-37, 2018. https://doi.org/10.1016/j.cor.2018.05.001
[3] Babalik A., Ozkis A., Uymaz S., and Kiran M., “A Multi-Objective Artificial Algae Algorithm,” Applied Soft Computing, vol. 68, pp. 377-395, 2018. https://doi.org/10.1016/j.asoc.2018.04.009
[4] Ban H., “Applying Metaheuristic for Time- Dependent Traveling Salesman Problem in Postdisaster,” International Journal of Computational Intelligence Systems, vol. 14, no. 1, pp. 1087-1107, 2021. DOI:10.2991/ijcis.d.210226.001
[5] Bas E. and Ulker E., “Discrete Social Spider Algorıthm for the Travelıng Salesman Problem,” Artificial Intelligence Review, vol. 54, no. 2, pp. 1063-1085, 2021. https://link.springer.com/article/10.1007/s10462- 020-09869-8
[6] Bello R., Gomez Y., Nowe A., and Garcia M., “Two-Step Particle Swarm Optimization to Solve the Feature Selection Problem,” in Proceedings of the 7th International Conference on Intelligent Systems Design and Applications, Rio de Janeiro, pp. 691-696, 2007. DOI: 10.1109/ISDA.2007.101
[7] Beskirli M., Koc I., Hakli H., and Kodaz H., “A New Optimization Algorithm for Solving Wind Turbine Placement Problem: Binary Artificial Algae Algorithm,” Renewable Energy, vol. 121, pp. 301-308, 2018. https://doi.org/10.1016/j.renene.2017.12.087
[8] Cavani S., Iori M., and Roberti R., “Exact Methods for the Traveling Salesman Problem with Multiple Drones,” Transportation Research Part C: Emerging Technologies, vol. 130, pp. 103280, 2021. https://doi.org/10.1016/j.trc.2021.103280
[9] Choong S., Wong L., and Lim C., “An Artificial Bee Colony Algorithm with a Modified Choice Function for the Traveling Salesman Problem,” Swarm and Evolutionary Computation, vol. 44, pp. 622-635, 2019. https://doi.org/10.1016/j.swevo.2018.08.004
[10] Cinar A., Korkmaz S., and Kiran M., “A Discrete Tree-Seed Algorithm for Solving Symmetric Traveling Salesman Problem,” Engineering Science and Technology, an International Journal, vol. 23, no. 4, pp. 879-890, 2020. https://doi.org/10.1016/j.jestch.2019.11.005 950 The International Arab Journal of Information Technology, Vol. 21, No. 5, September 2024
[11] Daoqing Z. and Mingyan J., “Parallel Discrete Lion Swarm Optimization Algorithm for Solving Traveling Salesman Problem,” Journal of Systems Engineering and Electronics, vol. 31, no. 4, pp. 751-760, 2020. DOI: 10.23919/JSEE.2020.000050
[12] Dell’Amico M., Montemanni R., and Novellani S., “Exact Models for the Flying Sidekick Traveling Salesman Problem,” International Transactions in Operational Research, vol. 29, no. 3, pp. 1360-1393, 2022. https://doi.org/10.1111/itor.13030
[13] Dodig M. and Smith M., “Apple Carving Algorithm to Approximate Traveling Salesman Problem from Compact Triangulation of Planar Point Sets,” International Journal of Advanced Computer Science and Applications, vol. 11, no. 3, pp. 1-7, 2020.
[14] Dong X., Xu M., Lin Q., Han S., Li Q., and Guo Q., “ITO Algorithm with Local Search for Large Scale Multiple Balanced Traveling Salesmen Problem,” Knowledge-Based Systems, vol. 229, pp. 107330, 2021. https://doi.org/10.1016/j.knosys.2021.107330
[15] Dorigo M. and Gambardella L., “Ant Colonies for the Travelling Salesman Problem,” Biosystems, vol. 43, no. 2, pp. 73-81, 1997. https://doi.org/10.1016/S0303-2647(97)01708-5
[16] Ebadinezhad S., “DEACO: Adopting Dynamic Evaporation Strategy to Enhance ACO Algorithm for the Traveling Salesman Problem,” Engineering Applications of Artificial Intelligence, vol. 92, pp. 103649, 2020. https://doi.org/10.1016/j.engappai.2020.103649
[17] Englert M., Roglin H., and Vocking B., “Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP,” Algorithmica, vol. 68, no. 1, pp. 190-264, 2014. https://link.springer.com/article/10.1007/s00453- 013-9801-4
[18] Eskandari L., Jafarian A., Rahimloo P., and Baleanu D., Mathematical Methods in Engineering, Springer, 2019. https://link.springer.com/chapter/10.1007/978-3- 319-91065-9_13
[19] Gang P., Iimura I., and Nakayama S., “An Evolutionary Multiple Heuristic with Genetic Local Search for Solving TSP,” International Journal of Information Technology, vol. 14, no. 2, pp. 1-11, 2008. https://intjit.org/cms/journal/volume/14/2/142_1.pdf
[20] Gharib A., Benhra J., and Chaouqi M., “A Performance Comparison of PSO and GA Applied to TSP,” International Journal of Computer Applications, vol. 975, no. 15, pp. 34-39, 2015. DOI: 10.5120/ijca2015907188
[21] Gulcu S., Mahi M., Baykan O., and Kodaz H., “A Parallel Cooperative Hybrid Method Based on Ant Colony Optimization and 3-Opt Algorithm for Solving Traveling Salesman Problem,” Soft Computing, vol. 22, no. 5, pp. 1669-1685, 2018. https://link.springer.com/article/10.1007/s00500- 016-2432-3
[22] Gunduz M. and Aslan M., “DJAYA: A Discrete Jaya Algorithm for Solving Traveling Salesman Problem,” Applied Soft Computing, vol. 105, pp. 107275, 2021. https://doi.org/10.1016/j.asoc.2021.107275
[23] Gunduz M., Kiran M., and Ozceylan E., “A Hierarchic Approach Based on Swarm Intelligence to Solve the Traveling Salesman Problem,” Turkish Journal of Electrical Engineering and Computer Sciences, vol. 23, no. 1, pp. 103-117, 2015. https://journals.tubitak.gov.tr/cgi/viewcontent.cgi ?article=2946&context=elektrik
[24] Hertono G., Ubadah., and Handari B., “The Modification of Hybrid Method of Ant Colony Optimization, Particle Swarm Optimization and 3- OPT Algorithm in Traveling Salesman Problem,” in Proceedings of the International Conference on Mathematics: Pure, Applied and Computation, Surabaya, pp. 1-8, 2018. DOI: 10.1088/1742- 6596/974/1/012032
[25] Hijazi M., Zeki A., and Ismail A., “Utilizing Artificial Bee Colony Algorithm as Feature Selection Method in Arabic Text Classification,” The International Arab Journal of Information Technology, vol. 20, no. 3A, pp. 536-547, 2023. https://doi.org/10.34028/iajit/20/3A/11
[26] Hore S., Chatterjee A., and Dewanji A., “Improving Variable Neighborhood Search to Solve the Traveling Salesman Problem,” Applied Soft Computing, vol. 68, pp. 83-91, 2018. https://doi.org/10.1016/j.asoc.2018.03.048
[27] Ismail A., “Domino Algorithm: A Novel Constructive Heuristics for Traveling Salesman Problem,” in Proceedings of the 11th International Seminar on Industrial Engineering and Management, Technology and Innovation Challenges towards Industry, Makasar, pp. 1-10, 2019. DOI:10.1088/1757-899X/528/1/012043
[28] Izzo D., Getzner I., Hennes D., and Simoes L., “Evolving Solutions to TSP Variants for Active Space Debris Removal,” in Proceedings of the Annual Conference on Genetic and Evolutionary Computation, Madrid, pp. 1207-1214 2015. https://dl.acm.org/doi/10.1145/2739480.2754727
[29] Jones T., “Crossover, Macromutation, and Population-Based Search,” in Proceedings of the 6th International Conference on Genetic Algorithms, Pittsburgh, pp. 73-80, 1995. https://dl.acm.org/doi/10.5555/645514.657932
[30] Kanna S., Sivakumar K., and Lingaraj N., “Development of Deer Hunting Linked Earthworm Optimization Algorithm for Solving A Novel Crossover based Discrete Artificial Algae Algorithm for Solving Traveling ... 951 Large Scale Traveling Salesman Problem,” Knowledge-Based Systems, vol. 227, pp. 107199, 2021. https://doi.org/10.1016/j.knosys.2021.107199
[31] Karaboga D. and Gorkemli B., “A Combinatorial Artificial Bee Colony Algorithm for Traveling Salesman Problem,” in Proceedings of the International Symposium on Innovations in Intelligent Systems and Applications, Istanbul, pp. 50-53, 2011. DOI: 10.1109/INISTA.2011.5946125
[32] Khan I. and Maiti M., “A Swap Sequence Based Artificial Bee Colony Algorithm for Traveling Salesman Problem,” Swarm and Evolutionary Computation, vol. 44, pp. 428-438, 2019. https://doi.org/10.1016/j.swevo.2018.05.006
[33] Kiran M., Iscan H., and Gunduz M., “The Analysis of Discrete Artificial Bee Colony Algorithm with Neighborhood Operator on Traveling Salesman Problem,” Neural Computing and Applications, vol. 23, no. 1, pp. 9-21, 2013. https://link.springer.com/article/10.1007/s00521- 011-0794-0
[34] Kumar M. and Dhillon J., “Hybrid Artificial Algae Algorithm for Economic Load Dispatch,” Applied Soft Computing, vol. 71, pp. 89-109, 2018. https://doi.org/10.1016/j.asoc.2018.06.035
[35] Lipowski A. and Lipowska D., “Roulette-Wheel Selection via Stochastic Acceptance,” Physica A: Statistical Mechanics and its Applications, vol. 391, no. 6, pp. 2193-2196, 2012. https://doi.org/10.1016/j.physa.2011.12.004
[36] Liu F. and Zeng G., “Study of Genetic Algorithm with Reinforcement Learning to Solve the TSP,” Expert Systems with Applications, vol. 36, no. 3, pp. 6995-7001, 2009. https://doi.org/10.1016/j.eswa.2008.08.026
[37] Lopez-Ibanez M. and Blum C., “Beam-ACO for the Travelling Salesman Problem with Time Windows,” Computers and Operations Research, vol. 37, no. 9, pp. 1570-1583, 2010. https://doi.org/10.1016/j.cor.2009.11.015
[38] Mahi M., Baykan O., and Kodaz H., “A New Hybrid Method Based on Particle Swarm Optimization, Ant Colony Optimization and 3- Opt Algorithms for Traveling Salesman Problem,” Applied Soft Computing, vol. 30, pp. 484-490, 2015. https://doi.org/10.1016/j.asoc.2015.01.068
[39] Mavrovouniotis M. and Yang S., “Ant Colony Optimization with Immigrants Schemes for the Dynamic Travelling Salesman Problem with Traffic Factors,” Applied Soft Computing, vol. 13, no. 10, pp. 4023-4037, 2013. https://doi.org/10.1016/j.asoc.2013.05.022
[40] Odili J., Kahar M., and Anwar S., “African Buffalo Optimization: A Swarm-Intelligence Technique,” Procedia Computer Science, vol. 76, pp. 443-448, 2015. https://doi.org/10.1016/j.procs.2015.12.291
[41] Odili J., Kahar M., Anwar S., and Azrag M., “A Comparative Study of African Buffalo Optimization and Randomized Insertion Algorithm for Asymmetric Travelling Salesman’s Problem,” in Proceedings of the 4th International Conference on Software Engineering and Computer Systems, Kuantan, pp. 90-95, 2015. DOI: 10.1109/ICSECS.2015.7333089
[42] Osaba E., Del Ser J., Sadollah A., Bilbao M., and Camacho D., “A Discrete Water Cycle Algorithm for Solving the Symmetric and Asymmetric Traveling Salesman Problem,” Applied Soft Computing, vol. 71, pp. 277-290, 2018. https://doi.org/10.1016/j.asoc.2018.06.047
[43] Pandiri V. and Singh A., “A Hyper-Heuristic Based Artificial Bee Colony Algorithm for k- Interconnected Multi-Depot Multi-Traveling Salesman Problem,” Information Sciences, vol. 463-464, pp. 261-281, 2018. https://doi.org/10.1016/j.ins.2018.06.027
[44] Pedro O., Saldanha R., and Camargo R., “A Tabu Search Approach for the Prize Collecting Traveling Salesman Problem,” Electronic Notes in Discrete Mathematics, vol. 41, pp. 261-268, 2013. https://doi.org/10.1016/j.endm.2013.05.101
[45] Reinelt G., “TSPLIB-A Traveling Salesman Problem Library,” ORSA Journal on Computing, vol. 3, no. 4, pp. 376-384, 1991. https://pubsonline.informs.org/doi/10.1287/ijoc.3.4.376
[46] Rokbani N., Kromer P., Twir I., and Alimi A., “A New Hybrid Gravitational Particle Swarm Optimisation-ACO with Local Search Mechanism, PSOGSA-ACO-Ls for TSP,” International Journal of Intelligent Engineering Informatics, vol. 7, no. 4, pp. 384-398, 2019. https://doi.org/10.1504/IJIEI.2019.101565
[47] Rokbani N., Kumar R., Abraham A., Alimi A., Long H., Priyadarshini I., and Son L., “Bi- Heuristic Ant Colony Optimization-based Approaches for Traveling Salesman Problem,” Soft Computing, vol. 25, pp. 3775-3794, 2021. https://www.softcomputing.net/soft2021.pdf
[48] Saraei M., Analouei R., and Mansouri P., “Solving of Travelling Salesman Problem Using Firefly Algorithm with Greedy Approach,” Cumhuriyet University Faculty of Science Journal, vol. 36, no. 6, pp. 267-273, 2015. https://arastirmax.com/sites/default/files/filefield _paths/5000142870-5000238948-1-pb.pdf
[49] Shang G., Lei Z., Fengting Z., and Chunxian Z., “Solving Traveling Salesman Problem by Ant Colony Optimization Algorithm with Association Rule,” in Proceedings of the 3rd International Conference on Natural Computation, Haikou, pp. 693-698, 2007. DOI: 10.1109/ICNC.2007.675
[50] Snyder L. and Daskin M., “A Random-Key 952 The International Arab Journal of Information Technology, Vol. 21, No. 5, September 2024 Genetic Algorithm for the Generalized Traveling Salesman Problem,” European Journal of Operational Research, vol. 174, no. 1, pp. 38-53, 2006. https://doi.org/10.1016/j.ejor.2004.09.057
[51] Taillard E. and Helsgaun K., “POPMUSIC for the Travelling Salesman Problem,” European Journal of Operational Research, vol. 272, no. 2, pp. 420- 429, 2019. https://doi.org/10.1016/j.ejor.2018.06.039
[52] Ulder N., Aarts E., Bandelt H., Van Laarhoven P., and Pesch E., “Genetic Local Search Algorithms for the Traveling Salesman Problem,” in Proceedings of the International Conference on Parallel Problem Solving from Nature, Dortmund, pp. 109-116, 1990. https://link.springer.com/chapter/10.1007/BFb0029740
[53] Uymaz S., Tezel G., and Yel E., “Artificial Algae Algorithm for Nonlinear Global Optimization,” Applied Soft Computing, vol. 31, pp. 153-171, 2015. https://doi.org/10.1016/j.asoc.2015.03.003
[54] Uymaz S., Tezel G., and Yel E., “Artificial Algae Algorithm with Multi-Light Source for Numerical Optimization and Applications,” Biosystems, vol. 138, pp. 25-38, 2015. https://doi.org/10.1016/j.biosystems.2015.11.004
[55] Wang J., Ersoy O., He M., and Wang F., “Multi- Offspring Genetic Algorithm and its Application to the Traveling Salesman Problem,” Applied Soft Computing, vol. 43, pp. 415-423, 2016. https://doi.org/10.1016/j.asoc.2016.02.021
[56] Yang J., Shi X., Marchese M., and Liang Y., “An Ant Colony Optimization Method for Generalized TSP Problem,” Progress in Natural Science, vol. 18, no. 11, pp. 1417-1422, 2008. https://doi.org/10.1016/j.pnsc.2008.03.028
[57] Zhang X., Wu C., Li J., Wang X., Yang Z., Lee J., and Jung K., “Binary Artificial Algae Algorithm for Multidimensional Knapsack Problems,” Applied Soft Computing, vol. 43, pp. 583-595, 2016. https://doi.org/10.1016/j.asoc.2016.02.027
[58] Zhong Y., Lin J., Wang L., and Zhang H., “Discrete Comprehensive Learning Particle Swarm Optimization Algorithm with Metropolis Acceptance Criterion for Traveling Salesman Problem,” Swarm and Evolutionary Computation, vol. 42, pp. 77-88, 2018. https://doi.org/10.1016/j.swevo.2018.02.017
[59] Zhou X., Gao D., Yang C., and Gui W., “Discrete State Transition Algorithm for Unconstrained Integer Optimization Problems,” Neurocomputing, vol. 173, pp. 864-874, 2016. https://doi.org/10.1016/j.neucom.2015.08.041