Genetic Evolution of Source Code

Question

I am curious about writing code in C# that "writes itself". I know that this is not possible in a broad sense, but I was thinking about setting up some kind of format for a dynamic assembly that defines everything except the body of some target function. Then an algorithm or maybe neural nets attempt to fill in the function body. After this the assembly is then executed, and the newly launched assembly then attempts to call the target function and after that creates another new assembly based of the same code, with hopefully a better implementation of that target function.

Given this kind of behavior would C# and dynamic assemblies be a suitable choice (I am concerned about the amount of time creating, and executing the assemblies would take). Is there some language that specializes in dynamically creating code to be executed, or is C# a good enough option?

Also any comments on the approach or setup of this whole assemblies creating assemblies idea is welcome, and appreciated! (I am very new if you couldn't tell)

Thanks!

Answer 1

I may be wrong, but it sounds very much like you are interested in Genetic Programming. A good base would be some reading (I would recommend this book on machine learning, it's great).

Specifically for Genetic Programming you could try GPdotNET, but for broader Machine Learning I would definitely look at the Accord .NET Framework. The guy behind Accord writes a great blog that which could be useful too.

Answer 2

If you want to "evolve" source code you have to be able to manipulate it. This is most easily done with Abstract Syntax Trees. Tools that make ASTs easy to manipulate are called program transformation systems, and these can encode source-to-source transformation rules that can act as genetic mutations.

One such rule code for our DMS Software Reengineering Toolkit would look like:

 swap_operators(x:product,y:term): sum-> sum
       "\x + \y " ->  "\x - \y" if  somecondition();

This replaces "+" by "-", if it is applied. You'd ideally have a bunch of these "crossover" operators (switching operators, changing expresssion precedence, change variables mentioned, changing control structures, etc.) and "somecondition"s that control whether the crossover operator is applied as part of an evolution step.

You need other means to compile/run/evaluate the fitness of the evolved program.

To do something like this with DMS, you'd have DMS read (parse to AST) a baseline program ("initial generation"), apply a set of evolution transforms, emit code for the modified ASTs, compile and run them (DMS can invoke subprocesses like "compile" and execute), evaluate the result pick the top N of this generation, apply evolution operators again, repeat until nirvana or your electric bill overflows.

Answer 3

C# is suitable for genetic programming, especially now that the dynamic language runtime is in the .NET framework and accessible with C#'s dynamic keyword.

GeneticProgramming .NET is a project that might get you off the ground. There was also an MSDN article on genetic programming with C# and Windows Forms a few years ago: Natural Selection with C#.

Answer 4

Mutating the code randomly doesnt make linear changes. Your small changes should mostly carry you to success. So it is not different from brute-force. Genetic algorithm will be draft into a state of chaos.