Have your spaghetti and eat it too: evolutionary algorithmics and post-evolutionary analysis

Created by W.Langdon from gp-bibliography.bib Revision:1.3872

@Article{Wolfson:2011:GPEM,
  author =       "Kfir Wolfson and Shay Zakov and Moshe Sipper and 
                 Michal Ziv-Ukelson",
  title =        "Have your spaghetti and eat it too: evolutionary
                 algorithmics and post-evolutionary analysis",
  journal =      "Genetic Programming and Evolvable Machines",
  year =         "2011",
  volume =       "12",
  number =       "2",
  pages =        "121--160",
  month =        jun,
  keywords =     "genetic algorithms, genetic programming, Darwinian
                 Software Engineering, Search algorithms,
                 Post-evolutionary analysis, Edit distance, Reasoning,
                 Building blocks",
  ISSN =         "1389-2576",
  URL =          "http://www.cs.bgu.ac.il/~wolfsonk/gpea_draft.pdf",
  DOI =          "doi:10.1007/s10710-010-9122-1",
  size =         "40 pages",
  abstract =     "This paper focuses on two issues, first perusing the
                 idea of algorithmic design through genetic programming
                 (GP), and, second, introducing a novel approach for
                 analysing and understanding the evolved solution trees.
                 Considering the problem of list search, we evolve
                 iterative algorithms for searching for a given key in
                 an array of integers, showing that both correct
                 linear-time and far more efficient logarithmic-time
                 algorithms can be repeatedly designed by Darwinian
                 means. Next, we turn to the (evolved) dish of spaghetti
                 (code) served by GP. Faced with the all-too-familiar
                 conundrum of understanding convoluted and usually
                 bloated GP-evolved trees, we present a novel analysis
                 approach, based on ideas borrowed from the field of
                 bioinformatics. Our system, dubbed G-PEA (GP
                 Post-Evolutionary Analysis), consists of two parts: (1)
                 Defining a functionality-based similarity score between
                 expressions, G-PEA uses this score to find subtrees
                 that carry out similar semantic tasks; (2) Clustering
                 similar sub-expressions from a number of independently
                 evolved fit solutions, thus identifying important
                 semantic building blocks ensconced within the
                 hard-to-read GP trees. These blocks help identify the
                 important parts of the evolved solutions and are a
                 crucial step in understanding how they work. Other
                 related GP aspects, such as code simplification, bloat
                 control, and building-block preserving crossover, may
                 be extended by applying the concepts we present.",
}

Genetic Programming entries for Kfir Wolfson Shay Zakov Moshe Sipper Michal Ziv-Ukelson

Citations