EXPERIMENTAL ANALYSIS OF MULTINATIONAL GENETIC ALGORITHM AND ITS MODIFICATIONS

Authors

  • N. M. Gulayeva National University of “Kyiv-Mohyla Academy”
  • S. A. Yaremko National University of “Kyiv-Mohyla Academy”

DOI:

https://doi.org/10.15588/1607-3274-2021-2-8

Keywords:

multimodal optimization problem, niching genetic algorithms, multinational genetic algorithm, hill-valley function, genetic algorithm convergence, real peak ratio, fake peak ratio.

Abstract

Context. Niching genetic algorithms are one of the most popular approaches to solve multimodal optimization problems. When classifying niching genetic algorithms it is possible to select algorithms explicitly analyzing topography of fitness function landscape; multinational genetic algorithm is one of the earliest examples of these algorithms.

Objective. Development and analysis of the multinational genetic algorithm and its modifications to find all maxima of a multimodal function.

Method. Experimental analysis of algorithms is carried out. Numerous runs of algorithms on well-known test problems are conducted and performance criteria are computed, namely, the percentage of convergence, real (global, local) and fake peak ratios; note that peak rations are computed only in case of algorithm convergence.

Results. Software implementation of a multinational genetic algorithm has been developed and experimental tuning of its parameters has been carried out. Two modifications of hill-valley function used for determining the relative position of individuals have been proposed. Experimental analysis of the multinational genetic algorithm with classic hill-valley function and with its modifications has been carried out.

Conclusions. The scientific novelty of the study is that hill-valley function modifications producing less number of wrong identifications of basins of attraction in comparison with classic hill-valley function are proposed. Using these modifications yields to performance improvements of the multinational genetic algorithm for a number of test functions; for other test functions improvement of the quality criteria is accompanied by the decrease of the convergence percentage. In general, the convergence percentage and the quality criterion values demonstrated by the algorithm studied are insufficient for practical use in comparison with other known algorithms. At the same time using modified hill-valley functions as a post-processing step for other niching algorithms seems to be a promising improvement of performance of these algorithms.

Author Biographies

N. M. Gulayeva, National University of “Kyiv-Mohyla Academy”

PhD, Associate Professor at the Department of Informatics.

S. A. Yaremko, National University of “Kyiv-Mohyla Academy”

Ms. Sc., Assistant Lecturer at the Department of Informatics.

References

Li X., Epitropakis M. G., Deb K. et al. Seeking Multiple Solutions: An Updated Survey on Niching Methods and Their Applications, IEEE Transactions on Evolutionary Computation, 2017, Vol. 21, No. 4, pp. 518–538. DOI: 10.1109/TEVC.2016.2638437.

Shen Z.-H., Zhao Y.-K., Wu W.-W. Niche Pseudo-Parallel Genetic Algorithms for Path Optimization of Autonomous Mobile Robot, Journal of Shanghai University (English Edition), 2006, Vol. 10, No. 5, pp. 449–453. DOI: 10.1007/s11741-006-0089-3.

Preuss M., Liapis A., Togelius J. Searching for Good and Diverse Game Levels, IEEE Conference on Computational Intelligence and Games, Dortmund, 26–29 August, 2014: proceedings. Piscataway, IEEE, 2014, pp. 1–8. DOI: 10.1109/CIG.2014.6932908.

Chica M., Barranquero J., Kajdanowicz T. et al. Multimodal Optimization: an Effective Framework for Model Calibration, Information Sciences, 2017, Vol. 375, pp. 79–97. DOI: 10.2139/ssrn.2828069.

Leoshchenko S. D., Oliinyk A. O., Subbotin S. A. et al. Modification and Parallelization of Genetic Algorithm For Synthesis of Artificial Neural Networks, Radio Electronics, Computer Science, Control, 2019, No. 4, pp. 68–82. DOI: 10.15588/1607-3274-2019-4-7.

