Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/22/17 01:32:13 (7 years ago)
Author:
abeham
Message:

#1614: fixed bugs

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/SolutionCreators/GreedyRandomizedSolutionCreator.cs

    r15555 r15558  
    6565      var weights = problemInstance.Weights;
    6666      var distances = problemInstance.Distances;
     67      var installCosts = problemInstance.InstallationCosts;
    6768      var demands = problemInstance.Demands;
    6869      var capacities = problemInstance.Capacities.ToArray();
    … …  
    7172      var locations = capacities.Length;
    7273      int tries = 0;
    73       var assignment = new int[equipments];
    7474      var slack = new double[locations];
    7575      double minViolation = double.MaxValue;
     76      int[] assignment = null;
    7677      int[] bestAssignment = null;
    7778      var F = new List<int>(equipments); // set of (initially) all facilities / equipments
    … …  
    8485      var W = new double[equipments]; // proportions for choosing facilities in stage 2
    8586      var Z = new double[locations]; // proportions for choosing locations in stage 2
     87     
     88      for (var k = 0; k < equipments; k++) {
     89        for (var h = 0; h < equipments; h++) {
     90          if (k == h) continue;
     91          W[k] += weights[k, h];
     92        }
     93        W[k] *= demands[k];
     94      }
    8695
    8796      while (maximumTries <= 0 || tries < maximumTries) {
    8897        cancelToken.ThrowIfCancellationRequested();
     98
     99        assignment = new int[equipments];
    89100
    90101        Array.Copy(capacities, slack, locations); // line 2 of Algorihm 2
    … …  
    96107        F.Clear(); F.AddRange(Enumerable.Range(0, equipments)); // line 2 of Algorihm 2
    97108        L.Clear(); L.AddRange(Enumerable.Range(0, locations)); // line 2 of Algorihm 2
     109
     110        Array.Clear(H, 0, H.Length);
    98111
    99112        double threshold = 1.0; // line 3 of Algorithm 2
    … …  
    104117            // does not contain an element in which case according to the formula
    105118            // 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);
     119            var HH = L.Select(x => H[x]);
    109120            int l = L.SampleProportional(random, 1, HH, false, false).Single(); // line 6 of Algorithm 2
    110121            L.Remove(l); // line 7 of Algorithm 2
    111122            CL_list.Add(l); // line 7 of Algorithm 2
    112123            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];
     124            // incrementally updating location weights
     125            foreach (var k in L)
     126              H[k] += capacities[k] * capacities[l] / distances[k, l];
     127
    116128            T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands)); // line 8 of Algorithm 2
    117129          }
    118130          if (T.Count > 0) { // line 10 of Algorithm 2
    119131            // 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
     132            var WW = T.Select(x => W[x]);
     133            var f = T.SampleProportional(random, 1, WW, false, false) // line 11 of Algorithm 2
    131134              .Single();
    132135            T.Remove(f); // line 12 of Algorithm 2
    … …  
    135138            var R = WhereSlackGreaterOrEqual(CL_list, demands[f], slack).ToList(); // line 13 of Algorithm 2
    136139            // 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];
     140            var l = R[0];
     141            if (R.Count > 1) { // optimization, calculate probabilistic weights only in case |R| > 1
     142              Array.Clear(Z, 0, R.Count);
     143              var zk = 0;
     144              foreach (var k in R) {
     145                // d is an increase in fitness if f would be assigned to location k
     146                var d = installCosts[f, k];
     147                foreach (var i in CF) {
     148                  if (assignment[i] == 0) continue; // i is unassigned
     149                  var j = assignment[i] - 1;
     150                  d += transportCosts * weights[f, i] * distances[k, j];
     151                }
     152                foreach (var h in CL_list) {
     153                  if (k == h) continue;
     154                  Z[zk] += slack[k] * capacities[h] / (d * distances[k, h]);
     155                }
     156                zk++;
    146157              }
    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++;
     158              l = R.SampleProportional(random, 1, Z.Take(R.Count), false, false).Single(); // line 14 of Algorithm 2
    152159            }
    153             int l = R.SampleProportional(random, 1, Z.Take(R.Count), false, false).Single(); // line 14 of Algorithm 2
    154160            assignment[f] = l + 1; // line 15 of Algorithm 2
    155161            slack[l] -= demands[f];
    … …  
    183189            minViolation = violation;
    184190          }
    185           assignment = new int[equipments];
    186191        }
    187192      }
Note: See TracChangeset for help on using the changeset viewer.