source: branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/GeneticAlgorithm.cs @ 15493

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab 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.
 *
 * HeuristicLab 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 HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.BinaryVectorEncoding;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Random;

namespace HeuristicLab.Problems.Scheduling.CFSAP {
  [Item("Genetic Algorithm (CFSAP)", "")]
  [StorableClass]
  public class GeneticAlgorithm : BasicAlgorithm {
    public override bool SupportsPause { get { return true; } }

    public override Type ProblemType {
      get { return typeof(CFSAP); }
    }

    public new CFSAP Problem {
      get { return (CFSAP)base.Problem; }
      set { base.Problem = value; }
    }

    [Storable]
    private IFixedValueParameter<IntValue> populationSizeParameter;
    public IFixedValueParameter<IntValue> PopulationSizeParameter {
      get { return populationSizeParameter; }
    }
    [Storable]
    private IFixedValueParameter<IntValue> elitesParameter;
    public IFixedValueParameter<IntValue> ElitesParameter {
      get { return elitesParameter; }
    }
    [Storable]
    private IFixedValueParameter<PercentValue> mutationProbabilityParameter;
    public IFixedValueParameter<PercentValue> MutationProbabilityParameter {
      get { return mutationProbabilityParameter; }
    }
    [Storable]
    private IFixedValueParameter<IntValue> maximumGenerationsParameter;
    public IFixedValueParameter<IntValue> MaximumGenerationsParameter {
      get { return maximumGenerationsParameter; }
    }
    [Storable]
    private IFixedValueParameter<IntValue> maximumEvaluatedSolutionsParameter;
    public IFixedValueParameter<IntValue> MaximumEvaluatedSolutionsParameter {
      get { return maximumEvaluatedSolutionsParameter; }
    }
    [Storable]
    private IFixedValueParameter<BoolValue> pauseAfterGenerationParameter;
    public IFixedValueParameter<BoolValue> PauseAfterGenerationParameter {
      get { return pauseAfterGenerationParameter; }
    }

    public int PopulationSize {
      get { return populationSizeParameter.Value.Value; }
      set { populationSizeParameter.Value.Value = value; }
    }
    public int Elites {
      get { return elitesParameter.Value.Value; }
      set { elitesParameter.Value.Value = value; }
    }
    public double MutationProbability {
      get { return mutationProbabilityParameter.Value.Value; }
      set { mutationProbabilityParameter.Value.Value = value; }
    }
    public int MaximumGenerations {
      get { return maximumGenerationsParameter.Value.Value; }
      set { maximumGenerationsParameter.Value.Value = value; }
    }
    public int MaximumEvaluatedSolutions {
      get { return maximumEvaluatedSolutionsParameter.Value.Value; }
      set { maximumEvaluatedSolutionsParameter.Value.Value = value; }
    }
    public bool PauseAfterGeneration {
      get { return pauseAfterGenerationParameter.Value.Value; }
      set { pauseAfterGenerationParameter.Value.Value = value; }
    }

