#region License Information /* HeuristicLab * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Collections.Generic; using System.Linq; using System.Threading; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.IntegerVectorEncoding; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Random; using HEAL.Attic; namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment { /// /// 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 /// [Item("GreedyRandomizedSolutionCreator", "Creates a solution according to the procedure 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.")] [StorableType("44919EFC-AF47-4F0D-8EE4-F5AECBF776CA")] public class GreedyRandomizedSolutionCreator : GQAPStochasticSolutionCreator { public IValueLookupParameter MaximumTriesParameter { get { return (IValueLookupParameter)Parameters["MaximumTries"]; } } public IValueLookupParameter CreateMostFeasibleSolutionParameter { get { return (IValueLookupParameter)Parameters["CreateMostFeasibleSolution"]; } } [StorableConstructor] protected GreedyRandomizedSolutionCreator(StorableConstructorFlag _) : base(_) { } protected GreedyRandomizedSolutionCreator(GreedyRandomizedSolutionCreator original, Cloner cloner) : base(original, cloner) { } public GreedyRandomizedSolutionCreator() : base() { Parameters.Add(new ValueLookupParameter("MaximumTries", "The maximum number of tries to create a feasible solution after which an exception is thrown. If it is set to 0 or a negative value there will be an infinite number of attempts.", new IntValue(100000))); Parameters.Add(new ValueLookupParameter("CreateMostFeasibleSolution", "If this is set to true the operator will always succeed, and outputs the solution with the least violation instead of throwing an exception.", new BoolValue(false))); } public override IDeepCloneable Clone(Cloner cloner) { return new GreedyRandomizedSolutionCreator(this, cloner); } public static IntegerVector CreateSolution(IRandom random, GQAPInstance problemInstance, int maximumTries, bool createMostFeasibleSolution, CancellationToken cancelToken) { var weights = problemInstance.Weights; var distances = problemInstance.Distances; var installCosts = problemInstance.InstallationCosts; var demands = problemInstance.Demands; var capacities = problemInstance.Capacities.ToArray(); var transportCosts = problemInstance.TransportationCosts; var equipments = demands.Length; var locations = capacities.Length; int tries = 0; var slack = new double[locations]; double minViolation = double.MaxValue; int[] assignment = null; int[] bestAssignment = null; var F = new List(equipments); // set of (initially) all facilities / equipments var CF = new List(equipments); // set of chosen facilities / equipments var L = new List(locations); // set of (initially) all locations var CL_list = new List(locations); // list of chosen locations var CL_selected = new bool[locations]; // bool decision if location is chosen var T = new List(equipments); // set of facilities / equpiments that can be assigned to the set of chosen locations (CL) var H = new double[locations]; // proportions for choosing locations in stage 1 var W = new double[equipments]; // proportions for choosing facilities in stage 2 var Z = new double[locations]; // proportions for choosing locations in stage 2 for (var k = 0; k < equipments; k++) { for (var h = 0; h < equipments; h++) { if (k == h) continue; W[k] += weights[k, h]; } W[k] *= demands[k]; } while (maximumTries <= 0 || tries < maximumTries) { cancelToken.ThrowIfCancellationRequested(); assignment = new int[equipments]; Array.Copy(capacities, slack, locations); // line 2 of Algorihm 2 CF.Clear(); // line 2 of Algorihm 2 Array.Clear(CL_selected, 0, locations); // line 2 of Algorihm 2 CL_list.Clear(); // line 2 of Algorihm 2 T.Clear(); // line 2 of Algorihm 2 F.Clear(); F.AddRange(Enumerable.Range(0, equipments)); // line 2 of Algorihm 2 L.Clear(); L.AddRange(Enumerable.Range(0, locations)); // line 2 of Algorihm 2 Array.Clear(H, 0, H.Length); double threshold = 1.0; // line 3 of Algorithm 2 do { // line 4 of Algorithm 2 if (L.Count > 0 && random.NextDouble() < threshold) { // line 5 of Algorithm 2 // H is the proportion that a location is chosen // The paper doesn't mention what happens if the candidate list CL // does not contain an element in which case according to the formula // all H_k elements would be 0 which would be equal to random selection var HH = L.Select(x => H[x]); int l = L.SampleProportional(random, 1, HH, false, false).Single(); // line 6 of Algorithm 2 L.Remove(l); // line 7 of Algorithm 2 CL_list.Add(l); // line 7 of Algorithm 2 CL_selected[l] = true; // line 7 of Algorithm 2 // incrementally updating location weights foreach (var k in L) H[k] += capacities[k] * capacities[l] / distances[k, l]; T = new List(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands)); // line 8 of Algorithm 2 } if (T.Count > 0) { // line 10 of Algorithm 2 // W is the proportion that an equipment is chosen var WW = T.Select(x => W[x]); var f = T.SampleProportional(random, 1, WW, false, false) // line 11 of Algorithm 2 .Single(); T.Remove(f); // line 12 of Algorithm 2 F.Remove(f); // line 12 of Algorithm 2 CF.Add(f); // line 12 of Algorithm 2 var R = WhereSlackGreaterOrEqual(CL_list, demands[f], slack).ToList(); // line 13 of Algorithm 2 // Z is the proportion that a location is chosen in stage 2 var l = R[0]; if (R.Count > 1) { // optimization, calculate probabilistic weights only in case |R| > 1 Array.Clear(Z, 0, R.Count); var zk = 0; foreach (var k in R) { // d is an increase in fitness if f would be assigned to location k var d = installCosts[f, k]; foreach (var i in CF) { if (assignment[i] == 0) continue; // i is unassigned var j = assignment[i] - 1; d += transportCosts * weights[f, i] * distances[k, j]; } foreach (var h in CL_list) { if (k == h) continue; Z[zk] += slack[k] * capacities[h] / (d * distances[k, h]); } zk++; } l = R.SampleProportional(random, 1, Z.Take(R.Count), false, false).Single(); // line 14 of Algorithm 2 } assignment[f] = l + 1; // line 15 of Algorithm 2 slack[l] -= demands[f]; T = new List(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands)); // line 16 of Algorithm 2 threshold = 1.0 - (double)T.Count / Math.Max(F.Count, 1.0); // line 17 of Algorithm 2 } } while (T.Count > 0 || L.Count > 0); // line 19 of Algorithm 2 if (maximumTries > 0) tries++; if (F.Count == 0) { bestAssignment = assignment.Select(x => x - 1).ToArray(); break; } else if (createMostFeasibleSolution) { // complete the solution and remember the one with least violation foreach (var l in L.ToArray()) { CL_list.Add(l); CL_selected[l] = true; L.Remove(l); } while (F.Count > 0) { var f = F.Select((v, i) => new { Index = i, Value = v }).MaxItems(x => demands[x.Value]).SampleRandom(random); var l = CL_list.MaxItems(x => slack[x]).SampleRandom(random); F.RemoveAt(f.Index); assignment[f.Value] = l + 1; slack[l] -= demands[f.Value]; } double violation = slack.Select(x => x < 0 ? -x : 0).Sum(); if (violation < minViolation) { bestAssignment = assignment.Select(x => x - 1).ToArray(); minViolation = violation; } } } if (bestAssignment == null) throw new InvalidOperationException(String.Format("No solution could be found in {0} tries.", maximumTries)); return new IntegerVector(bestAssignment); } protected override IntegerVector CreateRandomSolution(IRandom random, GQAPInstance problemInstance) { return CreateSolution(random, problemInstance, MaximumTriesParameter.ActualValue.Value, CreateMostFeasibleSolutionParameter.ActualValue.Value, CancellationToken); } private static IEnumerable WhereDemandEqualOrLess(IEnumerable facilities, double maximum, DoubleArray demands) { foreach (int f in facilities) { if (demands[f] <= maximum) yield return f; } } private static double GetMaximumSlack(double[] slack, bool[] CL) { var max = double.MinValue; for (var i = 0; i < slack.Length; i++) { if (CL[i] && max < slack[i]) max = slack[i]; } return max; } private static IEnumerable WhereSlackGreaterOrEqual(IEnumerable locations, double minimum, double[] slack) { foreach (int l in locations) { if (slack[l] >= minimum) yield return l; } } } }