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

Last change on this file since 15704 was 15704, checked in by abeham, 19 months ago

#1614:

  • fixed exception in case no solution could be found
  • fixed behavior in GRASP regarding infeasible solutions
File size: 16.5 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, 10, true, 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        } else if (Context.PopulationCount == 0) {
227          // Book-keeping
228          // pi_prime_vec is not feasible, but no other feasible solution has been found so far
229          var eval = Problem.ProblemInstance.Evaluate(pi_prime_vec);
230          Context.EvaluatedSolutions++;
231          var fit = Problem.ProblemInstance.ToSingleObjective(eval);
232          if (double.IsNaN(Context.BestQuality) || fit < Context.BestQuality) {
233            Context.BestQuality = fit;
234            Context.BestSolution = new GQAPSolution(pi_prime_vec, eval);
235          }
236        }
237
238        IResult result;
239        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
240          if (Results.TryGetValue("Iterations", out result))
241            ((IntValue)result.Value).Value = Context.Iterations;
242          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
243          if (Results.TryGetValue("EvaluatedSolutions", out result))
244            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
245          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
246          lastUpdate = ExecutionTime;
247        }
248        if (Results.TryGetValue("BestQuality", out result))
249          ((DoubleValue)result.Value).Value = Context.BestQuality;
250        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
251        if (Results.TryGetValue("BestSolution", out result))
252          result.Value = Context.BestSolution;
253        else Results.Add(new Result("BestSolution", Context.BestSolution));
254
255        try {
256          Context.RunOperator(Analyzer, cancellationToken);
257        } catch (OperationCanceledException) { }
258
259        Context.Iterations++;
260        if (cancellationToken.IsCancellationRequested) break;
261      }
262      IResult result2;
263      if (Results.TryGetValue("Iterations", out result2))
264        ((IntValue)result2.Value).Value = Context.Iterations;
265      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
266      if (Results.TryGetValue("EvaluatedSolutions", out result2))
267        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
268      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
269    }
270
271    private bool IsSufficientlyDifferent(IntegerVector vec) {
272      return Context.Population.All(x =>
273        HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length)
274      );
275    }
276
277    private GQAPSolution PathRelinking(GQAPSolution pi_prime, GQAPSolution pi_plus) {
278      // Following code represents line 1 of Algorithm 4
279      IntegerVector source = pi_prime.Assignment, target = pi_plus.Assignment;
280      Evaluation sourceEval = pi_prime.Evaluation, targetEval = pi_plus.Evaluation;
281      var sourceFit = Problem.ProblemInstance.ToSingleObjective(sourceEval);
282      var targetFit = Problem.ProblemInstance.ToSingleObjective(targetEval);
283      if (targetFit < sourceFit) {
284        var h = source;
285        source = target;
286        target = h;
287        var hh = sourceEval;
288        sourceEval = targetEval;
289        targetEval = hh;
290      }
291      int evaluatedSolutions;
292      // lines 2-36 of Algorithm 4 are implemented in the following call
293      var pi_star = GQAPPathRelinking.Apply(Context.Random, source, sourceEval,
294        target, targetEval, Problem.ProblemInstance, CandidateSizeFactor,
295        out evaluatedSolutions);
296      Context.EvaluatedSolutions += evaluatedSolutions;
297      return pi_star;
298    }
299
300    private void ApproxLocalSearch(GQAPSolution pi_prime) {
301      var localSearchEvaluations = 0;
302      ApproximateLocalSearch.Apply(Context.Random, pi_prime, MaximumCandidateListSize,
303        OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations);
304      Context.EvaluatedSolutions += localSearchEvaluations;
305    }
306  }
307}
Note: See TracBrowser for help on using the repository browser.