Changeset 15553 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves

Timestamp:

12/20/17 15:41:27 (7 years ago)

Author:

abeham

Message:

#1614:

• Implementing basic algorithm according to paper (rechecking all operators)
• Checking implementation with paper
• Improved speed of move generator
• Improved speed of randomized solution creator

File:

• branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/StochasticNMoveSingleMoveGenerator.cs (modified) (1 diff)

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

@@ -57 +57 @@
     }
 
+    public static NMove GenerateOneMove(IRandom random, IntegerVector assignment, DoubleArray capacities) {
+      var locations = capacities.Length;
+      if (locations <= 1) throw new ArgumentException("There must be at least two locations.");
+      var dim = assignment.Length;
+      var equip = random.Next(dim);
+      var equipments = new List<int>(1) { equip };
+
+      var reassignment = new int[dim];
+      reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);
+
+      return new NMove(reassignment, equipments);
+    }
+
+    public static NMove GenerateTwoMove(IRandom random, IntegerVector assignment, DoubleArray capacities) {
+      var locations = capacities.Length;
+      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 reassignment = new int[dim];
+      for (var i = 0; i < 2; i++) {
+        var equip = equipments[i];
+        reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);
+      }
+      return new NMove(reassignment, equipments);
+    }
+
     public static NMove GenerateExactlyN(IRandom random, IntegerVector assignment, int n, DoubleArray capacities) {
-      if (capacities.Length <= 1) throw new ArgumentException("There must be at least two locations.");
+      if (n == 1) return GenerateOneMove(random, assignment, capacities);
+      if (n == 2) return GenerateTwoMove(random, assignment, capacities);
+      var locations = capacities.Length;
+      if (locations <= 1) throw new ArgumentException("There must be at least two locations.");
       var dim = assignment.Length;
+      var equipments = Enumerable.Range(0, dim).SampleRandomWithoutRepetition(random, n, dim).ToList();
+
       var reassignment = new int[dim];
-      var equipments = Enumerable.Range(0, dim).SampleRandomWithoutRepetition(random, n, dim).ToList();
       for (var i = 0; i < n; i++) {
         var equip = equipments[i];
-        do {
-          reassignment[equip] = random.Next(capacities.Length) + 1;
-        } while (reassignment[equip] == assignment[equip] + 1);
+        reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], 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;
     }