source: branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASP.cs @ 15700

Last change on this file since 15700 was 15700, checked in by abeham, 3 years ago

#1614:

  • Changed performance measure to stopwatch instead of datetime for precision reasons
File size: 15.9 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.GRASP {
34
35  /// <summary>
36  /// 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
37  /// </summary>
38  /// <remarks>
39  /// A fine distinction to the described algorithm is that newly found best solutions are always accepted into the elite set. This is reasonable, but not mentioned in the paper by Mateus et al.
40  /// </remarks>
41  [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.")]
42  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
43  [StorableClass]
44  public sealed class GRASP : StochasticAlgorithm<GRASPContext, IntegerVectorEncoding> {
45
46    public override bool SupportsPause {
47      get { return true; }
48    }
49
50    public override Type ProblemType {
51      get { return typeof(GQAP); }
52    }
53
54    public new GQAP Problem {
55      get { return (GQAP)base.Problem; }
56      set { base.Problem = value; }
57    }
58
59    [Storable]
60    private FixedValueParameter<IntValue> eliteSetSizeParameter;
61    private IFixedValueParameter<IntValue> EliteSetSizeParameter {
62      get { return eliteSetSizeParameter; }
63    }
64    [Storable]
65    private FixedValueParameter<IntValue> minimiumEliteSetSizeParameter;
66    public IFixedValueParameter<IntValue> MinimumEliteSetSizeParameter {
67      get { return minimiumEliteSetSizeParameter; }
68    }
69    [Storable]
70    private FixedValueParameter<IntValue> maximumLocalSearchIterationsParameter;
71    public IFixedValueParameter<IntValue> MaximumLocalSearchIterationsParameter {
72      get { return maximumLocalSearchIterationsParameter; }
73    }
74    [Storable]
75    private FixedValueParameter<PercentValue> candidateSizeFactorParameter;
76    public IFixedValueParameter<PercentValue> CandidateSizeFactorParameter {
77      get { return candidateSizeFactorParameter; }
78    }
79    [Storable]
80    private FixedValueParameter<IntValue> maximumCandidateListSizeParameter;
81    public IFixedValueParameter<IntValue> MaximumCandidateListSizeParameter {
82      get { return maximumCandidateListSizeParameter; }
83    }
84    [Storable]
85    private FixedValueParameter<PercentValue> oneMoveProbabilityParameter;
86    public IFixedValueParameter<PercentValue> OneMoveProbabilityParameter {
87      get { return oneMoveProbabilityParameter; }
88    }
89    [Storable]
90    private FixedValueParameter<IntValue> minimumDifferenceParameter;
91    public IFixedValueParameter<IntValue> MinimumDifferenceParameter {
92      get { return minimumDifferenceParameter; }
93    }
94   
95    public int EliteSetSize {
96      get { return eliteSetSizeParameter.Value.Value; }
97      set { eliteSetSizeParameter.Value.Value = value; }
98    }
99    public int MinimumEliteSetSize {
100      get { return minimiumEliteSetSizeParameter.Value.Value; }
101      set { minimiumEliteSetSizeParameter.Value.Value = value; }
102    }
103    public int MaximumLocalSearchIterations {
104      get { return maximumLocalSearchIterationsParameter.Value.Value; }
105      set { maximumLocalSearchIterationsParameter.Value.Value = value; }
106    }
107    public double CandidateSizeFactor {
108      get { return candidateSizeFactorParameter.Value.Value; }
109      set { candidateSizeFactorParameter.Value.Value = value; }
110    }
111    public int MaximumCandidateListSize {
112      get { return maximumCandidateListSizeParameter.Value.Value; }
113      set { maximumCandidateListSizeParameter.Value.Value = value; }
114    }
115    public double OneMoveProbability {
116      get { return oneMoveProbabilityParameter.Value.Value; }
117      set { oneMoveProbabilityParameter.Value.Value = value; }
118    }
119    public int MinimumDifference {
120      get { return minimumDifferenceParameter.Value.Value; }
121      set { minimumDifferenceParameter.Value.Value = value; }
122    }
123
124    [StorableConstructor]
125    private GRASP(bool deserializing) : base(deserializing) { }
126    private GRASP(GRASP original, Cloner cloner)
127      : base(original, cloner) {
128      eliteSetSizeParameter = cloner.Clone(original.eliteSetSizeParameter);
129      minimiumEliteSetSizeParameter = cloner.Clone(original.minimiumEliteSetSizeParameter);
130      maximumLocalSearchIterationsParameter = cloner.Clone(original.maximumLocalSearchIterationsParameter);
131      candidateSizeFactorParameter = cloner.Clone(original.candidateSizeFactorParameter);
132      maximumCandidateListSizeParameter = cloner.Clone(original.maximumCandidateListSizeParameter);
133      oneMoveProbabilityParameter = cloner.Clone(original.oneMoveProbabilityParameter);
134      minimumDifferenceParameter = cloner.Clone(original.minimumDifferenceParameter);
135    }
136    public GRASP() {
137      Parameters.Add(eliteSetSizeParameter = new FixedValueParameter<IntValue>("EliteSetSize", "The (maximum) size of the elite set.", new IntValue(10)));
138      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)));
139      Parameters.Add(maximumLocalSearchIterationsParameter = new FixedValueParameter<IntValue>("MaximumLocalSearchIteration", "The maximum number of iterations that the approximate local search should run", new IntValue(100)));
140      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)));
141      Parameters.Add(maximumCandidateListSizeParameter = new FixedValueParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
142      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)));
143      Parameters.Add(minimumDifferenceParameter = new FixedValueParameter<IntValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new IntValue(4)));
144
145      Problem = new GQAP();
146    }
147
148    public override IDeepCloneable Clone(Cloner cloner) {
149      return new GRASP(this, cloner);
150    }
151
152    protected override void Initialize(CancellationToken cancellationToken) {
153      base.Initialize(cancellationToken);
154
155      Context.Problem = Problem;
156      Context.BestSolution = null;
157
158      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
159      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
160      Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
161      Results.Add(new Result("BestSolution", typeof(GQAPSolution)));
162    }
163
164    protected override void Run(CancellationToken cancellationToken) {
165      base.Run(cancellationToken);
166      var eq = new IntegerVectorEqualityComparer();
167      var lastUpdate = ExecutionTime;
168      while (!StoppingCriterion()) { // line 2 in Algorithm 1
169        // next: line 3 in Algorithm 1
170        IntegerVector pi_prime_vec = null;
171        try {
172          pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
173        } catch (OperationCanceledException) { break; }
174
175        if (Context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
176          GQAPSolution pi_prime;
177          if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1
178            pi_prime = (GQAPSolution)Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution.Clone(); // line 6 in Algorithm 1
179          else {
180            // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1
181            pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
182            Context.EvaluatedSolutions++;
183          }
184
185          ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1
186          var pi_plus = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)); // line 9 in Algorithm 1
187          pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1
188          ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1
189          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
190          // Book-keeping
191          var newBest = Context.BestQuality > fitness;
192          if (newBest) {
193            Context.BestQuality = fitness;
194            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
195          }
196
197          if (Context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
198            double[] similarities = Context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
199            // NOTE: In the original paper it is not described that new best solutions are accepted regardless of difference
200            // in this implementation a new best solution is always accepted into the elite set
201            if (newBest || similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1
202              var replacement = Context.Population.Select((v, i) => new { Scope = v, Index = i })
203                                          .Where(x => x.Scope.Fitness >= fitness) // cond. 1 of line 13 in Algorithm 1
204                                          .OrderByDescending(x => similarities[x.Index]) // line 14 in Algorithm 1
205                                          .FirstOrDefault();
206              if (replacement != null) {
207                Context.ReplaceAtPopulation(replacement.Index, Context.ToScope(pi_prime, fitness)); // line 14 in Algorithm 1
208              }
209            }
210            // NOTE: In the original paper it is not described that new best solutions are accepted regardless of difference
211            // in this implementation a new best solution is always accepted into the elite set
212          } else if (newBest || IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1
213            Context.AddToPopulation(Context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
214          }
215        } else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */
216          && IsSufficientlyDifferent(pi_prime_vec))  /* cond. 2 of line 21 in Algorithm 1 */ {
217          var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
218          Context.EvaluatedSolutions++;
219          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
220          Context.AddToPopulation(Context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
221          // Book-keeping
222          if (Context.PopulationCount == 1 || Context.BestQuality > fitness) {
223            Context.BestQuality = fitness;
224            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
225          }
226        }
227
228        IResult result;
229        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
230          if (Results.TryGetValue("Iterations", out result))
231            ((IntValue)result.Value).Value = Context.Iterations;
232          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
233          if (Results.TryGetValue("EvaluatedSolutions", out result))
234            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
235          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
236          lastUpdate = ExecutionTime;
237        }
238        if (Results.TryGetValue("BestQuality", out result))
239          ((DoubleValue)result.Value).Value = Context.BestQuality;
240        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
241        if (Results.TryGetValue("BestSolution", out result))
242          result.Value = Context.BestSolution;
243        else Results.Add(new Result("BestSolution", Context.BestSolution));
244
245        try {
246          Context.RunOperator(Analyzer, cancellationToken);
247        } catch (OperationCanceledException) { }
248
249        Context.Iterations++;
250        if (cancellationToken.IsCancellationRequested) break;
251      }
252      IResult result2;
253      if (Results.TryGetValue("Iterations", out result2))
254        ((IntValue)result2.Value).Value = Context.Iterations;
255      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
256      if (Results.TryGetValue("EvaluatedSolutions", out result2))
257        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
258      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
259    }
260
261    private bool IsSufficientlyDifferent(IntegerVector vec) {
262      return Context.Population.All(x =>
263        HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length)
264      );
265    }
266
267    private GQAPSolution PathRelinking(GQAPSolution pi_prime, GQAPSolution pi_plus) {
268      // Following code represents line 1 of Algorithm 4
269      IntegerVector source = pi_prime.Assignment, target = pi_plus.Assignment;
270      Evaluation sourceEval = pi_prime.Evaluation, targetEval = pi_plus.Evaluation;
271      var sourceFit = Problem.ProblemInstance.ToSingleObjective(sourceEval);
272      var targetFit = Problem.ProblemInstance.ToSingleObjective(targetEval);
273      if (targetFit < sourceFit) {
274        var h = source;
275        source = target;
276        target = h;
277        var hh = sourceEval;
278        sourceEval = targetEval;
279        targetEval = hh;
280      }
281      int evaluatedSolutions;
282      // lines 2-36 of Algorithm 4 are implemented in the following call
283      var pi_star = GQAPPathRelinking.Apply(Context.Random, source, sourceEval,
284        target, targetEval, Problem.ProblemInstance, CandidateSizeFactor,
285        out evaluatedSolutions);
286      Context.EvaluatedSolutions += evaluatedSolutions;
287      return pi_star;
288    }
289
290    private void ApproxLocalSearch(GQAPSolution pi_prime) {
291      var localSearchEvaluations = 0;
292      ApproximateLocalSearch.Apply(Context.Random, pi_prime, MaximumCandidateListSize,
293        OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations);
294      Context.EvaluatedSolutions += localSearchEvaluations;
295    }
296  }
297}
Note: See TracBrowser for help on using the repository browser.