nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Quality-Diversity Optimization: A Novel Branch of Stochastic Optimization

verfasst von : Konstantinos Chatzilygeroudis, Antoine Cully, Vassilis Vassiliades, Jean-Baptiste Mouret

Erschienen in: Black Box Optimization, Machine Learning, and No-Free Lunch Theorems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Traditional optimization algorithms search for a single global optimum that maximizes (or minimizes) the objective function. Multimodal optimization algorithms search for the highest peaks in the search space that can be more than one. Quality-Diversity algorithms are a recent addition to the evolutionary computation toolbox that do not only search for a single set of local optima, but instead try to illuminate the search space. In effect, they provide a holistic view of how high-performing solutions are distributed throughout a search space. The main differences with multimodal optimization algorithms are that (1) Quality-Diversity typically works in the behavioral space (or feature space), and not in the genotypic (or parameter) space, and (2) Quality-Diversity attempts to fill the whole behavior space, even if the niche is not a peak in the fitness landscape. In this chapter, we provide a gentle introduction to Quality-Diversity optimization, discuss the main representative algorithms, and the main current topics under consideration in the community. Throughout the chapter, we also discuss several successful applications of Quality-Diversity algorithms, including deep learning, robotics, and reinforcement learning.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Tuning Algorithms for Stochastic Black-Box Optimization: State of the Art and Future Perspectives

Nächstes Kapitel Multi-Objective Evolutionary Algorithms: Past, Present, and Future

Adams, M.D., Celniker, S.E., Holt, R.A., Evans, C.A., Gocayne, J.D., Amanatides, P.G., Scherer, S.E., Li, P.W., Hoskins, R.A., Galle, R.F., et al.: The genome sequence of Drosophila melanogaster. Science 287(5461), 2185–2195 (2000)CrossRef

Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-Time Analysis of the Multiarmed Bandit Problem. Springer, Berlin (2002)MATH

Barrera, J., Coello, C.A.C.: A review of particle swarm optimization methods used for multimodal optimization. In: Innovations in Swarm Intelligence, pp. 9–37. Springer, Berlin (2009)

Bartz-Beielstein, T., Zaefferer, M.: Model-based methods for continuous and discrete global optimization. Appl. Soft Comput. 55, 154–167 (2017)CrossRef

Beyer, H.-G., Schwefel, H.-P.: Evolution strategies–a comprehensive introduction. Nat. Comput. 1(1), 3–52 (2002)MathSciNetMATHCrossRef

Bradner, E., Iorio, F., Davis, M.: Parameters tell the design story: ideation and abstraction in design optimization. In: Simulation Series (2014)

Brochu, E., Cora, V.M., De Freitas, N.: A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning (2010). Preprint, arXiv:1012.2599

Cantú-Paz, E.: Adaptive sampling for noisy problems. In: Genetic and Evolutionary Computation Conference, pp. 947–958. Springer, Berlin (2004)

Cavicchio, D.J.: Adaptive search using simulated evolution. PhD thesis, University of Michigan, Ann Arbor, MI (1970)

10.

Chatzilygeroudis, K., Vassiliades, V., Mouret, J.-B.: Reset-free trial-and-error learning for robot damage recovery. Rob. Auton. Syst. 100, 236–250 (2018)CrossRef

11.

Clune, J., Mouret, J.-B., Lipson, H.: The evolutionary origins of modularity. Proc. R. Soc. B Biol. Sci. 280(1755), 20122863 (2013)CrossRef

12.

Cox, D.D., John, S.: A statistical method for global optimization. In: International Conference on Systems, Man, and Cybernetics, pp. 1241–1246. IEEE, Piscataway (1992)

13.

Cully, A.: Autonomous skill discovery with quality-diversity and unsupervised descriptors. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 81–89. ACM, New York (2019)

14.

Cully, A., Demiris, Y.: Hierarchical behavioral repertoires with unsupervised descriptors. In: Proceedings of the Genetic and Evolutionary Computation Conference (2018)

15.

Cully, A., Demiris, Y.: Quality and diversity optimization: a unifying modular framework. IEEE Trans. Evol. Comput. 22(2), 245–259 (2018)CrossRef

16.

