Diversity Control in Evolutionary Computation using Asynchronous Dual-Populations with Search Space Partitioning
Keywords:
Diversity;, exploration-exploitation tradeoff;, evolutionary algorithms;, heuristic initialization;, taxonomy;Abstract
Diversity control is vital for effective global optimization using evolutionary computation (EC) techniques. This paper classifies the various diversity control policies in the EC literature. Many research works have attributed the high risk of premature convergence to sub-optimal solutions to the poor exploration capabilities resulting from diversity collapse. Also, excessive cost of convergence to optimal solution has been linked to the poor exploitation capabilities necessary to focus the search. To address this exploration-exploitation trade-off, this paper deploys diversity control policies that ensure sustained exploration of the search space without compromising effective exploitation of its promising regions. First, a dual-pool EC algorithm that facilitates a temporal evolution-diversification strategy is proposed. Then a quasi-random heuristic initialisation based on search space partitioning (SSP) is introduced to ensure uniform sampling of the initial search space. Second, for the diversity measurement, a robust convergence detection mechanism that combines a spatial diversity measure; and a population evolvability measure is utilised. It was found that the proposed algorithm needed a pool size of only 50 samples to converge to optimal solutions of a variety of global optimization benchmarks. Overall, the proposed algorithm yields a 33.34% reduction in the cost incurred by a standard EC algorithm. The outcome justifies the efficacy of effective diversity control on solving complex global optimization landscapes.
References
Alba, E. and Tomassini, M. (2002). Parallelism and Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation, 6: 443-462.
Bashir, H. A. and Neville, R. S. (2012). Convergence Measurement in Evolutionary Computation Using Price's Theorem. IEEE Congress on Evolutionary Computation (CEC), 1961-1968.
Bassett, J. K.; M. A. Potter and K. A. De Jong. (2004). Looking Under the EA Hood with Price’s Equation. Genetic and Evolutionary Computation – GECCO 2004. Springer Berlin / Heidelberg, 3102: 914-922.
Blum, C.; M. Aguilera; A. Roli and M. Sampels. (2008). Hybrid Metaheuristics: An Introduction. Hybrid Metaheuristics. Springer Berlin / Heidelberg, 114: 1-30.
Blum, C.; J. Puchinger; G. Raidl and A. Roli. (2011). Hybrid Metaheuristics in Combinatorial Optimization: A Survey. Applied Soft Computing, 11:4135-4151.
Branke, J.; A. Eiben; T. Back; M. Schoenauer and H. P. Schwefel. (1998). Creating Robust Solutions by Means of Evolutionary Algorithms. Parallel Problem Solving from Nature PPSN V. Springer Berlin / Heidelberg, 1498: 119-128.
Branke, J.; T. Kau; I. Schmidt and H. Schmeck. (2000). A Multi-Population Approach to Dynamic Optimization Problems. In: Parmee I.C. (eds) Evolutionary Design and Manufacture. Springer, London, UK. 299-308.
Cheng, S.; Y. Shi; Q. Qin; Q. Zhang and R. Bai. (2015). Population Diversity Maintenance in Brain Storm Optimization Algorithm. Journal of Artificial Intelligence and Soft Computing Research (JAISCR). DE GRUYTER. 4(2):83-97.
Cobb, H. G. and Grefenstette, J. (1993). Genetic Algorithms for Tracking Changing Environments. Proceedings of the Fifth International Conference on Genetic Algorithms, Morgan Kaufmann. 523-530, San Francisco, United States.
Corriveau, G.; R. Guilbault; A. Tahan and R. Sabourin. (2012). Review and Study of Genotypic Diversity Measures for Real-Coded Representations. IEEE Transactions on Evolutionary Computation, 16: 695-710.
Dang, M. P.; T. P. Dao; N. L. Chau and H. G. Le. (2019). Effective Hybrid Algorithm of Taguchi Method, FEM, RSM, and Teaching Learning-Based Optimization for Multiobjective Optimization Design of a Compliant Rotary Positioning Stage for Nanoindentation Tester. Mathematical Problems in Engineering, 2019. Hindawi.
De Jong, K. (1975). An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Doctoral Dissertation: University of Michigan.
de-Melo, V. and Botazzo-Delbem, A. C. (2012). Investigating Smart Sampling as a Population Initialization Method for Differential Evolution in Continuous Problems. Information Sciences, 193 (1): 36-53.
Eiben, A. E.; R. Hinterding and Z. Michalewicz. (1999). Parameter Control in Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation, 3:124-141.
Eshelman, L. and Schaffer, D. (1991). Preventing Premature Convergence in Genetic Algorithms by Preventing Incest. Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann. 115-122, San Francisco, United States.
Fleming, P. J. and Purshouse, R. C. (2002). Evolutionary Algorithms in Control Systems Engineering: A Survey. Control Engineering Practice, 10:1223-1241.
Fogel, D. B. (1997). Evolutionary Computation: A New Transactions. IEEE Transactions on Evolutionary Computation, 1:1-2.
Frank, S. (1997). The Price Equation, Fisher's Fundamental Theorem, Kin Selection, and Causal Analysis. Evolution, 51:1712-1729.
Garcia, S.; D. Molina; M. Lozano and F. Herrera. (2009). 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, 15: 617-644.
Goldberg, D. E. and Holland, J. H. (1988). Genetic Algorithms and Machine Learning. Machine Learning, 3:95-99.
Gong, G.; Q. Deng; R. Chiong; X. Gong and H. Huang. (2019). An effective memetic algorithm for multi-objective job-shop scheduling, Knowledge-Based Systems, 182. Elsevier.
Greenhalgh, D. and Marshall, S. (2000). Convergence Criteria for Genetic Algorithms. SIAM J. Comput., 30:269-282.
Herrera, F. and Lozano, M. (1996). Adaptation of Genetic Algorithm Parameters Based on Fuzzy Logic Controllers. Genetic Algorithms and Soft Computing: Springer-Verlag, Spain.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. Michigan: The University of Michigan Press.
Hollander, M. and Wolfe, D. (1999). Nonparametric Statistical Methods, 2nd Edition: Wiley-Interscience.
Jih-Yiing, L. and Ying-Ping, C. (2011). Analysis on the Collaboration Between Global Search and Local Search in Memetic Computation. IEEE Transactions on Evolutionary Computation, 15: 608-623.
Joines, J. and Kay, M. (2003). Utilizing Hybrid Genetic Algorithms Evolutionary Optimization. Springer US, 48: 199-228.
Li, C.; S. Yang; T. T. Nguyen; E. L. Yu; X. Yao; Y. Jin; H. G. Beyer and P. N. Suganthan. (2008). Benchmark Generator for CEC'2009 Competition on Dynamic Optimization. Computer Science, University of Leicester, U.K.
Liang, J. J.; P. N. Suganthan and K. Deb. (2005). Novel Composition Test Functions for Numerical Global Optimization. IEEE Proceedings on Swarm Intelligence Symposium, SIS 2005. 68-75.
Liu, J.; H. A. Abbass and K. C. Tan. (2018). Evolutionary Computation and Complex Network. Technology & Engineering. Springer International Publishing, Spain.
Lozano, M.; F. Herrera and J. Cano. (2008). Replacement Strategies to Preserve Useful Diversity in Steady-State Genetic Algorithms. Inf. Sci., 178:4421-4433.
Lunacek, M. and Whitley, D. (2006). The Dispersion Metric and the CMA Evolution Strategy. Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, Seattle, Washington, 477–484, USA: ACM.
Maaranen, H.; K. Miettinen and M. M. Makela. (2004). Quasi-random Initial Population for Genetic Algorithms. Comput. Math. Appl., 47:1885-1895.
McGinley, B.; J. Maher; C. O'Riordan and F. Morgan. (2011). Maintaining Healthy Population Diversity Using Adaptive Crossover, Mutation, and Selection. IEEE Transactions on Evolutionary Computation, 15:692-714.
Michalewicz, Z. (1994). Genetic algorithms + data structures = evolution programs (2nd, extended ed.): Springer-Verlag New York, Inc.
Molina, D.; M. Lozano; C. G. Martinez and F. Herrera. (2010). Memetic algorithms for continuous optimisation based on local search chains. Evol. Comput., 18:27-63.
Morrison, R. W. (2003). Dispersion-based Population Initialization. Proceedings of the 2003 International Conference on Genetic and Evolutionary Computation: PartI Chicago, IL, USA: Springer-Verlag.
Moscato, P. (1999). Memetic Algorithms: A Short Introduction. New Ideas in Optimization: McGraw-Hill Ltd., UK, 219-234.
Muhlenbein, H. and Schlierkamp-Voosen, D. (1993). Predictive Models for the Breeder Genetic Algorithm I - Continuous Parameter Optimization. Evol. Comput., 1: 25-49.
Pengfei, G.; W. Xuezhi and H. Yingshi. (2010). The Enhanced Genetic Algorithms for the Optimization Design. 3rd International Conference on Biomedical Engineering and Informatics (BMEI), Yantai, China. 2990-2994. IEEE.
Potter, M. A.; J. K. Bassett and K. A. De Jong. (2003). Visualizing Evolvability with Price's Equation. Congress on Evolutionary Computation, CEC '03, 4: 2785-2790.
Rahnamayan, S.; H. R. Tizhoosh and M. M. Salama. (2007). A Novel Population Initialization Method for Accelerating Evolutionary Algorithms. Computers & Mathematics with Applications, 53:1605-1614.
Reeves, C. R. (1993). Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publishing, Oxford, UK.
Salomon, R. (1996). Re-evaluating Genetic Algorithm Performance under Coordinate Rotation of Benchmark Functions. A Survey of Some Theoretical and Practical Aspects of Genetic Algorithms. BioSystems, 39: 263-278.
Shetti, B. (2019). Curse of Dimensionality. Available online at: https://builtin.com/data-science/curse-dimensionality. Accessed on September 25, 2019.
Shir, O. M. (2012). Niching in Evolutionary Algorithms. Handbook of Natural Computing. Springer, Berlin, Heidelberg.
Segura, C.; A. Hernández-Aguirre; F. Luna and E. Alba. (2017). Improving Diversity in Evolutionary Algorithms: New Best Solutions for Frequency Assignment. IEEE Transactions on Evolutionary Computation, 21 (4): 539 - 553.
Sharma, H.; J. B. Chand and K. V. Arya. (2013). Diversity Measures in Artificial Bee Colony. Proceedings of Seventh International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA 2012). Advances in Intelligent Systems and Computing. 201 (1): 299-314.
Squillero, G. and Tonda, A. (2016). Promoting Diversity in Evolutionary Algorithms: An Updated Bibliography. Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion (GECCO '16). Denver, Colorado. 943-944. ACM. USA.
Taejin, P. and Kwang, R. R. (2010). A Dual-Population Genetic Algorithm for Adaptive Diversity Control. IEEE Transactions on Evolutionary Computation, 14:865-884.
Tenne, Y. and Armfield, S. W. (2005). Efficiently Minimizing Expensive Cost Functions with a Hybrid Evolutionary Algorithm using Clustering and a Derivative-free Optimizer: Preliminary Results. IEEE Congress on Evolutionary Computation, 3:1937-1944.
Thierens, D. (1998). Selection Schemes, Elitist Recombination, and Selection Intensity. Proceedings of 7th International Conference on Genetic Algorithms San Francisco, CA: Morgan Kaufmann, 152-159.
Tometzki, T. and Engell, S. (2011). Systematic Initialization Techniques for Hybrid Evolutionary Algorithms for Solving Two-Stage Stochastic Mixed-Integer Programs. IEEE Transactions on Evolutionary Computation, 15:196-214.
Tsutsui, S.; Y. Fujimoto and A. Ghosh. (1997). Forking Genetic Algorithms: GAs with Search Space Division Schemes. Evol. Comput., 5: 61-80.
Ursem, R. K. (1999). Multinational Evolutionary Algorithms. Proceedings of the 1999 Congress on Evolutionary Computation, CEC 99. 3:1640.
Wen, T. L.; W. S. Xiao; Q. H. Yong; F. L. Shu and Z. Jiang. (2010). A Hybrid Optimization Algorithm and Its Application for Conformal Array Pattern Synthesis. IEEE Transactions on Antennas and Propagation, 58:3401-3406.
Xianshun, C.; O. Yew-Soon; L. Meng-Hiot and K. C. Tan. (2011). A Multi-Facet Survey on Memetic Computation. IEEE Transactions on Evolutionary Computation, 15: 591-607.
Xu, W.; C. Chen; S. Ding and P. M. Pardalos. (2019). A bi-objective dynamic collaborative task assignment under uncertainty using modified MOEA/D with heuristic initialization. Expert Systems with Applications, Elsevier, 140 (1): 112-144.
Yi, J.; W. Ling and C. Li. (2008). A Hybrid Dynamical Evolutionary Algorithm for Classification Rule Discovery. Second International Symposium on Intelligent Information Technology Application, IITA '08, 76-79.
Additional Files
Published
Issue
Section
License
Copyright (c) 2020 Nigerian Journal of Technological Development
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
In accordance with the Copyright Act of 1976, which became effective January 1, 1978, the following statement signed by each author must accompany the manuscript submitted: "I, the undersigned author, transfer all copyright ownership of the manuscript referenced above to the Nigerian Journal of Technological Development, in the event the work is published. I warrant that the article is original, does not infringe upon any copyright or other proprietary right of any third party, is not under consideration by another journal, and has not been published previously. I have reviewed and approve the submitted version of the manuscript and agree to its publication in the Nigerian Journal of Technological Development." A copyright transfer form should be downloaded from the NJTD Website ( http://njtd.com.ng/index.php/njtd). Author(s) will be consulted, whenever possible, regarding republication of material. All authors must have access to the data presented and the authors and sponsor (if applicable) must agree to share original data with the editor if requested.
