The ``one-fifth rule'' with rollbacks for self-adjustment of the population size in the $(1 + (\lambda,\lambda))$ genetic algorithm

A. O. Bassin ; M. V. Buzdalov ; A. A. Shalyto

Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 4, pp. 488-508.

Résumé

Self-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the $(1 + (\lambda,\lambda))$ genetic algorithm, where adaptation of the population size helps to achieve the linear running time on the OneMax problem. However, on problems which interfere with the assumptions behind the self-adjustment procedure, its usage can lead to the performance degradation. In particular, this is the case with the “one-fifth rule” on problems with weak fitness-distance correlation. We propose a modification of the “one-fifth rule” in order to have less negative impact on the performance in the cases where the original rule is destructive. Our modification, while still yielding a provable linear runtime on OneMax, shows better results on linear function with random weights, as well as on random satisfiable MAX-3SAT problems.

Détail

Keywords: parameter adaptation, linear functions
Mots-clés : $(1 + (\lambda,\lambda))$ GA, MAX-3SAT.

Bibliographie

[1] J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan, 1975, 211 pp. | MR

[2] I. Rechenberg, Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution, Fromman-Holzboorg Verlag, Stuttgart, 1973

[3] H. P. Schwefel, Binäre Optimierung durch somatische Mutation, Tech. Rep., Technical University of Berlin and Medical University of Hannover, May 1975

[4] L. J. Fogel, “Autonomous automata”, Industrial Research, 4 (1962), 14–19

[5] J. R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, USA, 1992 | Zbl

[6] R. C. Eberhart, J. Kennedy, “A new optimizer using particle swarm theory”, Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 1995, 39–43 | DOI

[7] M. Dorigo, L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem”, IEEE Transactions on Evolutionary Computation, 1:1 (1997), 53–66 | DOI

[8] R. Poli, J. Kennedy, T. Blackwell, “Particle swarm optimization, An overview”, Swarm Intelligence, 1 (2007), 33–57 | DOI

[9] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by simulated annealing”, Science, 220:4598 (1983), 671–680 | DOI | MR | Zbl

[10] J. M. Bishop, “Stochastic searching networks”, Proceedings of 1st IEEE Conference on Artificial Neural Networks, 1989, 329–331

[11] R. Storn, K. Price, “Differential evolution — a simple and efficient heuristic for global optimization over continuous spaces”, Journal of Global Optimization, 11:4 (1997), 341–359 | DOI | MR | Zbl

[12] M. Pelikan, D. E. Goldberg, E. Cantu-Paz, “Linkage problem, distribution estimation, and bayesian networks”, Evolutionary Computation, 8:3 (2000), 311–340 | DOI | MR

[13] B. Doerr, M. S. Krejca, “Significance-based estimation-of-distribution algorithms”, Proceedings of Genetic and Evolutionary Computation Conference, 2018, 1483–1490 | DOI | MR

[14] S. Luke, Essentials of Metaheuristics, Lulu, 2009, 253 pp. | MR

[15] A. Orlov, V. V. Kureichik, A. Glushchenko, “Hybrid genetic algorithm for cutting stock and packaging problems”, Proceedings of East-West Design Test Symposium, IEEE, 2016

[16] L. A. Gladkov, N. V. Gladkova, S. A. Gromov, “Hybrid models of solving optimization tasks on the basis of integrating evolutionary design and multiagent technologies”, Proceedings of Computer Science Online Conference, Advances in Intelligent Systems and Computing, 985, 2019, 381–391 | DOI

[17] E. V. Kuliev, A. N. Dukkardt, V. V. Kureychik, A. A. Legebokov, “Neighborhood research approach in swarm intelligence for solving the optimization problems”, Proceedings of East-West Design Test Symposium, IEEE, 2014

[18] E. V. Kuliev, V. V. Kureichik, I. O. Kursitys, “Decision making in VLSI components placement problem based on grey wolf optimization”, Proceedings of East-West Design Test Symposium, IEEE, 2019

[19] V. V. Kureichik, D. V. Zaruba, “Combined approach to place electronic computing equipment circuit elements”, Proceedings of East-West Design Test Symposium, IEEE, 2015

[20] L. A. Gladkov, N. V. Gladkova, S. Leiba, “Electronic computing equipment schemes elements placement based on hybrid intelligence approach”, Proceedings of Computer Science Online Conference, Advances in Intelligent Systems and Computing, 348, 2015, 35–44 | DOI

[21] M. Semenkina, “Parallel version of self-configuring genetic algorithm application in spacecraft control system design”, Proceedings of Genetic and Evolutionary Computation Conference Companion, 2013, 1751–1752

[22] D. Chivilikhin, V. Ulyantsev, A. Shalyto, “Modified ant colony algorithm for constructingnite state machines from execution scenarios and temporal formulas”, Automation and Remote Control, 77:3 (2016), 473–484 | DOI | MR | Zbl

