GENOTIP.cs

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

// from pastebin
namespace Kromo
{
    public class Genotip
    {
        // CM --
        // 4 dimensional polynomial approximation
        private static double[,] rez_pokusa = new double[15, 4];
        static Genotip()
        {   // Rezultati pokusa

            // CM -- these are the sample points (x,y,z) and the resulting value I'll call (w)
            rez_pokusa[0, 0] = 165; rez_pokusa[0, 1] = 0.3; rez_pokusa[0, 2] = 2.0; rez_pokusa[0, 3] = 0.56;
            rez_pokusa[1, 0] = 180; rez_pokusa[1, 1] = 0.24; rez_pokusa[1, 2] = 2.7; rez_pokusa[1, 3] = 0.34;
            rez_pokusa[2, 0] = 165; rez_pokusa[2, 1] = 0.3; rez_pokusa[2, 2] = 0.82; rez_pokusa[2, 3] = 0.42;
            rez_pokusa[3, 0] = 190; rez_pokusa[3, 1] = 0.3; rez_pokusa[3, 2] = 2.0; rez_pokusa[3, 3] = 0.45;
            rez_pokusa[4, 0] = 165; rez_pokusa[4, 1] = 0.4; rez_pokusa[4, 2] = 2.0; rez_pokusa[4, 3] = 1.15;
            rez_pokusa[5, 0] = 165; rez_pokusa[5, 1] = 0.2; rez_pokusa[5, 2] = 2.0; rez_pokusa[5, 3] = 0.23;
            rez_pokusa[6, 0] = 180; rez_pokusa[6, 1] = 0.36; rez_pokusa[6, 2] = 2.7; rez_pokusa[6, 3] = 0.88;
            rez_pokusa[7, 0] = 150; rez_pokusa[7, 1] = 0.36; rez_pokusa[7, 2] = 1.3; rez_pokusa[7, 3] = 0.97;
            rez_pokusa[8, 0] = 150; rez_pokusa[8, 1] = 0.24; rez_pokusa[8, 2] = 2.7; rez_pokusa[8, 3] = 0.47;
            rez_pokusa[9, 0] = 140; rez_pokusa[9, 1] = 0.3; rez_pokusa[9, 2] = 2.0; rez_pokusa[9, 3] = 0.92;
            rez_pokusa[10, 0] = 150; rez_pokusa[10, 1] = 0.24; rez_pokusa[10, 2] = 1.3; rez_pokusa[10, 3] = 0.39;
            rez_pokusa[11, 0] = 180; rez_pokusa[11, 1] = 0.36; rez_pokusa[11, 2] = 1.3; rez_pokusa[11, 3] = 0.77;
            rez_pokusa[12, 0] = 150; rez_pokusa[12, 1] = 0.36; rez_pokusa[12, 2] = 2.7; rez_pokusa[12, 3] = 1.1;
            rez_pokusa[13, 0] = 165; rez_pokusa[13, 1] = 0.3; rez_pokusa[13, 2] = 3.18; rez_pokusa[13, 3] = 0.81;
            rez_pokusa[14, 0] = 180; rez_pokusa[14, 1] = 0.24; rez_pokusa[14, 2] = 1.3; rez_pokusa[14, 3] = 0.28;
        }

        public List<Kromosom> kromosom;
        Random random;
        private const double a = 0.7;

        public Genotip(int nrOfChro)
        {
            kromosom = new List<Kromosom>();
            random = new Random();

            for (int i = 0; i < nrOfChro; i++)
                kromosom.Add(new Kromosom(random));
        }

        // CM add evaluation function for re-use in charting the results in the output files
        // return - computed value for this sample
        // parameters
        // k - chromosome to evaluate
        // sample_index - which sample to test
        // actual - [out] the actual sample value
        public double eval(Kromosom k, int sample_index, out double actual)
        {
            int i = sample_index;

            // CM - 4D polynomial approximation
            double guess = k.Alele[0]
                + k.Alele[1] * rez_pokusa[i, 0]
                + k.Alele[2] * rez_pokusa[i, 1]
                + k.Alele[3] * rez_pokusa[i, 2]
                + k.Alele[4] * Math.Pow(rez_pokusa[i, 0], 2)
                + k.Alele[5] * Math.Pow(rez_pokusa[i, 1], 2)
                + k.Alele[6] * Math.Pow(rez_pokusa[i, 2], 2)
                + k.Alele[7] * rez_pokusa[i, 0] * rez_pokusa[i, 1]
                + k.Alele[8] * rez_pokusa[i, 0] * rez_pokusa[i, 2]
                + k.Alele[9] * rez_pokusa[i, 1] * rez_pokusa[i, 2]
                + k.Alele[10] * rez_pokusa[i, 0] * rez_pokusa[i, 1] * rez_pokusa[i, 2];

            actual = rez_pokusa[i,3];
            return guess;
        }

