Optimizing Genetic Algorithm by Implementation of An Enhanced Selection Operator

Mohammed BinJubier - Engineering Faculty, Sana’a Community College, Sana’a, Yemen
Mohd Arfian Ismail - Faculty of Computing, Universiti Malaysia Pahang Al-Sultan Abdullah, Pekan, Pahang, Malaysia
Muhaini Othman - Faculty of Computer Science and Information Technology, Universiti Tun Hussein Onn Malaysia, Parit Raja, Johor, Malaysia
Shahreen Kasim - Faculty of Computer Science and Information Technology, Universiti Tun Hussein Onn Malaysia, Parit Raja, Johor, Malaysia
Hidra Amnur - Department of Information Technology, Politeknik Negeri Padang, Padang, Indonesia


Citation Format:



DOI: http://dx.doi.org/10.62527/joiv.8.3-2.3449

Abstract


The Traveling Salesman Problem (TSP) represents an extensively researched challenge in combinatorial optimization. Genetic Algorithms (GAs), recognized for their nature-inspired approach, stand as potent heuristics for resolving combinatorial optimization problems. Nevertheless, GA exhibits inherent deficiencies, notably premature convergence, which diminishes population diversity and consequential inefficiencies in computational processes. Such drawbacks may result in protracted operations and potential misallocation of computational resources, particularly when confronting intricate NP-hard optimization problems. To address these challenges, the current study underscores the pivotal role of the selection operator in ameliorating GA efficiency. The proposed methodology introduces a novel parameter operator within the Stochastic Universal Selection (SUS) framework, aimed at constricting the search space and optimizing genetic operators for parent selection. This innovative approach concentrates on selecting individuals based on their fitness scores, thereby mitigating challenges associated with population sorting and individual ranking while concurrently alleviating computational complexity. Experimental results robustly validate the efficacy of the proposed approach in enhancing both solution quality and computational efficiency, thereby positioning it as a noteworthy contribution to the domain of combinatorial optimization.

Keywords


Genetic algorithm; traveling salesman problem; selection operator

Full Text:

PDF

References


R. W. Dewantoro, P. Sihombing, and others, “The combination of ant colony optimiza-tion (ACO) and tabu search (TS) algorithm to solve the traveling salesman problem (TSP),” in 2019 3rd International Conference on Electrical, Telecommunication and Computer Engineering (ELTICOM), 2019, pp. 160–164.

Y. Shi and Y. Zhang, “The neural network methods for solving Traveling Salesman Prob-lem,” Procedia Comput Sci, vol. 199, pp. 681–686, 2022, doi: 10.1016/j.procs.2022.01.084.

S. Prayudani, A. Hizriadi, E. B. Nababan, and S. Suwilo, “Analysis effect of tournament se-lection on genetic algorithm performance in traveling salesman problem (TSP),” in Journal of Physics: Conference Series, 2020, p. 12131.

H. R. Er and N. Erdogan, “Parallel Genetic Algorithm to Solve Traveling Salesman Prob-lem on MapReduce Framework using Hadoop Cluster,” Jscse, vol. 3, no. 3, pp. 380–386, 2013, doi:10.7321/jscse.v3.n3.57.

A. R. S. K. Hegde, “A Novel Method to Solve Travelling Salesman Problem Using Sequen-tial Constructive Crossover Using Map/Reduce Framework,” International Journal of Science and Research (IJSR), vol. 4, no. 5, pp. 1362–1367, 2015.

S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimed Tools Appl, vol. 80, no. 5, pp. 8091–8126, Feb. 2021, doi: 10.1007/s11042-020-10139-6.

Z. Drezner and T. D. Drezner, “Biologically Inspired Parent Selection in Genetic Algo-rithms,” Ann Oper Res, vol. 287, no. 1, pp. 161–183, Apr. 2020, doi: 10.1007/s10479-019-03343-7.

