Runtime Analysis of Non-elitist Populations: From Classical Optimisation to Partial Information
Tóm tắt
Although widely applied in optimisation, relatively little has been proven rigorously about the role and behaviour of populations in randomised search processes. This paper presents a new method to prove upper bounds on the expected optimisation time of population-based randomised search heuristics that use non-elitist selection mechanisms and unary variation operators. Our results follow from a detailed drift analysis of the population dynamics in these heuristics. This analysis shows that the optimisation time depends on the relationship between the strength of the selective pressure and the degree of variation introduced by the variation operator. Given limited variation, a surprisingly weak selective pressure suffices to optimise many functions in expected polynomial time. We derive upper bounds on the expected optimisation time of non-elitist evolutionary algorithms (EA) using various selection mechanisms, including fitness proportionate selection. We show that EAs using fitness proportionate selection can optimise standard benchmark functions in expected polynomial time given a sufficiently low mutation rate. As a second contribution, we consider an optimisation scenario with partial information, where fitness values of solutions are only partially available. We prove that non-elitist EAs under a set of specific conditions can optimise benchmark functions in expected polynomial time, even when vanishingly little information about the fitness values of individual solutions or populations is available. To our knowledge, this is the first runtime analysis of randomised search heuristics under partial information.
Tài liệu tham khảo
citation_title=Theory of Randomized Search Heuristics: Foundations and Recent Developments; citation_publication_date=2011; citation_id=CR1; citation_author=A Auger; citation_author=A Auger; citation_author=B Doerr; citation_publisher=World Scientific Publishing Co., Inc.
citation_journal_title=IEEE Trans. Syst. Man Cybernet. Part B; citation_title=A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems; citation_author=T Chen, J He, G Sun, G Chen, X Yao; citation_volume=39; citation_issue=5; citation_publication_date=2009; citation_pages=1092-1106; citation_doi=10.1109/TSMCB.2008.2012167; citation_id=CR2
citation_title=Variants of Evolutionary Algorithms for Real-World Applications; citation_publication_date=2012; citation_id=CR3; citation_publisher=Springer
Corus, D., Dang, D.-C., Eremeev, A.V., Lehre, P.K.: Level-based analysis of genetic algorithms and other search processes. In: Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN’14, Ljubljana, Slovenia, pp. 912–921. Springer International Publishing, Berlin (2014)
Dang, D.-C., Lehre, P.K.: Evolution under partial information. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’14, pp. 1359–1366 (2014)
Dang, D.-C., Lehre, P.K.: Refined upper bounds on the expected runtime of non-elitist populations from fitness-levels. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’14, pp. 1367–1374. ACM, New York (2014)
citation_journal_title=Algorithmica; citation_title=Multiplicative drift analysis; citation_author=B Doerr, D Johannsen, C Winzen; citation_volume=64; citation_issue=4; citation_publication_date=2012; citation_pages=673-697; citation_doi=10.1007/s00453-012-9622-x; citation_id=CR7
Droste, S.: Analysis of the (1+1) EA for a dynamically bitwise changing OneMax. In: Proceedings of the 2003 International Conference on Genetic and Evolutionary Computation, GECCO’03, pp 909–921. Springer, Berlin (2003)
Droste, S.: Analysis of the (1+1) EA for a noisy OneMax. In: Proceedings of the 2004 International Conference on Genetic and Evolutionary Computation, GECCO’04, pp. 1088–1099. Springer, Berlin (2004)
citation_title=Concentration of Measure for the Analysis of Randomized Algorithms; citation_publication_date=2009; citation_id=CR10; citation_author=D Dubhashi; citation_author=A Panconesi; citation_publisher=Cambridge University Press
Gießen, C., Kötzing, T.: Robustness of populations in stochastic environments. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’14, pp. 1383–1390. ACM, New York (2014)
Goldberg, D.E., Deb, K.: A comparative analysis of selection schemes used in genetic algorithms. In: Proceedings of Foundations of Genetic Algorithms, FOGA I, pp. 69–93. Morgan Kaufmann (1991)
citation_journal_title=Adv. Appl. Probab.; citation_title=Hitting-time and occupation-time bounds implied by drift analysis with applications; citation_author=B Hajek; citation_volume=14; citation_issue=3; citation_publication_date=1982; citation_pages=502-525; citation_doi=10.2307/1426671; citation_id=CR13
Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitness-proportional selection for optimizing linear functions. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’08, pp. 953–960 (2008)
citation_journal_title=Artif. Intell.; citation_title=Drift analysis and average time complexity of evolutionary algorithms; citation_author=J He, X Yao; citation_volume=127; citation_issue=1; citation_publication_date=2001; citation_pages=57-85; citation_doi=10.1016/S0004-3702(01)00058-3; citation_id=CR15
citation_journal_title=IEEE Trans. Evol. Comput.; citation_title=From an individual to a population: an analysis of the first hitting time of population-based evolutionary algorithms; citation_author=J He, X Yao; citation_volume=6; citation_issue=5; citation_publication_date=2002; citation_pages=495-511; citation_doi=10.1109/TEVC.2002.800886; citation_id=CR16
citation_title=Analyzing Evolutionary Algorithms—The Computer Science Perspective. Natural Computing Series; citation_publication_date=2013; citation_id=CR17; citation_author=T Jansen; citation_publisher=Springer
citation_journal_title=Swarm Evol. Comput.; citation_title=Surrogate-assisted evolutionary computation: recent advances and future challenges; citation_author=Y Jin; citation_volume=1; citation_issue=2; citation_publication_date=2011; citation_pages=61-70; citation_doi=10.1016/j.swevo.2011.05.001; citation_id=CR18
citation_journal_title=IEEE Trans. Evol. Comput.; citation_title=Evolutionary optimization in uncertain environments—a survey; citation_author=Y Jin, J Branke; citation_volume=9; citation_issue=3; citation_publication_date=2005; citation_pages=303-317; citation_doi=10.1109/TEVC.2005.846356; citation_id=CR19
citation_title=Foundations of Modern Probability; citation_publication_date=2002; citation_id=CR20; citation_author=O Kallenberg; citation_publisher=Springer
Kötzing, T., Neumann, F., Sudholt, D., Wagner, M.: Simple max-min ant systems and the optimization of linear pseudo-boolean functions, In: Proceedings of Foundations of Genetic Algorithms, FOGA XI, pp. 209–218 (2011)
Lässig, J., Sudholt, D.: General scheme for analyzing running times of parallel evolutionary algorithms. In: Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN’10, pp. 234–243 (2010)
Lehre, P.K.: Negative drift in populations. In: Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN’10, pp. 244–253. Springer, Berlin (2010)
Lehre, P.K.: Fitness-levels for non-elitist populations. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’11, pp. 2075–2082. ACM, New York (2011)
Lehre, P.K.: Drift analysis. In: Proceedings of the Annual Conference Companion on Genetic and Evolutionary Computation, GECCO’12, pp. 1239–1258. ACM, New York (2012)
citation_journal_title=IEEE Trans. Evol. Comput.; citation_title=On the impact of mutation-selection balance on the runtime of evolutionary algorithms; citation_author=PK Lehre, X Yao; citation_volume=16; citation_issue=2; citation_publication_date=2012; citation_pages=225-241; citation_doi=10.1109/TEVC.2011.2112665; citation_id=CR26
citation_journal_title=Evol. Comput.; citation_title=Genetic algorithms, selection schemes, and the varying effects of noise; citation_author=BL Miller, DE Goldberg; citation_volume=4; citation_publication_date=1996; citation_pages=113-131; citation_doi=10.1162/evco.1996.4.2.113; citation_id=CR27
citation_title=Elementary Inequalities; citation_publication_date=1964; citation_id=CR28; citation_author=DS Mitrinović; citation_publisher=P. Noordhoff Ltd
citation_title=Probability and Computing: Randomized Algorithms and Probabilistic Analysis; citation_publication_date=2005; citation_id=CR29; citation_author=M Mitzenmacher; citation_author=E Upfal; citation_publisher=Cambridge University Press
Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’09, pp. 835–842 (2009)
citation_title=Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity; citation_publication_date=2010; citation_id=CR31; citation_author=F Neumann; citation_author=C Witt; citation_publisher=Springer-Verlag New York Inc
citation_journal_title=Theor. Comput. Sci.; citation_title=The choice of the offspring population size in the
evolutionary algorithm; citation_author=JE Rowe, D Sudholt; citation_volume=545; citation_publication_date=2014; citation_pages=20-38; citation_doi=10.1016/j.tcs.2013.09.036; citation_id=CR32
citation_journal_title=IEEE Trans. Evol. Comput.; citation_title=A new method for lower bounds on the running time of evolutionary algorithms; citation_author=D Sudholt; citation_volume=17; citation_issue=3; citation_publication_date=2013; citation_pages=418-435; citation_doi=10.1109/TEVC.2012.2202241; citation_id=CR33
Wegener, I.: Methods for the analysis of evolutionary algorithms on pseudo-boolean functions. In: Evolutionary Optimization, vol. 48, pp. 349–369. Springer, New York (2002)
citation_journal_title=Evolutionary Computation; citation_title=Runtime analysis of the (
+ 1) EA on simple pseudo-boolean functions; citation_author=C Witt; citation_volume=14; citation_issue=1; citation_publication_date=2006; citation_pages=65-86; citation_id=CR35
citation_title=Evolutionary Computation in Practice, volume 88 of Studies in Computational Intelligence; citation_publication_date=2008; citation_id=CR36; citation_publisher=Springer