[Quantproject-developers] QuantProject/b1_ADT/Optimizing/Genetic GeneticOptimizer.cs,NONE,1.1 Genome.cs,NONE,1.1 GenomeComparer.cs,NONE,1.1 GenomeManagement.cs,NONE,1.1 GenomeManagerTest.cs,NONE,1.1 IGenomeManager.cs,NONE,1.1

[Marco M. <mi...@us...>]

Update of /cvsroot/quantproject/QuantProject/b1_ADT/Optimizing/Genetic
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv19295/b1_ADT/Optimizing/Genetic

Added Files:
	GeneticOptimizer.cs Genome.cs GenomeComparer.cs 
	GenomeManagement.cs GenomeManagerTest.cs IGenomeManager.cs 
Log Message:
Added GeneticOptimizer to the project

--- NEW FILE: Genome.cs ---
/*
QuantProject - Quantitative Finance Library

Genome.cs
Copyright (C) 2003 
Marco Milletti

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/


using System;
using System.Collections;

namespace QuantProject.ADT.Optimizing.Genetic
{
	/// <summary>
	/// Representation of an individual through features
	/// provided by biology
	/// </summary>
  public class Genome 
	{
	  private int[] genes;
    private int minValueForGenes;
    private int maxValueForGenes;
    private int size;
    private double fitness;
    private object meaning;

    IGenomeManager genomeManager;
		
    public double Fitness
    {
      get{return this.fitness;}
      set{this.fitness = value;}
    }

    public object Meaning
    {
      get{return this.meaning;}
      set{this.meaning = value;}
    }

    public int Size
    {
      get{return this.size;}
    }
    
    public int MinValueForGenes
    {
      get{return this.minValueForGenes;}
    }
    
    public int MaxValueForGenes
    {
      get{return this.maxValueForGenes;}
    }

    /// <summary>
    /// It creates a  new genome object initialized by a IGenomeManager
    /// </summary>
    public Genome(IGenomeManager genomeManager)
		{
			this.genomeManager = genomeManager;
			this.size = this.genomeManager.GenomeSize;
    	this.minValueForGenes = this.genomeManager.MinValueForGenes;
    	this.maxValueForGenes = this.genomeManager.MaxValueForGenes;
 			this.genes = new int[ this.size ];
		}
  
  	public void AssignMeaning()
    {
      this.meaning = this.genomeManager.Decode(this);
    }	 

		public void CreateGenes()
		{
			for (int i = 0 ; i < this.size ; i++)
				this.genes[i] = this.genomeManager.GetNewGeneValue(this);
		}
    
    public void CalculateFitness()
    {
      this.fitness = this.genomeManager.GetFitnessValue(this);
    }
    
    public Genome Clone()
    {
      Genome returnValue = new Genome(this.genomeManager);
      returnValue.Fitness = this.Fitness;
      returnValue.Meaning = this.Meaning;
      returnValue.CopyValuesInGenes(this.genes);
      
      return returnValue;
    }
            
    public int[] Genes()
		{
			return this.genes;
		}

		public void CopyValuesInGenes(int[] valuesToBeCopied)
		{
			for (int i = 0 ; i < this.size ; i++)
				this.genes[i] = valuesToBeCopied[i];
		}
    
    public void SetGeneValue(int geneValue, int genePosition)
    {
      if(genePosition >= this.size || genePosition<0)
        throw new IndexOutOfRangeException("Gene position not valid for the genome! ");
      
      this.genes[genePosition] = geneValue;
    }
    
    public int GetGeneValue(int genePosition)
    {
      if(genePosition >= this.size || genePosition<0)
        throw new IndexOutOfRangeException("Gene position not valid for the genome! ");
      
      return this.genes[genePosition];
    }
    
    /// <summary>
    /// It returns true if the given gene is already stored in the current genome
    /// </summary>
    public bool HasGene(int geneValue)
    {
      bool returnValue = false;
      foreach(int gene in this.Genes())
      {
        if( geneValue == gene )
              returnValue = true;
      }
      return returnValue;
    }

    /// <summary>
	  /// It returns true if the current instance of genome has some duplicate
	  /// values in genes
	  /// </summary>
    public bool HasSomeDuplicateGenes()
    {
      bool returnValue = false;
      for(int i = 0; i < this.size ; i++)
      {
        for(int j = i + 1; j < this.size ; j++)
        {
          if(this.genes[i] == this.genes[j])
            returnValue = true;
        }
      }
      return returnValue;
    }
	}
}

--- NEW FILE: GeneticOptimizer.cs ---
/*
QuantProject - Quantitative Finance Library

GeneticOptimizer.cs
Copyright (C) 2003 
Marco Milletti

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

using System;
using System.Collections;
using QuantProject.ADT.Optimizing.Genetic;

namespace QuantProject.ADT.Optimizing.Genetic
{
  /// <summary>
  /// The class needs to be initialized by an object implementing
  /// IGenomeManager interface 
  /// Default GO parameters: crossoverRate = 0.85, mutationRate = 0.02, elitismRate = 0.01,
  /// populationSize = 1000, generationNumber = 100
  /// keepOnRunningUntilConvergenceIsReached = false, minConvergenceRate = 0.80 
  /// </summary>
	public class GeneticOptimizer
	{
    #region fields  
    
    private double mutationRate = 0.02;
    private double crossoverRate = 0.85;
    private double elitismRate = 0.01;
    private double minConvergenceRate = 0.80;
    private bool keepOnRunningUntilConvergenceIsReached = false;
    private int populationSize = 1000;
    private int generationNumber = 100;
    private int genomeSize;
    private int minValueForGenes;
    private int maxValueForGenes;
    private double totalFitness;
    private Genome bestGenome;
    private Genome worstGenome;
    private IGenomeManager genomeManager;
    private GenomeComparer genomeComparer;
	
    private ArrayList currentGeneration;
    private ArrayList currentEliteToTransmitToNextGeneration;
    private ArrayList nextGeneration;
    private ArrayList cumulativeFitnessList;
	
    private static Random random = new Random((int)DateTime.Now.Ticks);
    private int generationCounter;
    #endregion
    
    #region properties
    public double MutationRate
    {
      get{return mutationRate;}
      set{mutationRate = value;}
    }
    public double CrossoverRate
    {
      get{return crossoverRate;}
      set{crossoverRate = value;}
    }
    
    public double ElitismRate
    {
      get{return this.elitismRate;}
      set{this.elitismRate = value;}
    }
    
    public double MinConvergenceRate
    {
      get{return this.minConvergenceRate;}
      set{this.minConvergenceRate = value;}
    }
    
    public bool KeepOnRunningUntilConvergenceIsReached
    {
      get{return this.keepOnRunningUntilConvergenceIsReached ;}
      set{this.keepOnRunningUntilConvergenceIsReached = value;}
    }

    public int PopulationSize
    {
      get{return populationSize;}
      set{populationSize = value;}
    }
    
    public int GenerationNumber
    {
      get{return generationNumber;}
      set{generationNumber = value;}
    }
		public int GenerationCounter
    {
      get{return this.generationCounter;}
    }

    public int GenomeSize
    {
      get{return genomeSize;}
    }
    
    public Genome BestGenome
    {
      get{return this.bestGenome;}
    }
    
    public Genome WorstGenome
    {
      get{return this.worstGenome;}
    }
    #endregion
    
    /// <summary>
    /// The class needs to be initialized by an object implementing
    /// IGenomeManager interface 
    /// Default GO parameters: crossoverRate = 0.85, mutationRate = 0.02, elitismRate = 0.01,
    /// populationSize = 1000, generationNumber = 100
    /// keepOnRunningUntilConvergenceIsReached = false, minConvergenceRate = 0.80 
    /// </summary>
    public GeneticOptimizer(IGenomeManager genomeManager)
    {
      this.genomeManager = genomeManager;
      
      this.commonInitialization();
    }
    
    
    public GeneticOptimizer(double crossoverRate, double mutationRate, double elitismRate, 
                            int populationSize, int generationNumber,
                            IGenomeManager genomeManager)
    {
      this.crossoverRate = crossoverRate;
      this.mutationRate = mutationRate;
      this.elitismRate = elitismRate;
      this.populationSize = populationSize;
      this.generationNumber = generationNumber;
      this.genomeManager = genomeManager;
      
      this.commonInitialization();
    }

    private void commonInitialization()
    {
      this.genomeSize = this.genomeManager.GenomeSize;
      this.minValueForGenes = this.genomeManager.MinValueForGenes;
      this.maxValueForGenes = this.genomeManager.MaxValueForGenes;
      this.genomeComparer = new GenomeComparer();
      this.cumulativeFitnessList = new ArrayList(this.PopulationSize);
      this.currentGeneration = new ArrayList(this.PopulationSize);
      this.nextGeneration = new ArrayList();
      this.currentEliteToTransmitToNextGeneration =
        new ArrayList((int)(this.ElitismRate*(double)this.PopulationSize));
      
      this.generationCounter = 1;
    }
    
    /// <summary>
    /// Method which starts the GeneticOptmizer
    /// </summary>
    public void Run(bool showOutputToConsole)
    {
      this.createFirstGeneration(showOutputToConsole);
      if(this.keepOnRunningUntilConvergenceIsReached)
      //The GO keeps on generating new population until convergence is reached
      {
        for (int i = 0; !this.IsConvergenceReached(); i++)
        {
        	this.generateNewPopulation(true);
        }
      }
      else // the GO simply generates the given number of populations and then stops
      {
        for (int i = 0; i < this.generationNumber; i++)
        {
          this.generateNewPopulation(true);
        }
      }
    }
    
    private void generateNewPopulation(bool showOutputToConsole)
    {
    	this.createNextGeneration();
      this.updateBestGenomeFoundInRunning((Genome)this.currentGeneration[populationSize-1]);
      this.updateWorstGenomeFoundInRunning((Genome)this.currentGeneration[0]);
      if (showOutputToConsole)
           this.showOutputToConsole();
    }
    
    private bool IsConvergenceReached()
    {
      bool returnValue = false;
      double averageFitnessOfCurrentGeneration = this.totalFitness / this.populationSize;
      double bestFitnessReachedUntilNow = this.BestGenome.Fitness;

      if (averageFitnessOfCurrentGeneration >= 
                            this.minConvergenceRate * bestFitnessReachedUntilNow )
          returnValue = true;
      
      return returnValue;
 
    }

    private void createFirstGeneration(bool showOutputToConsole)
    {
      if (this.genomeSize == 0 || this.genomeSize < 0)
        throw new IndexOutOfRangeException("Genome size not set");
      this.createGenomes();
      this.currentGeneration.Sort(this.genomeComparer);
      this.calculateTotalFitness();
      this.updateCumulativeFitnessList();
      this.setInitialBestAndWorstGenomes();
      
      if (showOutputToConsole)
        this.showOutputToConsole();
    }
    
    private void showOutputToConsole()
    {
      System.Console.WriteLine("\n\n\n\n*_*_*_*_*_*_*_*_*_*_*\n\nGeneration " + this.generationCounter +"\n");
      for(int i = 0; i < this.populationSize; i++)
      {
        System.Console.WriteLine((string)((Genome)this.currentGeneration[i]).Meaning +
          "--> " + ((Genome)this.currentGeneration[i]).Fitness);
      }
      //Console.WriteLine("Press enter key to continue ...");
			//Console.ReadLine();
    }

    /// <summary>
    /// It returns an int corresponding to a certain genome.
    /// The probability for a genome to be selected depends
    /// proportionally on the level of fitness.
    /// </summary>
    private int rouletteSelection()
    {
      double randomFitness = this.totalFitness *(double)GeneticOptimizer.random.Next(1,1001)/1000;
      int idx = -1;
      int mid;
      int first = 0;
      int last = this.populationSize -1;
      mid = (last - first)/2;

      //  Need to implement a specific search, because the
      //  ArrayList's BinarySearch is for exact values only
      
      while (idx == -1 && first <= last)
      {
        if (randomFitness < (double)this.cumulativeFitnessList[mid])
        {
          last = mid;
        }
        else if (randomFitness >= (double)this.cumulativeFitnessList[mid])
        {
          first = mid;
        }
        
        mid = (first + last)/2;
        if ((last - first) == 1) 
          idx = last;
          
      }
      return idx;
    }


    /// <summary>
    /// Calculate total fitness for current generation
    /// </summary>
    private void calculateTotalFitness()
    {
      this.totalFitness = 0;
      for (int i = 0; i < this.populationSize; i++)
      {
        Genome g = ((Genome) this.currentGeneration[i]);
        this.totalFitness += g.Fitness;
      }
      
    }
    
    /// <summary>
    /// Rank current generation and sort in order of fitness.
    /// </summary>
    private void updateCumulativeFitnessList()
    {
      double cumulativeFitness = 0.0;
      this.cumulativeFitnessList.Clear();
      for (int i = 0; i < this.populationSize; i++)
      {
        cumulativeFitness += ((Genome)this.currentGeneration[i]).Fitness;
        this.cumulativeFitnessList.Add(cumulativeFitness);
      }
    }
    private void createGenomes()
    {
      for (int i = 0; i < this.populationSize; i++)
      {
        Genome g = new Genome(this.genomeManager);
        g.CreateGenes();
        g.AssignMeaning();
        g.CalculateFitness();
        this.currentGeneration.Add(g);
      }
    }

    private void setCurrentEliteToTransmitToNextGeneration()
    {
      this.currentEliteToTransmitToNextGeneration.Clear();
      
      for(int i = populationSize - 1;
              i >=(populationSize - this.elitismRate*this.populationSize);
              i--)
      {
        this.currentEliteToTransmitToNextGeneration.Add((Genome)this.currentGeneration[i]);
      }
    }

    private void transmitEliteToNextGeneration()
    {
      for(int i = 0;
          i < this.currentEliteToTransmitToNextGeneration.Count-1;
          i++)
        
      {
        this.nextGeneration.Add(this.currentEliteToTransmitToNextGeneration[i]);
      }
    }

    private void createNextGeneration()
    {
      this.nextGeneration.Clear();

      for (int i = 0 ; i < this.populationSize ; i+=2)
      {
        int indexForParent1 = this.rouletteSelection();
        int indexForParent2 = this.rouletteSelection();
        
        Genome parent1, parent2;
      	Genome[] childs;
        parent1 = ((Genome) this.currentGeneration[indexForParent1]);
        parent2 = ((Genome) this.currentGeneration[indexForParent2]);
        if ((double)GeneticOptimizer.random.Next(1,1001)/1000 < this.crossoverRate)
        {
          childs = this.genomeManager.GetChilds(parent1, parent2);
         }
        else
        {//if the crossover doesn't take place there are only
        //two childs, identical to parents
          childs = new Genome[2];
          childs[0] = parent1.Clone();
          childs[1] = parent2.Clone();
        }
        foreach(Genome g in childs){
        	this.nextGeneration.Add(g);
        }
      }
      this.setCurrentEliteToTransmitToNextGeneration();
      this.transmitEliteToNextGeneration();
      
      this.mutateGenomes(this.nextGeneration);
      this.calculateFitnessAndMeaningForAllGenomes(this.nextGeneration);
      this.nextGeneration.Sort(this.genomeComparer);
      this.updateCurrentGeneration();
      this.currentGeneration.Sort(this.genomeComparer); 
      this.calculateTotalFitness();
      this.updateCumulativeFitnessList();
      
      this.generationCounter++;
    }
    
    //mutate all genomes of the given population, according to the mutation rate
    private void mutateGenomes(ArrayList populationOfGenomes)
    {
      foreach(Genome g in populationOfGenomes)
      {
        if(g != null)
           this.genomeManager.Mutate(g, this.MutationRate);
      }
    }
    
    //calculate Fitness and Meaning for each genome in populationOfGenomes
    private void calculateFitnessAndMeaningForAllGenomes(ArrayList populationOfGenomes)
    {
      foreach(Genome g in populationOfGenomes)
      {
        if(g != null)
        {
          g.CalculateFitness();
          g.AssignMeaning();
        }
      }
    }

    private void updateCurrentGeneration()
    {
      this.currentGeneration.Clear();
      // Note that next generation is greater than current:
      // due to the population size, genomes with lowest fitness are abandoned
      for (int i = 1 ; i <= this.populationSize; i++)
        this.currentGeneration.Add(this.nextGeneration[this.nextGeneration.Count - i]);
    }

    private void updateBestGenomeFoundInRunning(Genome genomeValue)
    {
      if(genomeValue.Fitness > this.bestGenome.Fitness)
        this.bestGenome = genomeValue.Clone();
    }
    private void updateWorstGenomeFoundInRunning(Genome genomeValue)
    {
      if(genomeValue.Fitness < this.worstGenome.Fitness)
        this.worstGenome = genomeValue.Clone();
    }
    private void setInitialBestAndWorstGenomes()
    {
      this.bestGenome = (Genome)this.currentGeneration[this.populationSize-1];
      this.worstGenome = (Genome)this.currentGeneration[0];
    }
    
  }
}

--- NEW FILE: GenomeManagerTest.cs ---
/*
QuantProject - Quantitative Finance Library

GenomeManagerTest.cs
Copyright (C) 2003 
Marco Milletti

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/


using System;
using System.Collections;

namespace QuantProject.ADT.Optimizing.Genetic
{
	/// <summary>
	/// Create a simple class implementing IGenomeManager, in order to test the
	/// behaviour of the genetic optimizer
	/// </summary>
  public class GenomeManagerTest : IGenomeManager
  {
    private int genomeSize;
    private int minValueForGenes;
    private int maxValueForGenes;
     
    public int GenomeSize
    {
      get{return this.genomeSize;}
    }
    
    public int MinValueForGenes
    {
      get{return this.minValueForGenes;}
    }
    
    public int MaxValueForGenes
    {
      get{return this.maxValueForGenes;}
    }
    
    public GenomeManagerTest(int genomeSize, int minValueForGenes,
                             int maxValueForGenes)
                          
    {
      this.genomeSize = genomeSize;
      this.minValueForGenes = minValueForGenes;
      this.maxValueForGenes = maxValueForGenes;
    }
    
    public int GetNewGeneValue(Genome genome)
    {
      return GenomeManagement.RandomGenerator.Next(genome.MinValueForGenes,
                                            genome.MaxValueForGenes + 1);
    }

 		public Genome[] GetChilds(Genome parent1, Genome parent2)
    {
      //return GenomeManagement.UniformCrossover(parent1, parent2);
			//return GenomeManagement.AlternateFixedCrossover(parent1, parent2);
    	return GenomeManagement.OnePointCrossover(parent1, parent2);
    }
		
		public void Mutate(Genome genome, double mutationRate)
    {
      GenomeManagement.MutateAllGenes(genome, mutationRate);
    }
    
    public double GetFitnessValue(Genome genome)
    {
      int[] intArray = genome.Genes();
      double returnValue;
      //function to be maximized
      double sum = 0;
      double product = 1;
      for (int i = 0; i < genome.Size; i++)
      {
        sum += (int)intArray[i];
        product *= (int)intArray[i];
      }
      returnValue = (double)(1/product);// fitness = 1 iff product is minimized
      //returnValue = (double)(product/sum);
      return returnValue;
    }
    
    public object Decode(Genome genome)
    {
      string sequenceOfGenes = "";
      foreach(int index in genome.Genes())
      {
        sequenceOfGenes += index + ";" ;
      }
      return (object)sequenceOfGenes;
    }

  }

}

--- NEW FILE: GenomeComparer.cs ---
/*
QuantProject - Quantitative Finance Library

GenomeComparer.cs
Copyright (C) 2003 
Marco Milletti

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

using System;
using System.Collections;

namespace QuantProject.ADT.Optimizing.Genetic
{
	/// <summary>
	/// Compares genomes by fitness
	/// </summary>
	public sealed class GenomeComparer : IComparer
	{
		public GenomeComparer()
		{
		}
		public int Compare( object x, object y)
		{
			if ( !(x is Genome) || !(y is Genome))
				throw new ArgumentException("Not of type Genome");

			if (((Genome) x).Fitness > ((Genome) y).Fitness)
				return 1;
			else if (((Genome) x).Fitness == ((Genome) y).Fitness)
				return 0;
			else
				return -1;
		}
	}
}

--- NEW FILE: IGenomeManager.cs ---
/*
QuantProject - Quantitative Finance Library

IGenomeManager.cs
Copyright (C) 2004 
Marco Milletti

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

using System;


namespace QuantProject.ADT.Optimizing.Genetic
{
	/// <summary>
	/// Interface to be implemented by any object used to run
	/// an instance of the GeneticOptimizer class.
	/// 
	/// The interface determines the genome format and provides:
	/// - an objective function used to calculate genome's fitness;
	/// - a decode function used to calculate genome's meaning as an object;
	/// - a GetChilds method used by the genetic optimizer to generate new
	///   population;
	/// - a Mutate method used by the genetic optimizer to mutate a 
	///   given genome
	/// </summary>
	public interface IGenomeManager
	{
    int GenomeSize{get;}
    int MinValueForGenes{get;}
    int MaxValueForGenes{get;}
    
    int GetNewGeneValue(Genome genome); // Used in generation of genes
    																    //  by the Genome parameter
    double GetFitnessValue(Genome genome);
    object Decode(Genome genome);
		Genome[] GetChilds(Genome parent1, Genome parent2);
		void Mutate(Genome genome, double mutationRate);
  }
}

--- NEW FILE: GenomeManagement.cs ---
/*
QuantProject - Quantitative Finance Library

GenomeManagement.cs
Copyright (C) 2003 
Marco Milletti

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/


using System;
using System.Collections;
using QuantProject.ADT.Optimizing.Genetic;

namespace QuantProject.ADT.Optimizing.Genetic
{
	/// <summary>
	/// Class providing static methods to manage Genomes
	/// (crossovering, mutating, etc.)
	/// </summary>
  public sealed class GenomeManagement 
	{
		
    public static Random RandomGenerator = new Random((int)DateTime.Now.Ticks);
    private static int genomeSize;
		private static Genome[] childs;
		private static int[,] maskForChilds;
    /*
    public GenomeManagement()
    {
	  				    	
		}
		*/
  	/// <summary>
		/// Returns an array of genome (childs) based 
		/// on classical one point crossover genes recombination
		/// </summary>
  	public static Genome[] OnePointCrossover(Genome parent1, Genome parent2)
		{
			if(parent1.Size != parent2.Size)
				throw new Exception("Genomes must have the same size!");	
			GenomeManagement.genomeSize = parent1.Size;
		  GenomeManagement.childs = new Genome[2]{parent1.Clone(),parent1.Clone()};
			
			int pos = GenomeManagement.RandomGenerator.Next(0, parent1.Size);
			for(int i = 0 ; i < parent1.Size ; i++)
			{
				if (i < pos)
				{
					childs[0].SetGeneValue(parent1.GetGeneValue(i), i);
					childs[1].SetGeneValue(parent2.GetGeneValue(i), i);
				}
				else
				{
					childs[0].SetGeneValue(parent2.GetGeneValue(i), i);
					childs[1].SetGeneValue(parent1.GetGeneValue(i), i);
				}
			}
			return GenomeManagement.childs;
		}
		
		private static void setMaskForChildsForUniformCrossover()
		{
			for(int childIndex = 0 ;
					childIndex < GenomeManagement.childs.Length;
					childIndex++)
      {
        for(int i = 0 ; i < GenomeManagement.genomeSize ; i++)
      	{
  	      maskForChilds[childIndex,i] = GenomeManagement.RandomGenerator.Next(1,3);
       	}
      }
		}
		
		private static void setMaskForChildsForAlternateFixedCrossover()
		{
			for(int childIndex = 0 ;
					childIndex < GenomeManagement.childs.Length;
					childIndex++)
      {
        for(int i = 0 ; i < GenomeManagement.genomeSize ; i++)
      	{
  	  		if(i%2 == 0)
					//index is even
						maskForChilds[childIndex, i] = 1;
					else
					// index is odd
						maskForChilds[childIndex, i] = 2;
	     	}
      }
		}
		
		private static void setMaskForChildsForMixingWithoutDuplicates(Genome parent1, Genome parent2)
		{
			for(int childIndex = 0 ;
					childIndex < GenomeManagement.childs.Length;
					childIndex++)
      {
        for(int i = 0 ; i < GenomeManagement.genomeSize ; i++)
      	{
   	      if(parent2.HasGene(parent1.GetGeneValue(i)) ||
   	         parent1.HasGene(parent2.GetGeneValue(i)))//index contains a common gene
  	      {
						maskForChilds[childIndex, i] = childIndex + 1;
  	      }
					else// index doesn't contain a common gene
					{
  	      	if(i%2 == 0)//index is even
							maskForChilds[childIndex, i] = childIndex%2 + 1;
						else// index is odd
							maskForChilds[childIndex, i] = childIndex%2 + 2;
					}
       	}
      }
		}
		
		//it assumes just two parents only
		private static void setChildsUsingMaskForChilds(Genome parent1,
		                                                Genome parent2)
		{
			for(int childIndex = 0 ;
					childIndex < GenomeManagement.childs.Length;
					childIndex++)
      {
        for(int i = 0 ; i < GenomeManagement.genomeSize ; i++)
      	{
  	      if(maskForChilds[childIndex,i]==1)
           	childs[childIndex].SetGeneValue(parent1.GetGeneValue(i), i);
       		else//maskForChilds[childIndex,i]==2
           	childs[childIndex].SetGeneValue(parent2.GetGeneValue(i), i);
        }
      }
			
		}
		
    /// <summary>
		/// This method returns an array of genomes based on 
		/// a random recombination of the genes of parents
		/// </summary> 
    public static Genome[] UniformCrossover(Genome parent1, Genome parent2)
    {
      if(parent1.Size != parent2.Size)
				throw new Exception("Genomes must have the same size!");	
      GenomeManagement.genomeSize = parent1.Size;
      GenomeManagement.childs = 
      						new Genome[2]{parent1.Clone(),parent1.Clone()};
      GenomeManagement.maskForChilds = new int[childs.Length, GenomeManagement.genomeSize];
			GenomeManagement.setMaskForChildsForUniformCrossover();
     	GenomeManagement.setChildsUsingMaskForChilds(parent1, parent2);
			    
      return GenomeManagement.childs;
    }

    /// <summary>
		/// This method returns an array of genomes based on 
		/// an alternate fixed recombination of the genes of parents
		/// </summary> 
    public static Genome[] AlternateFixedCrossover(Genome parent1, Genome parent2)
    {
      if(parent1.Size != parent2.Size)
				throw new Exception("Genomes must have the same size!");	
      GenomeManagement.genomeSize = parent1.Size;
      GenomeManagement.childs = 
      						new Genome[2]{parent1.Clone(),parent1.Clone()};
      GenomeManagement.maskForChilds = new int[childs.Length, GenomeManagement.genomeSize];
      GenomeManagement.setMaskForChildsForAlternateFixedCrossover();
     	GenomeManagement.setChildsUsingMaskForChilds(parent1, parent2);
      
      return GenomeManagement.childs;
    }

		/// <summary>
		/// This method returns an array of genomes based on 
		/// a mix of the genes of parents, such that childs,
		/// if possible, are different from parents and, at 
		/// the same time, childs' genes are not duplicated  
		/// </summary> 
    public static Genome[] MixGenesWithoutDuplicates(Genome parent1, Genome parent2)
    {
      if(parent1.Size > (parent1.MaxValueForGenes - parent1.MinValueForGenes + 1))
			//it is impossible not to duplicate genes if size is too
			// large for the range of variation of each gene
				throw new Exception("Impossible to avoid duplicates with the given size!");
      if(parent1.Size != parent2.Size)
				throw new Exception("Genomes must have the same size!");	
      GenomeManagement.genomeSize = parent1.Size;
      GenomeManagement.childs = 
      						new Genome[2]{parent1.Clone(),parent1.Clone()};
      GenomeManagement.maskForChilds = new int[childs.Length, GenomeManagement.genomeSize];
      GenomeManagement.setMaskForChildsForMixingWithoutDuplicates(parent1, parent2);
     	GenomeManagement.setChildsUsingMaskForChilds(parent1, parent2);
      
      return GenomeManagement.childs;
    }


		static public void MutateAllGenes(Genome genome, double mutationRate)
		{
			for (int pos = 0 ; pos < genome.Size; pos++)
			{
				if (GenomeManagement.RandomGenerator.Next(0,101) < (int)(mutationRate*100))
					genome.SetGeneValue(GenomeManagement.RandomGenerator.Next(genome.MinValueForGenes,
                                   genome.MaxValueForGenes + 1), pos);
			}
		}
		
		static public void MutateOneGene(Genome genome, double mutationRate,
		                          				int genePosition)
		{
		
			if (GenomeManagement.RandomGenerator.Next(0,101) < (int)(mutationRate*100))
				genome.SetGeneValue(GenomeManagement.RandomGenerator.Next(genome.MinValueForGenes,
                            genome.MaxValueForGenes + 1), genePosition);
			
		}
    
    static public void MutateOneGene(Genome genome, double mutationRate,
                                      int genePosition, int newValueOfGene)
    {
		  if (GenomeManagement.RandomGenerator.Next(0,101) < (int)(mutationRate*100))
              genome.SetGeneValue(newValueOfGene, genePosition);
			
    }
	}
}