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

Last change on this file since 15562 was 15562, checked in by abeham, 5 years ago

#1614: added additional algorithms

File size: 14.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  [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      while (!StoppingCriterion()) { // line 2 in Algorithm 1
167        // next: line 3 in Algorithm 1
168        var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
169        if (Context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
170          GQAPSolution pi_prime;
171          if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1
172            pi_prime = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution; // line 6 in Algorithm 1
173          else {
174            // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1
175            pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
176            Context.EvaluatedSolutions++;
177          }
178
179          ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1
180          var pi_plus = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)); // line 9 in Algorithm 1
181          pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1
182          ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1
183          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
184          // Book-keeping
185          if (Context.BestQuality > fitness) {
186            Context.BestQuality = fitness;
187            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
188          }
189
190          if (Context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
191            var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
192            double[] similarities = Context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
193            if (similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1
194              var replacement = Context.Population.Select((v, i) => new { V = v, Index = i })
195                                          .Where(x => x.V.Fitness >= fit).ToArray();
196              if (replacement.Length > 0) { // cond. 1 of line 13 in Algorithm 1
197                // next two lines: line 14 in Algorithm 1
198                replacement = replacement.OrderBy(x => similarities[x.Index]).ToArray();
199                Context.ReplaceAtPopulation(replacement.Last().Index, Context.ToScope(pi_prime, fit));
200              }
201            }
202          } else if (IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1
203            Context.AddToPopulation(Context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
204          }
205        } else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */
206          && IsSufficientlyDifferent(pi_prime_vec))  /* cond. 2 of line 21 in Algorithm 1 */ {
207          var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
208          Context.EvaluatedSolutions++;
209          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
210          Context.AddToPopulation(Context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
211          // Book-keeping
212          if (Context.PopulationCount == 1 || Context.BestQuality > fitness) {
213            Context.BestQuality = fitness;
214            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
215          }
216        }
217
218        IResult result;
219        if (Results.TryGetValue("Iterations", out result))
220          ((IntValue)result.Value).Value = Context.Iterations;
221        else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
222        if (Results.TryGetValue("EvaluatedSolutions", out result))
223          ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
224        else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
225        if (Results.TryGetValue("BestQuality", out result))
226          ((DoubleValue)result.Value).Value = Context.BestQuality;
227        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
228        if (Results.TryGetValue("BestSolution", out result))
229          result.Value = Context.BestSolution;
230        else Results.Add(new Result("BestSolution", Context.BestSolution));
231
232        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
233
234        Context.Iterations++;
235        if (cancellationToken.IsCancellationRequested) break;
236      }
237    }
238
239    private bool IsSufficientlyDifferent(IntegerVector vec) {
240      return Context.Population.All(x =>
241        HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length)
242      );
243    }
244
245    private GQAPSolution PathRelinking(GQAPSolution pi_prime, GQAPSolution pi_plus) {
246      // Following code represents line 1 of Algorithm 4
247      IntegerVector source = pi_prime.Assignment, target = pi_plus.Assignment;
248      Evaluation sourceEval = pi_prime.Evaluation, targetEval = pi_plus.Evaluation;
249      var sourceFit = Problem.ProblemInstance.ToSingleObjective(sourceEval);
250      var targetFit = Problem.ProblemInstance.ToSingleObjective(targetEval);
251      if (targetFit < sourceFit) {
252        var h = source;
253        source = target;
254        target = h;
255        var hh = sourceEval;
256        sourceEval = targetEval;
257        targetEval = hh;
258      }
259      int evaluatedSolutions;
260      // lines 2-36 of Algorithm 4 are implemented in the following call
261      var pi_star = GQAPPathRelinking.Apply(Context.Random, source, sourceEval,
262        target, targetEval, Problem.ProblemInstance, CandidateSizeFactor,
263        out evaluatedSolutions);
264      Context.EvaluatedSolutions += evaluatedSolutions;
265      return pi_star;
266    }
267
268    private void ApproxLocalSearch(GQAPSolution pi_prime) {
269      var localSearchEvaluations = 0;
270      ApproximateLocalSearch.Apply(Context.Random, pi_prime, MaximumCandidateListSize,
271        OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations);
272      Context.EvaluatedSolutions += localSearchEvaluations;
273    }
274  }
275}
Note: See TracBrowser for help on using the repository browser.