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

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

#1614: added additional algorithms

File size: 9.2 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.Problem = Problem;     
109      Context.BestQuality = double.NaN;
110      Context.BestSolution = null;
111
112      for (var m = 0; m < Mu; m++) {
113        var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length);
114        var eval = Problem.ProblemInstance.Evaluate(assign);
115        Context.EvaluatedSolutions++;
116
117        var ind = new ESGQAPSolution(assign, eval, 1.0 / assign.Length);
118        var fit = Problem.ProblemInstance.ToSingleObjective(eval);
119        Context.AddToPopulation(Context.ToScope(ind, fit));
120        if (double.IsNaN(Context.BestQuality) || fit < Context.BestQuality) {
121          Context.BestQuality = fit;
122          Context.BestSolution = (ESGQAPSolution)ind.Clone();
123        }
124      }
125
126      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
127      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
128      Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
129      Results.Add(new Result("BestSolution", Context.BestSolution));
130
131      Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
132    }
133
134    protected override void Run(CancellationToken cancellationToken) {
135      while (!StoppingCriterion()) {
136        var nextGen = new List<ISingleObjectiveSolutionScope<ESGQAPSolution>>(Lambda);
137
138        for (var l = 0; l < Lambda; l++) {
139          var m = Context.AtRandomPopulation();
140
141          var offspring = (ESGQAPSolution)m.Solution.Clone();
142          var count = Mutate(m, offspring);
143          offspring.SParam += ((1.0 / count) - offspring.SParam) / 10.0;
144
145          offspring.Evaluation = Problem.ProblemInstance.Evaluate(offspring.Assignment);
146          Context.EvaluatedSolutions++;
147          var fit = Problem.ProblemInstance.ToSingleObjective(offspring.Evaluation);
148          nextGen.Add(Context.ToScope(offspring, fit));
149
150          if (fit < Context.BestQuality) {
151            Context.BestQuality = fit;
152            Context.BestSolution = (ESGQAPSolution)offspring.Clone();
153          }
154        }
155
156        if (Selection == ESSelection.Comma) {
157          Context.ReplacePopulation(nextGen.OrderBy(x => x.Fitness).Take(Mu));
158        } else if (Selection == ESSelection.Plus) {
159          var best = nextGen.Concat(Context.Population).OrderBy(x => x.Fitness).Take(Mu).ToList();
160          Context.ReplacePopulation(best);
161        } else throw new InvalidOperationException("Unknown Selection strategy: " + Selection);
162
163        IResult result;
164        if (Results.TryGetValue("Iterations", out result))
165          ((IntValue)result.Value).Value = Context.Iterations;
166        else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
167        if (Results.TryGetValue("EvaluatedSolutions", out result))
168          ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
169        else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
170        if (Results.TryGetValue("BestQuality", out result))
171          ((DoubleValue)result.Value).Value = Context.BestQuality;
172        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
173        if (Results.TryGetValue("BestSolution", out result))
174          result.Value = Context.BestSolution;
175        else Results.Add(new Result("BestSolution", Context.BestSolution));
176
177        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
178
179        Context.Iterations++;
180        if (cancellationToken.IsCancellationRequested) break;
181      }
182    }
183
184    private int Mutate(ISingleObjectiveSolutionScope<ESGQAPSolution> m, ESGQAPSolution offspring) {
185      var offspringFeasible = offspring.Evaluation.IsFeasible;
186      double[] slack = null;
187      if (offspringFeasible) slack = offspring.Evaluation.Slack.ToArray();
188      var count = 1;
189      foreach (var equip in Enumerable.Range(0, Problem.ProblemInstance.Demands.Length).Shuffle(Context.Random)) {
190        var currentLoc = offspring.Assignment[equip];
191        if (offspringFeasible) {
192          var demand = Problem.ProblemInstance.Demands[equip];
193          var feasibleLoc = slack.Select((v, i) => new { Index = i, Value = v })
194            .Where(x => x.Index != currentLoc
195            && x.Value >= demand).ToList();
196          int newLoc = -1;
197          if (feasibleLoc.Count == 0) {
198            newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
199            if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
200            offspringFeasible = false;
201          } else {
202            newLoc = feasibleLoc.SampleRandom(Context.Random).Index;
203          }
204          offspring.Assignment[equip] = newLoc;
205          slack[currentLoc] += demand;
206          slack[newLoc] -= demand;
207        } else {
208          var newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
209          if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
210          offspring.Assignment[equip] = newLoc;
211        }
212        if (Context.Random.NextDouble() < m.Solution.SParam) break;
213        count++;
214      }
215
216      return count;
217    }
218  }
219}
Note: See TracBrowser for help on using the repository browser.