From black-box complexity to designing new genetic algorithms. (English) Zbl 1314.68290
Summary: Black-box complexity theory recently produced several surprisingly fast black-box optimization algorithms. In this work, we exhibit one possible reason: These black-box algorithms often profit from solutions inferior to the previous-best. In contrast, evolutionary approaches guided by the “survival of the fittest” paradigm often ignore such solutions. We use this insight to design a new crossover-based genetic algorithm. It uses mutation with a higher-than-usual mutation probability to increase the exploration speed and crossover with the parent to repair losses incurred by the more aggressive mutation. A rigorous runtime analysis proves that our algorithm for many parameter settings is asymptotically faster on the OneMax test function class than all what is known for classic evolutionary algorithms. A fitness-dependent choice of the offspring population size provably reduces the expected runtime further to linear in the dimension. Our experimental analysis on several test function classes shows advantages already for small problem sizes and broad parameter ranges. Also, a simple self-adaptive choice of these parameters gives surprisingly good results.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
heuristic search; theory of randomized search heuristics; genetic algorithms; runtime analysis; black-box complexityReferences:
| [1] | Afshani, Peyman; Agrawal, Manindra; Doerr, Benjamin; Doerr, Carola; Green Larsen, Kasper; Mehlhorn, Kurt, The query complexity of finding a hidden permutation, (Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, Lecture Notes in Computer Science, vol. 8066 (2013), Springer), 1-11 · Zbl 1391.68044 |
| [2] | Anil, Gautham; Wiegand, R. Paul, Black-box search by elimination of fitness functions, (Proc. of the 10th ACM Workshop on Foundations of Genetic Algorithms. Proc. of the 10th ACM Workshop on Foundations of Genetic Algorithms, FOGA’09 (2009), ACM), 67-78 · Zbl 1369.68291 |
| [3] | Arabas, Jaroslaw; Michalewicz, Zbigniew; Mulawka, Jan, GAVaPS - a genetic algorithm with varying population size, (Proceedings of the First IEEE Conference on Evolutionary Computation. Proceedings of the First IEEE Conference on Evolutionary Computation, CEC’94 (1994), IEEE), 73-78 |
| [4] | Auger, Anne, Benchmarking the \((1 + 1)\) evolution strategy with one-fifth success rule on the BBOB-2009 function testbed, (Proc. of the 9th Annual Genetic and Evolutionary Computation Conference (GECCO’09) (Companion) (2009), ACM), 2447-2452 |
| [5] | Auger, Anne; Hansen, Nikolaus, Linear convergence on positively homogeneous functions of a comparison based step-size adaptive randomized search: the \((1 + 1)\) ES with generalized one-fifth success rule, CoRR, abs/1310.8397. Available online at · Zbl 1346.65030 |
| [6] | Bäck, Thomas, Optimal mutation rates in genetic search, (Proceedings of the 5th International Conference on Genetic Algorithms. Proceedings of the 5th International Conference on Genetic Algorithms, ICGA’93 (1993), Morgan Kaufmann), 2-8 |
| [7] | Beyer, Hans-Georg, Toward a theory of evolution strategies: on the benefit of sex - the \(( \mu / \mu, λ)\)-theory, Evol. Comput., 3, 81-111 (1995) |
| [8] | Beyer, Hans-Georg, The Theory of Evolution Strategies (2002), Springer Verlag: Springer Verlag Heidelberg · Zbl 0969.68177 |
| [9] | Böttcher, Süntje; Doerr, Benjamin; Neumann, Frank, Optimal fixed and adaptive mutation rates for the LeadingOnes problem, (Proc. of the 11th International Conference on Parallel Problem Solving from Nature. Proc. of the 11th International Conference on Parallel Problem Solving from Nature, PPSN’10. Proc. of the 11th International Conference on Parallel Problem Solving from Nature. Proc. of the 11th International Conference on Parallel Problem Solving from Nature, PPSN’10, Lecture Notes in Computer Science, vol. 6238 (2010), Springer), 1-10 |
| [10] | Devroye, Luc, The compound random search (1972), Purdue Univ.: Purdue Univ. West Lafayette, IN, Ph.D. dissertation |
| [11] | Doerr, Benjamin, Analyzing randomized search heuristics: tools from probability theory, (Auger, Anne; Doerr, Benjamin, Theory of Randomized Search Heuristics (2011), World Scientific Publishing), 1-20 · Zbl 1235.90185 |
| [12] | Doerr, Benjamin; Doerr, Carola; Ebel, Franziska, Lessons from the black-box: fast crossover-based genetic algorithms, (Proc. of the Annual Genetic and Evolutionary Computation Conference. Proc. of the Annual Genetic and Evolutionary Computation Conference, GECCO’13 (2013), ACM), 781-788 |
| [13] | Doerr, Benjamin; Winzen, Carola, Playing Mastermind with constant-size memory, Theory Comput. Syst., 55, 658-684 (2014) · Zbl 1319.68101 |
| [14] | Doerr, Benjamin; Winzen, Carola, Ranking-based black-box complexity, Algorithmica, 68, 571-609 (2014) · Zbl 1360.68505 |
| [15] | Doerr, Benjamin; Winzen, Carola, Reducing the arity in unbiased black-box complexity, Theoret. Comput. Sci., 545, 108-121 (2014) · Zbl 1360.68777 |
| [16] | Doerr, Benjamin; Johannsen, Daniel; Kötzing, Timo; Lehre, Per Kristian; Wagner, Markus; Winzen, Carola, Faster black-box algorithms through higher arity operators, (Proc. of the 11th ACM Workshop on Foundations of Genetic Algorithms. Proc. of the 11th ACM Workshop on Foundations of Genetic Algorithms, FOGA’11 (2011), ACM), 163-172 · Zbl 1369.68238 |
| [17] | Doerr, Benjamin; Kötzing, Timo; Lengler, Johannes; Winzen, Carola, Black-box complexities of combinatorial problems, Theoret. Comput. Sci., 471, 84-106 (2013) · Zbl 1259.68181 |
| [18] | Droste, Stefan; Jansen, Thomas; Wegener, Ingo, On the analysis of the \((1 + 1)\) evolutionary algorithm, Theoret. Comput. Sci., 276, 51-81 (2002) · Zbl 1002.68037 |
| [19] | Droste, Stefan; Jansen, Thomas; Wegener, Ingo, Upper and lower bounds for randomized search heuristics in black-box optimization, Theory Comput. Syst., 39, 525-544 (2006) · Zbl 1103.68115 |
| [20] | Droste, Stefan; Jansen, Thomas; Tinnefeld, Karsten; Wegener, Ingo, A new framework for the valuation of algorithms for black-box optimization, (Proc. of the 7th Workshop on Foundations of Genetic Algorithms. Proc. of the 7th Workshop on Foundations of Genetic Algorithms, FOGA’03 (2003), Morgan Kaufmann), 253-270 |
| [21] | Eiben, Agoston Endre; Smith, Jim E., Introduction to Evolutionary Computing (2003), Springer Verlag: Springer Verlag Heidelberg · Zbl 1028.68022 |
| [22] | Endre Eiben, Agoston; Hinterding, Robert; Michalewicz, Zbigniew, Parameter control in evolutionary algorithms, IEEE Trans. Evol. Comput., 3, 124-141 (1999) |
| [23] | Erdős, Paul; Rényi, Alfréd, On two problems of information theory, Magy. Tud. Akad. Mat. Kut. Intéz. Közl., 8, 229-243 (1963) · Zbl 0119.34001 |
| [24] | Hansen, Nikolaus; Gawelczyk, Andreas; Ostermeier, Andreas, Sizing the population with respect to the local progress in \((1, \lambda )\)-evolution strategies - a theoretical analysis, (Proc. of the IEEE Congress on Evolutionary Computation. Proc. of the IEEE Congress on Evolutionary Computation, CEC’95 (1995), IEEE), 80-85 |
| [25] | Happ, Edda; Johannsen, Daniel; Klein, Christian; Neumann, Frank, Rigorous analyses of fitness-proportional selection for optimizing linear functions, (Proc. of the Annual Genetic and Evolutionary Computation Conference. Proc. of the Annual Genetic and Evolutionary Computation Conference, GECCO’08 (2008), ACM), 953-960 |
| [26] | Jägersküpper, Jens, Rigorous runtime analysis of the \((1 + 1)\) ES: 1/5-rule and ellipsoidal fitness landscapes, (Proc. of the 8th ACM Workshop on Foundations of Genetic Algorithms. Proc. of the 8th ACM Workshop on Foundations of Genetic Algorithms, FOGA’05. Proc. of the 8th ACM Workshop on Foundations of Genetic Algorithms. Proc. of the 8th ACM Workshop on Foundations of Genetic Algorithms, FOGA’05, Lecture Notes in Computer Science, vol. 3469 (2005), Springer), 260-281 · Zbl 1078.68701 |
| [27] | Jägersküpper, Jens; Storch, Tobias, When the plus strategy outperforms the comma strategy and when not, (Proc. of IEEE Symposium on Foundations of Computational Intelligence. Proc. of IEEE Symposium on Foundations of Computational Intelligence, FOCI’07 (2007), IEEE), 25-32 |
| [28] | Jansen, Thomas; De Jong, Kenneth A.; Wegener, Ingo, On the choice of the offspring population size in evolutionary algorithms, Evol. Comput., 13, 413-440 (2005) |
| [29] | Kötzing, Timo; Sudholt, Dirk; Theile, Madeleine, How crossover helps in pseudo-Boolean optimization, (Proc. of the 13th Annual Genetic and Evolutionary Computation Conference. Proc. of the 13th Annual Genetic and Evolutionary Computation Conference, GECCO’11 (2011), ACM), 989-996 |
| [30] | Lässig, Jörg; Sudholt, Dirk, Adaptive population models for offspring populations and parallel evolutionary algorithms, (Proc. of the 11th ACM Workshop on Foundations of Genetic Algorithms. Proc. of the 11th ACM Workshop on Foundations of Genetic Algorithms, FOGA’11 (2011), ACM), 181-192 · Zbl 1369.68316 |
| [31] | Lehre, Per Kristian; Witt, Carsten, Black-box search by unbiased variation, (Proc. of the 12th Annual Genetic and Evolutionary Computation Conference. Proc. of the 12th Annual Genetic and Evolutionary Computation Conference, GECCO’10 (2010), ACM), 1441-1448 · Zbl 1264.68221 |
| [32] | Lehre, Per Kristian; Witt, Carsten, Black-box search by unbiased variation, Algorithmica, 64, 623-642 (2012) · Zbl 1264.68221 |
| [33] | Mitchell, Melanie; Forrest, Stephanie; Holland, John H., The royal road for genetic algorithms: fitness landscapes and GA performance, (Proc. of the First European Conference on Artificial Life (1992), MIT Press), 245-254 |
| [34] | Moraglio, Alberto; Poli, Riccardo, Topological interpretation of crossover, (Proc. of the Annual Genetic and Evolutionary Computation Conference. Proc. of the Annual Genetic and Evolutionary Computation Conference, GECCO’04 (2004), ACM), 1377-1388 |
| [35] | Oliveto, Pietro Simone; Lehre, Per Kristian; Neumann, Frank, Theoretical analysis of rank-based mutation - combining exploration and exploitation, (Proc. of the IEEE Congress on Evolutionary Computation. Proc. of the IEEE Congress on Evolutionary Computation, CEC’09 (2009)), 1455-1462 |
| [36] | Oliveto, Pietro Simone; Witt, Carsten, Improved runtime analysis of the simple genetic algorithm, (Proc. of the Annual Genetic and Evolutionary Computation Conference. Proc. of the Annual Genetic and Evolutionary Computation Conference, GECCO’13 (2013), ACM), 1621-1628 |
| [37] | Rechenberg, Ingo, Evolutionsstrategie (1973), Friedrich Fromman Verlag (Günther Holzboog KG): Friedrich Fromman Verlag (Günther Holzboog KG) Stuttgart |
| [38] | Rowe, Jonathan E.; Sudholt, Dirk, The choice of the offspring population size in the \((1, \lambda )\) EA, (Proc. of the Annual Genetic and Evolutionary Computation Conference. Proc. of the Annual Genetic and Evolutionary Computation Conference, GECCO’12 (2012), ACM), 1349-1356 |
| [39] | Schumer, Michael A.; Steiglitz, Kenneth, Adaptive step size random search, IEEE Trans. Automat. Control, 13, 270-276 (1968) |
| [40] | Spears, William M.; De Jong, Kenneth A., An analysis of multi-point crossover, (Proc. of the 1st Workshop on Foundations of Genetic Algorithms. Proc. of the 1st Workshop on Foundations of Genetic Algorithms, FOGA’90 (1990), Morgan Kaufmann), 301-315 |
| [41] | Storch, Tobias, On the choice of the parent population size, Evol. Comput., 16, 557-578 (2008) |
| [42] | Sudholt, Dirk, Crossover speeds up building-block assembly, (Proc. of the 14th Annual Genetic and Evolutionary Computation Conference. Proc. of the 14th Annual Genetic and Evolutionary Computation Conference, GECCO’12 (2012), ACM), 689-702 |
| [43] | Sudholt, Dirk, A new method for lower bounds on the running time of evolutionary algorithms, IEEE Trans. Evol. Comput., 17, 418-435 (2013) |
| [44] | Syswerda, Gilbert, Uniform crossover in genetic algorithms, (Proc. of the 3rd International Conference on Genetic Algorithms. Proc. of the 3rd International Conference on Genetic Algorithms, ICGA’89 (1989), Morgan Kaufmann Publishers Inc.), 2-9 |
| [45] | Wegener, Ingo, Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions, (Sarker, S.; Yao, X.; Mohammadian, M., Evolutionary Optimization (2002), Kluwer: Kluwer Dordrecht), 349-369 |
| [46] | Witt, Carsten, Runtime analysis of the \(( \mu + 1)\) EA on simple pseudo-Boolean functions, Evol. Comput., 14, 65-86 (2006) |
| [47] | Witt, Carsten, Tight bounds on the optimization time of a randomized search heuristic on linear functions, Comb. Probab. Comput., 22, 294-318 (2013) · Zbl 1258.68183 |
| [48] | Zarges, Christine, Rigorous runtime analysis of inversely fitness proportional mutation rates, (Proc. of the 10th International Conference on Parallel Problem Solving from Nature. Proc. of the 10th International Conference on Parallel Problem Solving from Nature, PPSN’08. Proc. of the 10th International Conference on Parallel Problem Solving from Nature. Proc. of the 10th International Conference on Parallel Problem Solving from Nature, PPSN’08, Lecture Notes in Computer Science, vol. 5199 (2008), Springer), 112-122 |
| [49] | Zarges, Christine, On the utility of the population size for inversely fitness proportional mutation rates, (Proc. of the 10th ACM Workshop on Foundations of Genetic Algorithms. Proc. of the 10th ACM Workshop on Foundations of Genetic Algorithms, FOGA’09 (2009), ACM), 39-46 · Zbl 1369.68336 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