C. Nilsson, “Heuristics for the traveling salesman problem,” 2003. doi:10.1016/S0305-0548(98)00085-9.

G. Steven, “Evolutionary algorithms for single and multicriteria design optimization. A. Osyczka. Springer Verlag, Berlin, 2002, ISBN 3-7908-1418-01,” Structural and Multidisciplinary Optimization, vol. 24, no. 1, pp. 88–89, Aug. 2002, doi: 10.1007/s00158-002-0218-y.

A. Hussain and Y. S. Muhammad, “Trade-off between exploration and exploitation with genetic algorithm using a novel selection operator,” Complex & intelligent systems, vol. 6, no. 1, pp. 1–14, 2020.

Z. H. Ahmed, “Adaptive Sequential Constructive Crossover Operator in a Genetic Algo-rithm for Solving the Traveling Salesman Problem,” International Journal of Advanced Computer Science and Applications, vol. 11, no. 2, 2020, doi: 10.14569/ijacsa.2020.0110275.

G. Reinhelt, “TSPLIB: a library of sample instances for the TSP (and related problems) from various sources and of various types,” 2014.

C.-W. Tsai, S.-P. Tseng, M.-C. Chiang, C.-S. Yang, and T.-P. Hong, “A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case,” The Scientific World Jour-nal, vol. 2014, pp. 1–14, 2014, doi: 10.1155/2014/178621.

Z. H. Ahmed, “Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator,” Int J Biom Bioinformatics, vol. 3, no. 6, pp. 96–105, 2010.

A. Aranganayaki, “Reduce Total Distance and Time Using Genetic Algorithm in Traveling Salesman Problem,” International Journal of Computer Science & Engineering Technology, vol. 5, no. 2229–3345, p. 4, 2014.

K. Rani and V. Kumar, “Solving travelling Salesman problem using genetic algorithm based on heuristic crossover and mutation operator,” Int J Res Eng Technol, vol. 2, no. 2, pp. 27–34, 2014.

A. Phu-ang, “The new technique based on the galaxy based search algorithm for solving the symmetric travelling salesman problem,” in 2018 International ECTI Northern Section Con-ference on Electrical, Electronics, Computer and Telecommunications Engineering (ECTI-NCON), 2018, pp. 131–134. doi: 10.1109/ecti-ncon.2018.8378296.

Y. Gao and J. Ye, “An Improved Genetic Algorithm Based on Normal Distribution for Solving the Traveling Salesman Problem,” in 2018 International Conference on Virtual Reality and Intelligent Systems (ICVRIS), 2018, pp. 360–362. doi: 10.1109/icvris.2018.00094.

M. L. Islam, D. Pandhare, A. Makhthedar, and N. Shaikh, “A Heuristic Approach for Opti-mizing Travel Planning Using Genetics Algorithm,” International Journal of Research in Engi-neering and Technology eISSN: 2319-1163, pISSN: 2321, vol. 7308, no. 01, 2014.

A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015.

X. Liu, M. Zhang, Z. Bai, L. Wang, W. Du, and Y. Wang, “Function Call Flow based Fitness Function Design in Evolutionary Testing,” in 14th Asia-Pacific Software Engineering Conference (APSEC’07), 2007, pp. 57–64. doi: 10.1109/aspec.2007.13.

A. Rao and S. K. Hegde, “Literature Survey On Travelling Salesman Problem Using Genet-ic Algorithms,” 2015.

S. S. Juneja, P. Saraswat, K. Singh, J. Sharma, R. Majumdar, and S. Chowdhary, “Travelling Salesman Problem Optimization Using Genetic Algorithm,” in 2019 Amity International Con-ference on Artificial Intelligence (AICAI), 2019, pp. 264–268. doi:10.1109/aicai.2019.8701246.