        public int sampleCount {
            get { return rez_pokusa.GetLength(0); }
        }


        // CM - removed constructor with "ensured diversity" which
        // wasn't working anyhow

        // CM - calculate the raw and scaled fitness
        public void RacunajFunkcijuFitnesa(List<Kromosom> kromosom)
        {
            //CM NOTE: bug? looks like this should be inside the k loop, since it's not,
            //the value will likely grow VERY large, and 1/tempFitness will get smaller
            // with every chromosome.
            //
            // NOTE: I removed the temporary list altogether to speed thingsup
            //
            //double tempFitnes = 0;

            for (int k = 0; k < kromosom.Count; k++)
            {
                // CM initialize tempFitness to 0
                double sum_squares = 0;
                for (int i = 0; i < rez_pokusa.GetLength(0); i++) // for every sample point
                {
                    // evaluate kromosome k against sample data point i
                    double dummy;
                    var guess = eval( kromosom[k], i, out dummy );

                    // CM - avoid the use of a temporary List<double>:
                    sum_squares += Math.Pow (rez_pokusa[i,3]-guess,2); // least squares
                }

                //
                // error = rez_pokusa - calc
                // tempFitnes = Sum(error^2)
                // tempFitness = sum of error^2 / count = average ( sum of error^2 )
                // kromosome fitness = 1/ average(sum of error^2)
                //

                // CM -- track the RAW fitness values for logging, which
                // is the average sum of squared error
                kromosom[k].RawFitnes = sum_squares / rez_pokusa.Length;

                // CM -- this is fitness scaling, which is inverting the raw fitness (least squares)
                kromosom[k].ScaledFitness = 1 / kromosom[k].RawFitnes; // invert the fitness
            }
        }

        // CM - computes the normalized fitness
        public void RacunajFunkcijuSelekcije(List<Kromosom> kromosom)
        {
            double tempFitnessAll = 0.0;
            for (int k = 0; k < kromosom.Count; k++)
            {
                tempFitnessAll += kromosom[k].NicheScaledFitness; // CM -- changed this to "active" fitness, which can be controlled by developer
            }
            // CM - normalize the fitness values
            for (int k = 0; k < kromosom.Count; k++)
            {
                kromosom[k].NormalizedFitness = kromosom[k].NicheScaledFitness / tempFitnessAll;
            }

            // CM - sort by Normalized fitness, the normalized fitness
            kromosom.Sort();
        }

        // CM - added niching
        //
        public void Niching(List<Kromosom> kromosom, double max_stddev)
        {
            List<int> niches = new List<int>();

            // clear niches
            foreach(var k in kromosom) {
                k.Niche = -1;
            }

            // compute niches
            for(int i = 0; i<kromosom.Count; i++ ) {
                var k = kromosom[i];

                if(k.Niche != -1) continue; // already has a niche

                k.Niche = niches.Count;
                int count = 1;
                for(int j=i+1; j<kromosom.Count; j++) {
                    var kj = kromosom[j];
                    double stddev = k.StdDev(kj);
                    if(stddev < max_stddev) {
                        kj.Niche = k.Niche;
                        ++count;
                    }
                }
                niches.Add(count);
            }

            // calculate niche scaled fitness
            foreach(var k in kromosom) {
                k.NicheScaledFitness = k.ScaledFitness / niches[k.Niche];
            }
        }

