I read about genetic programming and decided to try to evolve a program that can sort numbers. Amazingly, after around two generations there was already a member of the population that could sort, and after about twenty the entire population could sort. The solutions found where something like this: 1)Start at the first number. 2)Repeat step 3- untill the list is sorted 3) IBR ---MR ---IAE ------IBL ---------SR ---------MR ------PROC2 ---------SR ---------MR Step three is the program that evolved. Here's how to read it: IBR/L = if the number to the right/left is bigger do the first thing, else, do the second MR = move one to the right IAE = if we're at the end do the first thing, else, do the second PROC2 = do both things SR = switch the current one with the one on the right. [edit] see my next post [/edit] The cool thing is that when I sat down and tried to solve this myself I came up with something very similar. I tested it with a list of the length of 10 and gave each program a maximum of 100 moves (a move is one run of the program). Now I'm going to try to also rate the programs by the amount of time it takes them to sort a list and see what comes out. What do you think? Any ideas on how I should proceed? [Edited by - daniel_i_l on November 9, 2007 6:46:44 AM]

Interesting. However, the main problem with evolving algorithms remains: you still need to provide a formal proof that the algorithm works. Looking at the one you provided, I have trouble imagining how it doesn't overflow the array.

I did a similar thing once. The general idea for my program was that i'd provide a simple set of operators that operated on a stack and evolved a program that could get from one integer to another.

It was quite interesting.

Oh, I forgot to say, at the end of the array then "right" means the beginning. And at the beginning "left" means the end. That's why there has to be a IAE condition - without it it'd be like sorting numbers on a circle. I don't know how to construct a formal proof but it's pretty easy to see how this particular program works.

That's cool, but I think the options you've given your program pretty much guide it to a particular solution(which I would guess is similar to bubble sort?). Using only neighbor swaps it's going to be difficult to get faster than O(n^2). I'd suggest giving it actions to make it possible for it to evolve an O(nlog(n)) sort. That would make it a lot more interesting.

What do you mean? Would giveing it the ability to swap and compare any two elements of the list be enough?

The problem is that your program imply a simplistic virtual machine. It should be hard to see an algorithm using divide and conquier strategy (like quicksort) to emerge. Quicksort require far more principle like recursion, by example, and recursion, which imply a stack... and so on :]

Quote: Original post by Alrecenk
That's cool, but I think the options you've given your program pretty much guide it to a particular solution(which I would guess is similar to bubble sort?). Using only neighbor swaps it's going to be difficult to get faster than O(n^2). I'd suggest giving it actions to make it possible for it to evolve an O(nlog(n)) sort. That would make it a lot more interesting.

I was going to say the same. I got the impression that you presupposed the conclusion though.

Make note that I am, in no way, discounting the cool factor of what you did. Just try to take it a bit further like alrecenk said.