nach oben

Evolutionary Intelligence

Erschienen in:

01.03.2015 | Special Issue

A semantic network-based evolutionary algorithm for computational creativity

verfasst von: Atılım Güneş Baydin, Ramon López de Mántaras, Santiago Ontañón

Erschienen in: Evolutionary Intelligence | Ausgabe 1/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We introduce a novel evolutionary algorithm (EA) with a semantic network-based representation. For enabling this, we establish new formulations of EA variation operators, crossover and mutation, that we adapt to work on semantic networks. The algorithm employs commonsense reasoning to ensure all operations preserve the meaningfulness of the networks, using ConceptNet and WordNet knowledge bases. The algorithm can be interpreted as a novel memetic algorithm (MA), given that (1) individuals represent pieces of information that undergo evolution, as in the original sense of memetics as it was introduced by Dawkins; and (2) this is different from existing MA, where the word “memetic” has been used as a synonym for local refinement after global optimization. For evaluating the approach, we introduce an analogical similarity-based fitness measure that is computed through structure mapping. This setup enables the open-ended generation of networks analogous to a given base network.

Vorheriger Artikel Special issue on creative intelligence

Nächster Artikel Monterey Mirror: an experiment in interactive music performance combining evolutionary computation and Zipf’s law

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

From a biological perspective, this sense emphasizes the effect of society, culture, and learning on the survival of individuals on top of their physical traits emerging through genetic evolution. An example would be the use of knowledge and technology by the human species to survive in diverse environments, far beyond the physical capabilities available to them solely by the human anatomy.

Or, information, idea, or belief.

Quoting Dawkins [9]: “Examples of memes are tunes, ideas, catch-phrases, clothes fashions, ways of making pots or of building arches. Just as genes propagate themselves in the gene pool by leaping from body to body via sperms or eggs, so memes propagate themselves in the meme pool by leaping from brain to brain...”.

This is in stark contrast with approaches such as GA, where a crossover operation of identical parents would yield identical offspring due to the linear nature of the representation

http://www.cyc.com/.

http://conceptnet5.media.mit.edu/.

http://rtw.ml.cmu.edu/rtw/.

http://wordnet.princeton.edu.

http://www.wikimedia.org/.

http://dbpedia.org/.

The default reliability score for a statement is 1 [19]; and zero or negative reliability scores are a good indication of information that can be considered noise.

Another definition of synset is that it is a set of synonyms that are interchangeable without changing the truth value of any propositions in which they are embedded.

Diversity, in EA, is a measure of homogeneity of the individuals in the population. A drop in diversity indicates an increased number of identical individuals, which is not desirable for the progress of evolution.

We define two concepts from different semantic networks as interchangeable if both can replace the other in all, or part, of the relations the other is involved in, queried from commonsense knowledge bases.

We define a distinct concept as attachable to a semantic network if at least one commonsense relation connecting the concept to any of the concepts in the network can be discovered from commonsense knowledge bases.

Kepler argued, in his Astronomia Nova, as light can travel undetectably on its way between the source and destination, and yet illuminate the destination, so can motive force be undetectable on its way from the Sun to planet, yet affect planet’s motion.

Readily available by using WordNet [34].

For ConceptNet version 4: IsA, HasA, PartOf, UsedFor, AtLocation, CapableOf, MadeOf, CreatedBy, HasSubevent, HasFirstSubevent, HasLastSubevent, HasPrerequisite, MotivatedByGoal, Causes, Desires, CausesDesire, HasProperty, ReceivesAction, DefinedAs, SymbolOf, LocatedNear, ObstructedBy, ConceptuallyRelatedTo, InheritsFrom.

Balkin JM (1998) Cultural software: a theory of ideology. Yale University Press, New Haven

Bedau MA, Snyder E, Brown CT (1997) A comparison of evolutionary activity in artificial evolving systems and in the biosphere. In: Husbands P, Harvey I (eds) Proceedings of the fourth European conference on artificial life. MIT Press, Cambridge, pp 125–134

Bickhard MH, Campbell DT (2003) Variations in variation and selection: the ubiquity of the variation-and-selective-retention ratchet in emergent organizational complexity. Found Sci 8:215–2182CrossRef

Boden MA (2009) Computer models of creativity. AI Mag 30(3):23–34

Chafe E (1991) Tonal allegory in the vocal music of JS Bach. University of California Press, Berkeley

Chen D, Aoki T, Homma N, Terasaki T, Higuchi T (2002) Graph-based evolutionary design of arithmetic circuits. IEEE Trans Evolut Comput 6(1):86–100CrossRef

Clement J (1988) Observed methods for generating analogies in scientific problem solving. Cogn Sci 12:563–586CrossRef

Colton S, Wiggins G (2012) Computational creativity: the final frontier? In: de Raedt C, Bessiere C, Dubois D, Doherty P (eds) Proceedings of the 20th European conference on artificial intelligence. IOS Press, Amsterdam, pp 21–26

Dawkins R (1976) The selfish gene. Oxford University Press, New York City

10.

Dennett DC (1995) Darwin’s dangerous idea: evolution and the meanings of life. Simon & Schuster, NY

11.

Diochnos DI (2013) Commonsense reasoning and large network analysis: a computational study of ConceptNet 4 http://arxiv.org/abs/1304.5863

12.

Falkenhainer B, Forbus KD, Gentner D (1989) The structure-mapping engine: algorithm and examples. Artif Intell 41:1–63CrossRefMATH

13.

Fauconnier G, Mark T (2002) The way we think: conceptual blending and the mind’s hidden complexities. Basic Books, New York

14.

Fellbaum C (1998) WordNet: an electronic lexical database. MIT Press, CambridgeMATH

