C# GA code with Explicit Fitness Sharing

using System;
using System.Collections.Generic;
using System.Text;

namespace GA2
{
    class MainClass
    {
        // chromosome definition
        class Chromosome {

            public float[] alele;
            public float fitness;           // raw fitness
            public float scaled_fitness;    // adjusted for better selection
            public int niche;               // for niche scaling
            public float niche_scaled_fitness; // scaled_fitness after applying explicit fitness sharing

            public Chromosome(int n, Random rand) {
                alele = new float[n];
                for(int i=0; i<n; i++) {
                    alele[i] = (float)(rand.NextDouble()*2000-1000);
                }
            }

            // create a new empty chromosome
            public Chromosome(int n) {
                alele = new float[n];
            }

            // clones this chromosome
            public Chromosome Clone() {
                Chromosome c =  new Chromosome(alele.Length);
                for(int i=0; i<alele.Length; i++) {
                    c.alele[i] = alele[i];
                }
                return c;
            }

            // compute the population standard deviation
            public float StdDev(Chromosome other) {
                float sum = 0.0f;
                for(int i=0; i<alele.Length; i++) {
                    float diff = other.alele[i] - alele[i];
                    sum += diff*diff;
                }
                return (float)Math.Sqrt(sum);
            }

            // string representation (MonoDevelop crashes for some reason
            // if this is the ToString override)
            public string ConvertToString ()
            {
                StringBuilder sb = new StringBuilder();
                sb.AppendFormat("{0:0.00000} niche={1} (", fitness, niche);
                for(int i=0; i<alele.Length; i++) {
                    if(i > 0) {
                        sb.Append(", ");
                    }
                    sb.AppendFormat("{0:0.000}", alele[i]);
                }
                sb.Append(")");
                return sb.ToString();
            }
        }

        // roulette selection selects items proportionally
        // to their fitness. Here a generic function is used
        // to extract the value for the roulette selection
        class Roulette<T> {
            Random rand;
            List<T> items = new List<T>();
            float sum;
            Func<T,float> fn;

            public Roulette(Random rand, Func<T,float> fn) {
                this.rand = rand;
                this.sum = 0.0f;
                this.fn = fn;
            }

            public void Add(T t) {
                items.Add(t);
                sum += fn(t);
            }

            public T Select() {
                float f = (float)(rand.NextDouble()*sum);
                float localsum = 0.0f;
                foreach(T t in items) {
                    localsum += fn(t);
                    if(localsum >= f) {
                        return t;
                    }
                }

                // this shouldn't happen, so just return the last item in the list
                return items[ items.Count - 1 ];
            }
        }

        List<Chromosome> population;
        int generation;
        Random rand;

        int POPULATION_SIZE = 100;
        int MAX_GENERATIONS = 100000;
        int ALELE_LENGTH = 10;
        float NICHE_MAX_STDDEV = 500.0f;

        public static void Main (string[] args) {
            new MainClass().Run();
        }

        MainClass() {
        }

        public void Run() {
            rand = new Random();
            generation = 0;
            Seed();

            for(int i=0; i<MAX_GENERATIONS; i++) {

                // evaluate fitness
                Eval(Eval_OrderedDistance);

                // scale fitness
                Scale_Invert(population);

                // sort so that the fittest is on top (using scaled fitness values)
                population.Sort( SortByDecreasingFitness );

                // compute niches
                int niche_count = ComputeNiches(NICHE_MAX_STDDEV);

                if(generation % 1000 == 0) {
                    // print entire population every 1000 iterations
                    for(int j=0; j<population.Count; j++) {
                        Console.WriteLine( generation + "[" + j + "]: " + population[j].ConvertToString());
                    }
                }
                else {
                    // print out the best-so-far
                    Console.WriteLine( generation + " nicheCount=" + niche_count + " : " + population[0].ConvertToString() );
                }

                // perform mutations to create the next generation
                Mutate();

                ++generation;
            }
        }

        // seed the population with completely random values
        public void Seed() {
            population = new List<Chromosome>();
            for(int i=0; i<POPULATION_SIZE; i++) {
                population.Add( new Chromosome(ALELE_LENGTH,rand));
            }
        }

