Changeset 15490 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers

Timestamp:

12/04/17 23:00:03 (7 years ago)

Author:

abeham

Message:

#1614:

• branched optimization
• adapted references
• renamed plugin

Location:

branches/GeneralizedQAP

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/CordeauCrossover.cs (modified) (8 diffs)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/GQAPPathRelinking.cs (modified) (6 diffs)

branches/GeneralizedQAP

@@ -2 +2 @@
 TestResults
 *.user
+.vs

@@ -2 +2 @@
 TestResults
 *.user
+.vs

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

@@ -21 +21 @@
 
 using System;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -27 +28 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
@@ -74 +76 @@
     public IValueLookupParameter<IGQAPEvaluator> EvaluatorParameter {
       get { return (IValueLookupParameter<IGQAPEvaluator>)Parameters["Evaluator"]; }
+    }
+    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
     }
 
@@ -96 +101 @@
       Parameters.Add(new ValueLookupParameter<DoubleValue>("ExpectedRandomQuality", GeneralizedQuadraticAssignmentProblem.ExpectedRandomQualityDescription));
       Parameters.Add(new ValueLookupParameter<IGQAPEvaluator>("Evaluator", "The evaluator used to evaluate solutions."));
+      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated solutions."));
     }
 
@@ -107 +113 @@
       DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
       DoubleArray demands, DoubleArray capacities,
-      double transportationCosts, double expectedRandomQuality, IGQAPEvaluator evaluator) {
-      var mediana = Inizialize(distances);
+      double transportationCosts, double expectedRandomQuality, IGQAPEvaluator evaluator, IntValue evaluatedSolutions) {
+      var medianDistances = Enumerable.Range(0, distances.Rows).Select(x => distances.GetRow(x).Median()).ToArray();
+
       int m = capacities.Length;
       int n = demands.Length;
-      int i, j, k, ik1, ik2;
-      int control;
-      bool nofound = false, onefound = false;
-      double fbest;
-      IntegerVector son = new IntegerVector(parent1.Length), result = null;
+      
+      bool onefound = false;
+      double fbest, fbestAttempt = maximization.Value ? double.MinValue : double.MaxValue;
+      IntegerVector bestAttempt = null;
+      IntegerVector result = null;
 
       fbest = quality1.Value;
@@ -126 +133 @@
       }
       var cap = new double[m];
