nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Observation of Unbounded Novelty in Evolutionary Algorithms is Unknowable

verfasst von : Eric Holloway, Robert Marks

Erschienen in: Artificial Intelligence and Soft Computing

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

Open ended evolution seeks computational structures whereby creation of unbounded diversity and novelty are possible. However, research has run into a problem known as the “novelty plateau” where further creation of novelty is not observed. Using standard algorithmic information theory and Chaitin’s Incompleteness Theorem, we prove no algorithm can detect unlimited novelty. Therefore observation of unbounded novelty in computer evolutionary programs is nonalgorithmic and, in this sense, unknowable.

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 A Study on Solving Single Stage Batch Process Scheduling Problems with an Evolutionary Algorithm Featuring Bacterial Mutations

Nächstes Kapitel Multi-swarm Optimization Algorithm Based on Firefly and Particle Swarm Optimization Techniques

Some authors use the notation “\(\overset{+}{=}\)” in lieu of “\(\underset{c}{=} \)” [31, 34].

Even though i is not prefix free (i.e. it will halt once \(b^*\) is executed, leaving \(a^*_{b^*}\) unread), the program that is run on the Turing machine \(\mathcal {U}\) is still prefix free because i is appended to \(p_c\), so the full execution on \(\mathcal {U}\) is \(\mathcal {U}(p_ci)\). Since \(p_c\) is prefix free, then so is \(p_ci\), as it will only halt once the entire string is read.

While Kolmogorov complexity is an exact metric, and has to account for both meaningful structure and random noise in the population, the Kolmogorov sufficient statistic can be used to measure just the meaningful structure in the population.

Mitchell, M., Forrest, S.: Genetic algorithms and artificial life. Artif. life 1(3), 267–289 (1994)CrossRef

Huneman, P.: Determinism, predictability and open-ended evolution: lessons from computational emergence. Synthese 185(2), 195–214 (2012)MathSciNetCrossRef

Komosinski, M., Rotaru-Varga, A.: From directed to open-ended evolution in a complex simulation model. Artif. Life 7, 293–299 (2000)

Sayama, H.: Seeking open-ended evolution in swarm chemistry. In: 2011 IEEE Symposium on Artificial Life (ALIFE), pp. 186–193. IEEE (2011)

Li, J., Storie, J., Clune, J.: Encouraging creative thinking in robots improves their ability to solve challenging problems. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 193–200. ACM (2014)

Soros, L., Stanley, K.O.: Identifying necessary conditions for open-ended evolution through the artificial life world of chromaria. Artif. life 14, 793–800 (2014)

Basener, W.F.: Exploring the concept of open-ended evolution. In: Biological Information: New Perspectives, pp. 87–104. World Scientific (2012)

Bedau, M.A., McCaskill, J.S., Packard, N.H., Rasmussen, S., Adami, C., Green, D.G., Ikegami, T., Kaneko, K., Ray, T.S.: Open problems in artificial life. Artif. life 6(4), 363–376 (2000)CrossRef

Ruiz-Mirazo, K., Peretó, J., Moreno, A.: A universal definition of life: autonomy and open-ended evolution. Orig. Life Evol. Biosph. 34(3), 323–346 (2004)CrossRef

10.

Ruiz-Mirazo, K., Umerez, J., Moreno, A.: Enabling conditions for open-ended evolution. Biol. Philos. 23(1), 67–85 (2008)CrossRef

11.

Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm Intelligence: from Natural to Artificial Systems, vol. 1. Oxford University Press, Oxford (1999)MATH

12.

Ewert, W., Marks, R.J., Thompson, B.B., Yu, A.: Evolutionary inversion of swarm emergence using disjunctive combs control. IEEE Trans. Syst. Man Cybern. Syst. 43(5), 1063–1076 (2013)CrossRef

13.

Roach, J., Ewert, W., Marks, R.J., Thompson, B.B.: Unexpected emergent behaviors from elementary swarms. In: 2013 45th Southeastern Symposium on System theory (SSST), pp. 41–50. IEEE (2013)

14.

Roach, J.H., Marks, R.J., Thompson, B.B.: Recovery from sensor failure in an evolving multiobjective swarm. IEEE Trans. Syst. Man Cybern. Syst. 45(1), 170–174 (2015)CrossRef

15.

Taylor, T.: Exploring the concept of open-ended evolution. In: Proceedings of the 13th International Conference on Artificial life, pp. 540–541 (2012)

16.

Jakobi, N.: Encoding scheme issues for open-ended artificial evolution. In: Voigt, H.-M., Ebeling, W., Rechenberg, I., Schwefel, H.-P. (eds.) PPSN 1996. LNCS, vol. 1141, pp. 52–61. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61723-X_969CrossRef

17.

Channon, A.: Three evolvability requirements for open-ended evolution. In: Artificial Life VII Workshop Proceedings, Portland, OR, pp. 39–40 (2000)

18.

Mueller, I.: Euclid’s elements and the axiomatic method. Br. J. Philos. Sci. 20(4), 289–309 (1969)MathSciNetMATHCrossRef

19.

Shenoy, P.P., Shafer, G.: Axioms for probability and belief-function propagation. In: Yager, R.R., Liu, L. (eds.) Classic Works of the Dempster-Shafer Theory of Belief Functions. STUDFUZZ, vol. 219, pp. 499–528. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-44792-4_20CrossRef

20.

Chaitin, G.J.: Algorithmic information theory. IBM J. Res. Dev. 21(4), 350–359 (1977)MathSciNetMATHCrossRef

21.

