Changeset 9473 for branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/MultiComponentVector/Moves/ThreeWay/MultiComponentVectorMoveGenerator.cs

Timestamp:

05/09/13 15:03:41 (11 years ago)

Author:

jhelm

Message:

#1966: Fixed some problems in MCV-move operators; Added parts of potvin-encoding implementation;

File:

• branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/MultiComponentVector/Moves/ThreeWay/MultiComponentVectorMoveGenerator.cs (modified) (6 diffs)

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/MultiComponentVector/Moves/ThreeWay/MultiComponentVectorMoveGenerator.cs

@@ -27 +27 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.BinPacking.Decoders;
 using HeuristicLab.Problems.BinPacking.Interfaces;
+using HeuristicLab.Problems.BinPacking.PackingBin;
+using HeuristicLab.Problems.BinPacking.PackingItem;
 
 namespace HeuristicLab.Encodings.PackingEncoding.MultiComponentVector {
@@ -44 +47 @@
     protected ScopeParameter CurrentScopeParameter {
       get { return (ScopeParameter)Parameters["CurrentScope"]; }
-    }
+    }               
+
 
     [StorableConstructor]
@@ -57 +61 @@
 
 
-
-
+    public static int NrOfRotationMoves(MultiComponentVectorEncoding mcv) {
+      return mcv.PackingInformations.Count;
+    }
     public static IEnumerable<MultiComponentVectorMove> GenerateRotationMoves(MultiComponentVectorEncoding multiComponentVector) {
       for (int i = 0; i < multiComponentVector.PackingInformations.Count; i++)
@@ -64 +69 @@
     }
 
+    public static int NrOfSingleGroupingMoves(MultiComponentVectorEncoding mcv) {
+      int nrOfBins = 0;
+      foreach (var pi in mcv.PackingInformations) {
+        if (pi.AssignedBin > nrOfBins)
+          nrOfBins = pi.AssignedBin;
+      }
+      nrOfBins++;
+      return mcv.PackingInformations.Count * (nrOfBins - 1);
+    }
     public static IEnumerable<MultiComponentVectorMove> GenerateSingleGroupingMoves(MultiComponentVectorEncoding multiComponentVector) {
       int nrOfBins = 0;
@@ -78 +92 @@
     }
 
-    public static IEnumerable<MultiComponentVectorMove> GenerateSwapSequenceMoves(MultiComponentVectorEncoding multiComponentVector) {
+    public static int NrOfSwapPositionMoves(MultiComponentVectorEncoding mcv) {
+      int nrOfBins = 0;
+      foreach (var pi in mcv.PackingInformations) {
+        if (pi.AssignedBin > nrOfBins)
+          nrOfBins = pi.AssignedBin;
+      }
+      nrOfBins++;
+      int[] itemsPerBin = new int[nrOfBins];
+      foreach (var pi in mcv.PackingInformations) {
+        itemsPerBin[pi.AssignedBin]++;
+      }
+      int nrOfSwapPositionMoves = 0;
+      foreach (int items in itemsPerBin) {
+        nrOfSwapPositionMoves += (items * (items - 1)) / 2;
+      }
+      return nrOfSwapPositionMoves;
+    }
+    public static IEnumerable<MultiComponentVectorMove> GenerateSwapPositionMoves(MultiComponentVectorEncoding multiComponentVector) {
       Dictionary<int, List<int>> indexesPerBin = new Dictionary<int, List<int>>();
       for (int i = 0; i < multiComponentVector.PackingInformations.Count; i++) {
@@ -89 +120 @@
         for (int i = 0; i < entry.Value.Count - 1; i++)
           for (int j = i + 1; j < entry.Value.Count; j++)
-            yield return new SwapSequenceMove(entry.Value[i], entry.Value[j], multiComponentVector);
+            yield return new SwapPositionMove(entry.Value[i], entry.Value[j], multiComponentVector);
       }
     }
 
+    public static int NrOfChangePositionMoves(MultiComponentVectorEncoding mcv) {
+      int nrOfBins = 0;
+      foreach (var pi in mcv.PackingInformations) {
+        if (pi.AssignedBin > nrOfBins)
+          nrOfBins = pi.AssignedBin;
+      }
+      nrOfBins++;
+      int[] itemsPerBin = new int[nrOfBins];
+      foreach (var pi in mcv.PackingInformations) {
+        itemsPerBin[pi.AssignedBin]++;
+      }
+      int nrOfSwapPositionMoves = 0;
+      foreach (int items in itemsPerBin) {
+        nrOfSwapPositionMoves += (items * (items - 1)) / 2;
+      }
+      return nrOfSwapPositionMoves;
+    }
+    public static IEnumerable<MultiComponentVectorMove> GenerateChangePositionMoves(MultiComponentVectorEncoding multiComponentVector) {
+      Dictionary<int, List<int>> indexesPerBin = new Dictionary<int, List<int>>();
+      for (int i = 0; i < multiComponentVector.PackingInformations.Count; i++) {
+        int currentBin = multiComponentVector.PackingInformations[i].AssignedBin;
+        if (!indexesPerBin.ContainsKey(currentBin))
+          indexesPerBin[currentBin] = new List<int>();
+        indexesPerBin[currentBin].Add(i);
+      }
+      foreach (var entry in indexesPerBin) {
+        for (int i = 0; i < entry.Value.Count - 1; i++)
+          for (int j = i + 1; j < entry.Value.Count; j++)
+            yield return new ChangePositionMove(entry.Value[i], entry.Value[j], multiComponentVector);
+      }
+    }
 
     public override IOperation Apply() {