Top

Published in:

2020 | OriginalPaper | Chapter

Benchmarking a \((\mu +\lambda )\) Genetic Algorithm with Configurable Crossover Probability

Authors : Furong Ye, Hao Wang, Carola Doerr, Thomas Bäck

Published in: Parallel Problem Solving from Nature – PPSN XVI

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We investigate a family of \((\mu +\lambda )\) Genetic Algorithms (GAs) which creates offspring either from mutation or by recombining two randomly chosen parents. By scaling the crossover probability, we can thus interpolate from a fully mutation-only algorithm towards a fully crossover-based GA. We analyze, by empirical means, how the performance depends on the interplay of population size and the crossover probability.

Our comparison on 25 pseudo-Boolean optimization problems reveals an advantage of crossover-based configurations on several easy optimization tasks, whereas the picture for more complex optimization problems is rather mixed. Moreover, we observe that the “fast” mutation scheme with its are power-law distributed mutation strengths outperforms standard bit mutation on complex optimization tasks when it is combined with crossover, but performs worse in the absence of crossover.

We then take a closer look at the surprisingly good performance of the crossover-based \((\mu +\lambda )\) GAs on the well-known LeadingOnes benchmark problem. We observe that the optimal crossover probability increases with increasing population size \(\mu \). At the same time, it decreases with increasing problem dimension, indicating that the advantages of the crossover are not visible in the asymptotic view classically applied in runtime analysis. We therefore argue that a mathematical investigation for fixed dimensions might help us observe effects which are not visible when focusing exclusively on asymptotic performance bounds.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Approximation Speed-Up by Quadratization on LeadingOnes

Afshani, P., Agrawal, M., Doerr, B., Doerr, C., Larsen, K.G., Mehlhorn, K.: The query complexity of finding a hidden permutation. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds.) Space-Efficient Data Structures, Streams, and Algorithms. LNCS, vol. 8066, pp. 1–11. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40273-9_1CrossRef

Bäck, T.: Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press Inc, Oxford (1996)MATH

Böttcher, S., Doerr, B., Neumann, F.: Optimal fixed and adaptive mutation rates for the leadingones problem. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 1–10. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15844-5_1CrossRef

Buskulic, N., Doerr, C.: Maximizing drift is not optimal for solving OneMax. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2019), pp. 425–426. ACM (2019). http://arxiv.org/abs/1904.07818

Pinto, E.C., Doerr, C.: A simple proof for the usefulness of crossover in black-box optimization. In: Auger, A., Fonseca, C.M., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds.) PPSN 2018. LNCS, vol. 11102, pp. 29–41. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99259-4_3 CrossRef

Chicano, F., Sutton, A.M., Whitley, L.D., Alba, E.: Fitness probability distribution of bit-flip mutation. Evol. Comput. 23(2), 217–248 (2015)CrossRef

Corus, D., Oliveto, P.S.: Standard steady state genetic algorithms can hillclimb faster than mutation-only evolutionary algorithms. IEEE Trans. Evol. Comput. 22(5), 720–732 (2018)CrossRef

Corus, D., Oliveto, P.S.: On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms. Algorithmica 1–31 (2020). https://doi.org/10.1007/s00453-020-00743-1

Haziza, D., Rapin, J.: HiPlot - high dimensional interactive plotting (2020). https://github.com/facebookresearch/hiplot

10.

Dang, D.C., et al.: Escaping local optima using crossover with emergent diversity. IEEE Trans. Evol. Comput. 22(3), 484–497 (2017)CrossRef

11.

De Jong, K.A.: An analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis, University of Michigan, Ann Arbor, MI, USA (1975)

12.

Doerr, B.: Analyzing randomized search heuristics via stochastic domination. Theoret. Comput. Sci. 773, 115–137 (2019)MathSciNetCrossRef

13.

Doerr, B., Doerr, C., Ebel, F.: From black-box complexity to designing new genetic algorithms. Theoret. Comput. Sci. 567, 87–104 (2015)MathSciNetCrossRef

14.

Doerr, B., Happ, E., Klein, C.: Crossover can provably be useful in evolutionary computation. Theoret. Comput. Sci. 425, 17–33 (2012)MathSciNetCrossRef

15.

Doerr, B., Johannsen, D., Kötzing, T., Neumann, F., Theile, M.: More effective crossover operators for the all-pairs shortest path problem. Theoret. Comput. Sci. 471, 12–26 (2013)MathSciNetCrossRef

16.

Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2017), pp. 777–784. ACM (2017)

17.

Doerr, B., Winzen, C.: Black-box complexity: breaking the O(n logn) barrier of leadingOnes. In: Hao, J.-K., Legrand, P., Collet, P., Monmarché, N., Lutton, E., Schoenauer, M. (eds.) EA 2011. LNCS, vol. 7401, pp. 205–216. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35533-2_18CrossRef

18.

Doerr, C., Wang, H., Ye, F., van Rijn, S., Bäck, T.: IOHprofiler: a benchmarking and profiling tool for iterative optimization heuristics. arXiv e-prints:1810.05281, October 2018. https://arxiv.org/abs/1810.05281

19.

Doerr, C., Ye, F., Horesh, N., Wang, H., Shir, O.M., Bäck, T.: Benchmarking discrete optimization heuristics with IOHprofiler. Appl. Soft Comput. 88, 106027 (2019)CrossRef

