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

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

#1614:

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