6

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)

seaotternerd
  • 6,298
  • 2
  • 47
  • 58
Josh Reuben
  • 577
  • 3
  • 20
  • you might wanna have a look at this question for a discussion on what genetic programming can or cannot do --> http://stackoverflow.com/questions/5732917/code-generation-by-genetic-algorithms – JohnIdol Apr 26 '11 at 10:11

3 Answers3

3

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.

Ry-
  • 218,210
  • 55
  • 464
  • 476
Sniggerfardimungus
  • 11,583
  • 10
  • 52
  • 97
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...

G__
  • 7,003
  • 5
  • 36
  • 54
1

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.

Charlie Martin
  • 110,348
  • 25
  • 193
  • 263
  • Charlie, just curious, how would you breed the next generation? I can't seem to grasp the fact of crossing sort and sort to create a new algorithm. Sorting algorithms differentiate in their whole approach to the task, not just parameters that you could play with. – pnt Feb 06 '11 at 18:30
  • 1
    That really is sort of the key problem. Remember that at the core, a GA makes progress by making lots of random changes and looking for one that's "better" by the fitness function. Same problem happens in biological evolution -- you might evolve from a fish to a bird, but anything that takes you much closer to bird is going to drown before it reproduces. – Charlie Martin Feb 06 '11 at 18:59
  • Another good example is the panda: it's very well suited to two things -- eating bamboo and being cute. The quiet bamboo forest niche is going away, and so they're endangered. On the other hand, it might just be that "being cute" is the characteristic that ensures continued survival. – Charlie Martin Feb 06 '11 at 19:01
  • Yes, but how would a GA make random changes in a sorting algorithm? There really are not that much properties that could be set and they differ a lot with different algorithms so there can't be a unified approach that takes two random algorithms and creates a new one by using property "A" from the first one and property "B" from the second one. You could have a pool and choose from it based on a performance rating function, but how would you combine them in a new breed not only semantically, but purely syntactically? – pnt Feb 06 '11 at 19:35
  • Ah, but I'm a theory guy and that's an implementation question. Seriously, you *could* just make random changes to program strings as instructions or even as ASCII text; it would just be very slow to get to a generation that did anything. Without giving it a ton of thought, I'd think about using sorting networks as the underlying "codons" http://en.wikipedia.org/wiki/Sorting_network. At least then you have something that will be a "sorting algorithm" every time, even if it's not particularly efficient, or even useful. – Charlie Martin Feb 06 '11 at 21:48
  • But it's still a real problem -- GA is generally a hill-climbing sort of thing. If you already have a good algorithm, like quicksort, any random mutation is likely to be "less fit" than its mutated "children". – Charlie Martin Feb 06 '11 at 21:51