Changeset 15533 for branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/OneOptAssignment.cs

Timestamp:

12/18/17 14:38:18 (6 years ago)

Author:

ddorfmei

Message:

#2747: Improved hard-coded genetic algorithm

• implemented restart strategy
• implemented 1-Opt algorithm
• added parameters to control restart strategy and optimal assignment strategy
• additional results: best solution found after number of generations, jobs/nests (for evaluation only)

File:

• branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/OneOptAssignment.cs (copied) (copied from branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/OptimalAssignment.cs) (1 diff)

branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/OneOptAssignment.cs

@@ -23 +23 @@
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.BinaryVectorEncoding;
 using HeuristicLab.Encodings.PermutationEncoding;
 
 namespace HeuristicLab.Problems.Scheduling.CFSAP {
-  public static class OptimalAssignment {
+  public static class OneOptAssignment {
 
-    public static int[] MakeAssignment(Permutation order, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes, out int T) {
-      var N = order.Length;
+    public static BinaryVector MakeAssignment(Permutation order, BinaryVector assignment, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes, out int T) {
+      var oneOptAssignment = (BinaryVector)assignment.Clone();
+      T = CFSAP.EvaluateAssignment(order, assignment, processingTimes, setupTimes);
 
-      int[,,] weights = new int[2, 2 * N, 2 * N];
-      int[,] graph = new int[2, N];
-      int[,] prevPath = new int[2, N + 1];                     //Only for optimal assignment evaluation
-      int[] optimalAssignment = new int[N];                //Only for optimal assignment evaluation
+      while (true) {
+        var foundBetterSolution = false;
 
-      //Calculate weights in the graph
-      for (int S = 0; S < N; S++) { //Starting point of the arc
-        for (int sM = 0; sM < 2; sM++) {    //Starting point machine
-          int eM = sM == 0 ? 1 : 0;
-          weights[sM, S, S + 1] = 0;
-
-          for (int E = S + 2; E < S + N; E++)
-            weights[sM, S, E] =
-              weights[sM, S, E - 1] +
-              processingTimes[eM, order[(E - 1) % N]] +
-              setupTimes[eM][order[(E - 1) % N], order[E % N]];
-
-          for (int E = S + 1; E < S + N; E++)
-            weights[sM, S, E] += (
-              processingTimes[sM, order[S % N]] +
-              setupTimes[sM][order[S % N], order[(E + 1) % N]]
-            );
-        }
-      }
-
-      //Determine the shortest path in the graph
-      T = int.MaxValue / 2;
-      for (int S = 0; S < N - 1; S++)      //Start node in graph          O(N)
-        for (int SM = 0; SM < 2; SM++) {   //Start node machine in graph  O(1)
-          graph[SM, S] = 0;
-          graph[SM == 0 ? 1 : 0, S] = int.MaxValue / 2;
-          prevPath[SM, 0] = -1;
-          for (int E = S + 1; E < N; E++)      //Currently calculated node          O(N)
-            for (int EM = 0; EM < 2; EM++) {   //Currently calculated node machine  O(1)
-              graph[EM, E] = int.MaxValue / 2;
-              for (int EC = S; EC < E; EC++) { //Nodes connected to node E          O(N)
-                int newWeight = graph[EM == 0 ? 1 : 0, EC] + weights[EM == 0 ? 1 : 0, EC, E];
-                if (newWeight < graph[EM, E]) {
-                  graph[EM, E] = newWeight;
-                  prevPath[EM, E] = EC;
-                }
-              }
-            }
-
-          int EP = S + N; //End point.
-          int newT = int.MaxValue / 2;
-          for (int EC = S + 1; EC < N; EC++) { //Nodes connected to EP O(N)
-            int newWeight = graph[SM == 0 ? 1 : 0, EC] + weights[SM == 0 ? 1 : 0, EC, EP];
-            if (newWeight < newT) {
-              newT = newWeight;
-              prevPath[SM, S] = EC;
-            }
-          }
-
-          if (newT < T) {
+        for (var i = 0; i < oneOptAssignment.Length; ++i) {
+          var newAssignment = (BinaryVector)oneOptAssignment.Clone();
+          newAssignment[i] = !newAssignment[i];
+          int newT = CFSAP.EvaluateAssignment(order, newAssignment, processingTimes, setupTimes);
+          if (newT < T) { // new best solution has been found
+            oneOptAssignment = newAssignment;
             T = newT;
-            optimalAssignment = MakeAssignement(S, SM, prevPath, order);
+            foundBetterSolution = true;
+            break;
           }
         }
 
-      //Omitted solutions
-      for (int machine = 0; machine < 2; machine++) {
-        int[] assignment = Enumerable.Repeat(machine, N).ToArray();
-        int newT = CFSAP.EvaluateAssignement(order, assignment, processingTimes, setupTimes);
-        if (newT < T) { //New best solution has been found
-          T = newT;
-          optimalAssignment = assignment;
-        }
+        if (!foundBetterSolution)
+          return oneOptAssignment;
       }
-
-      return optimalAssignment;
-    }
-
-    private static int[] MakeAssignement(int start, int startMach, int[,] prevPath, Permutation order) {
-      var N = order.Length;
-      int[] assignment = Enumerable.Repeat(-1, N).ToArray();
-      var inverseOrder = new int[N];
-
-      for (int i = 0; i < N; i++)
-        inverseOrder[order[i]] = i;
-
-      int end = start + N;
-
-      int currMach = startMach;
-      int currNode = start;
-      while (true) {
-        assignment[inverseOrder[currNode]] = currMach;
-        currNode = prevPath[currMach, currNode];
-        currMach = currMach == 0 ? 1 : 0;
-        if (currNode == start)
-          break;
-      }
-
-      currMach = startMach;
-      for (int i = 0; i < N; i++) {
-        if (assignment[inverseOrder[i]] != -1)
-          currMach = currMach == 0 ? 1 : 0;
-        else
-          assignment[inverseOrder[i]] = currMach;
-      }
-
-      return assignment;
     }
   }