Changeset 15555 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/SolutionCreators/GreedyRandomizedSolutionCreator.cs
 Timestamp:
 12/20/17 23:35:23 (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/SolutionCreators/GreedyRandomizedSolutionCreator.cs
r15553 r15555 33 33 34 34 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment { 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/s1073201091440 37 /// </summary> 35 38 [Item("GreedyRandomizedSolutionCreator", "Creates a solution according to the procedure described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with pathrelinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527565.")] 36 39 [StorableClass] … … 60 63 public static IntegerVector CreateSolution(IRandom random, GQAPInstance problemInstance, 61 64 int maximumTries, bool createMostFeasibleSolution, CancellationToken cancelToken) { 65 var weights = problemInstance.Weights; 66 var distances = problemInstance.Distances; 62 67 var demands = problemInstance.Demands; 63 68 var capacities = problemInstance.Capacities.ToArray(); 69 var transportCosts = problemInstance.TransportationCosts; 64 70 var equipments = demands.Length; 65 71 var locations = capacities.Length; … … 69 75 double minViolation = double.MaxValue; 70 76 int[] bestAssignment = null; 71 var CF = new bool[equipments]; // set of chosen facilities / equipments 72 var T = new List<int>(equipments); // set of facilities / equpiments that can be assigned to the set of chosen locations (CL) 77 var F = new List<int>(equipments); // set of (initially) all facilities / equipments 78 var CF = new List<int>(equipments); // set of chosen facilities / equipments 79 var L = new List<int>(locations); // set of (initially) all locations 73 80 var CL_list = new List<int>(locations); // list of chosen locations 74 81 var CL_selected = new bool[locations]; // bool decision if location is chosen 75 var F = new List<int>(equipments); // set of (initially) all facilities / equipments 76 var L = new List<int>(locations); // set of (initially) all locations 77 82 var T = new List<int>(equipments); // set of facilities / equpiments that can be assigned to the set of chosen locations (CL) 83 var H = new double[locations]; // proportions for choosing locations in stage 1 84 var W = new double[equipments]; // proportions for choosing facilities in stage 2 85 var Z = new double[locations]; // proportions for choosing locations in stage 2 86 78 87 while (maximumTries <= 0  tries < maximumTries) { 79 88 cancelToken.ThrowIfCancellationRequested(); 80 89 81 Array.Copy(capacities, slack, locations); 82 Array.Clear(CF, 0, equipments); 83 Array.Clear(CL_selected, 0, locations); 84 CL_list.Clear(); 85 T.Clear(); 86 87 F.Clear(); F.AddRange(Enumerable.Range(0, equipments)); 88 L.Clear(); L.AddRange(Enumerable.Range(0, locations)); 89 90 double threshold = 1.0; 91 do { 92 if (L.Count > 0 && random.NextDouble() < threshold) { 93 int l = L.SampleRandom(random); 94 L.Remove(l); 95 CL_list.Add(l); 96 CL_selected[l] = true; 97 T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands)); 98 } 99 if (T.Count > 0) { 100 var fidx = Enumerable.Range(0, T.Count).SampleRandom(random); 101 var f = T[fidx]; 102 T.RemoveAt(fidx); 103 F.Remove(f); // TODO: slow 104 CF[f] = true; 105 int l = WhereSlackGreaterOrEqual(CL_list, demands[f], slack).SampleRandom(random); 106 assignment[f] = l + 1; 90 Array.Copy(capacities, slack, locations); // line 2 of Algorihm 2 91 CF.Clear(); // line 2 of Algorihm 2 92 Array.Clear(CL_selected, 0, locations); // line 2 of Algorihm 2 93 CL_list.Clear(); // line 2 of Algorihm 2 94 T.Clear(); // line 2 of Algorihm 2 95 96 F.Clear(); F.AddRange(Enumerable.Range(0, equipments)); // line 2 of Algorihm 2 97 L.Clear(); L.AddRange(Enumerable.Range(0, locations)); // line 2 of Algorihm 2 98 99 double threshold = 1.0; // line 3 of Algorithm 2 100 do { // line 4 of Algorithm 2 101 if (L.Count > 0 && random.NextDouble() < threshold) { // line 5 of Algorithm 2 102 // H is the proportion that a location is chosen 103 // The paper doesn't mention what happens if the candidate list CL 104 // does not contain an element in which case according to the formula 105 // all H_k elements would be 0 which would be equal to random selection 106 var HH = H.Select((v, i) => new { Index = i, Value = v }) 107 .Where(x => !CL_selected[x.Index]) 108 .Select(x => x.Value); 109 int l = L.SampleProportional(random, 1, HH, false, false).Single(); // line 6 of Algorithm 2 110 L.Remove(l); // line 7 of Algorithm 2 111 CL_list.Add(l); // line 7 of Algorithm 2 112 CL_selected[l] = true; // line 7 of Algorithm 2 113 for (var k = 0; k < locations; k++) 114 if (!CL_selected[k]) 115 H[k] += capacities[k] * capacities[l] / distances[k, l]; 116 T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands)); // line 8 of Algorithm 2 117 } 118 if (T.Count > 0) { // line 10 of Algorithm 2 119 // W is the proportion that an equipment is chosen 120 Array.Clear(W, 0, W.Length); 121 var wk = 0; 122 foreach (var k in T) { 123 for (var h = 0; h < equipments; h++) { 124 if (k == h) continue; 125 W[wk] += weights[k, h]; 126 } 127 W[wk] *= demands[k]; 128 wk++; 129 } 130 var f = T.SampleProportional(random, 1, W.Take(T.Count), false, false) // line 11 of Algorithm 2 131 .Single(); 132 T.Remove(f); // line 12 of Algorithm 2 133 F.Remove(f); // line 12 of Algorithm 2 134 CF.Add(f); // line 12 of Algorithm 2 135 var R = WhereSlackGreaterOrEqual(CL_list, demands[f], slack).ToList(); // line 13 of Algorithm 2 136 // Z is the proportion that a location is chosen in stage 2 137 Array.Clear(Z, 0, Z.Length); 138 var zk = 0; 139 foreach (var k in R) { 140 // d is an increase in fitness if f would be assigned to location k 141 var d = problemInstance.InstallationCosts[f, k]; 142 foreach (var i in CF) { 143 if (assignment[i] == 0) continue; // i is unassigned 144 var j = assignment[i]  1; 145 d += transportCosts * weights[f, i] * distances[k, j]; 146 } 147 foreach (var h in CL_list) { 148 if (k == h) continue; 149 Z[zk] += slack[k] * capacities[h] / (d * distances[k, h]); 150 } 151 zk++; 152 } 153 int l = R.SampleProportional(random, 1, Z.Take(R.Count), false, false).Single(); // line 14 of Algorithm 2 154 assignment[f] = l + 1; // line 15 of Algorithm 2 107 155 slack[l] = demands[f]; 108 T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands)); 109 threshold = 1.0  (double)T.Count / Math.Max(F.Count, 1.0); 110 } 111 } while (T.Count > 0  L.Count > 0); 156 T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands)); // line 16 of Algorithm 2 157 threshold = 1.0  (double)T.Count / Math.Max(F.Count, 1.0); // line 17 of Algorithm 2 158 } 159 } while (T.Count > 0  L.Count > 0); // line 19 of Algorithm 2 160 112 161 if (maximumTries > 0) tries++; 162 113 163 if (F.Count == 0) { 114 bestAssignment = assignment ;164 bestAssignment = assignment.Select(x => x  1).ToArray(); 115 165 break; 116 166 } else if (createMostFeasibleSolution) { … … 130 180 double violation = slack.Select(x => x < 0 ? x : 0).Sum(); 131 181 if (violation < minViolation) { 132 bestAssignment = assignment; 133 assignment = new int[equipments]; 182 bestAssignment = assignment.Select(x => x  1).ToArray(); 134 183 minViolation = violation; 135 184 } 185 assignment = new int[equipments]; 136 186 } 137 187 } 138 188 139 if (bestAssignment == null  bestAssignment.Any(x => x == 0))189 if (bestAssignment == null) 140 190 throw new InvalidOperationException(String.Format("No solution could be found in {0} tries.", maximumTries)); 141 191 142 return new IntegerVector(bestAssignment .Select(x => x  1).ToArray());192 return new IntegerVector(bestAssignment); 143 193 } 144 194
Note: See TracChangeset
for help on using the changeset viewer.