[23] C. M. Fonseca, P. J. Fleming, “Nonlinear system identification with multiobjective genetic algorithm”, Proceedings of the World Congress of the International Federation of Automatic Control, 1996, 187–192

[24] I. Buzhinsky, V. Ulyantsev, D. Chivilikhin, A. Shalyto, “Inducing finite state machines from training samples using ant colony optimization”, Journal of Computer and Systems Sciences International, 53:2 (2014), 256–266 | DOI | Zbl

[25] D. Chivilikhin, V. Ulyantsev, A. Shalyto, “Extended finite-state machine inference with parallel ant colony based algorithms”, International Student Workshop on Bioinspired Optimization Methods andeir Applications, 2014, 117–126

[26] D. Chivilikhin, V. Ulyantsev, A. Shalyto, “Combining exact and metaheuristic techniques for learning Extended finite state machines from test scenarios and temporal properties”, Proceedings of International Conference on Machine Learning and Applications, 2014, 350–355

[27] I. Buzhinsky, V. Ulyantsev, F. Tsarev, A. Shalyto, “Search-based construction of finite-state machines with real-valued actions: New representation model”, Proceedings of Genetic and Evolutionary Computation Conference Companion, 2013, 199–200

[28] S. El-Khatib, Y. Skobtsov, S. Rodzin, “Improved particle swarm medical image segmentation algorithm for decision making”, Intelligent Distributed Computing XIII, Studies in Computational Intelligence, 868, 2019, 437–442

[29] A. V. Eremeev, Y. V. Kovalenko, “Genetic algorithm with optimal recombination for the asymmetric travelling salesman problem”, LSSC 2017: Large-Scale Scientific Computing, Lecture Notes in Computer Science, 10665, 2017, 341–349 | DOI | MR

[30] A. V. Eremeev, Y. V. Kovalenko, “A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem”, Memetic Computing, 12:1 (2020), 23–36 | DOI | MR

[31] D. S. Sanches, D. Whitley, R. Tinos, “Improving an exact solver for the traveling salesman problem using partition crossover”, Proceedings of Genetic and Evolutionary Computation Conference, 2017, 337–344 | DOI | MR

[32] L. D. Whitley, F. Chicano, B. W. Goldman, “Gray box optimization for Mk landscapes (NK landscapes and MAX-kSAT)”, Evolutionary Computation, 24:3 (2016), 491–519 | DOI | MR

[33] A. Glotic, A. Zamuda, “Short-term combined economic and emission hydrothermal optimization by surrogate differential evolution”, Applied Energy, 141 (2015), 42–56 | DOI

[34] T. Liao, P. J. Egbelu, P. Chang, “Two hybrid differential evolution algorithms for optimal inbound and outbound truck sequencing in cross docking operations”, Applied Soft Computing, 12:11 (2012), 3683–3697 | DOI

[35] V. Feoktistov, S. Pietravalle, N. Heslot, “Optimal experimental design ofeld trials using differential evolution”, Proceedings of Congress on Evolutionary Computation, 2017, 1690–1696 | MR

[36] T. Bäck, D. B. Fogel, Z. Michalewicz (eds.), Evolutionary Computation, v. 1, Basic Algorithms and Operators, Institute of Physics Publishing, 2000, 339 pp. | MR

[37] J. J. Grefenstette, “Optimization of control parameters for genetic algorithms”, IEEE Transactions on Systems, Man, and Cybernetics, 16 (1986), 122–128 | DOI | MR

[38] H. Muhlenbein, “How genetic algorithms really work: Mutation and hillclimbing”, Parallel Problem Solving from Nature – PPSN II, Elsevier, 1992, 15–26

[39] A. E. Eiben, R. Hinterding, Z. Michalewicz, “Parameter control in evolutionary algorithms”, IEEE Transactions on Evolutionary Computation, 3:2 (1999), 124–141 | DOI

[40] V. Stanovov, S. Akhmedova, E. Semenkin, M. Semenkina, “Generalized Lehmer mean for success history based adaptive differential evolution”, Proceedings of International Joint Conference on Computational Intelligence, 2019, 93–100

[41] V. Stanovov, S. Akhmedova, E. Semenkin, “LSHADE algorithm with rank-based selective pressure strategy for solving CEC 2017 benchmark problems”, Proceedings of Congress on Evolutionary Computation, IEEE, 2018

[42] M. Semenkina, E. Semenkin, “Memetic self-configuring genetic programming for solving machine learning problems”, Proceedings of International Congress on Advanced Applied Informatics, 2015, 599–604

