Changeset 15572 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment

Timestamp:

01/03/18 00:28:51 (7 years ago)

Author:

abeham

Message:

#1614:

• fixed a bug in GRASP where solutions in the elite set would be mutated
• introduced termination criteria when reaching best-known quality
• tweaked generating random numbers in StochasticNMoveSingleMoveGenerator
• changed DiscreteLocationCrossover to use an allele from one of the parents instead of introducing a mutation in case no feasible insert location is found
• changed OSGA maxselpress to 500
• slight change to contexts, introduced single-objectiveness much earlier in the class hierachy
  • limited ContextAlgorithm to SingleObjectiveBasicProblems (doesn't matter here)

Location:

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3

Files:

• Moves/StochasticNMoveSingleMoveGenerator.cs (modified) (3 diffs)
• Operators/Crossovers/DiscreteLocationCrossover.cs (modified) (2 diffs)
• Operators/Crossovers/GQAPPathRelinking.cs (modified) (1 diff)
• Operators/Manipulators/RelocateEquipmentManipluator.cs (modified) (1 diff)

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/StochasticNMoveSingleMoveGenerator.cs

@@ -65 +65 @@
 
       var reassignment = new int[dim];
-      reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);
+      reassignment[equip] = 1 + (assignment[equip] + random.Next(1, locations)) % locations;
 
       return new NMove(reassignment, equipments);
@@ -74 +74 @@
       if (locations <= 1) throw new ArgumentException("There must be at least two locations.");
       var dim = assignment.Length;
-      var equipments = new List<int>(2) { random.Next(dim), -1 };
-      do {
-        equipments[1] = random.Next(dim);
-      } while (equipments[0] == equipments[1]);
+      var equipments = new List<int>(2) { random.Next(dim) };
+      equipments.Add((equipments[0] + random.Next(1, dim)) % dim);
 
       var reassignment = new int[dim];
       for (var i = 0; i < 2; i++) {
         var equip = equipments[i];
-        reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);
+        reassignment[equip] = 1 + (assignment[equip] + random.Next(1, locations)) % locations;
       }
       return new NMove(reassignment, equipments);
@@ -98 +96 @@
       for (var i = 0; i < n; i++) {
         var equip = equipments[i];
-        reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);
+        reassignment[equip] = 1 + (assignment[equip] + random.Next(1, locations)) % locations;
       }
       return new NMove(reassignment, equipments);
-    }
-
-    private static int ReassignEquipment(IRandom random, int equip, int prevLocation, int locations) {
-      var newLoc = random.Next(locations) + 1;
-      while (newLoc == prevLocation + 1)
-        newLoc = random.Next(locations) + 1;
-      return newLoc;
     }
 

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

@@ -83 +83 @@
       }
 
-      var order = Enumerable.Range(0, takenEquip.Length).Shuffle(random); // avoid bias
+      var order = Enumerable.Range(0, takenEquip.Length)
+        .Where(x => !takenEquip[x])
+        .Shuffle(random); // avoid bias
       foreach (var e in order) {
-        if (takenEquip[e]) continue;
         var assigned = false;
         // try 1: find a parent where equipment can be assigned feasibly
-        foreach (var p in Enumerable.Range(0, parents.Length).Shuffle(random)) {
-          if (slack[parents[p][e]] >= demands[e]) {
-            child[e] = parents[p][e];
+        var fallback = -1;
+        var count = 1;
+        foreach (var p in parents.Shuffle(random)) {
+          if (slack[p[e]] >= demands[e]) {
+            child[e] = p[e];
             slack[child[e]] -= demands[e];
             assigned = true;
             break;
+          } else if (random.NextDouble() < 1.0 / count) {
+            fallback = p[e];
           }
+          count++;
         }
         // try 2: find a random feasible location
@@ -103 +109 @@
             child[e] = loc;
             slack[loc] -= demands[e];
-            assigned = true;
+          } else {
+            // otherwise: fallback
+            child[e] = fallback;
+            slack[child[e]] -= demands[e];
           }
-        }
-        // try 3: insert in a random location (no feasible insert found)
-        if (!assigned) {
-          child[e] = random.Next(locations);
-          slack[child[e]] -= demands[e];
         }
       }

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

@@ -79 +79 @@
       var sFit = problemInstance.ToSingleObjective(sourceEval);
       var tFit = problemInstance.ToSingleObjective(targetEval);
-      GQAPSolution pi_star = sFit < tFit ? new GQAPSolution(source, sourceEval) : new GQAPSolution(target, targetEval); // line 1 of Algorithm 4
+      GQAPSolution pi_star = sFit < tFit
+        ? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone())
+        : new GQAPSolution((IntegerVector)target.Clone(), (Evaluation)targetEval.Clone()); // line 1 of Algorithm 4
       double pi_star_Fit = problemInstance.ToSingleObjective(pi_star.Evaluation); // line 2 of Algorithm 4
       

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Manipulators/RelocateEquipmentManipluator.cs

@@ -51 +51 @@
       foreach (var equipment in equipments) {
         var oldLoc = assignment[equipment];
-        var newLoc =random.Next(locations - 1);
-        if (newLoc >= oldLoc) newLoc++; // don't reassign to current loc
-        assignment[equipment] = newLoc;
+        assignment[equipment] = (oldLoc + random.Next(1, locations)) % locations;
         if (random.NextDouble() < stopProb) break;
       }