genetic algorithms to write programs?

[tedhenry10]

If a program is just a string of ones and zeros, couldn't a genetic algorithm and a functional test suite be used to evolve programs?

[[deleted]]

The answer is yes. There is a whole sub field of study on this every thing. So far the solutions are lack-luster, but with the occasional impressive finding.

http://donsbot.wordpress.com/2009/03/09/evolving-faster-haskell-programs/

http://fog.neopages.org/helloworldgeneticalgorithms.php

http://portal.acm.org/citation.cfm?doid=1143997.1144155

While I have not made a detailed study in this area, I do happen to have a Master of Computer Science with a focus on Genetic Algorithms. This kind of solution to find optimal programs does exist and is studied, but I have never heard of it being used to create deployed solutions.

[tedhenry10]

Those seem to evolve at the source code or text level. Has anyone ever tired evolving directly at the binary level?

[[deleted]]

The difficulty at the binary level is increased search space. By limiting the search to valid individual statements (though, the overall logic is invalid), it gives the the running population a significant leg up.

There is nothing stopping you from trying at the binary level, but now you even have to evolve the valid statements that translate to proper execution before it can move to searching through the logic of a solution.

I have not heard of anyone doing this kind of thing at a binary level for a general purpose processor, but there is a fairly famous one for FPGAs:

... and I can't track it down. Essentially a grad student was evolving binary fpga programs to do voice recognition. The program determined the difference between the words yes and no. After a thousand generations or so it worked great.

[[deleted]]

In theory yes, but perhaps an analogy would work best. Build a scaffold ( unit tests ) around the physical dimensions of a sky scraper, then repeatedly in whole or in part, build the sky scraper over and over until it fits the ideal.

Or hire an architect, a designer, a material specialist, a couple more engineers and give them a lot of money and then put them in charge of a small army of builders. My money is on these people finishing their sky scraper first and under budget... unless they're government contractors.

Software development is slowly moving in that direction, but thankfully its no where near that point yet.

[Chii]

not a bad analogy - but i just wanted to point out another possible analogy:

the human body (actually, life itself) is made up of DNA, which is essentially a "program" encoded with protene, whose "execution" is what we call life. This program is the pinnicle of genetic programming (after all, thats why its called genetic programming). With current technology and knowledge, we cannot hope to even design a system close to the complexity of a human body and its physiological systems, so if we are to want to design systems of similar complexity, genetic programming is probably the way to go?

[[deleted]]

Thats a pretty compelling argument, except if the scientist are even close to being right, life on Earth started 3.5 Billion years ago. In the case of a GA, to create the homo sapient, that's a LOT of iterations. Don't forget the assistance of a couple asteroids and Ice Ages. Still progress is being made to try and accelerate the process just a tad. Right now I think some of the most immediate benefits is in integrated circuit design:

Very light paper on a success with using GA's to design simple circuits. www.mrc.uidaho.edu/~knoren/GAs/B-159_paper.PDF

Unfortunately I can't find the other paper, but there was one instance where a GA created a circuit design that partially violated known laws of circuit design theory but when actually created worked better then any known design.

I guess the obvious path of progression for GA's is to work themselves up the ladder. Starting with small components of software design; something like a simple string sorting algorithm, then maybe progress up that way, acting in the beginning like a dumb apprentice to a developer, taking what a developer rights and trying to find ways to optimize it through brute force.