Reflective evolutionary algorithm You have to write a program, implementing a function digitsum(int i). The program has to modify its own code (for languages, where this is not possible with f.e. reflection, please be creative) to get itself to solve the goal.

You start with 

function digitsum(int i){
    return i;
}


and implement an evolutionary algorithm that will modify the above function until it returns valid digitsums on function call. 

As this is a popularity contest, you have very much free hands, please be creative!

Guidelines:


Start with the defined function (translated to your language of course).
Print out at least the fittest function of each generation.
Print out your working solution tested for 0 &lt; i &lt; 10000.
Be creative!


Do not:


Hint your program to the solution, please use your whole language options!
Throw errors to the console.
Use any external input. You can write and save to files created by your program. No internet.


The valid solution with the most upvotes wins!
C#



This might not be completeley what you envisioned, but this is the best I could do right now. (At least with C# and CodeDom).

So how it works:


It calculates the digitsum base 2 (the base wasn't specified in the statement)
It tries to generate an expression with a lot of terms that look like ((i &amp; v1) &gt;&gt; v2). These terms will be the genes that will be mutated through the run.
The fitness function simply compares the values with a pre-calculated array, and uses the sum of the absolute value of the differences. This means a 0 value means we have arrived to the solution, and the less the value the fitter the solution.


The code:

using System;
using System.CodeDom;
using System.CodeDom.Compiler;
using Microsoft.CSharp;
using System.IO;
using System.Reflection;
using System.Collections.Generic;
using System.Linq;

namespace Evol
{
    class MainClass
    {
        const int BASE = 2;
        static int[] correctValues;
        static List&lt;Evolution&gt; values = new List&lt;Evolution&gt;();

        public static CodeCompileUnit generateCompileUnit(CodeStatementCollection statements) {
            CodeCompileUnit compileUnit = new CodeCompileUnit();
            CodeNamespace samples = new CodeNamespace("CodeGolf");
            compileUnit.Namespaces.Add(samples);
            samples.Imports.Add(new CodeNamespaceImport("System"));
            CodeTypeDeclaration digitSumClass = new CodeTypeDeclaration("DigitSum");
            samples.Types.Add(digitSumClass);
            CodeMemberMethod method = new CodeMemberMethod();
            method.Name = "digitsum";
            method.Attributes = MemberAttributes.Public | MemberAttributes.Static;
            method.ReturnType = new CodeTypeReference (typeof(int));
            method.Parameters.Add (new CodeParameterDeclarationExpression (typeof(int), "i"));
            method.Statements.AddRange (statements);
            digitSumClass.Members.Add(method);
            return compileUnit;
        }

        public static long CompileAndInvoke(CodeStatementCollection statements, bool printCode) {
            CompilerParameters cp = new CompilerParameters();
            cp.ReferencedAssemblies.Add( "System.dll" );
            cp.GenerateInMemory = true;
            CodeGeneratorOptions cgo = new CodeGeneratorOptions ();
            CodeDomProvider cpd = new CSharpCodeProvider ();
            CodeCompileUnit cu = generateCompileUnit (statements);
            StringWriter sw = new StringWriter();
            cpd.GenerateCodeFromCompileUnit(cu, sw, cgo);
            if (printCode) {
                System.Console.WriteLine (sw.ToString ());
            }

            var result = cpd.CompileAssemblyFromDom (cp, cu);

            if (result.Errors.Count != 0) {
                return -1;
            } else {
                var assembly = result.CompiledAssembly;
                var type = assembly.GetType ("CodeGolf.DigitSum");
                var method = type.GetMethod ("digitsum");
                long fitness = CalcFitness (method);
                return fitness;
            }
        }

        public static long CalcFitness(MethodInfo method) {
            long result = 0;
            for (int i = 0; i &lt; correctValues.Length; i++) {
                int r = (int)method.Invoke (null, new Object[] { i });
                result += Math.Abs (r - correctValues[i]);
            }
            return result;
        }

        public static CodeStatementCollection generateCodeDomFromString (Term[] terms) {
            CodeStatementCollection statements = new CodeStatementCollection ();
            CodeExpression expression = null;
            foreach (Term term in terms) {
                CodeExpression inner = new CodeArgumentReferenceExpression ("i");
                if (term.and.HasValue) {
                    inner = new CodeBinaryOperatorExpression (inner, CodeBinaryOperatorType.BitwiseAnd, new CodePrimitiveExpression(term.and.Value));
                }
                if (term.shift.HasValue) {
                    inner = new CodeBinaryOperatorExpression (inner, CodeBinaryOperatorType.Divide, new CodePrimitiveExpression(Math.Pow (2, term.shift.Value)));
                }
                if (expression == null) {
                    expression = inner;
                } else {
                    expression = new CodeBinaryOperatorExpression (expression, CodeBinaryOperatorType.Add, inner);
                }
            }
            statements.Add (new CodeMethodReturnStatement (expression));
            return statements;
        }


        public static void Main (string[] args)
        {
            correctValues = new int[10001];
            for (int i = 0; i &lt; correctValues.Length; i++) {
                int result = 0;
                int num = i;
                while (num != 0) {
                    result += num % BASE;
                    num /= BASE;
                }
                correctValues [i] = result;
            }
            values.Add (new Evolution (new Term[] { new Term (null, null) }));
            Random rnd = new Random ();
            while (true) {
                // run old generation
                foreach (var val in values) {
                    CodeStatementCollection stat = generateCodeDomFromString (val.term);
                    long fitness = CompileAndInvoke (stat, false);
                    val.score = fitness;
                    System.Console.WriteLine ("Fitness: {0}", fitness);
                }
                Evolution best = values.Aggregate ((i1, i2) =&gt; i1.score &lt; i2.score ? i1 : i2);
                CodeStatementCollection bestcoll = generateCodeDomFromString (best.term);
                CompileAndInvoke (bestcoll, true);
                System.Console.WriteLine ("Best fitness for this run: {0}", best.score);

                if (best.score == 0)
                    break;

                // generate new generation
                List&lt;Evolution&gt; top = values.OrderBy (i =&gt; i.score).Take (3).ToList();
                values = new List&lt;Evolution&gt; ();
                foreach (var e in top) {
                    values.Add (e);
                    if (e.term.Length &lt; 16) {
                        Term[] newTerm = new Term[e.term.Length + 1];
                        for (int i = 0; i &lt; e.term.Length; i++) {
                            newTerm [i] = e.term [i];
                        }
                        int rrr = rnd.Next (0, 17);
                        newTerm [e.term.Length] = new Term ((int)Math.Pow(2,rrr), rrr);
                        values.Add (new Evolution (newTerm));
                    }
                    {
                        int r = rnd.Next (0, e.term.Length);
                        Term[] newTerm = (Term[])e.term.Clone ();
                        int rrr = rnd.Next (0, 17);
                        newTerm [r] = new Term ((int)Math.Pow(2,rrr), rrr);
                        values.Add (new Evolution (newTerm));
                    }
                }
            }
        }

        public struct Term {
            public int? and;
            public int? shift;

            public Term(int? and, int? shift) {
                if (and!=0) {
                    this.and = and;
                } else this.and = null;
                if (shift!=0) {
                    this.shift = shift;
                } else this.shift=null;
            }
        }

        public class Evolution {
            public Term[] term;
            public long score;

            public Evolution(Term[] term) {
                this.term = term;
            }
        }
    }
}


Tested on OSX with Mono C# compiler version 3.2.6.0.

At each iteration it prints the fitness value of the current calculation. At the end it will print the best solution along with its fitness. The loop will run until one of the results have a fitness value of 0.

This is how it starts:

// ------------------------------------------------------------------------------
//  &lt;autogenerated&gt;
//      This code was generated by a tool.
//      Mono Runtime Version: 4.0.30319.17020
// 
//      Changes to this file may cause incorrect behavior and will be lost if 
//      the code is regenerated.
//  &lt;/autogenerated&gt;
// ------------------------------------------------------------------------------

namespace CodeGolf {
    using System;


    public class DigitSum {

        public static int digitsum(int i) {
            return i;
        }
    }
}

Best fitness for this run: 49940387


And after a while (takes around 30 minutes), this is how it ends (showing the last and almost last iteration):

// ------------------------------------------------------------------------------
//  &lt;autogenerated&gt;
//      This code was generated by a tool.
//      Mono Runtime Version: 4.0.30319.17020
// 
//      Changes to this file may cause incorrect behavior and will be lost if 
//      the code is regenerated.
//  &lt;/autogenerated&gt;
// ------------------------------------------------------------------------------

namespace CodeGolf {
    using System;


    public class DigitSum {

        public static int digitsum(int i) {
            return ((((((((((((((((i &amp; 4096) / 4096) + ((i &amp; 16) / 16)) + ((i &amp; 32) / 32)) + ((i &amp; 128) / 128)) + ((i &amp; 65536) / 65536)) + ((i &amp; 1024) / 1024)) + ((i &amp; 8) / 8)) + ((i &amp; 2) / 2)) + ((i &amp; 512) / 512)) + ((i &amp; 4) / 4)) + (i &amp; 1)) + ((i &amp; 256) / 256)) + ((i &amp; 128) / 128)) + ((i &amp; 8192) / 8192)) + ((i &amp; 2048) / 2048));
        }
    }
}

Best fitness for this run: 4992
Fitness: 4992
Fitness: 7040
Fitness: 4993
Fitness: 4992
Fitness: 0
Fitness: 4992
Fitness: 4992
Fitness: 7496
// ------------------------------------------------------------------------------
//  &lt;autogenerated&gt;
//      This code was generated by a tool.
//      Mono Runtime Version: 4.0.30319.17020
// 
//      Changes to this file may cause incorrect behavior and will be lost if 
//      the code is regenerated.
//  &lt;/autogenerated&gt;
// ------------------------------------------------------------------------------

namespace CodeGolf {
    using System;


    public class DigitSum {

        public static int digitsum(int i) {
            return (((((((((((((((((i &amp; 4096) / 4096) + ((i &amp; 16) / 16)) + ((i &amp; 32) / 32)) + ((i &amp; 64) / 64)) + ((i &amp; 32768) / 32768)) + ((i &amp; 1024) / 1024)) + ((i &amp; 8) / 8)) + ((i &amp; 2) / 2)) + ((i &amp; 512) / 512)) + ((i &amp; 4) / 4)) + (i &amp; 1)) + ((i &amp; 256) / 256)) + ((i &amp; 128) / 128)) + ((i &amp; 8192) / 8192)) + ((i &amp; 2048) / 2048)) + ((i &amp; 32768) / 32768));
        }
    }
}

Best fitness for this run: 0


Notes:


CodeDOM doesn't support the left shift operator so instead of a &gt;&gt; b I'm using a / 2^b
The initial iteration is just a return i; as required by the problem.
In the first few iterations priority is given to adding new terms (genes) to the sum. Later there is more priority in changing values (mutation) in terms randomly.
I'm generating terms that look like i &amp; a &gt;&gt; a instead of i &amp; a &gt;&gt; b, as in the latter case the evolution was simply too slow to be practical.
This is also why the solution is limited to finding an answer in the form return (i&amp;a&gt;&gt;b)+(i&amp;c&gt;&gt;d)+..., as any other kind (like trying to generate a "proper" code, with loops, assignments, condition checks, etc.) would simply converge too slowly. Also this way it is very easy to define the genes (each of the term), and is very easy to mutate them.
This is also the reason why I'm adding the digits in base 2 (the base wasn't specified in the problem statement, so I consider this fine). A base 10 solution would've been just to slow, and also it would've been really hard to define the actual genes. Adding a loop would also mean that you have to manage the running code, and find a possible way to kill it, before it enters a potentially infinite loop.
Genes are only mutated, there is no crossover in this solution. I don't know whether adding that would speed up the evolution process or not.
The solution is only tested for numbers 0..10000 (if you check the found solution you can see that it won't work for numbers larger than 16384)
The whole evolution process can be checked at this gist.