Genetic Programming and Search Algorithms

Question

Is Genetic Programming currently capable of evolving one type of search algorithm into another? For example, has any experiment ever ever bred / mutated BubbleSort from QuickSort (see http://en.wikipedia.org/wiki/Sorting_algorithm)

Answer 1

You might want to look at the work of W. Daniel Hillis from the 80s. He spent a great deal of time creating sorting networks by genetic programming. While he was more interested in solving the problem of sorting a constant number of objects (16-object sorting networks had been a major academic problem for nearly a decade,) it would be a good idea to be familiar with his work if you're really interested in genetic sorting algorithms.

In the evolution of an algorithm for sorting a list of arbitrary length, you might also want to be familiar with the concept of co-evolution. I've built a co-evolutionary system before where the point was to have one genetic algorithm evolving sorting algorithms while another GA develops unsorted lists of numbers. The fitness of the sorter is its accuracy (plus a bonus for fewer comparisons if it is 100% accurate) and the fitness of the list generator is how many errors sort algorithms make in sorting its list.

To answer your specific question of whether bubble had ever been evolved from quick, I would have to say that I would seriously doubt it, unless the programmer's fitness function was both very specific and ill-advised. Yes, bubble is very simple, so maybe a GP whose fitness function was accuracy plus program size would eventually find bubble. However, why would a programmer select size instead of number of comparisons as a fitness function when it is the latter that determines runtime?

By asking if GP can evolve one algorithm into another, I'm wondering if you're entirely clear on what GP is. Ideally, each unique chromosome defines a unique sort. A population of 200 chromosomes represents 200 different algorithms. Yes, quick and bubble may be in there somewhere, but so are 198 other, potentially unnamed, methods.

Answer 2

There's no reason why GP couldn't evolve e.g. either type of algorithm. I'm not sure that it really makes sense to think of evolving one "into" the other. GP will simply evolve a program that comes ever-closer to a fitness function you define.

If your fitness function only looks at sort correctness (and assuming you have the proper building blocks for your GP to use) then it could very well evolve both BubbleSort and QuickSort. If you also include efficiency as a measure of fitness, then that might influence which of these would be determined as a better solution.

You could seed the GP with e.g. QuickSort and if you had an appropriate fitness function it certainly could eventually come up with BubbleSort - but it could come up with anything else that is fitter than QuickSort as well.

Now how long it takes the GP engine to do this evolution is another question...

Answer 3

I'm not aware of one, and the particular direction you're suggesting in your example seems unlikely; it would take a sort of perverse fitness function, since bubble sort is in most measures worse than quicksort. It's not inconceivable that this could happen, but in general once you've got a well-understood algorithm, it's already pretty fit -- going to another one probably requires passing through some worse choices.

Being trapped in local minima isn't an unknown problem for most search strategies.