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

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

#1614: Added CPLEX algorithms

File size: 10.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, IntegerVectorEncoding> {
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    [Storable]
72    private FixedValueParameter<BoolValue> useRecombinationParameter;
73    public IFixedValueParameter<BoolValue> UseRecombinationParameter {
74      get { return useRecombinationParameter; }
75    }
76
77    public int Lambda {
78      get { return lambdaParameter.Value.Value; }
79      set { lambdaParameter.Value.Value = value; }
80    }
81    public int Mu {
82      get { return muParameter.Value.Value; }
83      set { muParameter.Value.Value = value; }
84    }
85    public ESSelection Selection {
86      get { return selectionParameter.Value.Value; }
87      set { selectionParameter.Value.Value = value; }
88    }
89    public bool UseRecombination {
90      get { return useRecombinationParameter.Value.Value; }
91      set { useRecombinationParameter.Value.Value = value; }
92    }
93
94    [StorableConstructor]
95    private EvolutionStrategy(bool deserializing) : base(deserializing) { }
96    private EvolutionStrategy(EvolutionStrategy original, Cloner cloner)
97      : base(original, cloner) {
98      lambdaParameter = cloner.Clone(original.lambdaParameter);
99      muParameter = cloner.Clone(original.muParameter);
100      selectionParameter = cloner.Clone(original.selectionParameter);
101      useRecombinationParameter = cloner.Clone(original.useRecombinationParameter);
102    }
103    public EvolutionStrategy() {
104      Parameters.Add(lambdaParameter = new FixedValueParameter<IntValue>("Lambda", "(λ) The amount of offspring that are created each generation.", new IntValue(10)));
105      Parameters.Add(muParameter = new FixedValueParameter<IntValue>("Mu", "(μ) The population size.", new IntValue(1)));
106      Parameters.Add(selectionParameter= new FixedValueParameter<EnumValue<ESSelection>>("Selection", "The selection strategy: elitist (plus) or generational (comma).", new EnumValue<ESSelection>(ESSelection.Plus)));
107      Parameters.Add(useRecombinationParameter = new FixedValueParameter<BoolValue>("Use Recombination", "Whether to create an \"intermediate\" solution to perform the mutation from.", new BoolValue(false)));
108
109      Problem = new GQAP();
110    }
111
112    public override IDeepCloneable Clone(Cloner cloner) {
113      return new EvolutionStrategy(this, cloner);
114    }
115
116    protected override void Initialize(CancellationToken cancellationToken) {
117      base.Initialize(cancellationToken);
118
119      Context.NormalRand = new NormalDistributedRandom(Context.Random, 0, 1);
120      Context.Problem = Problem;     
121      Context.BestQuality = double.NaN;
122      Context.BestSolution = null;
123     
124      for (var m = 0; m < Mu; m++) {
125        var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length);
126        var eval = Problem.ProblemInstance.Evaluate(assign);
127        Context.EvaluatedSolutions++;
128
129        var min = (1.0 / assign.Length) * 2 - 1; // desired min prob
130        var max = (4.0 / assign.Length) * 2 - 1; // desired max prob
131        min = 0.5 * (Math.Log(1 + min) - Math.Log(1 - min)); // arctanh
132        max = 0.5 * (Math.Log(1 + max) - Math.Log(1 - max));
133        var ind = new ESGQAPSolution(assign, eval, min + Context.Random.NextDouble() * (max - min));
134        var fit = Problem.ProblemInstance.ToSingleObjective(eval);
135        Context.AddToPopulation(Context.ToScope(ind, fit));
136        if (double.IsNaN(Context.BestQuality) || fit < Context.BestQuality) {
137          Context.BestQuality = fit;
138          Context.BestSolution = (ESGQAPSolution)ind.Clone();
139        }
140      }
141
142      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
143      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
144      Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
145      Results.Add(new Result("BestSolution", Context.BestSolution));
146
147      Context.RunOperator(Analyzer, cancellationToken);
148    }
149
150    protected override void Run(CancellationToken cancellationToken) {
151      var lastUpdate = ExecutionTime;
152      var eq = new IntegerVectorEqualityComparer();
153
154      while (!StoppingCriterion()) {
155        var nextGen = new List<ISingleObjectiveSolutionScope<ESGQAPSolution>>(Lambda);
156
157        for (var l = 0; l < Lambda; l++) {
158          IntegerVector child = null;
159          var sParam = 0.0;
160          if (UseRecombination) {
161            child = DiscreteLocationCrossover.Apply(Context.Random, new ItemArray<IntegerVector>(Context.Population.Select(x => x.Solution.Assignment)), Problem.ProblemInstance.Demands, Problem.ProblemInstance.Capacities);
162            sParam = Context.Population.Select(x => x.Solution.SParam).Average();
163          } else {
164            var m = Context.AtRandomPopulation();
165            child = (IntegerVector)m.Solution.Assignment.Clone();
166            sParam = m.Solution.SParam;
167          }
168          sParam += 0.7071 * Context.NormalRand.NextDouble();
169          RelocateEquipmentManipluator.Apply(Context.Random, child,
170            Problem.ProblemInstance.Capacities.Length, (Math.Tanh(sParam) + 1) / 2.0);
171          var eval = Problem.ProblemInstance.Evaluate(child);
172          Context.EvaluatedSolutions++;
173
174          var offspring = new ESGQAPSolution(child, eval, sParam);
175
176          var fit = Problem.ProblemInstance.ToSingleObjective(offspring.Evaluation);
177          if (Selection == ESSelection.Comma || Context.Population.Select(x => x.Solution.Assignment).All(x => !eq.Equals(child, x)))
178            nextGen.Add(Context.ToScope(offspring, fit));
179
180          if (fit < Context.BestQuality) {
181            Context.BestQuality = fit;
182            Context.BestSolution = (ESGQAPSolution)offspring.Clone();
183          }
184        }
185
186        if (Selection == ESSelection.Comma) {
187          Context.ReplacePopulation(nextGen.OrderBy(x => x.Fitness).Take(Mu));
188        } else if (Selection == ESSelection.Plus) {
189          var best = Context.Population.Concat(nextGen).OrderBy(x => x.Fitness).Take(Mu).ToList();
190          Context.ReplacePopulation(best);
191        } else throw new InvalidOperationException("Unknown Selection strategy: " + Selection);
192
193        IResult result;
194        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
195          if (Results.TryGetValue("Iterations", out result))
196            ((IntValue)result.Value).Value = Context.Iterations;
197          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
198          if (Results.TryGetValue("EvaluatedSolutions", out result))
199            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
200          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
201          lastUpdate = ExecutionTime;
202        }
203        if (Results.TryGetValue("BestQuality", out result))
204          ((DoubleValue)result.Value).Value = Context.BestQuality;
205        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
206        if (Results.TryGetValue("BestSolution", out result))
207          result.Value = Context.BestSolution;
208        else Results.Add(new Result("BestSolution", Context.BestSolution));
209
210        try {
211          Context.RunOperator(Analyzer, cancellationToken);
212        } catch (OperationCanceledException) { }
213
214        Context.Iterations++;
215        if (cancellationToken.IsCancellationRequested) break;
216      }
217      IResult result2;
218      if (Results.TryGetValue("Iterations", out result2))
219        ((IntValue)result2.Value).Value = Context.Iterations;
220      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
221      if (Results.TryGetValue("EvaluatedSolutions", out result2))
222        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
223      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
224    }
225  }
226}
Note: See TracBrowser for help on using the repository browser.