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

Timestamp:

01/03/18 00:28:51 (6 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)

File:

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

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];
         }
       }