source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/GQAPPathRelinking.cs @ 15553

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

#1614:

  • Implementing basic algorithm according to paper (rechecking all operators)
  • Checking implementation with paper
  • Improved speed of move generator
  • Improved speed of randomized solution creator
File size: 10.2 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.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.IntegerVectorEncoding;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Random;
32
33namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
34  [Item("GQAPPathRelinking", "Operator that performs path relinking between two solutions. It is 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.")]
35  [StorableClass]
36  public class GQAPPathRelinking : GQAPCrossover, IQualitiesAwareGQAPOperator {
37
38    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
39      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
40    }
41    public IScopeTreeLookupParameter<Evaluation> EvaluationParameter {
42      get { return (IScopeTreeLookupParameter<Evaluation>)Parameters["Evaluation"]; }
43    }
44
45    public IValueParameter<PercentValue> CandidateSizeFactorParameter {
46      get { return (IValueParameter<PercentValue>)Parameters["CandidateSizeFactor"]; }
47    }
48
49    [StorableConstructor]
50    protected GQAPPathRelinking(bool deserializing) : base(deserializing) { }
51    protected GQAPPathRelinking(GQAPPathRelinking original, Cloner cloner) : base(original, cloner) { }
52    public GQAPPathRelinking()
53      : base() {
54      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", ""));
55      Parameters.Add(new ScopeTreeLookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription));
56      Parameters.Add(new ValueParameter<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)));
57    }
58
59    public override IDeepCloneable Clone(Cloner cloner) {
60      return new GQAPPathRelinking(this, cloner);
61    }
62
63    public static GQAPSolution Apply(IRandom random,
64      IntegerVector source, Evaluation sourceEval,
65      IntegerVector target, Evaluation targetEval,
66      GQAPInstance problemInstance, double candidateSizeFactor,
67      out int evaluatedSolutions) {
68      evaluatedSolutions = 0;
69      var demands = problemInstance.Demands;
70      var capacities = problemInstance.Capacities;
71      var cmp = new IntegerVectorEqualityComparer();
72
73      var sFit = problemInstance.ToSingleObjective(sourceEval);
74      var tFit = problemInstance.ToSingleObjective(targetEval);
75      GQAPSolution pi_star = sFit < tFit ? new GQAPSolution(source, sourceEval) : new GQAPSolution(target, targetEval); // line 1 of Algorithm 4
76      double pi_star_Fit = problemInstance.ToSingleObjective(pi_star.Evaluation); // line 2 of Algorithm 4
77     
78      var pi_prime = (IntegerVector)source.Clone(); // line 3 of Algorithm 4
79      //var fix = new bool[demands.Length]; // line 3 of Algorithm 4, note that according to the description it is not necessary to track the fixed equipments
80      var nonFix = Enumerable.Range(0, demands.Length).ToList(); // line 3 of Algorithm 4
81      var phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)); // line 4 of Algorithm 4
82
83      while (phi.Count > 0) { // line 5 of Algorithm 4
84        var B = new List<GQAPSolution>((int)Math.Ceiling(phi.Count * candidateSizeFactor)); // line 6 of Algorithm 4
85        var B_fit = new List<double>(B.Capacity); // line 6 of Algorithm 4 (B is split into two synchronized lists)
86        foreach (var v in phi) { // line 7 of Algorithm 4
87          int oldLocation = pi_prime[v];
88          pi_prime[v] = target[v]; // line 8 of Algorithm 4
89          var pi_dash = MakeFeasible(random, pi_prime, v, nonFix, demands, capacities); // line 9 of Algorithm 4
90          pi_prime[v] = oldLocation; // not mentioned in Algorithm 4, but seems reasonable
91          var pi_dash_eval = problemInstance.Evaluate(pi_dash);
92          evaluatedSolutions++;
93          var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);
94
95          if (problemInstance.IsFeasible(pi_dash)) { // line 10 of Algorithm 4
96            if (B.Any(x => cmp.Equals(x.Assignment, pi_dash))) continue; // cond. 2 of line 12 and cond. 1 of line 16 in Algorithm 4
97
98            if (B.Count >= candidateSizeFactor * phi.Count) { // line 11 of Algorithm 4
99              var replacement = B_fit.Select((val, idx) => new { Index = idx, Fitness = val })
100                                            .Where(x => x.Fitness >= pi_dash_fit) // cond. 1 in line 12 of Algorithm 4
101                                            .Select(x => new { Index = x.Index, Fitness = x.Fitness, Similarity = HammingSimilarityCalculator.CalculateSimilarity(B[x.Index].Assignment, pi_dash) })
102                                            .ToArray();
103              if (replacement.Length > 0) {
104                var mostSimilar = replacement.MaxItems(x => x.Similarity).First().Index;
105                B[mostSimilar].Assignment = pi_dash; // line 13 of Algorithm 4
106                B[mostSimilar].Evaluation = pi_dash_eval; // line 13 of Algorithm 4
107                B_fit[mostSimilar] = pi_dash_fit; // line 13 of Algorithm 4
108              }
109            } else { // line 16, condition has been checked above already
110              B.Add(new GQAPSolution(pi_dash, pi_dash_eval)); // line 17 of Algorithm 4
111              B_fit.Add(pi_dash_fit); // line 17 of Algorithm 4
112            }
113          }
114        }
115        if (B.Count > 0) { // line 21 of Algorithm 4
116          var pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First(); // line 22 of Algorithm 4
117          var diff = IntegerVectorEqualityComparer.GetDifferingIndices(pi.Assignment, target); // line 23 of Algorithm 4
118          var I = phi.Except(diff); // line 24 of Algorithm 4
119          var i = I.SampleRandom(random); // line 25 of Algorithm 4
120          //fix[i] = true; // line 26 of Algorithm 4
121          nonFix.Remove(i); // line 26 of Algorithm 4
122          pi_prime = pi.Assignment; // line 27 of Algorithm 4
123          var fit = problemInstance.ToSingleObjective(pi.Evaluation);
124          if (fit < pi_star_Fit) { // line 28 of Algorithm 4
125            pi_star_Fit = fit; // line 29 of Algorithm 4
126            pi_star = pi; // line 30 of Algorithm 4
127          }
128        } else return pi_star ?? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone());
129        phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
130      }
131
132      return pi_star ?? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone());
133    }
134
135    protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents,
136      GQAPInstance problemInstance) {
137
138      var qualities = QualityParameter.ActualValue;
139      var evaluations = EvaluationParameter.ActualValue;
140      var betterParent = qualities[0].Value <= qualities[1].Value ? 0 : 1;
141      var worseParent = 1 - betterParent;
142      var source = parents[betterParent];
143      var target = parents[worseParent];
144
145      int evaluatedSolution;
146      return Apply(random, source, evaluations[betterParent],
147        target, evaluations[worseParent], problemInstance,
148        CandidateSizeFactorParameter.Value.Value, out evaluatedSolution).Assignment;
149    }
150
151    private static IntegerVector MakeFeasible(IRandom random, IntegerVector pi, int equipment, List<int> nonFix, DoubleArray demands, DoubleArray capacities, int maximumTries = 1000) {
152      int l = pi[equipment];
153      var slack = ComputeSlack(pi, demands, capacities);
154      if (slack[l] >= 0) // line 1 of Algorithm 5
155        return new IntegerVector(pi); // line 2 of Algorithm 5
156
157      IntegerVector pi_prime = null;
158      int k = 0; // line 4 of Algorithm 5
159      while (k < maximumTries && slack[l] < 0) {  // line 5 of Algorithm 5
160        pi_prime = new IntegerVector(pi); // line 6 of Algorithm 5
161        do {  // line 7 of Algorithm 5
162          var maxSlack = slack.Max(); // line 8-9 of Algorithm 5
163          var T = nonFix.Where(x => pi[x] == l && demands[x] <= maxSlack).ToList(); // line 8-9 of Algorithm 5
164          if (T.Count > 0) { // line 10 of Algorithm 5
165            int i = T.SampleProportional(random, 1, T.Select(x => demands[x]), false).First(); // line 11 of Algorithm 5
166            var j = Enumerable.Range(0, capacities.Length)
167              .Where(x => slack[x] >= demands[i]) // line 12 of Algorithm 5
168              .SampleRandom(random);  // line 13 of Algorithm 5
169            pi_prime[i] = j; // line 14 of Algorithm 5
170            slack[j] -= demands[i]; // line 14 of Algorithm 5
171            slack[l] += demands[i]; // line 14 of Algorithm 5
172          } else break; // cond. 1 in line 16 of Algorithm 5
173        } while (slack[l] < 0); // cond. 2 in line 16 of Algorithm 5
174        k++; // line 17 of Algorithm 5
175      }
176      return pi_prime; // line 19-23 of Algorithm 5
177    }
178
179    private static double[] ComputeSlack(IntegerVector assignment, DoubleArray demands, DoubleArray capacities) {
180      var slack = new double[capacities.Length];
181      for (int i = 0; i < assignment.Length; i++) {
182        slack[assignment[i]] -= demands[i];
183      }
184      return slack;
185    }
186  }
187}
Note: See TracBrowser for help on using the repository browser.