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

Location:
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/GQAPPathRelinking.cs

    r15555 r15558  
    4545      get { return (IScopeTreeLookupParameter<Evaluation>)Parameters["Evaluation"]; }
    4646    }
    47 
    4847    public IValueParameter<PercentValue> CandidateSizeFactorParameter {
    4948      get { return (IValueParameter<PercentValue>)Parameters["CandidateSizeFactor"]; }
     49    }
     50    public IValueLookupParameter<BoolValue> GreedyParameter {
     51      get { return (IValueLookupParameter<BoolValue>)Parameters["Greedy"]; }
    5052    }
    5153
    … …  
    5860      Parameters.Add(new ScopeTreeLookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription));
    5961      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)));
    6063    }
    6164
    … …  
    6871      IntegerVector target, Evaluation targetEval,
    6972      GQAPInstance problemInstance, double candidateSizeFactor,
    70       out int evaluatedSolutions) {
     73      out int evaluatedSolutions, bool greedy = true) {
    7174      evaluatedSolutions = 0;
    7275      var demands = problemInstance.Demands;
    7376      var capacities = problemInstance.Capacities;
    7477      var cmp = new IntegerVectorEqualityComparer();
    75 
    76       var greedy = true; // greedy performed better according to the paper
     78     
    7779      var sFit = problemInstance.ToSingleObjective(sourceEval);
    7880      var tFit = problemInstance.ToSingleObjective(targetEval);
    … …  
    8385      //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
    8486      var nonFix = Enumerable.Range(0, demands.Length).ToList(); // line 3 of Algorithm 4
    85       var phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)); // line 4 of Algorithm 4
    86 
     87      var phi = new List<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)); // line 4 of Algorithm 4
     88
     89      var B = new List<GQAPSolution>((int)Math.Ceiling(phi.Count * candidateSizeFactor));
     90      var B_fit = new List<double>(B.Capacity);
    8791      while (phi.Count > 0) { // line 5 of Algorithm 4
    88         var B = new List<GQAPSolution>((int)Math.Ceiling(phi.Count * candidateSizeFactor)); // line 6 of Algorithm 4
    89         var B_fit = new List<double>(B.Capacity); // line 6 of Algorithm 4 (B is split into two synchronized lists)
     92        B.Clear(); // line 6 of Algorithm 4
     93        B_fit.Clear(); // line 6 of Algorithm 4 (B is split into two synchronized lists)
    9094        foreach (var v in phi) { // line 7 of Algorithm 4
    9195          int oldLocation = pi_prime[v];
    … …  
    9397          var pi_dash = MakeFeasible(random, pi_prime, v, nonFix, demands, capacities); // line 9 of Algorithm 4
    9498          pi_prime[v] = oldLocation; // not mentioned in Algorithm 4, but seems reasonable
    95           var pi_dash_eval = problemInstance.Evaluate(pi_dash);
    96           evaluatedSolutions++;
    97           var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);
    9899
    99100          if (problemInstance.IsFeasible(pi_dash)) { // line 10 of Algorithm 4
     101            var pi_dash_eval = problemInstance.Evaluate(pi_dash);
     102            evaluatedSolutions++;
     103            var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);
     104
    100105            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
    101106
    … …  
    103108              var replacement = B_fit.Select((val, idx) => new { Index = idx, Fitness = val })
    104109                                            .Where(x => x.Fitness >= pi_dash_fit) // cond. 1 in line 12 of Algorithm 4
    105                                             .Select(x => new { Index = x.Index, Fitness = x.Fitness, Similarity = HammingSimilarityCalculator.CalculateSimilarity(B[x.Index].Assignment, pi_dash) })
     110                                            .Select(x => new { x.Index, x.Fitness, Similarity = HammingSimilarityCalculator.CalculateSimilarity(B[x.Index].Assignment, pi_dash) })
    106111                                            .ToArray();
    107112              if (replacement.Length > 0) {
    108                 var mostSimilar = replacement.MaxItems(x => x.Similarity).First().Index;
     113                var mostSimilar = replacement.MaxItems(x => x.Similarity).SampleRandom(random).Index;
    109114                B[mostSimilar].Assignment = pi_dash; // line 13 of Algorithm 4
    110115                B[mostSimilar].Evaluation = pi_dash_eval; // line 13 of Algorithm 4
    … …  
    121126          // line 22 of Algorithm 4
    122127          if (greedy) {
    123             pi = B.Select((val, idx) => new { Index = idx, Value = val }).MinItems(x => B_fit[x.Index]).Shuffle(random).First().Value;
     128            pi = B.Select((val, idx) => new { Index = idx, Value = val }).MinItems(x => B_fit[x.Index]).SampleRandom(random).Value;
    124129          } else {
    125130            pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First();
    … …  
    137142          }
    138143        } else return pi_star;
    139         phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
     144        phi = new List<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
    140145      }
    141146
    … …  
    156161      return Apply(random, source, evaluations[betterParent],
    157162        target, evaluations[worseParent], problemInstance,
    158         CandidateSizeFactorParameter.Value.Value, out evaluatedSolution).Assignment;
    159     }
    160 
     163        CandidateSizeFactorParameter.Value.Value, out evaluatedSolution,
     164        GreedyParameter.ActualValue.Value).Assignment;
     165    }
     166
     167    /// <summary>
     168    /// Relocates equipments in the same location as <paramref name="equipment"/> to other locations in case the location
     169    /// is overutilized.
     170    /// </summary>
     171    /// <remarks>
     172    /// This method is performance critical, called very often and should run as fast as possible.
     173    /// </remarks>
     174    /// <param name="random">The random number generator.</param>
     175    /// <param name="pi">The current solution.</param>
     176    /// <param name="equipment">The equipment that was just assigned to a new location.</param>
     177    /// <param name="nonFix">The equipments that have not yet been fixed.</param>
     178    /// <param name="demands">The demands for all equipments.</param>
     179    /// <param name="capacities">The capacities of all locations.</param>
     180    /// <param name="maximumTries">The number of tries that should be done in relocating the equipments.</param>
     181    /// <returns>A feasible or infeasible solution</returns>
    161182    private static IntegerVector MakeFeasible(IRandom random, IntegerVector pi, int equipment, List<int> nonFix, DoubleArray demands, DoubleArray capacities, int maximumTries = 1000) {
    162183      int l = pi[equipment];
    163184      var slack = ComputeSlack(pi, demands, capacities);
    164185      if (slack[l] >= 0) // line 1 of Algorithm 5
    165         return new IntegerVector(pi); // line 2 of Algorithm 5
     186        return (IntegerVector)pi.Clone(); // line 2 of Algorithm 5
    166187
    167188      IntegerVector pi_prime = null;
    168189      int k = 0; // line 4 of Algorithm 5
    169       while (k < maximumTries && slack[l] < 0) {  // line 5 of Algorithm 5
    170         pi_prime = new IntegerVector(pi); // line 6 of Algorithm 5
     190      var maxSlack = slack.Max(); // line 8-9 of Algorithm 5
     191      var slack_prime = (double[])slack.Clone();
     192      var maxSlack_prime = maxSlack;
     193      // note that FTL can be computed only once for all tries as all tries restart with the same solution
     194      var FTL = nonFix.Where(x => x != equipment && pi[x] == l && demands[x] <= maxSlack).ToList(); // line 8-9 of Algorithm 5
     195      var FTLweight = FTL.Select(x => demands[x]).ToList();
     196      while (k < maximumTries && slack_prime[l] < 0) {  // line 5 of Algorithm 5
     197        pi_prime = (IntegerVector)pi.Clone(); // line 6 of Algorithm 5
     198        // set T can only shrink and not grow, thus it is created outside the loop and only updated inside
     199        var T = new List<int>(FTL); // line 8-9 of Algorithm 5
     200        var weightT = new List<double>(FTLweight);
    171201        do {  // line 7 of Algorithm 5
    172           var maxSlack = slack.Max(); // line 8-9 of Algorithm 5
    173           var T = nonFix.Where(x => pi[x] == l && demands[x] <= maxSlack).ToList(); // line 8-9 of Algorithm 5
    174202          if (T.Count > 0) { // line 10 of Algorithm 5
    175             int i = T.SampleProportional(random, 1, T.Select(x => demands[x]), false).First(); // line 11 of Algorithm 5
     203            var idx = Enumerable.Range(0, T.Count).SampleProportional(random, 1, weightT, false, false).First(); // line 11 of Algorithm 5
     204            int i = T[idx]; // line 11 of Algorithm 5
    176205            var j = Enumerable.Range(0, capacities.Length)
    177               .Where(x => slack[x] >= demands[i]) // line 12 of Algorithm 5
     206              .Where(x => slack_prime[x] >= demands[i]) // line 12 of Algorithm 5
    178207              .SampleRandom(random);  // line 13 of Algorithm 5
    179208            pi_prime[i] = j; // line 14 of Algorithm 5
    180             slack[j] -= demands[i]; // line 14 of Algorithm 5
    181             slack[l] += demands[i]; // line 14 of Algorithm 5
     209            T.RemoveAt(idx);
     210            weightT.RemoveAt(idx);
     211            var recomputeMaxSlack = slack_prime[j] == maxSlack_prime; // efficiency improvement: recompute max slack only if we assign to a location whose slack equals maxSlack
     212            slack_prime[j] -= demands[i]; // line 14 of Algorithm 5
     213            slack_prime[l] += demands[i]; // line 14 of Algorithm 5
     214            if (recomputeMaxSlack) {
     215              maxSlack_prime = slack_prime.Max();
     216              // T needs to be removed of equipments whose demand is higher than maxSlack only if maxSlack changes
     217              for (var h = 0; h < T.Count; h++) {
     218                var f = T[h];
     219                if (demands[f] > maxSlack_prime) {
     220                  T.RemoveAt(h);
     221                  weightT.RemoveAt(h);
     222                  h--;
     223                }
     224              }
     225            }
    182226          } else break; // cond. 1 in line 16 of Algorithm 5
    183         } while (slack[l] < 0); // cond. 2 in line 16 of Algorithm 5
     227        } while (slack_prime[l] < 0); // cond. 2 in line 16 of Algorithm 5
    184228        k++; // line 17 of Algorithm 5
     229        if (slack_prime[l] < 0) {
     230          // reset
     231          Array.Copy(slack, slack_prime, slack.Length);
     232          maxSlack_prime = maxSlack;
     233        }
    185234      }
    186235      return pi_prime; // line 19-23 of Algorithm 5
    … …  
    188237
    189238    private static double[] ComputeSlack(IntegerVector assignment, DoubleArray demands, DoubleArray capacities) {
    190       var slack = new double[capacities.Length];
     239      var slack = capacities.ToArray();
    191240      for (int i = 0; i < assignment.Length; i++) {
    192241        slack[assignment[i]] -= demands[i];

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs

    r15555 r15558  
    7676      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
    7777    }
     78    public IValueLookupParameter<BoolValue> GreedyParameter {
     79      get { return (IValueLookupParameter<BoolValue>)Parameters["Greedy"]; }
     80    }
    7881
    7982    [StorableConstructor]
    … …  
    9295      Parameters.Add(new ValueLookupParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
    9396      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The result collection that stores the results."));
     97      Parameters.Add(new ValueLookupParameter<BoolValue>("Greedy", "Whether to use a greedy selection strategy or a probabilistic one.", new BoolValue(true)));
    9498    }
    9599
    … …  
    100104    public static void Apply(IRandom random, GQAPSolution sol, int maxCLS,
    101105      double oneMoveProbability, int maximumIterations,
    102       GQAPInstance problemInstance, out int evaluatedSolutions) {
     106      GQAPInstance problemInstance, out int evaluatedSolutions, bool greedy = true) {
    103107      var fit = problemInstance.ToSingleObjective(sol.Evaluation);
    104108      var eval = sol.Evaluation;
    105109      Apply(random, sol.Assignment, ref fit, ref eval, maxCLS, oneMoveProbability, maximumIterations, problemInstance,
    106         out evaluatedSolutions);
     110        out evaluatedSolutions, greedy);
    107111      sol.Evaluation = eval;
    108112    }
    109113
    110       /// <summary>
    111       /// </summary>
    112       /// <param name="random">The random number generator to use.</param>
    113       /// <param name="assignment">The equipment-location assignment vector.</param>
    114       /// <param name="quality">The solution quality.</param>
    115       /// <param name="evaluation">The evaluation result of the solution.</param>
    116       /// <param name="maxCLS">The maximum number of candidates that should be found in each step.</param>
    117       /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
    118       /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
    119       /// <param name="problemInstance">The problem instance that contains the data.</param>
    120       /// <param name="evaluatedSolutions">The number of evaluated solutions.</param>
    121       public static void Apply(IRandom random, IntegerVector assignment,
     114    /// <summary>
     115    /// </summary>
     116    /// <param name="random">The random number generator to use.</param>
     117    /// <param name="assignment">The equipment-location assignment vector.</param>
     118    /// <param name="quality">The solution quality.</param>
     119    /// <param name="evaluation">The evaluation result of the solution.</param>
     120    /// <param name="maxCLS">The maximum number of candidates that should be found in each step.</param>
     121    /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
     122    /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
     123    /// <param name="problemInstance">The problem instance that contains the data.</param>
     124    /// <param name="evaluatedSolutions">The number of evaluated solutions.</param>
     125    /// <param name="greedy">Greedy selection performed better in 5 of 8 instances according to the paper</param>
     126    public static void Apply(IRandom random, IntegerVector assignment,
    122127      ref double quality, ref Evaluation evaluation, int maxCLS,
    123128      double oneMoveProbability, int maximumIterations,
    124       GQAPInstance problemInstance, out int evaluatedSolutions) {
     129      GQAPInstance problemInstance, out int evaluatedSolutions, bool greedy = true) {
    125130      evaluatedSolutions = 0;
    126131      var capacities = problemInstance.Capacities;
    … …  
    128133      var evaluations = 0.0;
    129134      var deltaEvaluationFactor = 1.0 / assignment.Length;
    130       var greedy = true; // greedy selection performed better in 5 of 8 instances according to the paper
    131135      while (true) { // line 1 of Algorithm 3
    132136        var count = 0; // line 2 of Algorithm 3
    … …  
    183187        MaximumIterationsParameter.ActualValue.Value,
    184188        ProblemInstanceParameter.ActualValue,
    185         out evaluatedSolutions);
     189        out evaluatedSolutions,
     190        GreedyParameter.ActualValue.Value);
    186191
    187192      EvaluationParameter.ActualValue = evaluation;

  • 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.