source: branches/2747_CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/GeneticAlgorithm.cs @ 17958

#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 {
  public enum OptimalAssignmentType { None, Polynomial, OneOpt, Both };

  [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; }
    }
    [Storable]
    private IFixedValueParameter<EnumValue<OptimalAssignmentType>> optimalAssignmentParameter;
    public IFixedValueParameter<EnumValue<OptimalAssignmentType>> OptimalAssignmentParameter {
      get { return optimalAssignmentParameter; }
    }

    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; }
    }
    public OptimalAssignmentType OptimalAssignment {
      get { return optimalAssignmentParameter.Value.Value; }
      set { optimalAssignmentParameter.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);
      optimalAssignmentParameter = cloner.Clone(original.optimalAssignmentParameter);

      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(500)));
      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)));
      Parameters.Add(optimalAssignmentParameter = new FixedValueParameter<EnumValue<OptimalAssignmentType>>("OptimalAssignment", "Which optimal assignment strategy should be used.", new EnumValue<OptimalAssignmentType>(OptimalAssignmentType.Polynomial)));
    }

    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) {
            switch (OptimalAssignment) {
              case OptimalAssignmentType.None:
                break;
              case OptimalAssignmentType.Polynomial:
                OptimalPolynomialAssignment(nextGeneration[p]);
                break;
              case OptimalAssignmentType.OneOpt:
                OneOptAssignment(nextGeneration[p]);
                break;
              case OptimalAssignmentType.Both:
                HybridAssignment(nextGeneration[p]);
                break;
              default:
                throw new InvalidOperationException("Optimal assignment strategy not defined.");
            }

          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 void OptimalPolynomialAssignment(EncodedSolution generation) {
      if (!optimalSequences.Contains(generation.Sequence)) {
        var assignment = Scheduling.CFSAP.OptimalPolynomialAssignment.MakeAssignment(generation.Sequence, Problem.ProcessingTimes, Problem.SetupTimes, out var cycleTime);
        evaluatedSolutions++;
        generation.Assignment = new BinaryVector(assignment.Select(x => x == 1).ToArray());
        generation.Quality = cycleTime;
        optimalSequences.Add(generation.Sequence);
      }
    }

    private void OneOptAssignment(EncodedSolution generation) {
      var assignment = Scheduling.CFSAP.OneOptAssignment.MakeAssignment(generation.Sequence, generation.Assignment, Problem.ProcessingTimes, Problem.SetupTimes, out var cycleTime);
      evaluatedSolutions++;
      generation.Assignment = assignment;
      generation.Quality = cycleTime;
    }

    private void HybridAssignment(EncodedSolution generation) {
      var a = random.Next(2);
      switch (a) {
        case 0: OptimalPolynomialAssignment(generation); break;
        case 1: OneOptAssignment(generation); break;
        default: throw new InvalidOperationException("Assignment not defined.");
      }
    }

    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 m = random.Next(7);
      switch (m) {
        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("Manipulator 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));
    }

    [StorableClass]
    private class EncodedSolution : DeepCloneable, IComparable<EncodedSolution> {
      [Storable]
      public Permutation Sequence { get; set; }
      [Storable]
      public BinaryVector Assignment { get; set; }
      [Storable]
      public double Quality { get; set; }

      [StorableConstructor]
      private EncodedSolution(bool deserializing) { }

      private EncodedSolution(EncodedSolution original, Cloner cloner) : base(original, cloner) {
        Sequence = cloner.Clone(original.Sequence);
        Assignment = cloner.Clone(original.Assignment);
        Quality = original.Quality;
      }

      public EncodedSolution() { }

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

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