        // CM --
        // 72% chance that this will pick the larger of the two items in the tourney
        // 28% chance that the weaker survives
        // Added two parameters: probablity that the fitter krom wins, and the number of individuals to return
        public List<Kromosom> ProbabilisticBinaryTournamentSelection(List<Kromosom> kromosom, double prob, int N)
        {
            List<Kromosom> noviKromosom = new List<Kromosom>();
            Kromosom veći, manji;
            double probabilityOfTournament = prob, međa;
            Kromosom kro1, kro2;
            int pozicija_kro1, pozicija_kro2;

            while (noviKromosom.Count < N)
            {
                pozicija_kro1 = random.Next(kromosom.Count);
                do{
                    pozicija_kro2 = random.Next(kromosom.Count);
                }while(pozicija_kro1 == pozicija_kro2);

                kro1 = kromosom[pozicija_kro1];
                kro2 = kromosom[pozicija_kro2];

                međa= random.NextDouble(); // "border" ??? prob. threshold
                veći = kro1.NormalizedFitness >= kro2.NormalizedFitness ? kro1 : kro2; // larger
                manji = kro1.NormalizedFitness < kro2.NormalizedFitness ? kro1 : kro2; // smaller

                if (međa < probabilityOfTournament)
                    noviKromosom.Add(veći); // larger
                else
                    noviKromosom.Add(manji); // smaller
            }
            return noviKromosom;
        }

        // CM --
        // in the style of your other routines
        // Adding in a value for the number of items to select
        public List<Kromosom> RouletteSelection(List<Kromosom> kromosom, int N)
        {
            var list = new List<Kromosom>();
            for(int i=0; i<N; i++) {

                double r = random.NextDouble();
                double sum = 0.0;
                foreach(var k in kromosom) {
                    sum += k.NormalizedFitness;

                    if(r <= sum) {
                        list.Add( k );
                        break;
                    }
                }
            }

            return list;
        }

        // CM - output of this will be N chromosomes that have had crossover
        // applied, with a chance that no crossover has been appiled at all
        //
        // modification - removes elements from the input kromosom list
        public List<Kromosom> Crossover_2(List<Kromosom> kromosom, int N)
        {
            int parent_1,parent_2;
            Kromosom otac, majka; // father, mother
            List<Kromosom> crossoverKromosom = new List<Kromosom>();
            List<Kromosom> potomci = new List<Kromosom>();

            // CM - randomize the list (of tournament winners)
            RazbacajListu(kromosom);

            int n = 0;
            if(N == -1) N = kromosom.Count;

            while(n < N && kromosom.Count >= 2) {

                // CM - the randomization here surely doesn't hurt, but it might
                // be a bit overkill. you've already randomized kromosom above,
                // and that list itself was randomized during the tournament.
                // not really a critical point, just thought I'd mention it
                // because it could improve your performance (you could just
                // pop two off the list, instead of calling List.Remove(Chromosome))

                // just pop two off the front
                otac = kromosom[0];
                majka = kromosom[1];
                kromosom.RemoveRange(0,2);

                // CM - "progeny" == Multiply(father,mother)
                potomci = Razmnozi(otac,majka);

                crossoverKromosom.AddRange(potomci);

                n += potomci.Count;
            }

            return crossoverKromosom;
        }

        // CM - "Multiply" ??? performs a crossover operation??
        // and returns two children. Oh, I get it. Two parents mate
        // and "multiply" to create offspring.
        private List<Kromosom> Razmnozi(Kromosom otac, Kromosom majka)
        {
            double crossOverChance = random.NextDouble(); // CM - changed to double, allow different crossover techniques
            List<Kromosom> potomci = new List<Kromosom>();
            Kromosom sin = new Kromosom(otac.Alele);
            Kromosom kćer = new Kromosom(majka.Alele);

            float SINGLE_XOVER_PROB = 0.88f;  // 88% chance of single xover
            float EXTREME_XOVER_PROB = 0.98f; // 10% chance of extreme xover
            //float NO_XOVER_PROB = 1.0f;  // 2% chance that nothing happens

            // CM note -- 8/12, 2/3, 66^% chance of a crossover
            // CM change -- always perform crossovers
            //if (crossOverChance < 8)
            if (crossOverChance < SINGLE_XOVER_PROB)
            {
                int loc = random.Next(otac.Alele.Count);

                // swap only at a single location
                for(int i=loc; i<otac.Alele.Count; i++) {
                    double temp = sin.Alele[i];
                    sin.Alele[i] = kćer.Alele[i];
                    kćer.Alele[i] = temp;
                }
            }
            else if (crossOverChance < EXTREME_XOVER_PROB)
            {
                // son
                // CM -- cleaned this up a bit, same functionality as before
                for (int i = 0; i < sin.Alele.Count; i++) {
                    bool flip = random.Next(2) == 0;
                    sin.Alele[i] = flip ? otac.Alele[i] : majka.Alele[i];
                }

                // daughter
                for (int i = 0; i < kćer.Alele.Count; i++) {
                    bool flip = random.Next(2) == 0;
                    kćer.Alele[i] = flip ? majka.Alele[i] : otac.Alele[i];
                }
            }

            potomci.Add(sin);
            potomci.Add(kćer);
            return potomci;
        }