        // calculate the fitness of a chromosome
        void Eval(Func<Chromosome,float> fitnessFunc) {
            foreach(var chromosome in population) {
                chromosome.fitness = fitnessFunc(chromosome);
            }
        }

        // Sorting methods
        int SortByIncreasingFitness(Chromosome a, Chromosome b) {
            if(a.scaled_fitness < b.scaled_fitness) return -1;
            else if (a.scaled_fitness > b.scaled_fitness) return 1;
            return 0;
        }

        int SortByDecreasingFitness(Chromosome a, Chromosome b) {
            if(a.scaled_fitness < b.scaled_fitness) return 1;
            else if (a.scaled_fitness > b.scaled_fitness) return -1;
            return 0;
        }

        // Run the mutation and crossovers
        void Mutate() {

            // start a new population
            var new_population = new List<Chromosome>();

            // elitism, always keep the best
            Chromosome best = population[0];
            new_population.Add( best );

            // build the roulette selector
            Roulette<Chromosome> roulette = new Roulette<Chromosome>(rand,
                //(c)=>{ return c.scaled_fitness; }
                (c)=>{ return c.niche_scaled_fitness; }
            );
            foreach(var c in population) {
                roulette.Add(c);
            }

            // mutations
            for(int i=0; i<POPULATION_SIZE; i++) {
                Chromosome c;

                // half time choose crossover, half time choose mutation
                if(rand.NextDouble() < 0.5) {
                    // crossover
                    c = Crossover( roulette.Select(), roulette.Select() );
                }
                else {
                    // mutate
                    c = ChangeOne( roulette.Select() );
                }
                new_population.Add(c);
            }

            population =  new_population;
        }

        // returns: total number of niches in this population
        // max_stddev -- any two chromosomes with population stddev less than this max
        //               will be grouped together
        int ComputeNiches(float max_stddev) {
            List<int> niches = new List<int>();

            // clear niches
            foreach(var c in population) {
                c.niche = -1;
            }

            // calculate niches
            for(int i=0; i<population.Count; i++) {
                var c = population[i];
                if( c.niche != -1) continue; // niche already set

                // compute the niche by finding the stddev between the two chromosomes
                c.niche = niches.Count;
                int count_in_niche = 1; // includes the curent Chromosome
                for(int j=i+1; j<population.Count; j++) {
                    var d = population[j];
                    float stddev = c.StdDev(d);
                    if(stddev < max_stddev) {
                        d.niche = c.niche; // same niche
                        ++count_in_niche;
                    }
                }
                niches.Add(count_in_niche);
            }

            // penalize Chromosomes by their niche size
            foreach(var c in population) {
                c.niche_scaled_fitness = c.scaled_fitness / niches[c.niche];
            }

            return niches.Count;
        }

        // Pick a single random value to change to a different single random value
        Chromosome ChangeOne(Chromosome c) {
            Chromosome d = c.Clone();
            int i = rand.Next() % d.alele.Length;
            d.alele[i] = (float)(rand.NextDouble()*2000-1000);
            return d;
        }

        // A random crossover mutation
        Chromosome Crossover(Chromosome a, Chromosome b) {
            int location = rand.Next() % a.alele.Length;

            Chromosome c = new Chromosome(a.alele.Length);
            for(int i=0; i<location; i++) {
                c.alele[i] = a.alele[i];
            }
            for(int i=location; i<a.alele.Length; i++) {
                c.alele[i] = b.alele[i];
            }
            return c;
        }

        // try to pack the aleles together spaced apart by 1.0
        // returns the standard deviation of the samples from 1.0
        static float Eval_OrderedDistance(Chromosome c) {
            float sum = 0;
            int n = c.alele.Length;
            for(int i=1; i<n; i++) {
                float diff = (c.alele[i] - c.alele[i-1]) - 1.0f;
                sum += diff*diff; // variance from 1.0
            }

            return (float)Math.Sqrt(sum/n);
        }

        // invert the fitness of the population so that the low raw fitness
        // is converted to the highest fitness in the population
        static void Scale_Invert(IEnumerable<Chromosome> population) {
            float max = float.MinValue;
            foreach(var c in population) {
                max = Math.Max(c.fitness, max);
            }
            foreach(var c in population) {
                c.scaled_fitness = max - c.fitness;
            }
        }

    }
}