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