        // CM -- chose from several mutation algorithms, including
        // no mutation at all
        // N - number of elements to process, or -1 to process them all
        public List<Kromosom> Mutation(List<Kromosom> kromosom, int N)
        {
            List<Kromosom> mutations =  new List<Kromosom>();

            float PROB_REPLACEMENT = 0.3f;
            float PROB_SWAP = 0.6f;
            float PROB_SCALE = 0.75f;
            float PROB_SHIFT = 0.9f;
            // 1.0f no change

            // process them all if N is -1
            if (N == -1) N = kromosom.Count;

            for (int i=0; i<N && kromosom.Count > 0; i++)
            {
                var k = new Kromosom( kromosom[0].Alele );
                kromosom.RemoveAt(0);
                mutations.Add( k );

                // per-allele chance of mutation
                // mutate a single allele
                int j = random.Next( k.Alele.Count );

                double tempMutation = random.NextDouble();

                // CM -- this is pretty bold. really, very bold.
                //
                // There's a 30% chance of mutation
                // in the first 10 steps, and 5% chance of mutation after that?
                // You might want this to be more dynamic, say, based on the
                // variance of the population.
                //
                // And the 30% chance is a single-allele replacment, but
                // the 5% chance is a COMPLETELY NEW CHROMOSOME!
                //
                // CM -- changing this to pick a type of mutation
                if( tempMutation < PROB_REPLACEMENT) {
                    // replace a value
                    k.Alele[j] = random.NextDouble()*2000 - 1000;
                }
                else if (tempMutation < PROB_SWAP ) {
                    // swap two values
                    int j1 = j;
                    int j2 = j1;
                    while(j1 == j2) {
                        j2 = random.Next( k.Alele.Count );
                    }
                    double v = k.Alele[j1];
                    k.Alele[j1] = k.Alele[j2];
                    k.Alele[j2] = v;
                }
                else if (tempMutation < PROB_SCALE) {
                    // scale a value by a pct
                    double scale = 0.8 + random.NextDouble()*0.4; // range 0.8 to 1.2
                    k.Alele[ j ] *= scale;
                }
                else if (tempMutation < PROB_SHIFT) {
                    // shift by some range
                    double shift = -100 + random.NextDouble()*200; // +/- 100
                    k.Alele[ j ] += shift;
                }
            }

            return mutations;
        }

        // CM - randomize the list of chromosomes
        public void RazbacajListu(List<Kromosom> kromosom)
        {
            int n = kromosom.Count;

            while (n > 1)
            {
                int k = (random.Next(0, n) % n);
                n--;
                Kromosom value = kromosom[k];
                kromosom[k] = kromosom[n];
                kromosom[n] = value;
            }
        }

        // CM - calculate population variance
        public double RacunajVarijancu()
        {
            double meanOfThePopulation = 0.0;
            for (int i = 0; i <kromosom.Count ; i++)
            {
                meanOfThePopulation += kromosom[i].ScaledFitness;
            }
            meanOfThePopulation /= kromosom.Count;

            double zbrojKvadrataRazlika = 0.0;
            for (int i = 0; i < kromosom.Count; i++)
            {
                zbrojKvadrataRazlika += Math.Pow((kromosom[i].ScaledFitness-meanOfThePopulation),2);
            }

            double varijance = zbrojKvadrataRazlika / kromosom.Count;
            return varijance;
        }

        // CM - Check Convergence
        // najbolji = best
        //
        // This tests for convergence by seeing if the average fitness in the population
        // is greater than 95% of the best fitness so far.
        //
        // This could abort VERY EARLY since most of the population in the beginning
        // will have a VERY POOR FITNESS
        public bool ProvjeriKonvergenciju(List<Kromosom> kromosom, Kromosom najbolji)
        {
            double avgFitnesSvih = 0.0;
            foreach (var jedinka in kromosom)
            {
                avgFitnesSvih += jedinka.ScaledFitness;
            }
            avgFitnesSvih /= kromosom.Count;

            if (avgFitnesSvih > najbolji.ScaledFitness * 0.95)
                return true;
            else
                return false;
        }
    }

}