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

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

@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