Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 15493 was 15493, checked in by abeham, 5 years ago

#2747: Implemeted hard-coded genetic algorithm for faster evaluation

File size: 13.7 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  [Item("Genetic Algorithm (CFSAP)", "")]
38  [StorableClass]
39  public class GeneticAlgorithm : BasicAlgorithm {
40    public override bool SupportsPause { get { return true; } }
41
42    public override Type ProblemType {
43      get { return typeof(CFSAP); }
44    }
45
46    public new CFSAP Problem {
47      get { return (CFSAP)base.Problem; }
48      set { base.Problem = value; }
49    }
50
51    [Storable]
52    private IFixedValueParameter<IntValue> populationSizeParameter;
53    public IFixedValueParameter<IntValue> PopulationSizeParameter {
54      get { return populationSizeParameter; }
55    }
56    [Storable]
57    private IFixedValueParameter<IntValue> elitesParameter;
58    public IFixedValueParameter<IntValue> ElitesParameter {
59      get { return elitesParameter; }
60    }
61    [Storable]
62    private IFixedValueParameter<PercentValue> mutationProbabilityParameter;
63    public IFixedValueParameter<PercentValue> MutationProbabilityParameter {
64      get { return mutationProbabilityParameter; }
65    }
66    [Storable]
67    private IFixedValueParameter<IntValue> maximumGenerationsParameter;
68    public IFixedValueParameter<IntValue> MaximumGenerationsParameter {
69      get { return maximumGenerationsParameter; }
70    }
71    [Storable]
72    private IFixedValueParameter<IntValue> maximumEvaluatedSolutionsParameter;
73    public IFixedValueParameter<IntValue> MaximumEvaluatedSolutionsParameter {
74      get { return maximumEvaluatedSolutionsParameter; }
75    }
76    [Storable]
77    private IFixedValueParameter<BoolValue> pauseAfterGenerationParameter;
78    public IFixedValueParameter<BoolValue> PauseAfterGenerationParameter {
79      get { return pauseAfterGenerationParameter; }
80    }
81
82    public int PopulationSize {
83      get { return populationSizeParameter.Value.Value; }
84      set { populationSizeParameter.Value.Value = value; }
85    }
86    public int Elites {
87      get { return elitesParameter.Value.Value; }
88      set { elitesParameter.Value.Value = value; }
89    }
90    public double MutationProbability {
91      get { return mutationProbabilityParameter.Value.Value; }
92      set { mutationProbabilityParameter.Value.Value = value; }
93    }
94    public int MaximumGenerations {
95      get { return maximumGenerationsParameter.Value.Value; }
96      set { maximumGenerationsParameter.Value.Value = value; }
97    }
98    public int MaximumEvaluatedSolutions {
99      get { return maximumEvaluatedSolutionsParameter.Value.Value; }
100      set { maximumEvaluatedSolutionsParameter.Value.Value = value; }
101    }
102    public bool PauseAfterGeneration {
103      get { return pauseAfterGenerationParameter.Value.Value; }
104      set { pauseAfterGenerationParameter.Value.Value = value; }
105    }
106
107    [StorableConstructor]
108    protected GeneticAlgorithm(bool deserializing) : base(deserializing) { }
109    protected GeneticAlgorithm(GeneticAlgorithm original, Cloner cloner)
110      : base(original, cloner) {
111      populationSizeParameter = cloner.Clone(original.populationSizeParameter);
112      elitesParameter = cloner.Clone(original.elitesParameter);
113      mutationProbabilityParameter = cloner.Clone(original.mutationProbabilityParameter);
114      maximumGenerationsParameter = cloner.Clone(original.maximumGenerationsParameter);
115      maximumEvaluatedSolutionsParameter = cloner.Clone(original.maximumEvaluatedSolutionsParameter);
116      pauseAfterGenerationParameter = cloner.Clone(original.pauseAfterGenerationParameter);
117      generation = original.generation;
118      evaluatedSolutions = original.evaluatedSolutions;
119      bestQuality = original.bestQuality;
120      if (original.population != null)
121        population = original.population.Select(cloner.Clone).ToArray();
122      if (original.nextGeneration != null)
123        nextGeneration = original.nextGeneration.Select(cloner.Clone).ToArray();
124      if (original.optimalSequences != null)
125        optimalSequences = new HashSet<Permutation>(original.optimalSequences, new PermutationEqualityComparer());
126    }
127    public GeneticAlgorithm() {
128      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)));
129      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)));
130      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)));
131      Parameters.Add(maximumGenerationsParameter = new FixedValueParameter<IntValue>("MaximumGenerations", "The number of generations that the algorithm may run for.", new IntValue(1000000)));
132      Parameters.Add(maximumEvaluatedSolutionsParameter = new FixedValueParameter<IntValue>("MaximumEvaluatedSolutions", "The number of evaluated solutions before the algorithm terminates.", new IntValue(100000000)));
133      Parameters.Add(pauseAfterGenerationParameter = new FixedValueParameter<BoolValue>("PauseAfterGeneration", "Whether the algorithm should pause after each generation.", new BoolValue(true)));
134    }
135
136    public override IDeepCloneable Clone(Cloner cloner) {
137      return new GeneticAlgorithm(this, cloner);
138    }
139
140    protected override void OnProblemChanged() {
141      base.OnProblemChanged();
142    }
143   
144    [Storable]
145    private IRandom random;
146    [Storable]
147    private int generation;
148    [Storable]
149    private int evaluatedSolutions;
150    [Storable]
151    private double bestQuality;
152    [Storable]
153    private EncodedSolution[] population;
154    [Storable]
155    private EncodedSolution[] nextGeneration;
156    [Storable]
157    private HashSet<Permutation> optimalSequences;
158
159    protected override void Initialize(CancellationToken cancellationToken) {
160      base.Initialize(cancellationToken);
161      random = new MersenneTwister();
162      optimalSequences = new HashSet<Permutation>(new PermutationEqualityComparer());
163      generation = 0;
164      evaluatedSolutions = 0;
165      population = new EncodedSolution[PopulationSize];
166      nextGeneration = new EncodedSolution[PopulationSize - Elites];
167      bestQuality = double.MaxValue;
168      for (var p = 0; p < PopulationSize; p++) {
169        population[p] = new EncodedSolution() {
170          Sequence = new Permutation(PermutationTypes.RelativeDirected, Problem.ProcessingTimes.Columns, random),
171          Assignment = new BinaryVector(Problem.ProcessingTimes.Columns, random)
172        };
173        population[p].Quality = Problem.Evaluate(population[p].Sequence, population[p].Assignment);
174        evaluatedSolutions++;
175        if (population[p].Quality < bestQuality) bestQuality = population[p].Quality;
176      }
177      Array.Sort(population);
178      Results.Add(new Result("BestQuality", new DoubleValue(bestQuality)));
179      Results.Add(new Result("EvaluatedSolutions", new IntValue(evaluatedSolutions)));
180      Results.Add(new Result("Generation", new IntValue(generation)));
181      if (PauseAfterGeneration) Pause();
182    }
183
184    protected override void Run(CancellationToken cancellationToken) {
185      if (cancellationToken.IsCancellationRequested) return;
186
187      while (generation < MaximumGenerations) {
188        if (evaluatedSolutions > MaximumEvaluatedSolutions) return;
189        for (var p = 0; p < PopulationSize - Elites; p++) {
190          var parent1 = TournamentSelect((int)Math.Round(Math.Max(PopulationSize / 71.0, 2)));
191          var parent2 = TournamentSelect((int)Math.Round(Math.Max(PopulationSize / 71.0, 2)));
192          nextGeneration[p] = new EncodedSolution() {
193            Sequence = CrossSequence(parent1.Sequence, parent2.Sequence),
194            Assignment = CrossAssignment(parent1.Assignment, parent2.Assignment)
195          };
196          var mutProb = random.NextDouble();
197          if (mutProb < MutationProbability) {
198            MutateSequence(nextGeneration[p].Sequence);
199            MutateAssignment(nextGeneration[p].Assignment);
200          }
201          nextGeneration[p].Quality = Problem.Evaluate(nextGeneration[p].Sequence, nextGeneration[p].Assignment);
202          evaluatedSolutions++;
203
204          if (nextGeneration[p].Quality <= bestQuality) {
205            if (!optimalSequences.Contains(nextGeneration[p].Sequence)) {
206              int cycleTime;
207              var assignment = OptimalAssignment.MakeAssignment(nextGeneration[p].Sequence, Problem.ProcessingTimes, Problem.SetupTimes, out cycleTime);
208              evaluatedSolutions++;
209              nextGeneration[p].Assignment = new BinaryVector(assignment.Select(x => x == 1).ToArray());
210              nextGeneration[p].Quality = cycleTime;
211              optimalSequences.Add(nextGeneration[p].Sequence);
212            }
213            if (nextGeneration[p].Quality < bestQuality) {
214              bestQuality = nextGeneration[p].Quality;
215              ((DoubleValue)Results["BestQuality"].Value).Value = bestQuality;
216            }
217          }
218        }
219
220        for (var p = Elites; p < PopulationSize; p++) {
221          population[p] = nextGeneration[p - Elites];
222        }
223        Array.Sort(population);
224
225        generation++;
226
227        ((IntValue)Results["EvaluatedSolutions"].Value).Value = evaluatedSolutions;
228        ((IntValue)Results["Generation"].Value).Value = generation;
229
230        if (PauseAfterGeneration || cancellationToken.IsCancellationRequested) {
231          if (!cancellationToken.IsCancellationRequested) Pause();
232          break;
233        }
234      }
235    }
236
237    private EncodedSolution TournamentSelect(int groupSize) {
238      var selected = population[random.Next(population.Length)];
239      for (var i = 1; i < groupSize; i++) {
240        var competitor = population[random.Next(population.Length)];
241        if (selected.Quality > competitor.Quality) {
242          selected = competitor;
243        }
244      }
245      return selected;
246    }
247
248    private Permutation CrossSequence(Permutation sequence1, Permutation sequence2) {
249      var cx = random.Next(3);
250      switch (cx) {
251        case 0: return OrderCrossover.Apply(random, sequence1, sequence2);
252        case 1: return OrderCrossover2.Apply(random, sequence1, sequence2);
253        case 2: return MaximalPreservativeCrossover.Apply(random, sequence1, sequence2);
254        default: throw new InvalidOperationException("Crossover not defined.");
255      }
256    }
257
258    private void MutateSequence(Permutation sequence) {
259      var cx = random.Next(7);
260      switch (cx) {
261        case 0: InversionManipulator.Apply(random, sequence); break;
262        case 1: InsertionManipulator.Apply(random, sequence); break;
263        case 2: Swap2Manipulator.Apply(random, sequence); break;
264        case 3: Swap3Manipulator.Apply(random, sequence); break;
265        case 4: TranslocationManipulator.Apply(random, sequence); break;
266        case 5: TranslocationInversionManipulator.Apply(random, sequence); break;
267        case 6: ScrambleManipulator.Apply(random, sequence); break;
268        default: throw new InvalidOperationException("Crossover not defined.");
269      }
270    }
271
272    private BinaryVector CrossAssignment(BinaryVector assign1, BinaryVector assign2) {
273      var cx = random.Next(3);
274      switch (cx) {
275        case 0: return UniformCrossover.Apply(random, assign1, assign2);
276        case 1: return NPointCrossover.Apply(random, assign1, assign2, new IntValue(1));
277        case 2: return NPointCrossover.Apply(random, assign1, assign2, new IntValue(2));
278        default: throw new InvalidOperationException("Crossover not defined.");
279      }
280    }
281
282    private void MutateAssignment(BinaryVector assignment) {
283      SomePositionsBitflipManipulator.Apply(random, assignment, new DoubleValue(0.2));
284    }
285
286    private class EncodedSolution : IDeepCloneable, IComparable<EncodedSolution> {
287      public Permutation Sequence { get; set; }
288      public BinaryVector Assignment { get; set; }
289      public double Quality { get; set; }
290
291      public IDeepCloneable Clone(Cloner cloner) {
292        return new EncodedSolution() {
293          Sequence = cloner.Clone(this.Sequence),
294          Assignment = cloner.Clone(this.Assignment),
295          Quality = this.Quality
296        };
297      }
298
299      public object Clone() {
300        return Clone(new Cloner());
301      }
302
303      public int CompareTo(EncodedSolution other) {
304        return Quality.CompareTo(other.Quality);
305      }
306    }
307  }
308}
Note: See TracBrowser for help on using the repository browser.