Have your spaghetti and eat it too: evolutionary algorithmics and post-evolutionary analysis
Created by W.Langdon from
gp-bibliography.bib Revision:1.8098
- @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