NEWS

CSGA: A DUAL POPULATION GENETIC ALGORITHM BASED ON MEXICAN CAVEFISH GENETIC DIVERSITY


(Received: 11-Feb.-2024, Revised: 5-Apr.-2024 , Accepted: 27-Apr.-2024)
Genetic algorithms (GAs) are search algorithms based on population genetics and natural-selection concepts. Maintaining population variety in GAs is critical for ensuring global exploration and mitigating the risks of premature convergence. Rapid convergence to local optima is one such challenge in the application of genetic algorithms. To address this issue, we provide Cave-Surface GA (CSGA), an alternative method based on the Dual Population GA and inspired by the genetic variety observed in Mexican cavefish. Through inter-population cross-breeding, CSGA increases diversity via a secondary population (cave population) and facilitates the exchange of information between populations, effectively counteracting premature convergence. Several experiments are carried out utilizing benchmark instances of the Traveling Salesman Problem (TSP) obtained from TSPLIB, a well-known TSP problem library. Our experimental results over many TSP instances show that CSGA outperforms both classic GAs and other GAs that use diversity-preservation techniques, such as Multipopulation GA (MPGA). CSGA has the potential to give promising solutions to challenging optimization issues like TSP.

[1] W. F. Abd-El-Wahed, A. A. Mousa and M. A. El-Shorbagy, "Integrating Particle Swarm Optimization with Genetic Algorithms for Solving Nonlinear Optimization Problems," Journal of Computational and Applied Mathematics, vol. 235, no. 5, pp. 1446-1453, 2011.

[2] N. Al-Milli, A. Hudaib and N. Obeid, "Population Diversity Control of Genetic Algorithm Using a Novel Injection Method for Bankruptcy Prediction Problem," Mathematics, vol. 9, no. 8, p. 823, 2021.

[3] M. A. Albadr, S. Tiun, M. Ayob and F. Al-Dhief, "Genetic Algorithm Based on Natural Selection Theory for Optimization Problems," Symmetry, vol. 12, no. 11, p. 1758, 2020.

[4] E. Alkafaween and A. B. A. Hassanat, "Improving TSP Solutions Using GA with a New Hybrid Mutation Based on Knowledge and Randomness," Communications-Scientific Letters of the University of Zilina, vol. 22, no. 3, pp. 128-139, 2020.

[5] E. Alkafaween, A. B. A. Hassanat and S. Tarawneh, "Improving Initial Population for Genetic Algorithm Using the Multi Linear Regression Based Technique (MLRBT)," Communications-Scientific Letters of the University of Zilina, vol. 23, no. 1, pp. E1-E10, 2021.

[6] E. O. Alkafaween, "Novel Methods for Enhancing the Performance of Genetic Algorithms," arXiv preprint, arXiv: 1801.02827, 2018.

[7] E. Alkafaween, S. Elmougy, E. Essa and A. Hassanat, "An Efficiency Boost for Genetic Algorithms: Initializing the GA with the Iterative Approximate Method for Optimizing the Traveling Salesman Problem - Experimental Insights," Applied Sciences, vol. 14, no. 8, p. 3151, 2024.

[8] E. Alkafaween, S. Elmougy, E. Essa, S. Mnasri, A. S. Tarawneh and A. Hassanat, "IAM-TSP: Iterative Approximate Methods for Solving the Traveling Salesman Problem," Int. J. of Advanced Computer Science and Applications (IJACSA), vol. 14, no. 11, DOI: 10.14569/IJACSA.2023.0141143, 2023.

[9] M. Bradic, P. Beerli, F. J. García-de León, S. Esquivel-Bobadilla and R. L. Borowsky, "Gene Flow and Population Structure in the Mexican Blind Cavefish Complex (Astyanax Mexicanus)," BMC Evolutionary Biology, vol. 12, Article no. 9, pp. 1-17, 2012.

[10] C.-M. Chen, S. Lv, J. Ning and J. Ming-Tai Wu, "A Genetic Algorithm for the Waitable Time-varying Multi-depot Green Vehicle Routing Problem," Symmetry, vol. 15, no. 1, p. 124, 2023.

[11] E. C. Osuna, Theoretical and Empirical Evaluation of Diversity-preserving Mechanisms in Evolutionary Algorithms: On the Rigorous Runtime Analysis of Diversity-preserving Mechanisms in Evolutionary Algorithms, PhD Thesis, University of Sheffield, 2018.

[12] K. A. De Jong, "An Analysis of the Behavior of a Class of Genetic Adaptive Systems," Technical Report, University of Michigan, 1975.