[43] M. Semenkina, S. Akhmedova, C. Brester, E. Semenkin, “Choice of spacecraft control contour variant with self-configuring stochastic algorithms of multi-criteria optimization”, Proceedings of International Conference on Informatics in Control, Automation and Robotics, 2016, 281–286 | DOI

[44] V. Stanovov, E. Semenkin, O. Semenkina, “Self-configuring hybrid evolutionary algorithm for fuzzy imbalanced classification with adaptive instance selection”, Journal of Artificial Intelligence and Soft Computing Research, 6:3 (2016), 173–188 | DOI

[45] N. Hansen, A. Ostermeier, “Completely derandomized self-adaptation in evolution strategies”, Evolutionary Computation, 9 (2001), 159–195 | DOI | MR

[46] R. Tanabe, A. Fukunaga, “Success-history based parameter adaptation for differential evolution”, Proceedings of IEEE Congress on Evolutionary Computation, 2013, 71–78

[47] R. Senkerik, M. Pluhacek, T. Kadavy, A. Zamuda, “Distance based parameter adaptation for success-history based differential evolution”, Swarm and Evolutionary Computation, 50 (2019) | DOI

[48] N. Dang, C. Doerr, “Hyper-parameter tuning for the $(1 + (\lambda,\lambda))$ GA”, Proceedings of Genetic and Evolutionary Computation Conference, 2019, 889–897 | DOI

[49] E. Ridge, D. Kudenko, “Tuning an algorithm using design of experiments”, Experimental Methods for the Analysis of Optimization Algorithms, eds. T. Bartz-Beielstein, M. Chiarandini, L. Paquete, M. Preuss, Springer, 2010, 265–286 | DOI | MR | Zbl

[50] M. López-Ibáñez, J. Dubois-Lacoste, L. P. Cáceres, T. Stützle, M. Birattari, “The irace package: Iterated racing for automatic algorithm configuration”, Operations Research Perspectives, 3 (2016), 43–58 | DOI | MR

[51] F. Hutter, H. H. Hoos, K. Leyton-Brown, “Sequential model-based optimization for general algorithm configuration”, Proceedings of Learning and Intelligent Optimization, Springer, 2011, 507–523 | DOI

[52] F. Hutter, H. H. Hoos, K. Leyton-Brown, T. Stutzle, “ParamILS: An automatic algorithm configuration framework”, Journal of Artificial Intelligence Research, 36 (2009), 267–306 | DOI | Zbl

[53] I. Wegener, “Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions”, Evolutionary Optimization, International Series in Operations Research Management Science, 48, 2003, 349–369 | DOI | MR

[54] A. Auger, B. Doerr, Theory of Randomized Search Heuristics: Foundations and Recent Developments, World Scientific Publishing Co., Inc., River Edge, NJ, USA, 2011 | MR | Zbl

[55] B. Doerr, F. Neumann (eds.), Theory of Evolutionary Computation — Recent Developments in Discrete Optimization, Springer, 2020 | Zbl

[56] V. G. Red'ko, Y. Tsoy, “Estimation of the evolution speed for the quasispecies model: Arbitrary alphabet case”, Artificial Intelligence and Soft Computing — ICAISC 2006, Lecture Notes in Computer Science, 4029, 2006, 460–469 | DOI

[57] V. G. Red'ko, O. P. Mosalov, D. V. Prokhorov, “Investigation of evolving populations of adaptive agents”, Artificial Neural Networks: Biological Inspirations — ICANN 2005, Lecture Notes in Computer Science, 3696, 2005, 337–342 | DOI

[58] A. Antamoshkin, E. Antamoshkin, E. Semenkin, “Local search efficiency when optimizing unimodal pseudoboolean functions”, Informatica, 9:3 (1998) | MR | Zbl

[59] A. N. Antamoshkin, V. N. Saraev, E. Semenkin, “Optimization of unimodal monotone pseudoboolean functions”, Kybernetika, 26:5 (1990), 432–442 | MR | Zbl

[60] S. Rodzin, L. Rodzina, “Theory of bionic optimization and its application to evolutionary synthesis of digital devices”, Proceedings of East-West Design Test Symposium, IEEE, 2014

[61] S. El-Khatib, Y. Skobtsov, S. Rodzin, S. Potryasaev, “Theoretical and experimental evaluation of PSO-K-Means algorithm for MRI images segmentation using drift theorem”, Proceedings of Computer Science Online Conference, Advances in Intelligent Systems and Computing, 985, 2019, 316–323 | DOI

[62] P. A. Borisovsky, A. V. Eremeev, “Comparing evolutionary algorithms to the (1+1)-EA”, Theoretical Computer Science, 403:1 (2008), 33–41 | DOI | MR | Zbl

[63] D. Corus, D. C. Dang, A. V. Eremeev, P. K. Lehre, “Level-based analysis of genetic algorithms and other search processes”, IEEE Transactions on Evolutionary Computation, 22:5 (2018), 707–719 | DOI