15.

French RM (2002) The computational modeling of analogy-making. Trends Cogn Sci 6(5):200–205CrossRef

16.

Gabora L, Kaufman SB (2010) Evolutionary approaches to creativity. Cambridge University Press, Cambridge

17.

Gentner D (1983) Structure-mapping: a theoretical framework for analogy. Cogn Sci 7:155–170CrossRef

18.

Gil-White F (2008) Let the meme be (a meme): insisting too much on the genetic analogy will turn it into a straightjacket. In: Botz-Bornstein T (ed) Culture, nature, memes. Cambridge Scholars, Newcastle upon Tyne

19.

Havasi C, Speer R, Alonso J (2007) ConceptNet 3: a flexible, multilingual semantic network for common sense knowledge. In: Proceedings of recent advances in natural language processing

20.

Hofstadter DR (1995) Fluid concepts and creative analogies: computer models of the fundamental mechanisms of thought. Basic Books, New York

21.

Hofstadter DR (2001) Analogy as the core of cognition. In: Gentner D, Holyoak KJ, Kokinov B (eds) Analogical mind: perspectives from cognitive science. MIT Press, Cambridge, pp 499–538

22.

Hofstadter DR, Dennett DC (1981) The mind’s I: fantasies and reflections on self and soul. Basic, New YorkMATH

23.

Koza JR, Keane MA, Streeter MJ, Mydlowec W, Yu J, Lanza G (2003) Genetic programming IV: routine human-competitive machine intelligence. Kluwer, Dordrecht

24.

Kuo YL, Hsu J (2010) Bridging common sense knowledge bases with analogy by graph similarity. In: Workshops at the twenty-fourth AAAI conference on artificial intelligence

25.

Larkey LB, Love BC (2003) CAB: connectionist analogy builder. Cogn Sci 27(2003):781–794CrossRef

26.

Mabu S, Hirasawa K, Hu J (2007) A graph-based evolutionary algorithm: genetic network programming (GNP) and its extension using reinforcement learning. Evol Comput 15(3):369–398CrossRef

27.

Manurung HM (2003) An evolutionary algorithm approach to poetry generation. Ph.D. thesis, University of Edinburgh, Edinburgh, UK

28.

Martindale C, Locher P, Petrov VM (2007) Evolutionary and neurocognitive approaches to aesthetics, creaticity and the arts. Foundations and frontiers of aesthetics, Baywood Publishing Company

29.

McCarthy J (1958) Programs with common sense. In: Symposium on mechanization of thought processes. National Physical Laboratory, Teddington

30.

Minsky M (2006) Emotion machine: commonsense thinking, artificial intelligence, and the future of the human mind. Simon & Schuster, New York

31.

Montes HA, Wyatt JL (2004) Graph representation for program evolution: an overview. Tech. rep., University of Birmingham School of Computer Science

32.

Moscato PA, Cotta C, Mendes A (2004) Studies in fuzziness and soft computing—new optimization techniques in engineering, chap. memetic algorithms. Springer, New York

33.

Mueller ET (2006) Commonsense reasoning. Morgan Kaufmann, Los Altos

34.

Pedersen T, Patwardhan S, Michelizzi J (2004) Wordnet: similarity: measuring the relatedness of concepts. In: Demonstration papers at HLT-NAACL 2004, pp 38–41. Association for Computational Linguistics

35.

Pereira FB, Machado P, Costa E, Cardoso A (1999) Graph based crossover—a case study with the busy beaver problem. In: Proceedings of the genetic and evolutionary computation conference, vol 2. Morgan Kaufmann, Los Altos, pp 1149–1155

36.

Pereira FC (2007) Creativity and artificial intelligence: a conceptual blending approach. Mouton de Gruyter, New York

37.

Pezzotta E (2012) The metaphor of dance in Stanley Kubrick’s 2001: A space odyssey, a clockwork orange and full metal jacket. J Adapt Film Perform 5(1):51–64

38.

Pohlheim H (2006) Genetic and evolutionary algorithm toolbox documentation http://www.geatbx.com/docu/algindex-02.html

39.

Poli R (1999) New ideas in optimisation, chap. parallel distributed genetic programming. McGraw-Hill, New York

40.

Skusa A, Bedau MA (2002) Towards a comparison of evolutionary creativity in biological and cultural evolution. In: Standish R, Abbass HA, Bedau MA (eds) Artificial life VIII. MIT Press, Cambridge, pp 233–242

41.

Sowa JF (2000) Knowledge representation: logical philosophical, and computational foundations. Brooks/Cole, Pacific Grove

42.

Spears WM (1992) Foundations of genetic algorithms 2, chap. crossover or mutation?. Morgan Kaufmann, Los Altos, pp 221–237

43.

Teller A (1998) Algorithm evolution with internal reinforcement for signal understanding. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA

44.

Veale T, Keane M (1997) The competence of sub-optimal structure mapping on hard analogies. In: Proceedings of the 15th international joint conference on AI. Morgan Kauffman, San Mateo

45.

Zhu J, Ontañón S (2013) Evaluating analogy-based story generation: an empirical study. In: Proceedings of the 9th annual AAAI conference on artificial intelligence and interactive digital entertainment (AIIDE 2013). Boston, MA

Titel: A semantic network-based evolutionary algorithm for computational creativity
verfasst von: Atılım Güneş Baydin
Ramon López de Mántaras
Santiago Ontañón
Publikationsdatum: 01.03.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Evolutionary Intelligence / Ausgabe 1/2015
Print ISSN: 1864-5909
Elektronische ISSN: 1864-5917
DOI: https://doi.org/10.1007/s12065-014-0119-1

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"