Cully, A., Mouret, J.-B.: Behavioral repertoire learning in robotics. In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, pp. 175–182. ACM, New York (2013)

17.

Cully, A., Clune, J., Tarapore, D., Mouret, J.-B.: Robots that can adapt like animals. Nature 521(7553), 503–507 (2015)CrossRef

18.

Das, S., Maity, S., Qu, B.-Y., Suganthan, P.N.: Real-parameter evolutionary multimodal optimization—a survey of the state-of-the-art. Swarm Evol. Comput. 1, 71–88 (2011)CrossRef

19.

De Jong, K.A.: Analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan, Ann Arbor, MI (1975)

20.

Deb, K., Beyer, H.-G.: Self-adaptive genetic algorithms with simulated binary crossover. Evol. Comput. 9(2), 197–221 (2001)CrossRef

21.

Deb, K., Saha, A.: Finding multiple solutions for multimodal optimization problems using a multi-objective evolutionary approach. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 447–454 (2010)

22.

Du, Q., Faber, V., Gunzburger, M.: Centroidal Voronoi tessellations: applications and algorithms. SIAM Rev. 41, 637–676 (1999)MathSciNetMATHCrossRef

23.

Duarte, M., Gomes, J., Oliveira, S.M., Christensen, A.L.: Evolution of repertoire-based control for robots with complex locomotor systems. IEEE Trans. Evol. Comput. 22(2), 314–328 (2018)CrossRef

24.

Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K.O., Clune, J.: Go-explore: a new approach for hard-exploration problems (2019). Preprint, arXiv:1901.10995

25.

Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K.O., Clune, J.: First return then explore (2020). Preprint, arXiv:2004.12919

26.

Escande, A., Mansard, N., Wieber, P.-B.: Hierarchical quadratic programming: fast online humanoid-robot motion generation. Int. J. Robot. Res. 33(7), 1006–1028 (2014)CrossRef

27.

Flageat, M., Cully, A.: Fast and stable map-elites in noisy domains using deep grids. In: Proceeding of the Alife Conference (2020)

28.

Fontaine, M.C., Togelius, J., Nikolaidis, S., Hoover, A.K.: Covariance matrix adaptation for the rapid illumination of behavior space. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion (2020)

29.

Gaier, A., Asteroth, A., Mouret, J.-B.: Aerodynamic design exploration through surrogate-assisted illumination. In: 18th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, pp. 3330 (2017)

30.

Gaier, A., Asteroth, A., Mouret, J.-B.: Data-efficient exploration, optimization, and modeling of diverse designs through surrogate-assisted illumination. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 99–106. ACM, New York (2017)

31.

Gaier, A., Asteroth, A., Mouret, J.-B.: Data-efficient design exploration through surrogate-assisted illumination. Evol. Comput. 26, 1–30 (2018)CrossRef

32.

Gaier, A., Asteroth, A., Mouret, J.-B.: Discovering representations for black-box optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), vol. 11 (2020)

33.

Goldberg, D.E., Richardson, J., et al.: Genetic algorithms with sharing for multimodal function optimization. In: Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, pp. 41–49. Lawrence Erlbaum, Hillsdale (1987)

34.

Hansen, N., Ostermeier, A.: Completely derandomized self-adaptation in evolution strategies. Evol. Comput. 9(2), 159–195 (2001)CrossRef

35.

Harik, G.R.: Finding multimodal solutions using restricted tournament selection. In: Proceedings of the 6th International Conference on Genetic Algorithms, pp. 24–31. Morgan Kaufmann, San Francisco (1995)

36.

Hauschild, M., Pelikan, M.: An introduction and survey of estimation of distribution algorithms. Swarm Evol. Comput. 1(3), 111–128 (2011)CrossRef

37.

Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Glob. Optim. 13(4), 455–492 (1998)MathSciNetMATHCrossRef

38.

Ju, L., Du, Q., Gunzburger, M.: Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations. Parallel Comput. 28(10), 1477–1500 (2002)MathSciNetMATHCrossRef

39.

Justesen, N., Risi, S., Mouret, J.-B.: Map-elites for noisy domains by adaptive sampling. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 121–122. ACM, New York (2019)

40.

