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

Last change on this file since 15533 was 15533, checked in by ddorfmei, 5 years ago

#2747: Improved hard-coded genetic algorithm

  • implemented restart strategy
  • implemented 1-Opt algorithm
  • added parameters to control restart strategy and optimal assignment strategy
  • additional results: best solution found after number of generations, jobs/nests (for evaluation only)
File size: 16.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Threading;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.BinaryVectorEncoding;
30using HeuristicLab.Encodings.PermutationEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Problems.Scheduling.CFSAP {
37  public enum OptimalAssignmentType { None, Polynomial, OneOpt, Both };
38
39  [Item("Genetic Algorithm (CFSAP)", "")]
40  [StorableClass]
41  public class GeneticAlgorithm : BasicAlgorithm {
42    public override bool SupportsPause { get { return true; } }
43
44    public override Type ProblemType {
45      get { return typeof(CFSAP); }
46    }
47
48    public new CFSAP Problem {
49      get { return (CFSAP)base.Problem; }
50      set { base.Problem = value; }
51    }
52
53    [Storable]
54    private IFixedValueParameter<IntValue> populationSizeParameter;
55    public IFixedValueParameter<IntValue> PopulationSizeParameter {
56      get { return populationSizeParameter; }
57    }
58    [Storable]
59    private IFixedValueParameter<IntValue> elitesParameter;
60    public IFixedValueParameter<IntValue> ElitesParameter {
61      get { return elitesParameter; }
62    }
63    [Storable]
64    private IFixedValueParameter<PercentValue> mutationProbabilityParameter;
65    public IFixedValueParameter<PercentValue> MutationProbabilityParameter {
66      get { return mutationProbabilityParameter; }
67    }
68    [Storable]
69    private IFixedValueParameter<IntValue> maximumGenerationsParameter;
70    public IFixedValueParameter<IntValue> MaximumGenerationsParameter {
71      get { return maximumGenerationsParameter; }
72    }
73    [Storable]
74    private IFixedValueParameter<IntValue> maximumEvaluatedSolutionsParameter;
75    public IFixedValueParameter<IntValue> MaximumEvaluatedSolutionsParameter {
76      get { return maximumEvaluatedSolutionsParameter; }
77    }
78    [Storable]
79    private IFixedValueParameter<BoolValue> pauseAfterGenerationParameter;
80    public IFixedValueParameter<BoolValue> PauseAfterGenerationParameter {
81      get { return pauseAfterGenerationParameter; }
82    }
83    [Storable]
84    private IFixedValueParameter<EnumValue<OptimalAssignmentType>> optimalAssignmentParameter;
85    public IFixedValueParameter<EnumValue<OptimalAssignmentType>> OptimalAssignmentParameter {
86      get { return optimalAssignmentParameter; }
87    }
88
89    public int PopulationSize {
90      get { return populationSizeParameter.Value.Value; }
91      set { populationSizeParameter.Value.Value = value; }
92    }
93    public int Elites {
94      get { return elitesParameter.Value.Value; }
95      set { elitesParameter.Value.Value = value; }
96    }
97    public double MutationProbability {
98      get { return mutationProbabilityParameter.Value.Value; }
99      set { mutationProbabilityParameter.Value.Value = value; }
100    }
101    public int MaximumGenerations {
102      get { return maximumGenerationsParameter.Value.Value; }
103      set { maximumGenerationsParameter.Value.Value = value; }
104    }
105    public int MaximumEvaluatedSolutions {
106      get { return maximumEvaluatedSolutionsParameter.Value.Value; }
107      set { maximumEvaluatedSolutionsParameter.Value.Value = value; }
108    }
109    public bool PauseAfterGeneration {
110      get { return pauseAfterGenerationParameter.Value.Value; }
111      set { pauseAfterGenerationParameter.Value.Value = value; }
112    }
113    public OptimalAssignmentType OptimalAssignment {
114      get { return optimalAssignmentParameter.Value.Value; }
115      set { optimalAssignmentParameter.Value.Value = value; }
116    }
117
118    [StorableConstructor]
119    protected GeneticAlgorithm(bool deserializing) : base(deserializing) { }
120    protected GeneticAlgorithm(GeneticAlgorithm original, Cloner cloner)
121      : base(original, cloner) {
122      populationSizeParameter = cloner.Clone(original.populationSizeParameter);
123      elitesParameter = cloner.Clone(original.elitesParameter);
124      mutationProbabilityParameter = cloner.Clone(original.mutationProbabilityParameter);
125      maximumGenerationsParameter = cloner.Clone(original.maximumGenerationsParameter);
126      maximumEvaluatedSolutionsParameter = cloner.Clone(original.maximumEvaluatedSolutionsParameter);
127      pauseAfterGenerationParameter = cloner.Clone(original.pauseAfterGenerationParameter);
128      optimalAssignmentParameter = cloner.Clone(original.optimalAssignmentParameter);
129
130      generation = original.generation;
131      evaluatedSolutions = original.evaluatedSolutions;
132      bestQuality = original.bestQuality;
133
134      if (original.population != null)
135        population = original.population.Select(cloner.Clone).ToArray();
136      if (original.nextGeneration != null)
137        nextGeneration = original.nextGeneration.Select(cloner.Clone).ToArray();
138      if (original.optimalSequences != null)
139        optimalSequences = new HashSet<Permutation>(original.optimalSequences, new PermutationEqualityComparer());
140    }
141    public GeneticAlgorithm() {
142      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)));
143      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)));
144      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)));
145      Parameters.Add(maximumGenerationsParameter = new FixedValueParameter<IntValue>("MaximumGenerations", "The number of generations that the algorithm may run for.", new IntValue(1000000)));
146      Parameters.Add(maximumEvaluatedSolutionsParameter = new FixedValueParameter<IntValue>("MaximumEvaluatedSolutions", "The number of evaluated solutions before the algorithm terminates.", new IntValue(100000000)));
147      Parameters.Add(pauseAfterGenerationParameter = new FixedValueParameter<BoolValue>("PauseAfterGeneration", "Whether the algorithm should pause after each generation.", new BoolValue(true)));
148      Parameters.Add(optimalAssignmentParameter = new FixedValueParameter<EnumValue<OptimalAssignmentType>>("OptimalAssignment", "Which optimal assignment strategy should be used.", new EnumValue<OptimalAssignmentType>(OptimalAssignmentType.Polynomial)));
149    }
150
151    public override IDeepCloneable Clone(Cloner cloner) {
152      return new GeneticAlgorithm(this, cloner);
153    }
154
155    protected override void OnProblemChanged() {
156      base.OnProblemChanged();
157    }
158   
159    [Storable]
160    private IRandom random;
161    [Storable]
162    private int generation;
163    [Storable]
164    private int evaluatedSolutions;
165    [Storable]
166    private double bestQuality;
167    [Storable]
168    private EncodedSolution[] population;
169    [Storable]
170    private EncodedSolution[] nextGeneration;
171    [Storable]
172    private HashSet<Permutation> optimalSequences;
173
174    protected override void Initialize(CancellationToken cancellationToken) {
175      base.Initialize(cancellationToken);
176      random = new MersenneTwister();
177      optimalSequences = new HashSet<Permutation>(new PermutationEqualityComparer());
178      generation = 0;
179      evaluatedSolutions = 0;
180      population = new EncodedSolution[PopulationSize];
181      nextGeneration = new EncodedSolution[PopulationSize - Elites];
182      bestQuality = double.MaxValue;
183      for (var p = 0; p < PopulationSize; p++) {
184        population[p] = new EncodedSolution() {
185          Sequence = new Permutation(PermutationTypes.RelativeDirected, Problem.ProcessingTimes.Columns, random),
186          Assignment = new BinaryVector(Problem.ProcessingTimes.Columns, random)
187        };
188        population[p].Quality = Problem.Evaluate(population[p].Sequence, population[p].Assignment);
189        evaluatedSolutions++;
190        if (population[p].Quality < bestQuality) bestQuality = population[p].Quality;
191      }
192      Array.Sort(population);
193      Results.Add(new Result("BestQuality", new DoubleValue(bestQuality)));
194      Results.Add(new Result("EvaluatedSolutions", new IntValue(evaluatedSolutions)));
195      Results.Add(new Result("Generation", new IntValue(generation)));
196      if (PauseAfterGeneration) Pause();
197    }
198
199    protected override void Run(CancellationToken cancellationToken) {
200      if (cancellationToken.IsCancellationRequested) return;
201
202      while (generation < MaximumGenerations) {
203        if (evaluatedSolutions > MaximumEvaluatedSolutions) return;
204        for (var p = 0; p < PopulationSize - Elites; p++) {
205          var parent1 = TournamentSelect((int)Math.Round(Math.Max(PopulationSize / 71.0, 2)));
206          var parent2 = TournamentSelect((int)Math.Round(Math.Max(PopulationSize / 71.0, 2)));
207          nextGeneration[p] = new EncodedSolution() {
208            Sequence = CrossSequence(parent1.Sequence, parent2.Sequence),
209            Assignment = CrossAssignment(parent1.Assignment, parent2.Assignment)
210          };
211
212          var mutProb = random.NextDouble();
213          if (mutProb < MutationProbability) {
214            MutateSequence(nextGeneration[p].Sequence);
215            MutateAssignment(nextGeneration[p].Assignment);
216          }
217
218          nextGeneration[p].Quality = Problem.Evaluate(nextGeneration[p].Sequence, nextGeneration[p].Assignment);
219          evaluatedSolutions++;
220
221          if (nextGeneration[p].Quality <= bestQuality) {
222            switch (OptimalAssignment) {
223              case OptimalAssignmentType.None:
224                break;
225              case OptimalAssignmentType.Polynomial:
226                OptimalPolynomialAssignment(nextGeneration[p]);
227                break;
228              case OptimalAssignmentType.OneOpt:
229                OneOptAssignment(nextGeneration[p]);
230                break;
231              case OptimalAssignmentType.Both:
232                HybridAssignment(nextGeneration[p]);
233                break;
234              default:
235                throw new InvalidOperationException("Optimal assignment strategy not defined.");
236            }
237
238          if (nextGeneration[p].Quality < bestQuality) {
239              bestQuality = nextGeneration[p].Quality;
240              ((DoubleValue)Results["BestQuality"].Value).Value = bestQuality;
241            }
242          }
243        }
244
245        for (var p = Elites; p < PopulationSize; p++) {
246          population[p] = nextGeneration[p - Elites];
247        }
248        Array.Sort(population);
249
250        generation++;
251
252        ((IntValue)Results["EvaluatedSolutions"].Value).Value = evaluatedSolutions;
253        ((IntValue)Results["Generation"].Value).Value = generation;
254
255        if (PauseAfterGeneration || cancellationToken.IsCancellationRequested) {
256          if (!cancellationToken.IsCancellationRequested) Pause();
257          break;
258        }
259      }
260    }
261
262    private void OptimalPolynomialAssignment(EncodedSolution generation) {
263      if (!optimalSequences.Contains(generation.Sequence)) {
264        var assignment = Scheduling.CFSAP.OptimalPolynomialAssignment.MakeAssignment(generation.Sequence, Problem.ProcessingTimes, Problem.SetupTimes, out var cycleTime);
265        evaluatedSolutions++;
266        generation.Assignment = new BinaryVector(assignment.Select(x => x == 1).ToArray());
267        generation.Quality = cycleTime;
268        optimalSequences.Add(generation.Sequence);
269      }
270    }
271
272    private void OneOptAssignment(EncodedSolution generation) {
273      var assignment = Scheduling.CFSAP.OneOptAssignment.MakeAssignment(generation.Sequence, generation.Assignment, Problem.ProcessingTimes, Problem.SetupTimes, out var cycleTime);
274      evaluatedSolutions++;
275      generation.Assignment = assignment;
276      generation.Quality = cycleTime;
277    }
278
279    private void HybridAssignment(EncodedSolution generation) {
280      var a = random.Next(2);
281      switch (a) {
282        case 0: OptimalPolynomialAssignment(generation); break;
283        case 1: OneOptAssignment(generation); break;
284        default: throw new InvalidOperationException("Assignment not defined.");
285      }
286    }
287
288    private EncodedSolution TournamentSelect(int groupSize) {
289      var selected = population[random.Next(population.Length)];
290      for (var i = 1; i < groupSize; i++) {
291        var competitor = population[random.Next(population.Length)];
292        if (selected.Quality > competitor.Quality) {
293          selected = competitor;
294        }
295      }
296      return selected;
297    }
298
299    private Permutation CrossSequence(Permutation sequence1, Permutation sequence2) {
300      var cx = random.Next(3);
301      switch (cx) {
302        case 0: return OrderCrossover.Apply(random, sequence1, sequence2);
303        case 1: return OrderCrossover2.Apply(random, sequence1, sequence2);
304        case 2: return MaximalPreservativeCrossover.Apply(random, sequence1, sequence2);
305        default: throw new InvalidOperationException("Crossover not defined.");
306      }
307    }
308
309    private void MutateSequence(Permutation sequence) {
310      var m = random.Next(7);
311      switch (m) {
312        case 0: InversionManipulator.Apply(random, sequence); break;
313        case 1: InsertionManipulator.Apply(random, sequence); break;
314        case 2: Swap2Manipulator.Apply(random, sequence); break;
315        case 3: Swap3Manipulator.Apply(random, sequence); break;
316        case 4: TranslocationManipulator.Apply(random, sequence); break;
317        case 5: TranslocationInversionManipulator.Apply(random, sequence); break;
318        case 6: ScrambleManipulator.Apply(random, sequence); break;
319        default: throw new InvalidOperationException("Manipulator not defined.");
320      }
321    }
322
323    private BinaryVector CrossAssignment(BinaryVector assign1, BinaryVector assign2) {
324      var cx = random.Next(3);
325      switch (cx) {
326        case 0: return UniformCrossover.Apply(random, assign1, assign2);
327        case 1: return NPointCrossover.Apply(random, assign1, assign2, new IntValue(1));
328        case 2: return NPointCrossover.Apply(random, assign1, assign2, new IntValue(2));
329        default: throw new InvalidOperationException("Crossover not defined.");
330      }
331    }
332
333    private void MutateAssignment(BinaryVector assignment) {
334      SomePositionsBitflipManipulator.Apply(random, assignment, new DoubleValue(0.2));
335    }
336
337    [StorableClass]
338    private class EncodedSolution : DeepCloneable, IComparable<EncodedSolution> {
339      [Storable]
340      public Permutation Sequence { get; set; }
341      [Storable]
342      public BinaryVector Assignment { get; set; }
343      [Storable]
344      public double Quality { get; set; }
345
346      [StorableConstructor]
347      private EncodedSolution(bool deserializing) { }
348
349      private EncodedSolution(EncodedSolution original, Cloner cloner) : base(original, cloner) {
350        Sequence = cloner.Clone(original.Sequence);
351        Assignment = cloner.Clone(original.Assignment);
352        Quality = original.Quality;
353      }
354
355      public EncodedSolution() { }
356
357      public override IDeepCloneable Clone(Cloner cloner) {
358        return new EncodedSolution(this, cloner);
359      }
360
361      public int CompareTo(EncodedSolution other) {
362        return Quality.CompareTo(other.Quality);
363      }
364    }
365  }
366}
Note: See TracBrowser for help on using the repository browser.