M. S. H. Kalathingal, S. Basak, and J. Mitra, “Artificial neural network modeling and genetic algorithm optimization of process parameters in fluidized bed drying of green tea leaves,” J Food Process Eng, vol. 43, no. 1, p. e13128, Jan. 2020, doi: 10.1111/jfpe.13128.

I. Jannoud, Y. Jaradat, M. Z. Masoud, A. Manasrah, and M. Alia, “The Role of Genetic Al-gorithm Selection Operators in Extending WSN Stability Period: A Comparative Study,” Electronics (Basel), vol. 11, no. 1, p. 28, Dec. 2021, doi: 10.3390/electronics11010028.

S. N. Sivanandam and S. N. Deepa, Introduction to Genetic Algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. doi:10.1007/978-3-540-73190-0.

J. Too and A. R. Abdullah, “A new and fast rival genetic algorithm for feature selection,” J Supercomput, vol. 77, no. 3, pp. 2844–2874, Mar. 2021, doi: 10.1007/s11227-020-03378-9.

M. Noraini and J. Geraghty, “Genetic algorithm performance with different selection strategies in solving TSP,” in World Congress on Engineering, 2011, pp. 4–9.

M. Gen and R. Cheng, Genetic Algorithms and Engineering Optimization, vol. 7. Wiley, 1999. doi: 10.1002/9780470172261.

S. Mirjalili, “Genetic Algorithm,” in Evolutionary Algorithms and Neural Networks: Theory and Applications, Springer, 2019, pp. 43–55. doi: 10.1007/978-3-319-93025-1_4.

D. E. Goldberg and K. Deb, “A Comparative Analysis of Selection Schemes Used in Ge-netic Algorithms,” in Foundations of genetic algorithms, vol. 1, 1991, pp. 69–93.

K. Asghari, M. Masdari, F. S. Gharehchopogh, and R. Saneifard, “Multi-swarm and chaotic whale-particle swarm optimization algorithm with a selection method based on roulette wheel,” Expert Syst, vol. 38, no. 8, p. e12779, Dec. 2021, doi: 10.1111/exsy.12779.

T. Blickle and L. Thiele, “A Comparison of Selection Schemes used in Genetic Algo-rithms,” Evol Comput, vol. 2, no. 11, pp. 311–347, 1995, doi: 10.1162/evco.1996.4.4.361.

M. Mitchell, “Genetic algorithms: An overview,” Complexity, vol. 1, no. 1, pp. 31–39, Sep. 1995, doi: 10.1002/cplx.6130010108.

J. E. Baker, “Reducing bias and inefficiency in the selection algorithm,” in Proceedings of the second international conference on genetic algorithms, 1987, pp. 14–21.

T. Harada and E. Alba, “Parallel Genetic Algorithms,” ACM Comput Surv, vol. 53, no. 4, pp. 1–39, Jul. 2021, doi: 10.1145/3400031.

H. M. Pandey, “Performance Evaluation of Selection Methods of Genetic Algorithm and Network Security Concerns,” Procedia Comput Sci, vol. 78, no. December 2015, pp. 13–18, 2016, doi:10.1016/j.procs.2016.02.004.

M. Abbasi, M. Rafiee, M. R. Khosravi, A. Jolfaei, V. G. Menon, and J. M. Koushyar, “An efficient parallel genetic algorithm solution for vehicle routing problem in cloud imple-mentation of the intelligent transportation systems,” Journal of Cloud Computing, vol. 9, no. 1, p. 6, Dec. 2020, doi: 10.1186/s13677-020-0157-4.

Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996. doi:10.1007/978-3-662-03315-9.

A. Plichta, T. Gaciarz, B. Baranowski, and S. Szominski, “Implementation Of The Genetic Algorithm By Means Of CUDA Technology Involved In Travelling Salesman Problem,” in ECMS 2014 Proceedings edited by: Flaminio Squazzoni, Fabio Baronio, Claudia Archetti, Marco Castellani, 2014, pp. 475–479. doi:10.7148/2014-0475.