Glybovets M. M., Gulayeva N. M., Butenko S., Pardalos P. M., Shylo V. (eds.). Evolutionary Multimodal Optimization, Optimization methods and applications. In honor of Ivan V. Sergienko’s 80th birthday. Cham, Springer, 2017, pp. 129– 173. DOI: 10.1007/978-3-319-68640-0_8. (Series “Springer Optimization and Its Applications”)

Preuss M. Multimodal Optimization by Means of Evolutionary Algorithms. Berlin, Springer, 2015, 175 p. DOI: 10.1007/978-3-319-07407-8.

Törn A., Viitanen S., Floudas C. A., Pardalos P. M. (eds.), Topographical Global Optimization, Recent Advances in Global Optimization. Princeton University Press, 1992, pp. 384–398. DOI: 10.1515/9781400862528.384.

Wessing S., Preuss M. The True Destination of EGO is Multi-Local Optimization, IEEE Latin American Conference on Computational Intelligence (LA-CCI), Arequipa, 8–10 November, 2017, proceedings. Piscataway, IEEE, 2017, pp. 1–6. DOI: 10.1109/LA-CCI.2017.8285677.

Preuss M. Niching the CMA-ES via Nearest-Better Clustering, Genetic and Evolutionary Computation Conference (GECCO), Portland, 7–11 July, 2010: proceedings. New York, ACM, 2010, pp. 1711–1718. DOI: 10.1145/1830761.1830793.

Preuss M., Di Chio C., Agapitos A., Cagnoni S. et al. (eds.)Improved Topological Niching for Real-Valued Global Optimization, Applications of Evolutionary Computation (EvoApplications), Málaga, 11–13 April, 2012: proceedings. Berlin, Springer, 2012, Vol. 7248, pp. 386–395. DOI: 10.1007/978-3-642-29178-4_39. (Series “Lecture Notes in Computer Science”)

Li Y., Yu J., Takagi H. Niche Method Complementing the Nearest-Better Clustering, IEEE Symposium Series on Computational Intelligence (SSCI), Xiamen, 6–9 December, 2019: proceedings. Piscataway, IEEE, 2019, pp. 3065–3071. DOI: 10.1109/SSCI44817.2019.9002742.

Luo W. Qiao Y., Lin X. et al. Hybridizing Niching, Particle Swarm Optimization, and Evolution Strategy for Multimodal Optimization, IEEE Transactions on Cybernetics: early access article, 2020. DOI: 10.1109/TCYB.2020.3032995.

Ursem R. K. Multinational Evolutionary Algorithms / R. K. Ursem // Congress on Evolutionary Computation (CEC99), Washington, 6–9 July, 1999, proceedings. Piscataway, IEEE, 1999, Vol. 3, pp. 1633–1640. DOI: 10.1109/CEC.1999.785470.

Ursem R. K. Multinational GAs: Multimodal Optimization Techniques in Dynamic Environments, Genetic and Evolutionary Computation Conference (GECCO), Las Vegas, 8– 12 July, 2000, proceedings. San Francisco, Morgan Kaufmann, 2000, Vol. 1, pp. 19–26.

Stoean C., Preuss M., Stoean R. et al. Disburdening the Species Conservation Evolutionary Algorithm of Arguing with Radii, Genetic and Evolutionary Computation Conference (GECCO), London, 7–11 July, 2007: proceedings. New York, ACM, 2007, pp. 1420–1427. DOI: 10.1145/1276958.1277220.

Stoean C., Preuss M., Stoean R. et al. Multimodal Optimization by Means of a Topological Species Conservation Algorithm, IEEE Transactions on Evolutionary Computation, 2010, Vol. 14, No. 6, pp. 842–864. DOI: 10.1109/TEVC.2010.2041668.

Cioppa A. D., Marcelli A., Napoli P. Speciation in Evolutionary Algorithms: Adaptive Species Discovery, Genetic and Evolutionary Computation Conference (GECCO), Dublin, 12–16 July, 2011: proceedings. New York, ACM, 2011, pp. 1053–1060. DOI: 10.1145/2001576.2001719.

