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

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/Operators

Files:

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

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