Raatikainen, P.: On interpreting Chaitin’s incompleteness theorem. J. Philos. Log. 27(6), 569–586 (1998)MathSciNetMATHCrossRef

22.

Chaitin, G.J.: Information, Randomness & Incompleteness: Papers on Algorithmic Information Theory, vol. 8. World Scientific, Singapore (1990)MATHCrossRef

23.

Grünwald, P.D., Vitányi, P.M., et al.: Algorithmic information theory. In: Handbook of the Philosophy of Information, pp. 281–320 (2008)CrossRef

24.

Seibt, P.: Algorithmic Information Theory. Springer, Heidelberg (2006). https://doi.org/10.1007/978-3-540-33219-0MATHCrossRef

25.

Van Lambalgen, M.: Algorithmic information theory. J. Symb. Log. 54(4), 1389–1400 (1989)MathSciNetMATHCrossRef

26.

Chaitin, G.: Proving Darwin: Making Biology Mathematical. Vintage, New York (2012)MATH

27.

Chaitin, G.J.: Toward a mathematical definition of life. In: Information, Randomness & Incompleteness: Papers on Algorithmic Information Theory, pp. 86–104. World Scientific (1987)

28.

Gecow, A.: The purposeful information. On the difference between natural and artificial life. Dialogue Univers. 18(11/12), 191–206 (2008)CrossRef

29.

Pattee, H.H.: Artificial life needs a real epistemology. In: Morán, F., Moreno, A., Merelo, J.J., Chacón, P. (eds.) ECAL 1995. LNCS, vol. 929, pp. 21–38. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-59496-5_286CrossRef

30.

Chaitin, G.J.: The Unknowable. Springer Science & Business Media, Heidelberg (1999)MATH

31.

Bennett, C.H., Gács, P., Li, M., Vitanyi, P., Zurek, W.H.: Information distance. arXiv preprint arXiv:1006.3520 (2010)

32.

Calude, C.S.: Algorithmic randomness, quantum physics, and incompleteness. In: Margenstern, M. (ed.) MCU 2004. LNCS, vol. 3354, pp. 1–17. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31834-7_1CrossRef

33.

Ming, L., Vitányi, P.M.: Kolmogorov complexity and its applications. Algorithms Complex. 1, 187 (2014)MATH

34.

Vitányi, P.M., Li, M.: Minimum description length induction, Bayesianism, and Kolmogorov complexity. IEEE Trans. Inf. Theory 46(2), 446–464 (2000)MathSciNetMATHCrossRef

35.

Wallace, C.S., Dowe, D.L.: Minimum message length and Kolmogorov complexity. Comput. J. 42(4), 270–283 (1999)MATHCrossRef

36.

Muller, G.B., Wagner, G.P.: Novelty in evolution: restructuring the concept. Ann. Rev. Ecol. Syst. 22(1), 229–256 (1991)CrossRef

37.

Pigliucci, M.: What, if anything, is an evolutionary novelty? Philos. Sci. 75(5), 887–898 (2008)CrossRef

38.

Li, X., Croft, W.B.: An information-pattern-based approach to novelty detection. Inf. Process. Manag. 44(3), 1159–1188 (2008)CrossRef

39.

Zhao, L., Zhang, M., Ma, S.: The nature of novelty detection. Inf. Retr. 9(5), 521–541 (2006)CrossRef

40.

Kowaliw, T., Dorin, A., McCormack, J.: An empirical exploration of a definition of creative novelty for generative art. In: Korb, K., Randall, M., Hendtlass, T. (eds.) ACAL 2009. LNCS (LNAI), vol. 5865, pp. 1–10. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10427-5_1CrossRef

41.

Chandola, V., Banerjee, A., Kumar, V.: Anomaly detection: a survey. ACM Comput. Surv. (CSUR) 41(3), 15 (2009)CrossRef

42.

Venkatasubramanian, V., Rengaswamy, R., Yin, K., Kavuri, S.N.: A review of process fault detection and diagnosis: part I: quantitative model-based methods. Comput. Chem. Eng. 27(3), 293–311 (2003)CrossRef

43.

Hodge, V., Austin, J.: A survey of outlier detection methodologies. Artif. Intell. Rev. 22(2), 85–126 (2004)MATHCrossRef

44.

Pimentel, M.A., Clifton, D.A., Clifton, L., Tarassenko, L.: A review of novelty detection. Sig. Process. 99, 215–249 (2014)CrossRef

45.

Reed, R., Marks, R.J.: Neural Smithing: Supervised Learning in Feedforward Artificial Neural Networks. MIT Press, Cambridge (1999)CrossRef

46.

Thompson, B.B., Marks, R.J., Choi, J.J., El-Sharkawi, M.A., Huang, M.Y., Bunje, C.: Implicit learning in autoencoder novelty assessment. In: 2002 Proceedings of the 2002 International Joint Conference on Neural Networks, IJCNN 2002, vol. 3, pp. 2878–2883. IEEE (2002)

47.

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

48.

Mouret, J.B.: Novelty-based multiobjectivization. In: Doncieux, S., Bredèche, N., Mouret, J.B. (eds.) New Horizons in Evolutionary Robotics. SCI, vol. 341, pp. 139–154. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-18272-3_10CrossRef

Titel: Observation of Unbounded Novelty in Evolutionary Algorithms is Unknowable
verfasst von: Eric Holloway
Robert Marks
Verlag: Springer International Publishing
Buch: Artificial Intelligence and Soft Computing
Print ISBN: 978-3-319-91252-3

Electronic ISBN: 978-3-319-91253-0

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-91253-0_37

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"