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

Last change on this file since 15572 was 15572, checked in by abeham, 23 months ago

#1614:

  • fixed a bug in GRASP where solutions in the elite set would be mutated
  • introduced termination criteria when reaching best-known quality
  • tweaked generating random numbers in StochasticNMoveSingleMoveGenerator
  • changed DiscreteLocationCrossover to use an allele from one of the parents instead of introducing a mutation in case no feasible insert location is found
  • changed OSGA maxselpress to 500
  • slight change to contexts, introduced single-objectiveness much earlier in the class hierachy
    • limited ContextAlgorithm to SingleObjectiveBasicProblems (doesn't matter here)
File size: 13.4 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  /// <summary>
35  /// 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
36  /// </summary>
37  [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.")]
38  [StorableClass]
39  public class GQAPPathRelinking : GQAPCrossover, IQualitiesAwareGQAPOperator {
40
41    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
42      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
43    }
44    public IScopeTreeLookupParameter<Evaluation> EvaluationParameter {
45      get { return (IScopeTreeLookupParameter<Evaluation>)Parameters["Evaluation"]; }
46    }
47    public IValueParameter<PercentValue> CandidateSizeFactorParameter {
48      get { return (IValueParameter<PercentValue>)Parameters["CandidateSizeFactor"]; }
49    }
50    public IValueLookupParameter<BoolValue> GreedyParameter {
51      get { return (IValueLookupParameter<BoolValue>)Parameters["Greedy"]; }
52    }
53
54    [StorableConstructor]
55    protected GQAPPathRelinking(bool deserializing) : base(deserializing) { }
56    protected GQAPPathRelinking(GQAPPathRelinking original, Cloner cloner) : base(original, cloner) { }
57    public GQAPPathRelinking()
58      : base() {
59      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", ""));
60      Parameters.Add(new ScopeTreeLookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription));
61      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)));
62      Parameters.Add(new ValueLookupParameter<BoolValue>("Greedy", "Whether to use a greedy selection strategy or a probabilistic one.", new BoolValue(true)));
63    }
64
65    public override IDeepCloneable Clone(Cloner cloner) {
66      return new GQAPPathRelinking(this, cloner);
67    }
68
69    public static GQAPSolution Apply(IRandom random,
70      IntegerVector source, Evaluation sourceEval,
71      IntegerVector target, Evaluation targetEval,
72      GQAPInstance problemInstance, double candidateSizeFactor,
73      out int evaluatedSolutions, bool greedy = true) {
74      evaluatedSolutions = 0;
75      var demands = problemInstance.Demands;
76      var capacities = problemInstance.Capacities;
77      var cmp = new IntegerVectorEqualityComparer();
78     
79      var sFit = problemInstance.ToSingleObjective(sourceEval);
80      var tFit = problemInstance.ToSingleObjective(targetEval);
81      GQAPSolution pi_star = sFit < tFit
82        ? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone())
83        : new GQAPSolution((IntegerVector)target.Clone(), (Evaluation)targetEval.Clone()); // line 1 of Algorithm 4
84      double pi_star_Fit = problemInstance.ToSingleObjective(pi_star.Evaluation); // line 2 of Algorithm 4
85     
86      var pi_prime = (IntegerVector)source.Clone(); // line 3 of Algorithm 4
87      //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
88      var nonFix = Enumerable.Range(0, demands.Length).ToList(); // line 3 of Algorithm 4
89      var phi = new List<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)); // line 4 of Algorithm 4
90
91      var B = new List<GQAPSolution>((int)Math.Ceiling(phi.Count * candidateSizeFactor));
92      var B_fit = new List<double>(B.Capacity);
93      while (phi.Count > 0) { // line 5 of Algorithm 4
94        B.Clear(); // line 6 of Algorithm 4
95        B_fit.Clear(); // line 6 of Algorithm 4 (B is split into two synchronized lists)
96        foreach (var v in phi) { // line 7 of Algorithm 4
97          int oldLocation = pi_prime[v];
98          pi_prime[v] = target[v]; // line 8 of Algorithm 4
99          var pi_dash = MakeFeasible(random, pi_prime, v, nonFix, demands, capacities); // line 9 of Algorithm 4
100          pi_prime[v] = oldLocation; // not mentioned in Algorithm 4, but seems reasonable
101
102          if (problemInstance.IsFeasible(pi_dash)) { // line 10 of Algorithm 4
103            var pi_dash_eval = problemInstance.Evaluate(pi_dash);
104            evaluatedSolutions++;
105            var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);
106
107            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
108
109            if (B.Count >= candidateSizeFactor * phi.Count) { // line 11 of Algorithm 4
110              var replacement = B_fit.Select((val, idx) => new { Index = idx, Fitness = val })
111                                            .Where(x => x.Fitness >= pi_dash_fit) // cond. 1 in line 12 of Algorithm 4
112                                            .Select(x => new { x.Index, x.Fitness, Similarity = HammingSimilarityCalculator.CalculateSimilarity(B[x.Index].Assignment, pi_dash) })
113                                            .ToArray();
114              if (replacement.Length > 0) {
115                var mostSimilar = replacement.MaxItems(x => x.Similarity).SampleRandom(random).Index;
116                B[mostSimilar].Assignment = pi_dash; // line 13 of Algorithm 4
117                B[mostSimilar].Evaluation = pi_dash_eval; // line 13 of Algorithm 4
118                B_fit[mostSimilar] = pi_dash_fit; // line 13 of Algorithm 4
119              }
120            } else { // line 16, condition has been checked above already
121              B.Add(new GQAPSolution(pi_dash, pi_dash_eval)); // line 17 of Algorithm 4
122              B_fit.Add(pi_dash_fit); // line 17 of Algorithm 4
123            }
124          }
125        }
126        if (B.Count > 0) { // line 21 of Algorithm 4
127          GQAPSolution pi;
128          // line 22 of Algorithm 4
129          if (greedy) {
130            pi = B.Select((val, idx) => new { Index = idx, Value = val }).MinItems(x => B_fit[x.Index]).SampleRandom(random).Value;
131          } else {
132            pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First();
133          }
134          var diff = IntegerVectorEqualityComparer.GetDifferingIndices(pi.Assignment, target); // line 23 of Algorithm 4
135          var I = phi.Except(diff); // line 24 of Algorithm 4
136          var i = I.SampleRandom(random); // line 25 of Algorithm 4
137          //fix[i] = true; // line 26 of Algorithm 4
138          nonFix.Remove(i); // line 26 of Algorithm 4
139          pi_prime = pi.Assignment; // line 27 of Algorithm 4
140          var fit = problemInstance.ToSingleObjective(pi.Evaluation);
141          if (fit < pi_star_Fit) { // line 28 of Algorithm 4
142            pi_star_Fit = fit; // line 29 of Algorithm 4
143            pi_star = pi; // line 30 of Algorithm 4
144          }
145        } else return pi_star;
146        phi = new List<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
147      }
148
149      return pi_star;
150    }
151
152    protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents,
153      GQAPInstance problemInstance) {
154
155      var qualities = QualityParameter.ActualValue;
156      var evaluations = EvaluationParameter.ActualValue;
157      var betterParent = qualities[0].Value <= qualities[1].Value ? 0 : 1;
158      var worseParent = 1 - betterParent;
159      var source = parents[betterParent];
160      var target = parents[worseParent];
161
162      int evaluatedSolution;
163      return Apply(random, source, evaluations[betterParent],
164        target, evaluations[worseParent], problemInstance,
165        CandidateSizeFactorParameter.Value.Value, out evaluatedSolution,
166        GreedyParameter.ActualValue.Value).Assignment;
167    }
168
169    /// <summary>
170    /// Relocates equipments in the same location as <paramref name="equipment"/> to other locations in case the location
171    /// is overutilized.
172    /// </summary>
173    /// <remarks>
174    /// This method is performance critical, called very often and should run as fast as possible.
175    /// </remarks>
176    /// <param name="random">The random number generator.</param>
177    /// <param name="pi">The current solution.</param>
178    /// <param name="equipment">The equipment that was just assigned to a new location.</param>
179    /// <param name="nonFix">The equipments that have not yet been fixed.</param>
180    /// <param name="demands">The demands for all equipments.</param>
181    /// <param name="capacities">The capacities of all locations.</param>
182    /// <param name="maximumTries">The number of tries that should be done in relocating the equipments.</param>
183    /// <returns>A feasible or infeasible solution</returns>
184    private static IntegerVector MakeFeasible(IRandom random, IntegerVector pi, int equipment, List<int> nonFix, DoubleArray demands, DoubleArray capacities, int maximumTries = 1000) {
185      int l = pi[equipment];
186      var slack = ComputeSlack(pi, demands, capacities);
187      if (slack[l] >= 0) // line 1 of Algorithm 5
188        return (IntegerVector)pi.Clone(); // line 2 of Algorithm 5
189
190      IntegerVector pi_prime = null;
191      int k = 0; // line 4 of Algorithm 5
192      var maxSlack = slack.Max(); // line 8-9 of Algorithm 5
193      var slack_prime = (double[])slack.Clone();
194      var maxSlack_prime = maxSlack;
195      // note that FTL can be computed only once for all tries as all tries restart with the same solution
196      var FTL = nonFix.Where(x => x != equipment && pi[x] == l && demands[x] <= maxSlack).ToList(); // line 8-9 of Algorithm 5
197      var FTLweight = FTL.Select(x => demands[x]).ToList();
198      while (k < maximumTries && slack_prime[l] < 0) {  // line 5 of Algorithm 5
199        pi_prime = (IntegerVector)pi.Clone(); // line 6 of Algorithm 5
200        // set T can only shrink and not grow, thus it is created outside the loop and only updated inside
201        var T = new List<int>(FTL); // line 8-9 of Algorithm 5
202        var weightT = new List<double>(FTLweight);
203        do {  // line 7 of Algorithm 5
204          if (T.Count > 0) { // line 10 of Algorithm 5
205            var idx = Enumerable.Range(0, T.Count).SampleProportional(random, 1, weightT, false, false).First(); // line 11 of Algorithm 5
206            int i = T[idx]; // line 11 of Algorithm 5
207            var j = Enumerable.Range(0, capacities.Length)
208              .Where(x => slack_prime[x] >= demands[i]) // line 12 of Algorithm 5
209              .SampleRandom(random);  // line 13 of Algorithm 5
210            pi_prime[i] = j; // line 14 of Algorithm 5
211            T.RemoveAt(idx);
212            weightT.RemoveAt(idx);
213            var recomputeMaxSlack = slack_prime[j] == maxSlack_prime; // efficiency improvement: recompute max slack only if we assign to a location whose slack equals maxSlack
214            slack_prime[j] -= demands[i]; // line 14 of Algorithm 5
215            slack_prime[l] += demands[i]; // line 14 of Algorithm 5
216            if (recomputeMaxSlack) {
217              maxSlack_prime = slack_prime.Max();
218              // T needs to be removed of equipments whose demand is higher than maxSlack only if maxSlack changes
219              for (var h = 0; h < T.Count; h++) {
220                var f = T[h];
221                if (demands[f] > maxSlack_prime) {
222                  T.RemoveAt(h);
223                  weightT.RemoveAt(h);
224                  h--;
225                }
226              }
227            }
228          } else break; // cond. 1 in line 16 of Algorithm 5
229        } while (slack_prime[l] < 0); // cond. 2 in line 16 of Algorithm 5
230        k++; // line 17 of Algorithm 5
231        if (slack_prime[l] < 0) {
232          // reset
233          Array.Copy(slack, slack_prime, slack.Length);
234          maxSlack_prime = maxSlack;
235        }
236      }
237      return pi_prime; // line 19-23 of Algorithm 5
238    }
239
240    private static double[] ComputeSlack(IntegerVector assignment, DoubleArray demands, DoubleArray capacities) {
241      var slack = capacities.ToArray();
242      for (int i = 0; i < assignment.Length; i++) {
243        slack[assignment[i]] -= demands[i];
244      }
245      return slack;
246    }
247  }
248}
Note: See TracBrowser for help on using the repository browser.