Changeset 15558 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/GQAPPathRelinking.cs

Timestamp:

12/22/17 01:32:13 (6 years ago)

Author:

abeham

Message:

#1614: fixed bugs

File:

• branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/GQAPPathRelinking.cs (modified) (10 diffs)

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

@@ -45 +45 @@
       get { return (IScopeTreeLookupParameter<Evaluation>)Parameters["Evaluation"]; }
     }
-
     public IValueParameter<PercentValue> CandidateSizeFactorParameter {
       get { return (IValueParameter<PercentValue>)Parameters["CandidateSizeFactor"]; }
+    }
+    public IValueLookupParameter<BoolValue> GreedyParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["Greedy"]; }
     }
 
@@ -58 +60 @@
       Parameters.Add(new ScopeTreeLookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription));
       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)));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("Greedy", "Whether to use a greedy selection strategy or a probabilistic one.", new BoolValue(true)));
     }
 
@@ -68 +71 @@
       IntegerVector target, Evaluation targetEval,
       GQAPInstance problemInstance, double candidateSizeFactor,
-      out int evaluatedSolutions) {
+      out int evaluatedSolutions, bool greedy = true) {
       evaluatedSolutions = 0;
       var demands = problemInstance.Demands;
       var capacities = problemInstance.Capacities;
       var cmp = new IntegerVectorEqualityComparer();
-
-      var greedy = true; // greedy performed better according to the paper
+      
       var sFit = problemInstance.ToSingleObjective(sourceEval);
       var tFit = problemInstance.ToSingleObjective(targetEval);
@@ -83 +85 @@
       //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
       var nonFix = Enumerable.Range(0, demands.Length).ToList(); // line 3 of Algorithm 4
-      var phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)); // line 4 of Algorithm 4
-
+      var phi = new List<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)); // line 4 of Algorithm 4
+
+      var B = new List<GQAPSolution>((int)Math.Ceiling(phi.Count * candidateSizeFactor));
+      var B_fit = new List<double>(B.Capacity);
       while (phi.Count > 0) { // line 5 of Algorithm 4
-        var B = new List<GQAPSolution>((int)Math.Ceiling(phi.Count * candidateSizeFactor)); // line 6 of Algorithm 4
-        var B_fit = new List<double>(B.Capacity); // line 6 of Algorithm 4 (B is split into two synchronized lists)
+        B.Clear(); // line 6 of Algorithm 4
+        B_fit.Clear(); // line 6 of Algorithm 4 (B is split into two synchronized lists)
         foreach (var v in phi) { // line 7 of Algorithm 4
           int oldLocation = pi_prime[v];
@@ -93 +97 @@
           var pi_dash = MakeFeasible(random, pi_prime, v, nonFix, demands, capacities); // line 9 of Algorithm 4
           pi_prime[v] = oldLocation; // not mentioned in Algorithm 4, but seems reasonable
-          var pi_dash_eval = problemInstance.Evaluate(pi_dash);
-          evaluatedSolutions++;
-          var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);
 
           if (problemInstance.IsFeasible(pi_dash)) { // line 10 of Algorithm 4
+            var pi_dash_eval = problemInstance.Evaluate(pi_dash);
+            evaluatedSolutions++;
+            var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);
+
             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
 
@@ -103 +108 @@
               var replacement = B_fit.Select((val, idx) => new { Index = idx, Fitness = val })
                                             .Where(x => x.Fitness >= pi_dash_fit) // cond. 1 in line 12 of Algorithm 4
-                                            .Select(x => new { Index = x.Index, Fitness = x.Fitness, Similarity = HammingSimilarityCalculator.CalculateSimilarity(B[x.Index].Assignment, pi_dash) })
+                                            .Select(x => new { x.Index, x.Fitness, Similarity = HammingSimilarityCalculator.CalculateSimilarity(B[x.Index].Assignment, pi_dash) })
                                             .ToArray();
               if (replacement.Length > 0) {
-                var mostSimilar = replacement.MaxItems(x => x.Similarity).First().Index;
+                var mostSimilar = replacement.MaxItems(x => x.Similarity).SampleRandom(random).Index;
                 B[mostSimilar].Assignment = pi_dash; // line 13 of Algorithm 4
                 B[mostSimilar].Evaluation = pi_dash_eval; // line 13 of Algorithm 4
@@ -121 +126 @@
           // line 22 of Algorithm 4
           if (greedy) {
-            pi = B.Select((val, idx) => new { Index = idx, Value = val }).MinItems(x => B_fit[x.Index]).Shuffle(random).First().Value;
+            pi = B.Select((val, idx) => new { Index = idx, Value = val }).MinItems(x => B_fit[x.Index]).SampleRandom(random).Value;
           } else {
             pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First();
@@ -137 +142 @@
           }
         } else return pi_star;
-        phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
+        phi = new List<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
       }
 