S. García, D. Molina, M. Lozano, and F. Herrera, “A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 Special Session on Real Parameter Optimization,” Journal of Heuristics, vol. 15, no. 6, pp. 617–644, Dec. 2009, doi: 10.1007/s10732-008-9080-4.

K. Moorthy, K. Mohd Daud, S. R. Arokiasamy, and M. R. I. Tomal, “Hybrid Biometric Au-thentication for Automatic Teller Machine,” International Journal of Software Engineering and Computer Systems, vol. 10, no. 1, pp. 32–39, Sep. 2024, doi:10.15282/ijsecs.10.1.2024.3.0121.

Y. Zhong, K. M. Daud, A. N. B. M. Nor, R. A. Ikuesan, and K. Moorthy, “Offline Handwrit-ten Chinese Character Using Convolutional Neural Network: State-of-the-Art Methods,” Journal of Advanced Computational Intelligence and Intelligent Informatics, vol. 27, no. 4, pp. 567–575, 2023, doi: 10.20965/jaciii.2023.p0567.

A. Nuhu, A. F. Mat Raffei, M. F. Ab Razak, and Abubakar Ahmad, “Distributed Denial of Service Attack Detection in IoT Networks using Deep Learning and Feature Fusion: A Re-view,” Mesopotamian Journal of CyberSecurity, vol. 4, no. 1, pp. 47–70, Apr. 2024, doi:10.58496/mjcs/2024/004.

M. I. Jaya and M. F. Ab. Razak, “Dynamic Ransomware Detection for Windows Platform Using Machine Learning Classifiers,” JOIV : International Journal on Informatics Visualization, vol. 6, no. 2–2, p. 469, Aug. 2022, doi: 10.30630/joiv.6.2-2.1093.

N. S. Nordin and M. A. Ismail, “A hybridization of butterfly optimization algorithm and harmony search for fuzzy modelling in phishing attack detection,” Neural Comput Appl, vol. 35, no. 7, pp. 5501–5512, Mar. 2023, doi: 10.1007/S00521-022-07957-0/tables/6.

E. H. Tusher, M. A. Ismail, M. A. Rahman, A. H. Alenezi, and M. Uddin, “Email Spam: A Comprehensive Review of Optimize Detection Methods, Challenges, and Open Research Problems,” IEEE Access, vol. 12, pp. 143627–143657, 2024, doi:10.1109/access.2024.3467996.

M. A. I. Rohismadi, A. F. M. Raffei, N. S. A. Zulkifli, M. H. Ithnin, and S. F. Othman, “An Automated Strabismus Classification Using Machine Learning Algorithm for Binocular Vi-sion Management System,” in 2023 IEEE 8th International Conference On Software Engineering and Computer Systems (ICSECS), 2023, pp. 487–492. doi: 10.1109/icsecs58457.2023.10256291.

A. F. Z. Abidin et al., “Adaboost-multilayer perceptron to predict the student’s perfor-mance in software engineering,” Bulletin of Electrical Engineering and Informatics, vol. 8, no. 4, pp. 1556–1562, 2019, doi:10.11591/eei.v8i4.1432.

A. Feizollah, N. B. Anuar, R. Mehdi, A. Firdaus, and A. Sulaiman, “Understanding COVID-19 Halal Vaccination Discourse on Facebook and Twitter Using Aspect-Based Sentiment Analysis and Text Emotion Analysis,” Int J Environ Res Public Health, vol. 19, no. 10, 2022, doi: 10.3390/ijerph19106269.

N. F. Idris, M. A. Ismail, M. I. M. Jaya, A. O. Ibrahim, A. W. Abulfaraj, and F. Binzagr, “Stacking with Recursive Feature Elimination-Isolation Forest for classification of diabetes mellitus,” PLOS ONE, vol. 19, no. 5, p. e0302595, May 2024, doi:10.1371/journal.pone.0302595.