Efficient List Search Algorithms

author = "Kfir Wolfson and Moshe Sipper",

title = "Efficient List Search Algorithms",

booktitle = "9th International Conference, Evolution Artificielle, EA 2009",

year = "2009",

editor = "Pierre Collet and Nicolas Monmarche and Pierrick Legrand and Marc Schoenauer and Evelyne Lutton",

volume = "5975",

series = "Lecture Notes in Computer Science",

pages = "158--169",

address = "Strasbourg, France",

month = oct # " 26-28",

publisher = "Springer",

note = "Revised Selected Papers",

keywords = "genetic algorithms, genetic programming",

isbn13 = "978-3-642-14155-3",

URL = "

http://www.cs.bgu.ac.il/~wolfsonk/sublinear_draft.pdf",

DOI = "

doi:10.1007/978-3-642-14156-0_14",

size = "12 pages",

abstract = "We peruse the idea of algorithmic design through Darwinian evolution, focusing on the problem of evolving list search algorithms. Specifically, we employ genetic programming (GP) to evolve iterative algorithms for searching for a given key in an array of integers. Our judicious design of an evolutionary language renders the evolution of linear-time search algorithms easy. We then turn to the far more difficult problem of logarithmic-time search, and show that our evolutionary system successfully handles this case. Subsequently, because our setup might be perceived as being geared towards the emergence of binary search, we generalise our genomic representation, allowing evolution to assemble its own useful functions via the mechanism of automatically defined functions (ADFs). We show that our approach routinely and repeatedly evolves general and correct efficient algorithms.",

notes = "EA'09 Published 2010. ECJ, memory Array[INDEX] M0 M1 KEY NOP setm0 progn2 if <>== ITER iteration Java. Pop 250, 5000 generations. p168 'Our phenotypes are not Turing complete'",