[13] M. Dong and Y. Wu, "Dynamic Crossover and Mutation Genetic Algorithm Based on Expansion Sampling," Proc. of the Int. Conf. on Artificial Intelligence and Computational Intelligence (AICI 2009), Proceedings 1, pp. 141-149, Shanghai, China, Springer, November 7-8, 2009.

[14] H. Du, Z. Wang, W. Zhan and J. Guo, "Elitism and Distance Strategy for Selection of Evolutionary Algorithms," IEEE Access, vol. 6, pp. 44531-44541, 2018.

[15] Y. Elipot, H. Hinaux, J. Callebert and S. Rétaux, "Evolutionary Shift from Fighting to Foraging in Blind Cavefish through Changes in the Serotonin Network," Current Biology, vol. 23, no. 1, pp. 1-10, 2013.

[16] Y. Fu, G. Tian, Z. Li and Z. Wang, "Parallel Machine Scheduling with Dynamic Resource Allocation via a Master-Slave Genetic Algorithm," IEEJ Transactions on Electrical and Electronic Engineering, vol. 13, no. 5, pp. 748-756, 2018.

[17] J. B. Gross, "The Complex Origin of Astyanax Cavefish," BMC Evolutionary Biology, vol. 12, no. 1, pp. 1-12, 2012.

[18] D. Gupta and S Ghafar, "An Overview of Methods Maintaining Diversity in Genetic Algorithms," Int. J. of Emerging Technology and Advanced Engineering, vol. 2, no. 5, pp. 56-60, 2012.

[19] S. Han and L. Xiao, "An Improved Adaptive Genetic Algorithm," Proc. of the 2022 Int. Conf. on Information Technology in Education and Management Engineering (ITEME2022), SHS Web of Conf., vol. 140, p. 01044, EDP Sciences, 2022.

[20] E.-ul Haq, I. Ahmad, A. Hussain and I. M. Almanjahie, "A Novel Selection Approach for Genetic Algorithms for Global Optimization of Multimodal Continuous Functions," Computational Intelligence and Neuroscience, vol. 2019, Article ID 8640218, pp. 1-14, 2019.

[21] A. Hassanat et al., "Choosing Mutation and Crossover Ratios for Genetic Algorithms: A Review with a New Dynamic Approach," Information, vol. 10, no. 12, p. 390, 2019.

[22] A. B. Hassanat et al., "An Improved Genetic Algorithm with a New Initialization Mechanism Based on Regression Techniques," Information, vol. 9, no. 7, p.167, 2018.

[23] A. B. A. Hassanat, "Enhancing Genetic Algorithms Using Multi Mutations: Experimental Results on the Travelling Salesman Problem," Int. Journal of Computer Science and Information Security, vol. 14, no. 7, p. 785, 2016.

[24] A. B. A Hassanat and E. Alkafaween, "On Enhancing Genetic Algorithms Using New Crossovers," Int. Journal of Computer Applications in Technology, vol. 55, no. 3, pp. 202-212, 2017.

[25] J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence, no. 53, ISBN: 9780262581110, MIT Press, 1992.

[26] 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.

[27] S. Katoch, S. S. Chauhan and V. Kumar, "A Review on Genetic Algorithm: Past, Present and Future," Multimedia Tools and Applications, vol. 80, pp. 8091-8126, 2021.

[28] B. Koohestani, "A Crossover Operator for Improving the Efficiency of Permutation-based Genetic Algorithms," Expert Systems with Applications, vol. 151, p. 113381, DOI: 10.1016/j.eswa.2020.113381, 2020.

[29] L. Kou, J. Wan, H. Liu, W. Ke, H. Li, J. Chen, Z. Yu and Q. Yuan, "Optimized Design of Patrol Path for Offshore Wind Farms Based on Genetic Algorithm and Particle Swarm Optimization with Traveling Salesman Problem," Concurrency and Computation: Practice and Experience, vol. 36, no. 2, p. e7907, DOI: 10.1002/cpe.7907, 2023.

[30] S. Mahmoudinazlou and C. Kwon, "A Hybrid Genetic Algorithm for the Min-max Multiple Traveling Salesman Problem," Computers & Operations Research, vol. 162, p. 106455, DOI: 10.1016/j.cor.2023.106455, 2024.

[31] S. Malik and S. Wadhwa, "Preventing Premature Convergence in Genetic Algorithm Using DGCA and Elitist Technique," Int. Journal of Advanced Research in Computer Science and Software Engineering, vol. 4, no. 6, pp. 410-418, 2014.

[32] E. Simona Nicoară, "Mechanisms to Avoid the Premature Convergence of Genetic Algorithms," Petroleum-Gas University of Ploiesti Bulletin, Mathematics-Informatics-Physics Series, vol. 61, no. 1, 2009.