@@ -156 +161 @@
       return Apply(random, source, evaluations[betterParent],
         target, evaluations[worseParent], problemInstance,
-        CandidateSizeFactorParameter.Value.Value, out evaluatedSolution).Assignment;
-    }
-
+        CandidateSizeFactorParameter.Value.Value, out evaluatedSolution,
+        GreedyParameter.ActualValue.Value).Assignment;
+    }
+
+    /// <summary>
+    /// Relocates equipments in the same location as <paramref name="equipment"/> to other locations in case the location
+    /// is overutilized.
+    /// </summary>
+    /// <remarks>
+    /// This method is performance critical, called very often and should run as fast as possible.
+    /// </remarks>
+    /// <param name="random">The random number generator.</param>
+    /// <param name="pi">The current solution.</param>
+    /// <param name="equipment">The equipment that was just assigned to a new location.</param>
+    /// <param name="nonFix">The equipments that have not yet been fixed.</param>
+    /// <param name="demands">The demands for all equipments.</param>
+    /// <param name="capacities">The capacities of all locations.</param>
+    /// <param name="maximumTries">The number of tries that should be done in relocating the equipments.</param>
+    /// <returns>A feasible or infeasible solution</returns>
     private static IntegerVector MakeFeasible(IRandom random, IntegerVector pi, int equipment, List<int> nonFix, DoubleArray demands, DoubleArray capacities, int maximumTries = 1000) {
       int l = pi[equipment];
       var slack = ComputeSlack(pi, demands, capacities);
       if (slack[l] >= 0) // line 1 of Algorithm 5
-        return new IntegerVector(pi); // line 2 of Algorithm 5
+        return (IntegerVector)pi.Clone(); // line 2 of Algorithm 5
 
       IntegerVector pi_prime = null;
       int k = 0; // line 4 of Algorithm 5
-      while (k < maximumTries && slack[l] < 0) {  // line 5 of Algorithm 5
-        pi_prime = new IntegerVector(pi); // line 6 of Algorithm 5
+      var maxSlack = slack.Max(); // line 8-9 of Algorithm 5
+      var slack_prime = (double[])slack.Clone();
+      var maxSlack_prime = maxSlack;
+      // note that FTL can be computed only once for all tries as all tries restart with the same solution
+      var FTL = nonFix.Where(x => x != equipment && pi[x] == l && demands[x] <= maxSlack).ToList(); // line 8-9 of Algorithm 5
+      var FTLweight = FTL.Select(x => demands[x]).ToList();
+      while (k < maximumTries && slack_prime[l] < 0) {  // line 5 of Algorithm 5
+        pi_prime = (IntegerVector)pi.Clone(); // line 6 of Algorithm 5
+        // set T can only shrink and not grow, thus it is created outside the loop and only updated inside
+        var T = new List<int>(FTL); // line 8-9 of Algorithm 5
+        var weightT = new List<double>(FTLweight);
         do {  // line 7 of Algorithm 5
-          var maxSlack = slack.Max(); // line 8-9 of Algorithm 5
-          var T = nonFix.Where(x => pi[x] == l && demands[x] <= maxSlack).ToList(); // line 8-9 of Algorithm 5
           if (T.Count > 0) { // line 10 of Algorithm 5
-            int i = T.SampleProportional(random, 1, T.Select(x => demands[x]), false).First(); // line 11 of Algorithm 5
+            var idx = Enumerable.Range(0, T.Count).SampleProportional(random, 1, weightT, false, false).First(); // line 11 of Algorithm 5
+            int i = T[idx]; // line 11 of Algorithm 5
             var j = Enumerable.Range(0, capacities.Length)
-              .Where(x => slack[x] >= demands[i]) // line 12 of Algorithm 5
+              .Where(x => slack_prime[x] >= demands[i]) // line 12 of Algorithm 5
               .SampleRandom(random);  // line 13 of Algorithm 5
             pi_prime[i] = j; // line 14 of Algorithm 5
-            slack[j] -= demands[i]; // line 14 of Algorithm 5
-            slack[l] += demands[i]; // line 14 of Algorithm 5
+            T.RemoveAt(idx);
+            weightT.RemoveAt(idx);
+            var recomputeMaxSlack = slack_prime[j] == maxSlack_prime; // efficiency improvement: recompute max slack only if we assign to a location whose slack equals maxSlack
+            slack_prime[j] -= demands[i]; // line 14 of Algorithm 5
+            slack_prime[l] += demands[i]; // line 14 of Algorithm 5
+            if (recomputeMaxSlack) {
+              maxSlack_prime = slack_prime.Max();
+              // T needs to be removed of equipments whose demand is higher than maxSlack only if maxSlack changes
+              for (var h = 0; h < T.Count; h++) {
+                var f = T[h];
+                if (demands[f] > maxSlack_prime) {
+                  T.RemoveAt(h);
+                  weightT.RemoveAt(h);
+                  h--;
+                }
+              }
+            }
           } else break; // cond. 1 in line 16 of Algorithm 5
-        } while (slack[l] < 0); // cond. 2 in line 16 of Algorithm 5
+        } while (slack_prime[l] < 0); // cond. 2 in line 16 of Algorithm 5
         k++; // line 17 of Algorithm 5
+        if (slack_prime[l] < 0) {
+          // reset
+          Array.Copy(slack, slack_prime, slack.Length);
+          maxSlack_prime = maxSlack;
+        }
       }
       return pi_prime; // line 19-23 of Algorithm 5
@@ -188 +237 @@
 
     private static double[] ComputeSlack(IntegerVector assignment, DoubleArray demands, DoubleArray capacities) {
-      var slack = new double[capacities.Length];
+      var slack = capacities.ToArray();
       for (int i = 0; i < assignment.Length; i++) {
         slack[assignment[i]] -= demands[i];