-      for (i = 0; i < m; i++) {
-
-        for (j = 0; j < m; j++) cap[j] = 0;
-
-        for (k = 0; k < n; k++) {
-          son[k] = -1;
-          ik1 = parent1[k];
-          ik2 = parent2[k];
-          if (distances[i, ik1] < mediana[i]) {
-            son[k] = ik1;
-            cap[ik1] += demands[k];
-          } else if (distances[i, ik2] > mediana[i]) {
-            son[k] = ik2;
-            cap[ik2] += demands[k];
-          }
-        }
-        k = 0;
-        nofound = false;
-        while (k < n && !nofound) {
-          if (son[k] < 0) {
-            control = 0;
-            do {
-              j = random.Next(m);
-              control++;
-            }
-            while (cap[j] + demands[k] > capacities[j] && control < 3 * m);
-            if (cap[j] + demands[k] <= capacities[j]) {
-              son[k] = j;
-              cap[j] += demands[k];
-            } else {
-              nofound = true;
-            }
-          }
-          k++;
-        }
-        if (!nofound) {
-          double sonQual = evaluator.Evaluate(son, weights, distances, installationCosts, demands, capacities, transportationCosts, expectedRandomQuality);
-          if (sonQual < fbest) {
-            fbest = sonQual;
-            result = (IntegerVector)son.Clone();
+      for (var i = 0; i < m; i++) {
+        int unassigned;
+        Array.Clear(cap, 0, m);
+        var child = Merge(parent1, parent2, distances, demands, medianDistances, m, n, i, cap, out unassigned);
+        if (unassigned > 0)
+          TryRandomAssignment(random, demands, capacities, m, n, cap, child, ref unassigned);
+        if (unassigned == 0) {
+          var childFit = evaluator.Evaluate(child, weights, distances, installationCosts, demands, capacities, transportationCosts, expectedRandomQuality);
+          evaluatedSolutions.Value++;
+          if (maximization.Value && childFit >= fbest
+            || !maximization.Value && childFit <= fbest) {
+            fbest = childFit;
+            result = child;
             onefound = true;
           }
-        }/* else {
-          abortedmerge++;
-          printf("aborted merge %8d\n", abortedmerge);
-        } */
-      }
-      if (!onefound && !nofound) {
-        i = random.Next(m);
-        for (j = 0; j < m; j++) {
-          cap[j] = 0.0;
-        }
-        for (k = 0; k < n; k++) {
-          son[k] = -1;
-          ik1 = parent1[k];
-          ik2 = parent2[k];
-          if (distances[i, ik1] < mediana[i]) {
-            son[k] = ik1;
-            cap[ik1] += demands[k];
-          } else if (distances[i, ik2] > mediana[i]) {
-            son[k] = ik2;
-            cap[ik2] += demands[k];
+          if (!onefound && (maximization.Value && fbestAttempt < childFit || !maximization.Value && fbestAttempt > childFit)) {
+            bestAttempt = child;
+            fbestAttempt = childFit;
           }
         }
-        for (k = 0; k < n; k++) {
-          if (son[k] < 0) {
-            j = random.Next(m);
-            son[k] = j;
-            cap[j] += demands[k];
-          }
-        }
-        if (result == null) {
-          result = (IntegerVector)son.Clone();
+      }
+
+      if (!onefound) {
+        var i = random.Next(m);
+        int unassigned;
+        Array.Clear(cap, 0, m);
+        var child = Merge(parent1, parent2, distances, demands, medianDistances, m, n, i, cap, out unassigned);
+        RandomAssignment(random, demands, capacities, m, n, cap, child, ref unassigned);
+
+        var childFit = evaluator.Evaluate(child, weights, distances, installationCosts, demands, capacities, transportationCosts, expectedRandomQuality);
+        evaluatedSolutions.Value++;
+        if (childFit < fbest) {
+          fbest = childFit;
+          result = child;
           onefound = true;
-        } else {
-          double sonQual = evaluator.Evaluate(son, weights, distances, installationCosts, demands, capacities, transportationCosts, expectedRandomQuality);
-          if (sonQual < fbest) {
-            fbest = sonQual;
-            result = (IntegerVector)son.Clone();
-            onefound = true;
-          }
-        }
+        }
+
+        if (!onefound && (maximization.Value && fbestAttempt < childFit || !maximization.Value && fbestAttempt > childFit)) {
+          bestAttempt = child;
+          fbestAttempt = childFit;
+        }
+      }
         /*if (tabufix(&son, 0.5 * sqrt(n * m), round(n * m * log10(n)), &tabufix_it)) {
           solution_cost(&son);
@@ -216 +183 @@
             merge_fixed++;
           }*/
-      }
-      if (result == null) throw new InvalidOperationException("Child could not be created.");
-      return result;
+      return result ?? bestAttempt;
+    }
+
+    private static IntegerVector Merge(IntegerVector p1, IntegerVector p2,
+      DoubleMatrix distances, DoubleArray demands, double[] mediana,
+      int m, int n, int i, double[] cap, out int unassigned) {
+      unassigned = n;
+      var child = new IntegerVector(n);
+      for (var k = 0; k < n; k++) {
+        child[k] = -1;
+        var ik1 = p1[k];
+        var ik2 = p2[k];
+        if (distances[i, ik1] < mediana[i]) {
+          child[k] = ik1;
+          cap[ik1] += demands[k];
+          unassigned--;
+        } else if (distances[i, ik2] > mediana[i]) {
+          child[k] = ik2;
+          cap[ik2] += demands[k];
+          unassigned--;
+        };
+      }
+      return child;
+    }
+
+    private static bool TryRandomAssignment(IRandom random, DoubleArray demands, DoubleArray capacities, int m, int n, double[] cap, IntegerVector child, ref int unassigned) {
+      var unbiasedOrder = Enumerable.Range(0, n).Shuffle(random).ToList();
+      for (var idx = 0; idx < n; idx++) {
+        var k = unbiasedOrder[idx];
+        if (child[k] < 0) {
+          var feasibleInserts = Enumerable.Range(0, m)
+            .Select((v, i) => new { Pos = i, Slack = capacities[i] - cap[i] })
+            .Where(x => x.Slack >= demands[k]).ToList();
+          if (feasibleInserts.Count == 0) return false;
+          var j = feasibleInserts.SampleRandom(random).Pos;
+          child[k] = j;
+          cap[j] += demands[k];
+          unassigned--;
+        }
+      }
+      return true;
+    }
+
+    private static void RandomAssignment(IRandom random, DoubleArray demands, DoubleArray capacities, int m, int n, double[] cap, IntegerVector child, ref int unassigned) {
+      for (var k = 0; k < n; k++) {
+        if (child[k] < 0) {
+          var j = random.Next(m);
+          child[k] = j;
+          cap[j] += demands[k];
+          unassigned--;
+        }
+      }
     }
 
@@ -232 +248 @@
         DemandsParameter.ActualValue, CapacitiesParameter.ActualValue,
         TransportationCostsParameter.ActualValue.Value, ExpectedRandomQualityParameter.ActualValue.Value,
-        EvaluatorParameter.ActualValue);
-    }
-
-    private static double[] Inizialize(DoubleMatrix distances) {
-      int i, j;
-      double mdi;
-      double delta;
-      int ilow, ihigh;
-      bool balance;
-      int operation;
-      int count;
-      int m = distances.Rows;
-
-      double[] mediana = new double[distances.Rows];
-
-      for (i = 0; i < m; i++) {
-        mdi = 0;
-        for (j = 0; j < m; j++) {
-          mdi += distances[i, j];
-        }
-        mediana[i] = mdi / m;
-        balance = false;
-        delta = 1;
-        operation = 0;
-        count = 0;
-        while (!balance && count < 200) {
-          ilow = 0;
-          ihigh = 0;
-          count++;
-          for (j = 0; j < m; j++) {
-            if (distances[i, j] < mediana[i]) ilow++;
-            else if (distances[i, j] > mediana[i]) ihigh++;
-          }
-          if (ilow > ((m + 1) / 2)) {
-            mediana[i] = mediana[i] - delta;
-            if (operation == 1) delta = delta / 2;
-            operation = -1;
-          } else if (ihigh > ((m + 1) / 2)) {
-            mediana[i] = mediana[i] + delta;
-            if (operation == -1) delta = delta / 2;
-            operation = 1;
-          } else balance = true;
-        }
-      }
-      return mediana;
+        EvaluatorParameter.ActualValue, EvaluatedSolutionsParameter.ActualValue);
     }
   }

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