    [StorableConstructor]
    protected GeneticAlgorithm(bool deserializing) : base(deserializing) { }
    protected GeneticAlgorithm(GeneticAlgorithm original, Cloner cloner)
      : base(original, cloner) {
      populationSizeParameter = cloner.Clone(original.populationSizeParameter);
      elitesParameter = cloner.Clone(original.elitesParameter);
      mutationProbabilityParameter = cloner.Clone(original.mutationProbabilityParameter);
      maximumGenerationsParameter = cloner.Clone(original.maximumGenerationsParameter);
      maximumEvaluatedSolutionsParameter = cloner.Clone(original.maximumEvaluatedSolutionsParameter);
      pauseAfterGenerationParameter = cloner.Clone(original.pauseAfterGenerationParameter);
      generation = original.generation;
      evaluatedSolutions = original.evaluatedSolutions;
      bestQuality = original.bestQuality;
      if (original.population != null)
        population = original.population.Select(cloner.Clone).ToArray();
      if (original.nextGeneration != null)
        nextGeneration = original.nextGeneration.Select(cloner.Clone).ToArray();
      if (original.optimalSequences != null)
        optimalSequences = new HashSet<Permutation>(original.optimalSequences, new PermutationEqualityComparer());
    }
    public GeneticAlgorithm() {
      Parameters.Add(populationSizeParameter = new FixedValueParameter<IntValue>("PopulationSize", "The size of the population, each individual of the population is a solution with a permutation and a binary vector.", new IntValue(100)));
      Parameters.Add(elitesParameter = new FixedValueParameter<IntValue>("Elites", "The number of best individuals from the previous population that will continue to the next generation.", new IntValue(1)));
      Parameters.Add(mutationProbabilityParameter = new FixedValueParameter<PercentValue>("MutationProbability", "The probability that an individual should be mutated after it has been created through crossover.", new PercentValue(0.05)));
      Parameters.Add(maximumGenerationsParameter = new FixedValueParameter<IntValue>("MaximumGenerations", "The number of generations that the algorithm may run for.", new IntValue(1000000)));
      Parameters.Add(maximumEvaluatedSolutionsParameter = new FixedValueParameter<IntValue>("MaximumEvaluatedSolutions", "The number of evaluated solutions before the algorithm terminates.", new IntValue(100000000)));
      Parameters.Add(pauseAfterGenerationParameter = new FixedValueParameter<BoolValue>("PauseAfterGeneration", "Whether the algorithm should pause after each generation.", new BoolValue(true)));
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new GeneticAlgorithm(this, cloner);
    }

    protected override void OnProblemChanged() {
      base.OnProblemChanged();
    }
    
    [Storable]
    private IRandom random;
    [Storable]
    private int generation;
    [Storable]
    private int evaluatedSolutions;
    [Storable]
    private double bestQuality;
    [Storable]
    private EncodedSolution[] population;
    [Storable]
    private EncodedSolution[] nextGeneration;
    [Storable]
    private HashSet<Permutation> optimalSequences;

    protected override void Initialize(CancellationToken cancellationToken) {
      base.Initialize(cancellationToken);
      random = new MersenneTwister();
      optimalSequences = new HashSet<Permutation>(new PermutationEqualityComparer());
      generation = 0;
      evaluatedSolutions = 0;
      population = new EncodedSolution[PopulationSize];
      nextGeneration = new EncodedSolution[PopulationSize - Elites];
      bestQuality = double.MaxValue;
      for (var p = 0; p < PopulationSize; p++) {
        population[p] = new EncodedSolution() {
          Sequence = new Permutation(PermutationTypes.RelativeDirected, Problem.ProcessingTimes.Columns, random),
          Assignment = new BinaryVector(Problem.ProcessingTimes.Columns, random)
        };
        population[p].Quality = Problem.Evaluate(population[p].Sequence, population[p].Assignment);
        evaluatedSolutions++;
        if (population[p].Quality < bestQuality) bestQuality = population[p].Quality;
      }
      Array.Sort(population);
      Results.Add(new Result("BestQuality", new DoubleValue(bestQuality)));
      Results.Add(new Result("EvaluatedSolutions", new IntValue(evaluatedSolutions)));
      Results.Add(new Result("Generation", new IntValue(generation)));
      if (PauseAfterGeneration) Pause();
    }