[64] A. V. Eremeev, “On non-elitist evolutionary algorithms optimizing fitness functions with a plateau”, Mathematical Optimization Theory and Operations Research, Lecture Notes in Computer Science, 12095, 2020, 329–342 | DOI | Zbl

[65] A. V. Eremeev, “On proportions of fit individuals in population of mutation-based evolutionary algorithm with tournament selection”, Evolutionary Computation, 26:2 (2018), 269–297 | DOI

[66] B. Doerr, C. Doerr, F. Ebel, “From black-box complexity to designing new genetic algorithms”, Theoretical Computer Science, 567 (2015), 87–104 | DOI | MR | Zbl

[67] B. Doerr, C. Doerr, F. Ebel, “Lessons from the black-box: Fast crossover-based genetic algorithms”, Proceedings of Genetic and Evolutionary Computation Conference, 2013, 781–788 | DOI | MR

[68] B. Doerr, C. Doerr, “Optimal static and self-adjusting parameter choices for the $(1 + (\lambda,\lambda))$ genetic algorithm”, Algorithmica, 80:5 (2018), 1658–1709 | DOI | MR | Zbl

[69] B. Doerr, C. Doerr, “Optimal parameter choices through self-adjustment: Applying the 1/5-th rule in discrete settings”, Proceedings of Genetic and Evolutionary Computation Conference, 2015, 1335–1342

[70] D. Antipov, M. Buzdalov, B. Doerr, “Fast mutation in crossover-based algorithms”, Proceedings of Genetic and Evolutionary Computation Conference, ACM, 2020, 1268–1276

[71] B. Goldman, W. Punch, “Parameter-less population pyramid”, Proceedings of Genetic and Evolutionary Computation Conference, 2014, 785–792

[72] M. Buzdalov, B. Doerr, “Runtime analysis of the $(1 + (\lambda,\lambda))$ genetic algorithm on random satisfiable 3-CNF formulas”, Proceedings of Genetic and Evolutionary Computation Conference, 2017, 1343–1350 | DOI | MR

[73] A. Gandomi, B. Goldman, “Parameter-less population pyramid for large-scale tower optimization”, Expert Systems with Applications, 96 (2018), 175–184 | DOI

[74] V. Mironovich, M. Buzdalov, “Hard test generation for maximum flow algorithms with the fast crossover-based evolutionary algorithm”, Proceedings of Genetic and Evolutionary Computation Conference Companion, 2015, 1229–1232

[75] M. A. Hevia Fajardo, D. Sudholt, “On the choice of the parameter control mechanism in the $(1 + (\lambda,\lambda))$ genetic algorithm”, Proceedings of Genetic and Evolutionary Computation Conference, 2020, 832–840

[76] A. Bassin, M. Buzdalov, “The 1/5-th rule with rollbacks: On self-adjustment of the population size in the $(1 + (\lambda,\lambda))$ GA”, Proceedings of Genetic and Evolutionary Computation Conference Companion, 2019, 277–278, arXiv: 1904.07284 | DOI | MR

[77] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the theory of NP-Completeness, W. H. Freeman Co., New York, NY, USA, 1979, 338 pp. | MR | Zbl

[78] D. Mitchell, B. Selman, H. Levesque, “Hard and easy distributions of SAT problems”, Proceedings of AAAI Conference on Artificial Intelligence, 1992, 459–465

[79] A. M. Sutton, F. Neumann, “Runtime analysis of evolutionary algorithms on randomly constructed high-density satisfiable 3-CNF formulas”, Proceedings of Parallel Problem Solving from Nature, Lecture Notes in Computer Science, 8672, 2014, 942–951 | DOI

[80] B. Doerr, F. Neumann, A. M. Sutton, “Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation”, Proceedings of Genetic and Evolutionary Computation Conference, 2015, 1415–1422 | MR

[81] B. Doerr, C. Doerr, “A tight runtime analysis of the $(1 + (\lambda,\lambda))$ genetic algorithm on OneMax”, Proceedings of Genetic and Evolutionary Computation Conference, 2015, 1423–1430 | MR

[82] E. Carvalho Pinto, C. Doerr, Towards a more practice-aware runtime analysis of evolutionary algorithms, 2018, arXiv: 1812.00493

[83] E. C. Pinto, C. Doerr, “A simple proof for the usefulness of crossover in black-box optimization”, Parallel Problem Solving from Nature PPSN XV, v. 2, Lecture Notes in Computer Science, 11102, 2018, 29–41 | DOI | MR

[84] B. Doerr, “Optimal parameter settings for the $(1 + (\lambda,\lambda))$ genetic algorithm”, Proceedings of Genetic and Evolutionary Computation Conference, 2016, 1107–1114 ; Full version arXiv: 1604.01088 | MR