EXPERIMENTAL ANALYSIS OF MULTINATIONAL GENETIC ALGORITHM AND ITS MODIFICATIONS
DOI:
https://doi.org/10.15588/1607-3274-2021-2-8Keywords:
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.
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
How to Cite
Issue
Section
License
Copyright (c) 2021 Н. М. Гулаєва , С. А. Яремко
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