Karafotias, G., Hoogendoorn, M., Eiben, Á.E.: Parameter control in evolutionary algorithms: Trends and challenges. IEEE Trans. Evol. Comput. 19(2), 167–187 (2014)CrossRef

41.

Kent, P., Branke, J.: Bop-elites, a Bayesian optimisation algorithm for quality-diversity search (2020). Preprint, arXiv:2005.04320

42.

Kingma, D.P., Welling, M.: Auto-encoding variational Bayes. In: Bengio, Y., LeCun, Y. (eds.) International Conference on Learning Representation (ICLR) (2014)

43.

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

44.

LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proc. IEEE 86(11), 2278–2324 (1998)CrossRef

45.

Lee, C.-G., Cho, D.-H., Jung, H.-K.: Niching genetic algorithm with restricted competition selection for multimodal function optimization. IEEE Trans. Magn. 35(3), 1722–1725 (1999)CrossRef

46.

Lehman, J., Stanley, K.O.: Abandoning objectives: evolution through the search for novelty alone. Evol. Comput. 19(2), 189–223 (2011)CrossRef

47.

Lehman, J., Stanley, K.O.: Evolving a diversity of virtual creatures through novelty search and local competition. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pp. 211–218. ACM, New York (2011)

48.

Lehman, J., Risi, S., Clune, J.: Creative generation of 3D objects with deep learning and innovation engines. In: Proceedings of the 7th International Conference on Computational Creativity (2016)

49.

Liapis, A., Martınez, H.P., Togelius, J., Yannakakis, G.N.: Transforming exploratory creativity with DeLeNoX. In: Proceedings of the Fourth International Conference on Computational Creativity, pp. 56–63. AAAI Press, Palo Alto (2013)

50.

MacQueen, J.: Some methods for classification and analysis of multivariate observations. In: Proc. 5th Berkeley Symp. on Math. Statist. and Prob., vol. 1, pp. 281–297. Univ. of Calif. Press, Berkeley (1967)

51.

Mahfoud, S.: Niching methods for genetic algorithms. PhD thesis, University of Illinois at Urbana-Champaign, Urbana, IL (1995)

52.

Mayne, D.Q., Rawlings, J.B., Rao, C.V., Scokaert, P.O.: Constrained model predictive control: stability and optimality. Automatica 36(6), 789–814 (2000)MathSciNetMATHCrossRef

53.

Mouret, J.-B., Clune, J.: Illuminating search spaces by mapping elites (2015). Preprint, arXiv:1504.04909

54.

Mouret, J.-B., Doncieux, S.: Encouraging behavioral diversity in evolutionary robotics: an empirical study. Evol. Comput. 20(1), 91–133 (2012)CrossRef

55.

Mouret, J.-B., Maguire, G.: Quality diversity for multi-task optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference. ACM, New York (2020)

56.

Nguyen, A., Yosinski, J., Clune, J.: Deep neural networks are easily fooled: high confidence predictions for unrecognizable images. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 427–436 (2015)

57.

Nguyen, A.M., Yosinski, J., Clune, J.: Innovation engines: automated creativity and improved stochastic optimization via deep learning. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 959–966. ACM, New York (2015)

58.

Nordmoen, J., Samuelsen, E., Ellefsen, K.O., Glette, K.: Dynamic mutation in map-elites for robotic repertoire generation. In: Artificial Life Conference Proceedings, pp. 598–605. MIT Press, Cambridge (2018)

59.

Ong, Y.S., Nair, P.B., Keane, A.J.: Evolutionary optimization of computationally expensive problems via surrogate modeling. AIAA J. 41(4), 687–696 (2003)CrossRef

60.

Paolo, G., Laflaquiere, A., Coninx, A., Doncieux, S.: Unsupervised learning and exploration of reachable outcome space. Algorithms 24, 25 (2019)

61.

Pearce, M., Branke, J.: Continuous multi-task bayesian optimisation with correlation. Eur. J. Oper. Res. 270(3), 1074–1085 (2018)MathSciNetMATHCrossRef

62.

Pétrowski, A.: A clearing procedure as a niching method for genetic algorithms. In: Proceedings of IEEE International Conference on Evolutionary Computation, pp. 798–803. IEEE, Piscataway (1996)

