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

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

#1614: Added CPLEX algorithms

File size: 16.0 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.BestQuality = double.NaN;
157      Context.BestSolution = null;
158
159      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
160      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
161      Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
162      Results.Add(new Result("BestSolution", typeof(GQAPSolution)));
163
164      Context.RunOperator(Analyzer, cancellationToken);
165    }
166
167    protected override void Run(CancellationToken cancellationToken) {
168      var eq = new IntegerVectorEqualityComparer();
169      var lastUpdate = ExecutionTime;
170      while (!StoppingCriterion()) { // line 2 in Algorithm 1
171        // next: line 3 in Algorithm 1
172        IntegerVector pi_prime_vec = null;
173        try {
174          pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
175        } catch (OperationCanceledException) { break; }
176
177        if (Context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
178          GQAPSolution pi_prime;
179          if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1
180            pi_prime = (GQAPSolution)Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution.Clone(); // line 6 in Algorithm 1
181          else {
182            // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1
183            pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
184            Context.EvaluatedSolutions++;
185          }
186
187          ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1
188          var pi_plus = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)); // line 9 in Algorithm 1
189          pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1
190          ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1
191          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
192          // Book-keeping
193          var newBest = Context.BestQuality > fitness;
194          if (newBest) {
195            Context.BestQuality = fitness;
196            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
197          }
198
199          if (Context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
200            double[] similarities = Context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
201            // NOTE: In the original paper it is not described that new best solutions are accepted regardless of difference
202            // in this implementation a new best solution is always accepted into the elite set
203            if (newBest || similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1
204              var replacement = Context.Population.Select((v, i) => new { Scope = v, Index = i })
205                                          .Where(x => x.Scope.Fitness >= fitness) // cond. 1 of line 13 in Algorithm 1
206                                          .OrderByDescending(x => similarities[x.Index]) // line 14 in Algorithm 1
207                                          .FirstOrDefault();
208              if (replacement != null) {
209                Context.ReplaceAtPopulation(replacement.Index, Context.ToScope(pi_prime, fitness)); // line 14 in Algorithm 1
210              }
211            }
212            // NOTE: In the original paper it is not described that new best solutions are accepted regardless of difference
213            // in this implementation a new best solution is always accepted into the elite set
214          } else if (newBest || IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1
215            Context.AddToPopulation(Context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
216          }
217        } else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */
218          && IsSufficientlyDifferent(pi_prime_vec))  /* cond. 2 of line 21 in Algorithm 1 */ {
219          var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
220          Context.EvaluatedSolutions++;
221          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
222          Context.AddToPopulation(Context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
223          // Book-keeping
224          if (Context.PopulationCount == 1 || Context.BestQuality > fitness) {
225            Context.BestQuality = fitness;
226            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
227          }
228        }
229
230        IResult result;
231        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
232          if (Results.TryGetValue("Iterations", out result))
233            ((IntValue)result.Value).Value = Context.Iterations;
234          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
235          if (Results.TryGetValue("EvaluatedSolutions", out result))
236            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
237          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
238          lastUpdate = ExecutionTime;
239        }
240        if (Results.TryGetValue("BestQuality", out result))
241          ((DoubleValue)result.Value).Value = Context.BestQuality;
242        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
243        if (Results.TryGetValue("BestSolution", out result))
244          result.Value = Context.BestSolution;
245        else Results.Add(new Result("BestSolution", Context.BestSolution));
246
247        try {
248          Context.RunOperator(Analyzer, cancellationToken);
249        } catch (OperationCanceledException) { }
250
251        Context.Iterations++;
252        if (cancellationToken.IsCancellationRequested) break;
253      }
254      IResult result2;
255      if (Results.TryGetValue("Iterations", out result2))
256        ((IntValue)result2.Value).Value = Context.Iterations;
257      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
258      if (Results.TryGetValue("EvaluatedSolutions", out result2))
259        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
260      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
261    }
262
263    private bool IsSufficientlyDifferent(IntegerVector vec) {
264      return Context.Population.All(x =>
265        HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length)
266      );
267    }
268
269    private GQAPSolution PathRelinking(GQAPSolution pi_prime, GQAPSolution pi_plus) {
270      // Following code represents line 1 of Algorithm 4
271      IntegerVector source = pi_prime.Assignment, target = pi_plus.Assignment;
272      Evaluation sourceEval = pi_prime.Evaluation, targetEval = pi_plus.Evaluation;
273      var sourceFit = Problem.ProblemInstance.ToSingleObjective(sourceEval);
274      var targetFit = Problem.ProblemInstance.ToSingleObjective(targetEval);
275      if (targetFit < sourceFit) {
276        var h = source;
277        source = target;
278        target = h;
279        var hh = sourceEval;
280        sourceEval = targetEval;
281        targetEval = hh;
282      }
283      int evaluatedSolutions;
284      // lines 2-36 of Algorithm 4 are implemented in the following call
285      var pi_star = GQAPPathRelinking.Apply(Context.Random, source, sourceEval,
286        target, targetEval, Problem.ProblemInstance, CandidateSizeFactor,
287        out evaluatedSolutions);
288      Context.EvaluatedSolutions += evaluatedSolutions;
289      return pi_star;
290    }
291
292    private void ApproxLocalSearch(GQAPSolution pi_prime) {
293      var localSearchEvaluations = 0;
294      ApproximateLocalSearch.Apply(Context.Random, pi_prime, MaximumCandidateListSize,
295        OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations);
296      Context.EvaluatedSolutions += localSearchEvaluations;
297    }
298  }
299}
Note: See TracBrowser for help on using the repository browser.