@@ -29 +29 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common;
 using HeuristicLab.Random;
 
@@ -138 +137 @@
       var fix = new HashSet<int>();
       var nonFix = new HashSet<int>(Enumerable.Range(0, demands.Length));
-      var phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
+      var phi = new HashSet<int>((pi_prime.GetDifferingIndices(target)));
 
       while (phi.Any()) {
@@ -162 +161 @@
               for (int i = 0; i < B.Count; i++) {
                 if (IsBetter(maximization.Value, solution.Quality.Value, B[i].Quality.Value)) {
-                  var similarity = IntegerVectorEqualityComparer.GetSimilarity(solution.Assignment, B[i].Assignment);
+                  var similarity = HammingSimilarityCalculator.CalculateSimilarity(solution.Assignment, B[i].Assignment);
                   if (similarity == 1.0) {
                     mostSimilarIndex = -1;
@@ -177 +176 @@
               bool contains = false;
               foreach (var b in B) {
-                if (!IntegerVectorEqualityComparer.GetDifferingIndices(solution.Assignment, b.Assignment).Any()) {
+                if (!solution.Assignment.GetDifferingIndices(b.Assignment).Any()) {
                   contains = true;
                   break;
@@ -190 +189 @@
           if (maximization.Value) pi = B.SampleProportional(random, 1, B.Select(x => x.Quality.Value), false).First();
           else pi = B.SampleProportional(random, 1, B.Select(x => 1.0 / x.Quality.Value), false).First();
-          var diff = IntegerVectorEqualityComparer.GetDifferingIndices(pi.Assignment, target);
+          var diff = pi.Assignment.GetDifferingIndices(target);
           var I = phi.Except(diff);
           var i = I.SampleRandom(random);
@@ -204 +203 @@
           }
         } else return result;
-        phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
+        phi = new HashSet<int>(pi_prime.GetDifferingIndices(target));
       }
 

@@ -2 +2 @@
 TestResults
 *.user
+.vs