Li L., Tang K. History-Based Topological Speciation for Multimodal Optimization, IEEE Transactions on Evolutionary Computation, 2015, Vol. 19, No. 1, pp. 136–150. DOI: 10.1109/TEVC.2014.2306677.

Maree S. C., Alderliesten T., Thierens D. et al. Real-Valued Evolutionary Multi-Modal Optimization Driven by HillValley Clustering, Genetic and Evolutionary Computation Conference (GECCO), Kyoto, 15–19 July, 2018: proceedings. New York, ACM, 2018, pp. 857–864. DOI: 10.1145/3205455.3205477.

Maree S. C., Alderliesten T., Bosman P. A. N. Benchmarking HillVallEA for the GECCO 2019 Competition on Multimodal Optimization [Electronic resource], 2019. Access mode: https://arxiv.org/abs/1907.10988.

Navarro R., Kim C. H. Niching Multimodal Landscapes Faster Yet Effectively: VMO and HillVallEA Benefit Together, Mathematics, 2020, Vol. 8, No. 5 (665). DOI: 10.3390/math8050665.

Navarro R., Kim C. H. Improved Population Control for More Efficient Multimodal Optimizers, Congreso Internacional de Innovación y Tendencias en Ingeniería (CONIITI), Bogotá, 30 September – 2 October, 2020: proceedings. Piscataway, IEEE, 2020, pp. 1–6. DOI: 10.1109/CONIITI51147.2020.9240365.

Ahrari A., Deb K., Preuss M. Multimodal Optimization by Covariance Matrix Self-Adaptation Evolution Strategy with Repelling Subpopulations, Evolutionary Computation, 2017. Vol. 25, No. 3, pp. 439–471. DOI: 10.1162/evco_a_00182.

Ahrari A., Deb K., Preuss M. Benchmarking Covariance Matrix Self Adaption Evolution Strategy with Repelling Subpopulations for GECCO 2017 Competition on Multimodal Optimization : technical report : 2017014, Computational Optimization and Innovation Laboratory (COIN), Michigan State University. Michigan, 2017, 5 p.

Jamil M., Yang X.-S. A Literature Survey of Benchmark Functions for Global Optimization Problems / M. Jamil, // International Journal of Mathematical Modelling and Numerical Optimisation, 2013, Vol. 4, No. 2, pp. 150–194. DOI: 10.1504/IJMMNO.2013.055204.

Li X., Engelbrecht A., Epitropakis M. G. Benchmark Functions for CEC’2013 Special Session and Competition on Niching Methods for Multimodal Function Optimization : report, Evolutionary Computation and Machine Learning Group, RMIT University. Melbourne, 2013, 10 p.

Shylo V. P., Glybovets M. M., Gulayeva N. M. et al.Genetic Algorithm of Tournament Crowding Based on Gaussian Mutation, Cybernetics and Systems Analysis, 2020, Vol. 56, No. 2, pp. 231–242. DOI: 10.1007/s10559-020-00239-4.

Li J.-P., Balazs M. E., Parks G. T. et al. A Species Conserving Genetic Algorithm for Multimodal Function Optimization, Evolutionary Computation, 2002, Vol. 10, No. 3, pp. 207–234. DOI: 10.1162/106365602760234081.

Yao J., Kharma N., Grogono P. Bi-Objective Multipopulation Genetic Algorithm for Multimodal Function Optimization, IEEE Transactions on Evolutionary Computation, 2010, Vol. 14, No. 1, pp. 80–102. DOI: 10.1109/TEVC.2009.2017517.

Downloads

Published

2021-07-03

How to Cite

Gulayeva, N. M., & Yaremko, S. A. (2021). EXPERIMENTAL ANALYSIS OF MULTINATIONAL GENETIC ALGORITHM AND ITS MODIFICATIONS . Radio Electronics, Computer Science, Control, (2), 71–83. https://doi.org/10.15588/1607-3274-2021-2-8

Issue

Section

Neuroinformatics and intelligent systems