20.

Doerr, C., Ye, F., van Rijn, S., Wang, H., Bäck, T.: Towards a theory-guided benchmarking suite for discrete black-box optimization heuristics: profiling (1 + \(\lambda \)) EA variants on onemax and leadingones. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2018), pp. 951–958. ACM (2018)

21.

Elsayed, S.M., Sarker, R.A., Essam, D.L.: Multi-operator based evolutionary algorithms for solving constrained optimization problems. Comput. Oper. Res. 38(12), 1877–1896 (2011)MathSciNetCrossRef

22.

Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning, 1st edn. Addison-Wesley Longman Publishing Co. Inc, Boston (1989)MATH

23.

Yoon, H.S., Moon, B.R.: An empirical study on the synergy of multiple crossover operators. IEEE Trans. Evol. Comput. 6(2), 212–223 (2002)CrossRef

24.

Jansen, T., De Jong, K.A., Wegener, I.: On the choice of the offspring population size in evolutionary algorithms. Evol. Comput. 13, 413–440 (2005)CrossRef

25.

Jansen, T., Wegener, I.: The analysis of evolutionary algorithms–a proof that crossover really can help. Algorithmica 34, 47–66 (2002). https://doi.org/10.1007/s00453-002-0940-2MathSciNetCrossRefMATH

26.

Jansen, T., Wegener, I.: Real royal road functions-where crossover provably is essential. Discrete Appl. Math. 149(1–3), 111–125 (2005)MathSciNetCrossRef

27.

Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983)MathSciNetCrossRef

28.

Kötzing, T., Sudholt, D., Theile, M.: How crossover helps in pseudo-Boolean optimization. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2011), pp. 989–996. ACM (2011)

29.

Lehre, P.K., Witt, C.: Black-box search by unbiased variation. Algorithmica 64, 623–642 (2012). https://doi.org/10.1007/s00453-012-9616-8MathSciNetCrossRefMATH

30.

Lehre, P.K., Yao, X.: Crossover can be constructive when computing unique input-output sequences. Soft. Comput. 15(9), 1675–1687 (2011). https://doi.org/10.1007/s00500-010-0610-2CrossRefMATH

31.

Mironovich, V., Buzdalov, M.: Evaluation of heavy-tailed mutation operator on maximum flow test generation problem. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2017), Companion Material, pp. 1423–1426. ACM (2017)

32.

Mitchell, M., Holland, J.H., Forrest, S.: When will a genetic algorithm outperform hill climbing? In: Proceedings of Neural Information Processing Systems Conference (NIPS 1993). Advances in Neural Information Processing Systems, vol. 6, pp. 51–58. Morgan Kaufmann (1993)

33.

Murata, T., Ishibuchi, H.: Positive and negative combination effects of crossover and mutation operators in sequencing problems. In: Proceedings of Conference on Evolutionary Computation, pp. 170–175, May 1996

34.

Neumann, F., Oliveto, P.S., Rudolph, G., Sudholt, D.: On the effectiveness of crossover for migration in parallel evolutionary algorithms. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2011), pp. 1587–1594. ACM (2011)

35.

Selman, B., Levesque, H.J., Mitchell, D.G.: A new method for solving hard satisfiability problems. In: Proceedings of National Conference on Artificial Intelligence, pp. 440–446. AAAI (1992)

36.

Spears, W.M.: Crossover or mutation? In: Banzhaf, W. (ed.) Foundations of Genetic Algorithms, vol. 2, pp. 221–237. Elsevier, Amsterdam (1993)

37.

Sudholt, D.: Crossover is provably essential for the Ising model on trees. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2005), pp. 1161–1167. ACM Press (2005)

38.

Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17, 418–435 (2013)CrossRef

39.

Sudholt, D.: How crossover speeds up building block assembly in genetic algorithms. Evol. Comput. 25(2), 237–274 (2017)CrossRef

40.

Varadarajan, S., Whitley, D.: The massively parallel mixing genetic algorithm for the traveling salesman problem. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2019), pp. 872–879. ACM (2019)

41.

Watson, R.A., Jansen, T.: A building-block royal road where crossover is provably essential. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2007), pp. 1452–1459. ACM (2007)

42.

Weise, T., Wu, Z.: Difficult features of combinatorial optimization problems and the tunable w-model benchmark problem for simulating them. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2018, Companion Material), pp. 1769–1776. ACM (2018)

43.

Whitley, D., Varadarajan, S., Hirsch, R., Mukhopadhyay, A.: Exploration and exploitation without mutation: solving the Jump function in \(\theta (n)\) time. In: Auger, A., Fonseca, C.M., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds.) PPSN 2018. LNCS, vol. 11102, pp. 55–66. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99259-4_5CrossRef

44.

Ye, F., Wang, H., Doerr, C., Bäck, T.: Experimental data sets for the study benchmarking a \((\mu +\lambda )\) genetic algorithm with configurable crossover probability, April 2020. https://doi.org/10.5281/zenodo.3753086

Title: Benchmarking a Genetic Algorithm with Configurable Crossover Probability
Authors: Furong Ye
Hao Wang
Carola Doerr
Thomas Bäck
Publisher: Springer International Publishing
Book: Parallel Problem Solving from Nature – PPSN XVI
Print ISBN: 978-3-030-58114-5

Electronic ISBN: 978-3-030-58115-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-58115-2_49

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner