source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/EvolutionStrategy.cs @ 15563

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

#1614:

  • Added LAHC and pLAHC-s
  • Changed all algorithms to update high frequency results only every second
File size: 10.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.IntegerVectorEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.Random;
34
35namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary {
36  public enum ESSelection { Plus = 0, Comma = 1 }
37
38  [Item("Evolution Strategy (GQAP)", "The algorithm implements a simple evolution strategy (ES).")]
39  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
40  [StorableClass]
41  public sealed class EvolutionStrategy : StochasticAlgorithm<ESContext> {
42
43    public override bool SupportsPause {
44      get { return true; }
45    }
46
47    public override Type ProblemType {
48      get { return typeof(GQAP); }
49    }
50
51    public new GQAP Problem {
52      get { return (GQAP)base.Problem; }
53      set { base.Problem = value; }
54    }
55
56    [Storable]
57    private FixedValueParameter<IntValue> lambdaParameter;
58    private IFixedValueParameter<IntValue> LambdaParameter {
59      get { return lambdaParameter; }
60    }
61    [Storable]
62    private FixedValueParameter<IntValue> muParameter;
63    public IFixedValueParameter<IntValue> MuParameter {
64      get { return muParameter; }
65    }
66    [Storable]
67    private FixedValueParameter<EnumValue<ESSelection>> selectionParameter;
68    public IFixedValueParameter<EnumValue<ESSelection>> SelectionParameter {
69      get { return selectionParameter; }
70    }
71
72    public int Lambda {
73      get { return lambdaParameter.Value.Value; }
74      set { lambdaParameter.Value.Value = value; }
75    }
76    public int Mu {
77      get { return muParameter.Value.Value; }
78      set { muParameter.Value.Value = value; }
79    }
80    public ESSelection Selection {
81      get { return selectionParameter.Value.Value; }
82      set { selectionParameter.Value.Value = value; }
83    }
84
85    [StorableConstructor]
86    private EvolutionStrategy(bool deserializing) : base(deserializing) { }
87    private EvolutionStrategy(EvolutionStrategy original, Cloner cloner)
88      : base(original, cloner) {
89      lambdaParameter = cloner.Clone(original.lambdaParameter);
90      muParameter = cloner.Clone(original.muParameter);
91      selectionParameter = cloner.Clone(original.selectionParameter);
92    }
93    public EvolutionStrategy() {
94      Parameters.Add(lambdaParameter = new FixedValueParameter<IntValue>("Lambda", "(λ) The amount of offspring that are created each generation.", new IntValue(10)));
95      Parameters.Add(muParameter = new FixedValueParameter<IntValue>("Mu", "(μ) The population size.", new IntValue(1)));
96      Parameters.Add(selectionParameter= new FixedValueParameter<EnumValue<ESSelection>>("Selection", "The selection strategy: elitist (plus) or generational (comma).", new EnumValue<ESSelection>(ESSelection.Plus)));
97     
98      Problem = new GQAP();
99    }
100
101    public override IDeepCloneable Clone(Cloner cloner) {
102      return new EvolutionStrategy(this, cloner);
103    }
104
105    protected override void Initialize(CancellationToken cancellationToken) {
106      base.Initialize(cancellationToken);
107
108      Context.NormalRand = new NormalDistributedRandom(Context.Random, 0, 1);
109      Context.Problem = Problem;     
110      Context.BestQuality = double.NaN;
111      Context.BestSolution = null;
112     
113      for (var m = 0; m < Mu; m++) {
114        var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length);
115        var eval = Problem.ProblemInstance.Evaluate(assign);
116        Context.EvaluatedSolutions++;
117
118        var ind = new ESGQAPSolution(assign, eval, Context.Random.NextDouble() * 2 - 1);
119        var fit = Problem.ProblemInstance.ToSingleObjective(eval);
120        Context.AddToPopulation(Context.ToScope(ind, fit));
121        if (double.IsNaN(Context.BestQuality) || fit < Context.BestQuality) {
122          Context.BestQuality = fit;
123          Context.BestSolution = (ESGQAPSolution)ind.Clone();
124        }
125      }
126
127      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
128      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
129      Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
130      Results.Add(new Result("BestSolution", Context.BestSolution));
131
132      Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
133    }
134
135    protected override void Run(CancellationToken cancellationToken) {
136      var lastUpdate = ExecutionTime;
137
138      while (!StoppingCriterion()) {
139        var nextGen = new List<ISingleObjectiveSolutionScope<ESGQAPSolution>>(Lambda);
140
141        for (var l = 0; l < Lambda; l++) {
142          var m = Context.AtRandomPopulation();
143
144          var offspring = (ESGQAPSolution)m.Solution.Clone();
145          var count = Mutate(m, offspring);
146          offspring.SParam += 0.7071 * Context.NormalRand.NextDouble(); //((1.0 / count) - offspring.SParam) / 10.0;
147
148          offspring.Evaluation = Problem.ProblemInstance.Evaluate(offspring.Assignment);
149          Context.EvaluatedSolutions++;
150          var fit = Problem.ProblemInstance.ToSingleObjective(offspring.Evaluation);
151          nextGen.Add(Context.ToScope(offspring, fit));
152
153          if (fit < Context.BestQuality) {
154            Context.BestQuality = fit;
155            Context.BestSolution = (ESGQAPSolution)offspring.Clone();
156          }
157        }
158
159        if (Selection == ESSelection.Comma) {
160          Context.ReplacePopulation(nextGen.OrderBy(x => x.Fitness).Take(Mu));
161        } else if (Selection == ESSelection.Plus) {
162          var best = nextGen.Concat(Context.Population).OrderBy(x => x.Fitness).Take(Mu).ToList();
163          Context.ReplacePopulation(best);
164        } else throw new InvalidOperationException("Unknown Selection strategy: " + Selection);
165
166        IResult result;
167        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
168          if (Results.TryGetValue("Iterations", out result))
169            ((IntValue)result.Value).Value = Context.Iterations;
170          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
171          if (Results.TryGetValue("EvaluatedSolutions", out result))
172            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
173          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
174          lastUpdate = ExecutionTime;
175        }
176        if (Results.TryGetValue("BestQuality", out result))
177          ((DoubleValue)result.Value).Value = Context.BestQuality;
178        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
179        if (Results.TryGetValue("BestSolution", out result))
180          result.Value = Context.BestSolution;
181        else Results.Add(new Result("BestSolution", Context.BestSolution));
182
183        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
184
185        Context.Iterations++;
186        if (cancellationToken.IsCancellationRequested) break;
187      }
188      IResult result2;
189      if (Results.TryGetValue("Iterations", out result2))
190        ((IntValue)result2.Value).Value = Context.Iterations;
191      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
192      if (Results.TryGetValue("EvaluatedSolutions", out result2))
193        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
194      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
195    }
196
197    private int Mutate(ISingleObjectiveSolutionScope<ESGQAPSolution> m, ESGQAPSolution offspring) {
198      var stopProb = (Math.Tanh(m.Solution.SParam) + 1) / 2.0; // squash strategy parameter to ]0;1[
199      var offspringFeasible = offspring.Evaluation.IsFeasible;
200      double[] slack = null;
201      if (offspringFeasible) slack = offspring.Evaluation.Slack.ToArray();
202      var count = 1;
203      foreach (var equip in Enumerable.Range(0, Problem.ProblemInstance.Demands.Length).Shuffle(Context.Random)) {
204        var currentLoc = offspring.Assignment[equip];
205        if (offspringFeasible) {
206          var demand = Problem.ProblemInstance.Demands[equip];
207          var feasibleLoc = slack.Select((v, i) => new { Index = i, Value = v })
208            .Where(x => x.Index != currentLoc
209            && x.Value >= demand).ToList();
210          int newLoc = -1;
211          if (feasibleLoc.Count == 0) {
212            newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
213            if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
214            offspringFeasible = false;
215          } else {
216            newLoc = feasibleLoc.SampleRandom(Context.Random).Index;
217          }
218          offspring.Assignment[equip] = newLoc;
219          slack[currentLoc] += demand;
220          slack[newLoc] -= demand;
221        } else {
222          var newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
223          if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
224          offspring.Assignment[equip] = newLoc;
225        }
226        if (Context.Random.NextDouble() < stopProb) break;
227        count++;
228      }
229
230      return count;
231    }
232  }
233}
Note: See TracBrowser for help on using the repository browser.