63.

Preuss, M.: Multimodal Optimization by Means of Evolutionary Algorithms. Springer, Berlin (2015)MATHCrossRef

64.

Preuss, M., Schönemann, L., Emmerich, M.: Counteracting genetic drift and disruptive recombination in (\(\mu \overset {+}{,} \lambda \))-EA on multimodal fitness landscapes. In: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation, pp. 865–872 (2005)

65.

Pugh, J.K., Soros, L., Szerlip, P.A., Stanley, K.O.: Confronting the challenge of quality diversity. In: Proceedings of the 2015 on Genetic and Evolutionary Computation Conference, pp. 967–974. ACM, New York (2015)

66.

Pugh, J.K., Soros, L.B., Stanley, K.O.: Quality diversity: a new frontier for evolutionary computation. Front. Robot. AI 3, 40 (2016)CrossRef

67.

Rudolph, G.: Self-adaptive mutations may lead to premature convergence. IEEE Trans. Evol. Comput. 5(4), 410–414 (2001)CrossRef

68.

Sareni, B., Krahenbuhl, L.: Fitness sharing and niching methods revisited. IEEE Trans. Evol. Comput. 2, 97–106 (1998)CrossRef

69.

Shahriari, B., Swersky, K., Wang, Z., Adams, R.P., De Freitas, N.: Taking the human out of the loop: a review of bayesian optimization. Proc. IEEE 104(1), 148–175 (2015)CrossRef

70.

Shir, O., Emmerich, M., Bäck, T., Vrakking, M.: Conceptual designs in laser pulse shaping obtained by niching in evolution strategies. In: EUROGEN 2007 (2007)

71.

Sigmund, O.: A 99 line topology optimization code written in matlab. Struct. Multidiscipl. Optim. 21(2), 120–127 (2001)CrossRef

72.

Singh, G., Deb, K.: Comparison of multi-modal optimization algorithms based on evolutionary algorithms. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pp. 1305–1312 (2006)

73.

Srinivas, N., Krause, A., Kakade, S., Seeger, M.: Gaussian process optimization in the bandit setting: no regret and experimental design. In: Proceedings of the 27th International Conference on International Conference on Machine Learning, pp. 1015–1022 (2010)

74.

Tarapore, D., Clune, J., Cully, A., Mouret, J.-B.: How do different encodings influence the performance of the map-elites algorithm? In: Genetic and Evolutionary Computation Conference (2016)

75.

Vassiliades, V., Mouret, J.-B.: Discovering the elite hypervolume by leveraging interspecies correlation. In: Proceedings of the Genetic and Evolutionary Computation Conference (2018)

76.

Vassiliades, V., Chatzilygeroudis, K., Mouret, J.-B.: Comparing multimodal optimization and illumination. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 97–98. ACM, New York (2017)

77.

Vassiliades, V., Chatzilygeroudis, K., Mouret, J.-B.: A comparison of illumination algorithms in unbounded spaces. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 1578–1581. ACM, New York (2017)

78.

Vassiliades, V., Chatzilygeroudis, K., Mouret, J.-B.: Using centroidal Voronoi tessellations to scale up the multidimensional archive of phenotypic elites algorithm. IEEE Trans. Evol. Comput. 22(4), 623–630 (2018)CrossRef

79.

Williams, C.K., Rasmussen, C.E.: Gaussian Processes for Machine Learning, vol. 2. MIT Press, Cambridge (2006)MATH

80.

Yin, X., Germay, N.: A fast genetic algorithm with sharing scheme using cluster analysis methods in multimodal function optimization. In: Artificial Neural Nets and Genetic Algorithms, pp. 450–457. Springer, Berlin (1993)

Titel: Quality-Diversity Optimization: A Novel Branch of Stochastic Optimization
verfasst von: Konstantinos Chatzilygeroudis
Antoine Cully
Vassilis Vassiliades
Jean-Baptiste Mouret
Verlag: Springer International Publishing
Buch: Black Box Optimization, Machine Learning, and No-Free Lunch Theorems
Print ISBN: 978-3-030-66514-2

Electronic ISBN: 978-3-030-66515-9

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-66515-9_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner