Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Evolutionary Intelligence
Published in: Evolutionary Intelligence 1/2015

01-03-2015 | Special Issue

A semantic network-based evolutionary algorithm for computational creativity

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

Published in: Evolutionary Intelligence | Issue 1/2015

Log in

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

search-config
loading …

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.
previous article Special issue on creative intelligence
next article Monterey Mirror: an experiment in interactive music performance combining evolutionary computation and Zipf’s law

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
Footnotes
1
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.
 
2
Or, information, idea, or belief.
 
3
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...”.
 
4
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
 
11
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.
 
12
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.
 
13
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.
 
14
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.
 
15
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.
 
16
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.
 
17
Readily available by using WordNet [34].
 
18
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.
 
Literature
1.
Balkin JM (1998) Cultural software: a theory of ideology. Yale University Press, New Haven
2.
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
3.
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
4.
Boden MA (2009) Computer models of creativity. AI Mag 30(3):23–34
5.
Chafe E (1991) Tonal allegory in the vocal music of JS Bach. University of California Press, Berkeley
6.
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
7.
Clement J (1988) Observed methods for generating analogies in scientific problem solving. Cogn Sci 12:563–586CrossRef
8.
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
9.
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.
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.
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
Metadata
Title
A semantic network-based evolutionary algorithm for computational creativity
Authors
Atılım Güneş Baydin
Ramon López de Mántaras
Santiago Ontañón
Publication date
01-03-2015
Publisher
Springer Berlin Heidelberg
Published in
Evolutionary Intelligence / Issue 1/2015
Print ISSN: 1864-5909
Electronic ISSN: 1864-5917
DOI
https://doi.org/10.1007/s12065-014-0119-1

Premium Partner

    Image Credits