source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/OSGA.cs @ 15564

Last change on this file since 15564 was 15564, checked in by abeham, 2 years ago

#1614:

  • Fixed some bugs
  • Added OSGA
  • Updated ES (added recombination)
  • Reusing operators among algorihtms (RelocateEquipmentManipluator)
  • Rewrote DiscreteLocationCrossover
File size: 9.6 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.Linq;
24using System.Threading;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.IntegerVectorEncoding;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary {
34  [Item("OSGA (GQAP)", "The algorithm implements a strict offspring selection genetic algorithm (OSGA).")]
35  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
36  [StorableClass]
37  public sealed class OSGA : StochasticAlgorithm<OSGAContext> {
38
39    public override bool SupportsPause {
40      get { return true; }
41    }
42
43    public override Type ProblemType {
44      get { return typeof(GQAP); }
45    }
46
47    public new GQAP Problem {
48      get { return (GQAP)base.Problem; }
49      set { base.Problem = value; }
50    }
51
52    [Storable]
53    private FixedValueParameter<IntValue> populationSizeParameter;
54    public IFixedValueParameter<IntValue> PopulationSizeParameter {
55      get { return populationSizeParameter; }
56    }
57    [Storable]
58    private FixedValueParameter<PercentValue> mutationProbabilityParameter;
59    public IFixedValueParameter<PercentValue> MutationProbabilityParameter {
60      get { return mutationProbabilityParameter; }
61    }
62
63    public int PopulationSize {
64      get { return populationSizeParameter.Value.Value; }
65      set { populationSizeParameter.Value.Value = value; }
66    }
67    public double MutationProbability {
68      get { return mutationProbabilityParameter.Value.Value; }
69      set { mutationProbabilityParameter.Value.Value = value; }
70    }
71
72    [StorableConstructor]
73    private OSGA(bool deserializing) : base(deserializing) { }
74    private OSGA(OSGA original, Cloner cloner)
75      : base(original, cloner) {
76      populationSizeParameter = cloner.Clone(original.populationSizeParameter);
77      mutationProbabilityParameter = cloner.Clone(original.mutationProbabilityParameter);
78    }
79    public OSGA() {
80      Parameters.Add(populationSizeParameter = new FixedValueParameter<IntValue>("Population Size", "(μ) The population size.", new IntValue(500)));
81      Parameters.Add(mutationProbabilityParameter = new FixedValueParameter<PercentValue>("Mutation Probability", "The chance for an offspring to get mutated.", new PercentValue(0.05)));
82
83      Problem = new GQAP();
84    }
85
86    public override IDeepCloneable Clone(Cloner cloner) {
87      return new OSGA(this, cloner);
88    }
89
90    protected override void Initialize(CancellationToken cancellationToken) {
91      base.Initialize(cancellationToken);
92     
93      Context.Problem = Problem;
94      Context.BestQuality = double.NaN;
95      Context.BestSolution = null;
96
97      for (var m = 0; m < PopulationSize; m++) {
98        var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length);
99        var eval = Problem.ProblemInstance.Evaluate(assign);
100        Context.EvaluatedSolutions++;
101       
102        var ind = new GQAPSolution(assign, eval);
103        var fit = Problem.ProblemInstance.ToSingleObjective(eval);
104        Context.AddToPopulation(Context.ToScope(ind, fit));
105        if (double.IsNaN(Context.BestQuality) || fit < Context.BestQuality) {
106          Context.BestQuality = fit;
107          Context.BestSolution = (GQAPSolution)ind.Clone();
108        }
109      }
110
111      Context.SelectionPressure = 0;
112      Context.Attempts = 0;
113      Context.NextGeneration = new ItemList<ISingleObjectiveSolutionScope<GQAPSolution>>();
114
115      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
116      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
117      Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
118      Results.Add(new Result("BestSolution", Context.BestSolution));
119
120      Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
121    }
122
123    protected override void Run(CancellationToken cancellationToken) {
124      var lastUpdate = ExecutionTime;
125
126      while (!StoppingCriterion()) {
127       
128        while (!StoppingCriterion() && Context.NextGeneration.Count < PopulationSize
129          && Context.SelectionPressure < 1000) {
130
131          var idx1 = Context.Random.Next(PopulationSize);
132          var idx2 = (idx1 + Context.Random.Next(1, PopulationSize)) % PopulationSize;
133
134          var p1 = Context.AtPopulation(idx1);
135          var p2 = Context.AtPopulation(idx2);
136
137          var assign = DiscreteLocationCrossover.Apply(Context.Random,
138            new ItemArray<IntegerVector>(new[] { p1.Solution.Assignment, p2.Solution.Assignment }),
139            Problem.ProblemInstance.Demands, Problem.ProblemInstance.Capacities);
140
141          if (Context.Random.NextDouble() < MutationProbability) {
142            RelocateEquipmentManipluator.Apply(Context.Random, assign, Problem.ProblemInstance.Capacities.Length, 4.0 / assign.Length);
143          }
144
145          var eval = Problem.ProblemInstance.Evaluate(assign);
146          Context.EvaluatedSolutions++;
147
148          var offspring = new GQAPSolution(assign, eval);
149
150          var fit = Problem.ProblemInstance.ToSingleObjective(offspring.Evaluation);
151          if (fit < p1.Fitness && fit < p2.Fitness) { // strict OS
152            Context.NextGeneration.Add(Context.ToScope(offspring, fit));
153
154            if (fit < Context.BestQuality) {
155              Context.BestQuality = fit;
156              Context.BestSolution = (GQAPSolution)offspring.Clone();
157            }
158          }
159
160          Context.SelectionPressure += 1.0 / PopulationSize;
161          Context.Attempts++;
162          if (Context.SelectionPressure > 10
163            && Context.NextGeneration.Count / (double)PopulationSize < Context.SelectionPressure / 1000)
164            break;
165          if (cancellationToken.IsCancellationRequested) return;
166        }
167       
168        var restart = Context.NextGeneration.Count < PopulationSize;
169
170        if (restart) {
171          var best = Context.Population.Concat(Context.NextGeneration)
172            .OrderBy(x => x.Fitness).Take(PopulationSize).ToList();
173          Context.ReplacePopulation(best);
174        } else {
175          Context.ReplacePopulation(Context.NextGeneration);
176        }
177        Context.NextGeneration.Clear();
178
179        IResult result;
180        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
181          if (Results.TryGetValue("Iterations", out result))
182            ((IntValue)result.Value).Value = Context.Iterations;
183          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
184          if (Results.TryGetValue("EvaluatedSolutions", out result))
185            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
186          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
187          lastUpdate = ExecutionTime;
188        }
189        if (Results.TryGetValue("BestQuality", out result))
190          ((DoubleValue)result.Value).Value = Context.BestQuality;
191        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
192        if (Results.TryGetValue("BestSolution", out result))
193          result.Value = Context.BestSolution;
194        else Results.Add(new Result("BestSolution", Context.BestSolution));
195
196        try {
197          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
198        } catch (OperationCanceledException) { }
199
200        Context.Iterations++;
201
202        if (restart) {
203          var seed = Context.Population.Select(x => (IntegerVector)x.Solution.Assignment.Clone()).ToList();
204          for (var s = 0; s < seed.Count; s++) {
205            RelocateEquipmentManipluator.Apply(Context.Random, seed[s], Problem.ProblemInstance.Capacities.Length, 0.0);
206            var eval = Problem.ProblemInstance.Evaluate(seed[s]);
207            Context.EvaluatedSolutions++;
208            var fit = Problem.ProblemInstance.ToSingleObjective(eval);
209            Context.NextGeneration.Add(Context.ToScope(new GQAPSolution(seed[s], eval), fit));
210          }
211          Context.ReplacePopulation(Context.NextGeneration);
212          Context.NextGeneration.Clear();
213        }
214        Context.SelectionPressure = 0;
215
216        if (cancellationToken.IsCancellationRequested) break;
217      }
218      IResult result2;
219      if (Results.TryGetValue("Iterations", out result2))
220        ((IntValue)result2.Value).Value = Context.Iterations;
221      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
222      if (Results.TryGetValue("EvaluatedSolutions", out result2))
223        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
224      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
225    }
226  }
227}
Note: See TracBrowser for help on using the repository browser.