Is it possible for evolutionary algorithms to create machine code? [closed]

Question

This is a question of general interest, as I am not trying to solve a specific problem. I have looked around to try to find some articles that cover this area, but am struggling to even put together some good search terms.

Let's start with what I know: I've got a university level education in AI, including genetic programming and the wider class of evolutionary algorithms, although I haven't played around with them much since I graduated ten years ago. I wonder whether or not these approaches could be used to create machine code to solve problems (perhaps x86, or some 'arbitrary' instruction set). Could we evolve algorithms themselves, such as one that could calculate square roots, or draw pleasing images on the screen? Could an evolutionary algorithm be used to create whole compilers that create optimised code (for size, speed etc)?

Additionally, I've often thought that genetic programming or evolutionary algorithms are not good evidence by themselves of the evolution of species. Problem solving approaches involving evolutionary algorithms always seem to need intelligence written into them. How does a person create a truly evolutionary algorithm, in such a way that genuinely interesting and surprising results could truly occur?

TLDR: Can the use of evolutionary algorithms ever be useful in creating a sort of machine code, and are there previous examples of evolutionary algorithms in general producing truly interesting and surprising results?

Nick

Virtual

I solved quadratic equation by genetic algorithm as well as i read about genetic algo, you can also draw images randomly. – Offoffbroadway

Machine code isn't a good raw genome for GAs due to the fact that the vast majority of random sequences are inherently malformed (won't even run, let alone do something useful.) This isn't to say that GAs can't be used to evolve interesting code, but you need to carefully choose the nature of the genome (in particular, its interpretation) and the fitness function you wish to apply. You could try using machine code, but I suspect you'd have serious convergence problems. – Randi

I think it all depends on what you mean by "create machine code". You can always create some virtual set of instructions that get compiled or translated into machine code. Take for example this: msdn.microsoft.com/en-us/magazine/cc163934.aspx (stolen from #14508 although strictly speaking, they're compiling C#/.NET) – Manpower

I've read in some article or a book about producing optimal expression-evaluating Forth code with GAs. It's possible. – Pettifogger

Answer 1

One thing that makes evolution in nature work is that it is very open-ended; you just have to find a way, any way, to pass on your genes, and there is a whole spectrum of varying success rates.

Programs, by contrast, are expected to do something very specific, and usually either work or don't. For genetic algorithms, small changes need to be able to contribute small (or large) improvements in order to climb in the fitness landscape. But the fitness landscape for programs is horrendous.

To put it another way: there are an infinite number of programs that "almost" sort a list that are completely different from a program that does sort a list, and therefore cannot be made into one by a small mutation. Most programs that do sort a list also break horribly with just one mutation, rather than producing a result that is almost correct, whatever that means. These combined mean that it is very hard to produce such an algorithm (or any algorithm) by evolution by small gradual degrees.

At least, this is what I think I learned when I tried to do something similar. I would love to be proven wrong.

Struble

Actually, sorting networks (a predefined set of comparisons guaranteed to sort n values) were among the first successful examples of highly-competent programs generated using evolutionary techniques. Danny Hillis used an evolutionary technique to generate very good sorting networks: kk.org/outofcontrol/ch15-d.html – Pertain

Answer 2

Can GP produce executable code? Sure! Just use LISP.

John Koza long ago established that you could use genetic programming to create programs. http://www.genetic-programming.com/johnkoza.html He wrote 2 very thick books on the subject.

The reason that most GP has been done in LISP is that machine code is extremely structured, so it's not feasible to your genome-to-phenome mapping "Let 00000 be MOV, let 00001 be JNE, etc." Instead, you essentially have to work with a more complex encoding. S-expressions emerge as the really obvious building blocks.

Pertain

Answer 3

I know of at least one approach that is called FINCH which is a methodology to evolve Java byte code. They have some presentations and reference publications on their site. I think byte code is probably easier to evolve than x86 machine code since that's code for a stack machine and not a register machine. Register machines are much more complex since you need to align the register of the write instruction with the read instruction. On a stack machine you just push a value on the stack and the next operation reads it.

Thirsty