context: /* ***************************************************************************
   * This file is part of SharpNEAT - Evolution of Neural Networks.
   * 
   * Copyright 2004-2006, 2009-2010 Colin Green (sharpneat@gmail.com)
   *
   * SharpNEAT 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 3 of the License, or
   * (at your option) any later version.
   *
   * SharpNEAT 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 SharpNEAT.  If not, see <http://www.gnu.org/licenses/>.
   */
  
  using System;
  using System.Collections.Generic;
  using System.Diagnostics;
  using SharpNEAT.Core.DistanceMetrics;
  using SharpNEAT.Core.SpeciationStrategies;
  using SharpNEAT.Evolution.ComplexityRegulation;
  using SharpNEAT.Interfaces;
  using SharpNeat;
  using SharpNeat.Core;
  using SharpNeat.Utility;
  
  namespace SharpNEAT.Evolution
  {
      /// <summary>
      /// Implementation of the NEAT evolution algorithm. 
      /// Incorporates:
      ///     - Speciation with fitness sharing.
      ///     - Creating offspring via both sexual and asexual reproduction.
      /// </summary>
      /// <typeparam name="TGenome">The genome type that the algorithm will operate on.</typeparam>
      public class NeatEvolutionAlgorithm<TGenome> : AbstractGenerationalAlgorithm<TGenome>
          where TGenome : class, IGenome<TGenome>
      {
          NeatEvolutionAlgorithmParameters _eaParams;
          readonly NeatEvolutionAlgorithmParameters _eaParamsComplexifying;
          readonly NeatEvolutionAlgorithmParameters _eaParamsSimplifying;
  
          readonly ISpeciationStrategy<TGenome> _speciationStrategy;
          IList<ISpecie<TGenome>> _specieList;
          /// <summary>Index of the specie that contains _currentBestGenome.</summary>
          int _bestSpecieIdx;
          readonly FastRandom _rng = new FastRandom();
          readonly NeatAlgorithmStats _stats;
  
          ComplexityRegulationMode _complexityRegulationMode;
          readonly IComplexityRegulationStrategy _complexityRegulationStrategy;
  
          #region Constructors
  
          /// <summary>
          /// Constructs with the default NeatEvolutionAlgorithmParameters and speciation strategy 
          /// (KMeansClusteringStrategy with ManhattanDistanceMetric).
          /// </summary>
          public NeatEvolutionAlgorithm()
          {
              _eaParams = new NeatEvolutionAlgorithmParameters();
              _eaParamsComplexifying = _eaParams;
              _eaParamsSimplifying = _eaParams.CreateSimplifyingParameters();
              _stats = new NeatAlgorithmStats(_eaParams);
              _speciationStrategy = new KMeansClusteringStrategy<TGenome>(new ManhattanDistanceMetric());
  
              _complexityRegulationMode = ComplexityRegulationMode.Complexifying;
              _complexityRegulationStrategy = new NullComplexityRegulationStrategy();
          }
  
          /// <summary>
          /// Constructs with the provided NeatEvolutionAlgorithmParameters and ISpeciationStrategy.
          /// </summary>
          public NeatEvolutionAlgorithm(NeatEvolutionAlgorithmParameters eaParams,
                                        ISpeciationStrategy<TGenome> speciationStrategy,
                                        IComplexityRegulationStrategy complexityRegulationStrategy)
          {
              _eaParams = eaParams;
              _eaParamsComplexifying = _eaParams;
              _eaParamsSimplifying = _eaParams.CreateSimplifyingParameters();
              _stats = new NeatAlgorithmStats(_eaParams);
              _speciationStrategy = speciationStrategy;
  
              _complexityRegulationMode = ComplexityRegulationMode.Complexifying;
              _complexityRegulationStrategy = complexityRegulationStrategy;
          }
  
          #endregion
  
          #region Properties
  
          /// <summary>
          /// Gets a list of all current genomes. The current population of genomes. These genomes
          /// are also divided into the species available through the SpeciesList property.
          /// </summary>
          public IList<TGenome> GenomeList
          {
              get { return _genomeList; }
          }
  
          /// <summary>
          /// Gets a list of all current species. The genomes contained within the species are the same genomes
          /// available through the GenomeList property.
          /// </summary>
          public IList<ISpecie<TGenome>> SpecieList
          {
              get { return _specieList; }
          }
  
          /// <summary>
          /// Gets the algorithm statistics object.
          /// </summary>
          public NeatAlgorithmStats Statistics
          {
              get { return _stats; }
          }
  
          /// <summary>
          /// Gets the current complexity regulation mode.
          /// </summary>
          public ComplexityRegulationMode ComplexityRegulationMode
          {
              get { return _complexityRegulationMode; }
          }
  
          #endregion
  
          #region Public Methods [Initialization]
  
          /// <summary>
          /// Initializes the evolution algorithm with the provided IGenomeListEvaluator, IGenomeFactory
          /// and an initial population of genomes.
          /// </summary>
          /// <param name="genomeListEvaluator">The genome evaluation scheme for the evolution algorithm.</param>
          /// <param name="genomeFactory">The factory that was used to create the genomeList and which is therefore referenced by the genomes.</param>
          /// <param name="genomeList">An initial genome population.</param>
          public override void Initialize(IGenomeListEvaluator<TGenome> genomeListEvaluator,
                                          IGenomeFactory<TGenome> genomeFactory,
                                          List<TGenome> genomeList)
          {
              base.Initialize(genomeListEvaluator, genomeFactory, genomeList);
              Initialize();
          }
  
          /// <summary>
          /// Initializes the evolution algorithm with the provided IGenomeListEvaluator
          /// and an IGenomeFactory that can be used to create an initial population of genomes.
          /// </summary>
          /// <param name="genomeListEvaluator">The genome evaluation scheme for the evolution algorithm.</param>
          /// <param name="genomeFactory">The factory that was used to create the genomeList and which is therefore referenced by the genomes.</param>
          /// <param name="populationSize">The number of genomes to create for the initial population.</param>
          public override void Initialize(IGenomeListEvaluator<TGenome> genomeListEvaluator,
                                          IGenomeFactory<TGenome> genomeFactory,
                                          int populationSize)
          {
              base.Initialize(genomeListEvaluator, genomeFactory, populationSize);
              Initialize();
          }
  
          /// <summary>
          /// Code common to both public Initialize methods.
          /// </summary>
          private void Initialize()
          {
              // Evaluate the genomes.
              _genomeListEvaluator.Evaluate(_genomeList);
  
              // Speciate the genomes.
              _specieList = _speciationStrategy.InitializeSpeciation(_genomeList, _eaParams.SpecieCount);
              Debug.Assert(!TestForEmptySpecies(_specieList), "Speciation resulted in one or more empty species.");
              
              // Sort the genomes in each specie fittest first, secondary sort youngest first.
              SortSpecieGenomes();
  
              // Store ref to best genome.
              UpdateBestGenome();
          }
  
          #endregion
  
          #region Evolution Algorithm Main Method [PerformOneGeneration]
  
          /// <summary>
          /// Progress forward by one generation. Perform one generation/iteration of the evolution algorithm.
          /// </summary>
          protected override void PerformOneGeneration()
          {
              // Calculate statistics for each specie (mean fitness, target size, number of offspring to produce etc.)
              int offspringCount;
              SpecieStats[] specieStatsArr = CalcSpecieStats(out offspringCount);
  
              // Create offspring.
              List<TGenome> offspringList = CreateOffspring(specieStatsArr, offspringCount);
  
              // Trim species back to their elite genomes.
              bool emptySpeciesFlag = TrimSpeciesBackToElite(specieStatsArr);
  
              // Rebuild _genomeList. It will now contain just the elite genomes.
              RebuildGenomeList();
  
              // Append offspring genomes to the elite genomes in _genomeList. We do this before calling the
              // _genomeListEvaluator.Evaluate because some evaluation schemes re-evaluate the elite genomes 
              // (otherwise we could just evaluate offspringList).
              _genomeList.AddRange(offspringList);
  
              // Evaluate genomes.
              _genomeListEvaluator.Evaluate(_genomeList);
  
              // Integrate offspring into species.
              if(emptySpeciesFlag)
              {   
                  // We have one or more terminated species. Therefore we need to fully re-speciate all genomes to divide them
                  // evenly between the required number of species.
  
                  // Clear all genomes from species (we still have the elite genomes in _genomeList).
                  ClearAllSpecies();
  
                  // Speciate genomeList.
                  _speciationStrategy.SpeciateGenomes(_genomeList, _specieList);
              }
              else
              {
                  // Integrate offspring into the existing species. 
                  _speciationStrategy.SpeciateOffspring(offspringList, _specieList);            
              }
              Debug.Assert(!TestForEmptySpecies(_specieList), "Speciation resulted in one or more empty species.");
  
              // Sort the genomes in each specie. Fittest first (secondary sort - youngest first).
              SortSpecieGenomes();
               
              // Update stats and store reference to best genome.
              UpdateBestGenome();
              UpdateStats();
  
              // Determine the complexity regulation mode and switch over to the appropriate set of evolution
              // algorithm parameters. Also notify the genome factory to allow it to modify how it creates genomes
              // (e.g. reduce or disable additive mutations).
              _complexityRegulationMode = _complexityRegulationStrategy.DetermineMode(_stats);
              _genomeFactory.SearchMode = (int)_complexityRegulationMode;
              switch(_complexityRegulationMode)
              {
                  case ComplexityRegulationMode.Complexifying:
                      _eaParams = _eaParamsComplexifying;
                      break;
                  case ComplexityRegulationMode.Simplifying:
                      _eaParams = _eaParamsSimplifying;
                      break;
              }
  
              // TODO: More checks.
              Debug.Assert(_genomeList.Count == _populationSize);
          }
  
          #endregion
  
          #region Private Methods [High Level Algorithm Methods. CalcSpecieStats/CreateOffspring]
  
          /// <summary>
          /// Calculate statistics for each specie. This method is at the heart of the evolutionary algorithm,
          /// the key things that are achieved in this method are - for each specie we calculate:
          ///  1) The target size based on fitness of the specie's member genomes.
          ///  2) The elite size based on the current size. Potentially this could be higher than the target 
          ///     size, so a target size is taken to be a hard limit.
          ///  3) Following (1) and (2) we can calculate the total number offspring that need to be generated 
          ///     for the current generation.
          /// </summary>
          private SpecieStats[] CalcSpecieStats(out int offspringCount)
          {
              double totalMeanFitness = 0.0;
  
              // Build stats array and get the mean fitness of each specie.
              int specieCount = _specieList.Count;
              SpecieStats[] specieStatsArr = new SpecieStats[specieCount];
              for(int i=0; i<specieCount; i++)
              {   
                  SpecieStats inst = new SpecieStats();
                  specieStatsArr[i] = inst;
                  inst._meanFitness = _specieList[i].CalcMeanFitness();
                  totalMeanFitness += inst._meanFitness;
              }
  
              // Calculate the new target size of each specie using fitness sharing. 
              // Keep a total of all allocated target sizes, typically this will vary slightly from the
              // overall target population size due to rounding of each real/fractional target size.
              int totalTargetSizeInt = 0;
  
              if(0.0 == totalMeanFitness)
              {   // Handle specific case where all genomes/species have a zero fitness. 
                  // Assign all species an equal targetSize.
                  double targetSizeReal = (double)_populationSize / (double)specieCount;
  
  
gt:                 for(int i=0; i<specieCount; i++) 