    protected override void Run(CancellationToken cancellationToken) {
      if (cancellationToken.IsCancellationRequested) return;

      while (generation < MaximumGenerations) {
        if (evaluatedSolutions > MaximumEvaluatedSolutions) return;
        for (var p = 0; p < PopulationSize - Elites; p++) {
          var parent1 = TournamentSelect((int)Math.Round(Math.Max(PopulationSize / 71.0, 2)));
          var parent2 = TournamentSelect((int)Math.Round(Math.Max(PopulationSize / 71.0, 2)));
          nextGeneration[p] = new EncodedSolution() {
            Sequence = CrossSequence(parent1.Sequence, parent2.Sequence),
            Assignment = CrossAssignment(parent1.Assignment, parent2.Assignment)
          };
          var mutProb = random.NextDouble();
          if (mutProb < MutationProbability) {
            MutateSequence(nextGeneration[p].Sequence);
            MutateAssignment(nextGeneration[p].Assignment);
          }
          nextGeneration[p].Quality = Problem.Evaluate(nextGeneration[p].Sequence, nextGeneration[p].Assignment);
          evaluatedSolutions++;

          if (nextGeneration[p].Quality <= bestQuality) {
            if (!optimalSequences.Contains(nextGeneration[p].Sequence)) {
              int cycleTime;
              var assignment = OptimalAssignment.MakeAssignment(nextGeneration[p].Sequence, Problem.ProcessingTimes, Problem.SetupTimes, out cycleTime);
              evaluatedSolutions++;
              nextGeneration[p].Assignment = new BinaryVector(assignment.Select(x => x == 1).ToArray());
              nextGeneration[p].Quality = cycleTime;
              optimalSequences.Add(nextGeneration[p].Sequence);
            }
            if (nextGeneration[p].Quality < bestQuality) {
              bestQuality = nextGeneration[p].Quality;
              ((DoubleValue)Results["BestQuality"].Value).Value = bestQuality;
            }
          }
        }

        for (var p = Elites; p < PopulationSize; p++) {
          population[p] = nextGeneration[p - Elites];
        }
        Array.Sort(population);

        generation++;

        ((IntValue)Results["EvaluatedSolutions"].Value).Value = evaluatedSolutions;
        ((IntValue)Results["Generation"].Value).Value = generation;

        if (PauseAfterGeneration || cancellationToken.IsCancellationRequested) {
          if (!cancellationToken.IsCancellationRequested) Pause();
          break;
        }
      }
    }

    private EncodedSolution TournamentSelect(int groupSize) {
      var selected = population[random.Next(population.Length)];
      for (var i = 1; i < groupSize; i++) {
        var competitor = population[random.Next(population.Length)];
        if (selected.Quality > competitor.Quality) {
          selected = competitor;
        }
      }
      return selected;
    }

    private Permutation CrossSequence(Permutation sequence1, Permutation sequence2) {
      var cx = random.Next(3);
      switch (cx) {
        case 0: return OrderCrossover.Apply(random, sequence1, sequence2);
        case 1: return OrderCrossover2.Apply(random, sequence1, sequence2);
        case 2: return MaximalPreservativeCrossover.Apply(random, sequence1, sequence2);
        default: throw new InvalidOperationException("Crossover not defined.");
      }
    }

    private void MutateSequence(Permutation sequence) {
      var cx = random.Next(7);
      switch (cx) {
        case 0: InversionManipulator.Apply(random, sequence); break;
        case 1: InsertionManipulator.Apply(random, sequence); break;
        case 2: Swap2Manipulator.Apply(random, sequence); break;
        case 3: Swap3Manipulator.Apply(random, sequence); break;
        case 4: TranslocationManipulator.Apply(random, sequence); break;
        case 5: TranslocationInversionManipulator.Apply(random, sequence); break;
        case 6: ScrambleManipulator.Apply(random, sequence); break;
        default: throw new InvalidOperationException("Crossover not defined.");
      }
    }

    private BinaryVector CrossAssignment(BinaryVector assign1, BinaryVector assign2) {
      var cx = random.Next(3);
      switch (cx) {
        case 0: return UniformCrossover.Apply(random, assign1, assign2);
        case 1: return NPointCrossover.Apply(random, assign1, assign2, new IntValue(1));
        case 2: return NPointCrossover.Apply(random, assign1, assign2, new IntValue(2));
        default: throw new InvalidOperationException("Crossover not defined.");
      }
    }

    private void MutateAssignment(BinaryVector assignment) {
      SomePositionsBitflipManipulator.Apply(random, assignment, new DoubleValue(0.2));
    }

    private class EncodedSolution : IDeepCloneable, IComparable<EncodedSolution> {
      public Permutation Sequence { get; set; }
      public BinaryVector Assignment { get; set; }
      public double Quality { get; set; }

      public IDeepCloneable Clone(Cloner cloner) {
        return new EncodedSolution() {
          Sequence = cloner.Clone(this.Sequence),
          Assignment = cloner.Clone(this.Assignment),
          Quality = this.Quality
        };
      }

      public object Clone() {
        return Clone(new Cloner());
      }

      public int CompareTo(EncodedSolution other) {
        return Quality.CompareTo(other.Quality);
      }
    }
  }
}