[33] R. Ohira, M. S. Islam, J. Jo and B. Stantic, "LCS Based Diversity Maintenance in Adaptive Genetic Algorithms," Proc. of the 16th Australasian Conf. on Data Mining (AusDM 2018), pp. 56-68, Bahrurst, NSW, Australia, November 28-30, 2018, Springer, 2019.

[34] E. C. Osuna and D. Sudholt, "On the Runtime Analysis of the Clearing Diversity-preserving Mechanism," Evolutionary Computation, vol. 27, no. 3, pp. 403-433, 2019.

[35] H. M. Pandey, A. Chaudhary and D. Mehrotra, "A Comparative Review of Approaches to Prevent Premature Convergence in GA," Applied Soft Computing, vol. 24, pp. 1047-1077, 2014.

[36] T. Park and K. Ryel Ryu, "A Dual Population Genetic Algorithm with Evolving Diversity," Proc. of the 2007 IEEE Congress on Evolutionary Computation, pp. 3516-3522, Singapore, 2007.

[37] P. V. Paul et al., "A New Population Seeding Technique for Permutation-coded Genetic Algorithm: Service Transfer Approach," Journal of Computational Science, vol. 5, no. 2, pp. 277-297, 2014.

[38] B. R. Rajakumar and A. George, "APOGA: An Adaptive Population Pool Size Based Genetic Algorithm," AASRI Procedia, vol. 4, pp. 288-296, DOI: 10.1016/j.aasri.2013.10.043, 2013.

[39] G. Reinelt, "TSBLIB, 1996" ftp to softlib.rice.edu, 2023.

[40] X. Shi, W. Long, Y. Li, D. Deng and Y Wei, "Research on the Performance of Multi-population Genetic Algorithms with Different Complex Network Structures," Soft Computing, vol. 24, pp. 13441-13459, 2020.

[41] E. Shojaedini, M. Majd and R. Safabakhsh, "Novel Adaptive Genetic Algorithm Sample Consensus," Applied Soft Computing, vol. 77, pp. 635-642, 2019.

[42] M. Srinivas and L. M. Patnaik, "Adaptive Probabilities of Crossover and Mutation in GeneticAlgorithms," IEEE Transactions on Systems, Man and Cybernetics, vol. 24, no. 4, pp. 656-667, 1994.

[43] B. A. Stahl et al., "Manipulation of Gene Function in Mexican Cavefish," Journal of Visualized Experiments (JoVE), vol. 146, p. e59093, 2019.

[44] P. A. Vikhar, "Evolutionary Algorithms: A Critical Review and Its Future Prospects," Proc. of the 2016 Int. Conf. on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC), pp. 261-265, Jalgaon, India, 2016.

[45] D. Whitley, S. Rana and R. B. Heckendorn, "The Island Model Genetic Algorithm: On Separability, Population Size and Convergence," J. of Computing and Inf. Technolo., vol. 7, no. 1, pp. 33-47, 1999.

[46] Z. Wu, "A Comparative Study of Solving Traveling Salesman Problem with Genetic Algorithm, Ant Colony Algorithm and Particle Swarm Optimization," Proc. of the 2020 2nd Int. Conf. on Robotics Systems and Vehicle Technology, pp. 95-99, Xiamen, China, 2020.

[47] W. Xu et al., "Optimization Approaches for Solving Production Scheduling Problem: A Brief Overview and a Case Study for Hybrid Flow Shop Using Genetic Algorithms," Advances in Production Engineering & Management, vol. 17, no. 1, pp. 45-56, 2022.

[48] Y. Xue, H. Zhu, J. Liang and A. Sşowik, "Adaptive Crossover Operator Based Multi-objective Binary Genetic Algorithm for Feature Selection in Classification," Knowledge-based Systems, vol. 227, p. 107218, DOI: 10.1016/j.knosys.2021.107218, 2021.

[49] S. Yang, "PDGA: The Primal-dual Genetic Algorithm," Design and application of Hybrid Intelligent Systems, pp. 214-223, Chapter in Book: Design and Application of Hybrid Intelligent Systems, IOS Press, 2003.

[50] P. Zhang et al., "A Genetic Algorithm with Jumping Gene and Heuristic Operators for Traveling Salesman Problem," Applied Soft Computing, vol. 127, p. 109339, DOI: 10.1016/j.asoc.2022.109339, 2022.

[51] G. Zhou et al., "Location Optimization of Electric Vehicle Charging Stations: Based on Cost Model and Genetic Algorithm," Energy, vol. 247, p. 123437, DOI: 10.1016/ j.energy.2022.123437, 2022.