source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP.cs @ 15553

Last change on this file since 15553 was 15553, checked in by abeham, 4 years ago

#1614:

  • Implementing basic algorithm according to paper (rechecking all operators)
  • Checking implementation with paper
  • Improved speed of move generator
  • Improved speed of randomized solution creator
File size: 17.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.Linq;
24using System.Threading;
25using HeuristicLab.Analysis;
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.GRASP {
36
37  /// <summary>
38  /// This is an implementation of the algorithm described in Mateus, G.R., Resende, M.G.C. & Silva, R.M.A. J Heuristics (2011) 17: 527. https://doi.org/10.1007/s10732-010-9144-0
39  /// </summary>
40  [Item("GRASP+PR (GQAP)", "The algorithm implements the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking as described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.")]
41  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
42  [StorableClass]
43  public class GRASP : BasicAlgorithm {
44
45    public override bool SupportsPause {
46      get { return true; }
47    }
48
49    public override Type ProblemType {
50      get { return typeof(GQAP); }
51    }
52
53    public new GQAP Problem {
54      get { return (GQAP)base.Problem; }
55      set { base.Problem = value; }
56    }
57
58    [Storable]
59    private ValueParameter<IAnalyzer> analyzerParameter;
60    public IValueParameter<IAnalyzer> AnalyzerParameter {
61      get { return analyzerParameter; }
62    }
63
64    [Storable]
65    private FixedValueParameter<BoolValue> setSeedRandomlyParameter;
66    private IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {
67      get { return setSeedRandomlyParameter; }
68    }
69    [Storable]
70    private FixedValueParameter<IntValue> seedParameter;
71    private IFixedValueParameter<IntValue> SeedParameter {
72      get { return seedParameter; }
73    }
74    [Storable]
75    private FixedValueParameter<IntValue> eliteSetSizeParameter;
76    private IFixedValueParameter<IntValue> EliteSetSizeParameter {
77      get { return eliteSetSizeParameter; }
78    }
79    [Storable]
80    private FixedValueParameter<IntValue> minimiumEliteSetSizeParameter;
81    public IFixedValueParameter<IntValue> MinimumEliteSetSizeParameter {
82      get { return minimiumEliteSetSizeParameter; }
83    }
84    [Storable]
85    private FixedValueParameter<IntValue> maximumIterationsParameter;
86    public IFixedValueParameter<IntValue> MaximumIterationsParameter {
87      get { return maximumIterationsParameter; }
88    }
89    [Storable]
90    private FixedValueParameter<IntValue> maximumLocalSearchIterationsParameter;
91    public IFixedValueParameter<IntValue> MaximumLocalSearchIterationsParameter {
92      get { return maximumIterationsParameter; }
93    }
94    [Storable]
95    private FixedValueParameter<PercentValue> candidateSizeFactorParameter;
96    public IFixedValueParameter<PercentValue> CandidateSizeFactorParameter {
97      get { return candidateSizeFactorParameter; }
98    }
99    [Storable]
100    private FixedValueParameter<IntValue> maximumCandidateListSizeParameter;
101    public IFixedValueParameter<IntValue> MaximumCandidateListSizeParameter {
102      get { return maximumCandidateListSizeParameter; }
103    }
104    [Storable]
105    private FixedValueParameter<PercentValue> oneMoveProbabilityParameter;
106    public IFixedValueParameter<PercentValue> OneMoveProbabilityParameter {
107      get { return oneMoveProbabilityParameter; }
108    }
109    [Storable]
110    private FixedValueParameter<PercentValue> minimumDifferenceParameter;
111    public IFixedValueParameter<PercentValue> MinimumDifferenceParameter {
112      get { return minimumDifferenceParameter; }
113    }
114   
115    public bool SetSeedRandomly {
116      get { return setSeedRandomlyParameter.Value.Value; }
117      set { setSeedRandomlyParameter.Value.Value = value; }
118    }
119    public int Seed {
120      get { return seedParameter.Value.Value; }
121      set { seedParameter.Value.Value = value; }
122    }
123    public int MinimumEliteSetSize {
124      get { return minimiumEliteSetSizeParameter.Value.Value; }
125      set { minimiumEliteSetSizeParameter.Value.Value = value; }
126    }
127    public int EliteSetSize {
128      get { return eliteSetSizeParameter.Value.Value; }
129      set { eliteSetSizeParameter.Value.Value = value; }
130    }
131    public double CandidateSizeFactor {
132      get { return candidateSizeFactorParameter.Value.Value; }
133      set { candidateSizeFactorParameter.Value.Value = value; }
134    }
135    public int MaximumCandidateListSize {
136      get { return maximumCandidateListSizeParameter.Value.Value; }
137      set { maximumCandidateListSizeParameter.Value.Value = value; }
138    }
139    public double OneMoveProbability {
140      get { return oneMoveProbabilityParameter.Value.Value; }
141      set { oneMoveProbabilityParameter.Value.Value = value; }
142    }
143    public double MinimumDifference {
144      get { return minimumDifferenceParameter.Value.Value; }
145      set { minimumDifferenceParameter.Value.Value = value; }
146    }
147
148    [StorableConstructor]
149    protected GRASP(bool deserializing) : base(deserializing) { }
150    protected GRASP(GRASP original, Cloner cloner)
151      : base(original, cloner) {
152      setSeedRandomlyParameter = cloner.Clone(original.setSeedRandomlyParameter);
153      seedParameter = cloner.Clone(original.seedParameter);
154      analyzerParameter = cloner.Clone(original.analyzerParameter);
155      eliteSetSizeParameter = cloner.Clone(original.eliteSetSizeParameter);
156      minimiumEliteSetSizeParameter = cloner.Clone(original.minimiumEliteSetSizeParameter);
157      maximumIterationsParameter = cloner.Clone(original.maximumIterationsParameter);
158      maximumLocalSearchIterationsParameter = cloner.Clone(original.maximumLocalSearchIterationsParameter);
159      candidateSizeFactorParameter = cloner.Clone(original.candidateSizeFactorParameter);
160      maximumCandidateListSizeParameter = cloner.Clone(original.maximumCandidateListSizeParameter);
161      oneMoveProbabilityParameter = cloner.Clone(original.oneMoveProbabilityParameter);
162      minimumDifferenceParameter = cloner.Clone(original.minimumDifferenceParameter);
163      context = cloner.Clone(original.context);
164    }
165    public GRASP() {
166      Parameters.Add(setSeedRandomlyParameter = new FixedValueParameter<BoolValue>("SetSeedRandomly", "Whether to overwrite the seed with a random value each time the algorithm is run.", new BoolValue(true)));
167      Parameters.Add(seedParameter = new FixedValueParameter<IntValue>("Seed", "The random seed that is used in the stochastic algorithm", new IntValue(0)));
168      Parameters.Add(analyzerParameter = new ValueParameter<IAnalyzer>("Analyzer", "The analyzers that are used to perform an analysis of the solutions.", new MultiAnalyzer()));
169      Parameters.Add(eliteSetSizeParameter = new FixedValueParameter<IntValue>("EliteSetSize", "The (maximum) size of the elite set.", new IntValue(10)));
170      Parameters.Add(minimiumEliteSetSizeParameter = new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimal size of the elite set, before local search and path relinking are applied.", new IntValue(2)));
171      Parameters.Add(maximumIterationsParameter = new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run.", new IntValue(1000)));
172      Parameters.Add(maximumLocalSearchIterationsParameter = new FixedValueParameter<IntValue>("MaximumLocalSearchIteration", "The maximum number of iterations that the approximate local search should run", new IntValue(100)));
173      Parameters.Add(candidateSizeFactorParameter = new FixedValueParameter<PercentValue>("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each path - relinking step relative to the maximum size.A value of 50 % means that only half of all possible moves are considered each step.", new PercentValue(0.5)));
174      Parameters.Add(maximumCandidateListSizeParameter = new FixedValueParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
175      Parameters.Add(oneMoveProbabilityParameter = new FixedValueParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
176      Parameters.Add(minimumDifferenceParameter = new FixedValueParameter<PercentValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new PercentValue(1e-7)));
177      Problem = new GQAP();
178    }
179
180    public override IDeepCloneable Clone(Cloner cloner) {
181      return new GRASP(this, cloner);
182    }
183
184    public override void Prepare() {
185      base.Prepare();
186      Results.Clear();
187      context = null;
188    }
189
190    [Storable]
191    private GRASPContext context;
192
193    protected override void Initialize(CancellationToken cancellationToken) {
194      base.Initialize(cancellationToken);
195      context = new GRASPContext();
196      context.Problem = Problem;
197      context.Scope.Variables.Add(new Variable("Results", Results));
198
199      IExecutionContext ctxt = null;
200      foreach (var item in Problem.ExecutionContextItems)
201        ctxt = new Core.ExecutionContext(ctxt, item, context.Scope);
202      ctxt = new Core.ExecutionContext(ctxt, this, context.Scope);
203      context.Parent = ctxt;
204
205      if (SetSeedRandomly) {
206        var rnd = new System.Random();
207        Seed = rnd.Next();
208      }
209      context.Random = new MersenneTwister((uint)Seed);
210      context.Iterations = 0;
211      context.EvaluatedSolutions = 0;
212      context.BestQuality = double.NaN;
213      context.BestSolution = null;
214
215      context.Initialized = true;
216
217      Results.Add(new Result("Iterations", new IntValue(context.Iterations)));
218      Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions)));
219      Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality)));
220      Results.Add(new Result("BestSolution", typeof(GQAPSolution)));
221
222      context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
223    }
224
225    protected override void Run(CancellationToken cancellationToken) {
226      var eq = new IntegerVectorEqualityComparer();
227      while (!StoppingCriterion()) { // line 2 in Algorithm 1
228        // next: line 3 in Algorithm 1
229        var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
230        if (context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
231          GQAPSolution pi_prime;
232          if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1
233            pi_prime = context.AtPopulation(context.Random.Next(context.PopulationCount)).Solution; // line 6 in Algorithm 1
234          else {
235            // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1
236            pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
237            context.EvaluatedSolutions++;
238          }
239
240          ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1
241          var pi_plus = context.AtPopulation(context.Random.Next(context.PopulationCount)); // line 9 in Algorithm 1
242          pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1
243          ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1
244          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
245          // Book-keeping
246          if (context.BestQuality > fitness) {
247            context.BestQuality = fitness;
248            context.BestSolution = (GQAPSolution)pi_prime.Clone();
249          }
250
251          if (context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
252            var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
253            double[] similarities = context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
254            if (similarities.Max() <= 1.0 - MinimumDifference) { // cond. 2 of line 13 in Algorithm 1
255              var replacement = context.Population.Select((v, i) => new { V = v, Index = i })
256                                          .Where(x => x.V.Fitness >= fit).ToArray();
257              if (replacement.Length > 0) { // cond. 1 of line 13 in Algorithm 1
258                // next two lines: line 14 in Algorithm 1
259                replacement = replacement.OrderBy(x => similarities[x.Index]).ToArray();
260                context.ReplaceAtPopulation(replacement.Last().Index, context.ToScope(pi_prime, fit));
261              }
262            }
263          } else if (IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1
264            context.AddToPopulation(context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
265          }
266        } else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */
267          && IsSufficientlyDifferent(pi_prime_vec))  /* cond. 2 of line 21 in Algorithm 1 */ {
268          var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
269          context.EvaluatedSolutions++;
270          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
271          context.AddToPopulation(context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
272          // Book-keeping
273          if (context.PopulationCount == 1 || context.BestQuality > fitness) {
274            context.BestQuality = fitness;
275            context.BestSolution = (GQAPSolution)pi_prime.Clone();
276          }
277        }
278
279        context.Iterations++;
280
281        IResult result;
282        if (Results.TryGetValue("Iterations", out result))
283          ((IntValue)result.Value).Value = context.Iterations;
284        else Results.Add(new Result("Iterations", new IntValue(context.Iterations)));
285        if (Results.TryGetValue("EvaluatedSolutions", out result))
286          ((IntValue)result.Value).Value = context.EvaluatedSolutions;
287        else Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions)));
288        if (Results.TryGetValue("BestQuality", out result))
289          ((DoubleValue)result.Value).Value = context.BestQuality;
290        else Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality)));
291        if (Results.TryGetValue("BestSolution", out result))
292          result.Value = context.BestSolution;
293        else Results.Add(new Result("BestSolution", context.BestSolution));
294
295        context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
296      }
297    }
298
299    private bool IsSufficientlyDifferent(IntegerVector vec) {
300      return context.Population.All(x =>
301        HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, vec) <= 1.0 - MinimumDifference
302      );
303    }
304
305    private GQAPSolution PathRelinking(GQAPSolution pi_prime, GQAPSolution pi_plus) {
306      // Following code represents line 1 of Algorithm 4
307      IntegerVector source = pi_prime.Assignment, target = pi_plus.Assignment;
308      Evaluation sourceEval = pi_prime.Evaluation, targetEval = pi_plus.Evaluation;
309      var sourceFit = Problem.ProblemInstance.ToSingleObjective(sourceEval);
310      var targetFit = Problem.ProblemInstance.ToSingleObjective(targetEval);
311      if (targetFit < sourceFit) {
312        var h = source;
313        source = target;
314        target = h;
315        var hh = sourceEval;
316        sourceEval = targetEval;
317        targetEval = hh;
318      }
319      int evaluatedSolutions;
320      // lines 2-36 of Algorithm 4 are implemented in the following call
321      var pi_star = GQAPPathRelinking.Apply(context.Random, source, sourceEval,
322        target, targetEval, Problem.ProblemInstance, CandidateSizeFactor,
323        out evaluatedSolutions);
324      context.EvaluatedSolutions += evaluatedSolutions;
325      return pi_star;
326    }
327
328    private void ApproxLocalSearch(GQAPSolution pi_prime) {
329      var localSearchEvaluations = 0;
330      ApproximateLocalSearch.Apply(context.Random, pi_prime, MaximumCandidateListSize,
331        OneMoveProbability, 1000, Problem.ProblemInstance, out localSearchEvaluations);
332      context.EvaluatedSolutions += localSearchEvaluations;
333    }
334
335    private bool StoppingCriterion() {
336      return context.Iterations > MaximumIterationsParameter.Value.Value;
337    }
338  }
339}
Note: See TracBrowser for help on using the repository browser.