Changeset 9495 for branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/EP

Timestamp:

05/15/13 22:23:36 (11 years ago)

Author:

jhelm

Message:

#1966: Did some major refactoring in Decoder-classes; Added MoveEvaluator classes for different encodings and dimensions; Added new crossover-class for MCV encoding;

Location:

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/EP

Files:

• ExtremePointGroupingVectorDecoder3D.cs (modified) (2 diffs)
• ExtremePointMultiComponentVectorDecoder3D.cs (modified) (2 diffs)
• ExtremePointPackingSequenceDecoder3D.cs (modified) (2 diffs)
• ExtremePointsFunctions3D.cs (modified) (15 diffs)
• ISOContainerMultiComponentVectorDecoder3D.cs (added)

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/EP/ExtremePointGroupingVectorDecoder3D.cs

@@ -41 +41 @@
   [Item("Identical bin, three dimensional, extreme points based decoder for the GroupingVector encoding.", "<Description missing...>")]
   [StorableClass]
-  public class ExtremePointGroupingVectorDecoder3D : IdenticalBinPackingSolutionDecoder<
+  public class ExtremePointGroupingVectorDecoder3D : PackingSolutionDecoder<
       ThreeDimensionalPacking,
       CuboidPackingBin,
-      CuboidPackingItem,
-      PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> {
+      CuboidPackingItem> {
 
     public ExtremePointGroupingVectorDecoder3D ()
@@ -68 +67 @@
     }
 
-    protected override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution) {
+    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
                       
       var solution = encodedSolution as GroupingVectorEncoding;
       if (solution == null) throw new InvalidOperationException("Encoding is not of type GroupingVector");
 
-      return Decode(solution, PackingBinMeasuresParameter.ActualValue, PackingItemMeasuresParameter.ActualValue);
+      return Decode(solution, binMeasures, itemMeasures);
     }
   }

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/EP/ExtremePointMultiComponentVectorDecoder3D.cs

@@ -42 +42 @@
   [Item("Identical bin, three dimensional, extreme points based decoder for the MultiComponentVector encoding.", "<Description missing...>")]
   [StorableClass]
-  public class ExtremePointMultiComponentVectorDecoder3D : IdenticalBinPackingSolutionDecoder<
+  public class ExtremePointMultiComponentVectorDecoder3D : PackingSolutionDecoder<
       ThreeDimensionalPacking,
       CuboidPackingBin,
-      CuboidPackingItem,
-      PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> {
+      CuboidPackingItem> {
 
     public ExtremePointMultiComponentVectorDecoder3D ()
@@ -69 +68 @@
     }
 
-    protected override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution) {
+    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
 
       var solution = encodedSolution as MultiComponentVectorEncoding;
       if (solution == null) throw new InvalidOperationException("Encoding is not of type MultiComponentVector");
 
-      return Decode(solution, PackingBinMeasuresParameter.ActualValue, PackingItemMeasuresParameter.ActualValue);
+      return Decode(solution, binMeasures, itemMeasures);
     }
   }

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/EP/ExtremePointPackingSequenceDecoder3D.cs

@@ -40 +40 @@
   [Item("Identical bin, three dimensional, extreme points based decoder for the PackingSequence encoding.", "<Description missing...>")]
   [StorableClass]
-  public class ExtremePointPackingSequenceDecoder3D : IdenticalBinPackingSolutionDecoder<
+  public class ExtremePointPackingSequenceDecoder3D : PackingSolutionDecoder<
       ThreeDimensionalPacking,
       CuboidPackingBin,
-      CuboidPackingItem,
-      PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> {
+      CuboidPackingItem> {
 
     public ExtremePointPackingSequenceDecoder3D ()
@@ -59 +58 @@
 
 
-    protected override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution) {
+    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
 
       var solution = encodedSolution as PackingSequenceEncoding;

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/EP/ExtremePointsFunctions3D.cs

@@ -9 +9 @@
 using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
 using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
-using HeuristicLab.Encodings.PackingEncoding.Potvin;
 using HeuristicLab.Problems.BinPacking.Dimensions;
 using HeuristicLab.Problems.BinPacking.Interfaces;
@@ -20 +19 @@
 
 
-
-    public static ObservableDictionary<int, ThreeDimensionalPacking> ExtremePointBasedPacking(ref PotvinEncoding solution, 
-      ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures) {
-        if (!solution.DelimiterInitialized) {
-          #region Preperations
-          var itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
-          int nrOfBins = 1;
-
-          var occupiedPoints = new List<int[, ,]>();
-          occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
-
-          HashSet<ThreeDimensionalPacking> extremePoints = new HashSet<ThreeDimensionalPacking>();
-          extremePoints.Add(new ThreeDimensionalPacking(0, 0, 0, 0, false));
-          #endregion
-
-          Dictionary<int, List<int>> itemIndexesForBin = new Dictionary<int, List<int>>();
-          itemIndexesForBin[0] = new List<int>();
-
-          foreach (int itemIndex in solution.IntVector) {
-            var item = itemMeasures[itemIndex];
-            extremePoints = OrderExtremePoints(extremePoints, occupiedPoints, binMeasures);
-            var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions);
-            if (positionFound != null) {
-              extremePoints.Remove(positionFound);
-            } else {
-              positionFound = new ThreeDimensionalPacking(nrOfBins, 0, 0, 0);
-              occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
-              itemIndexesForBin[nrOfBins] = new List<int>();
-              nrOfBins++;
-            }
-            itemPositions[itemIndex] = positionFound;
-            itemIndexesForBin[positionFound.AssignedBin].Add(itemIndex);
-            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
-            extremePoints = GenerateNewExtremePointsForNewItem(extremePoints, occupiedPoints, item, positionFound, binMeasures);
-          }
-          List<int> intVector = new List<int>();
-          foreach (var indexes in itemIndexesForBin) {
-            foreach (var index in indexes.Value) {
-              intVector.Add(index);
-            }
-            intVector.Add(-1);
-          }
-          intVector.RemoveAt(intVector.Count - 1);
-          solution.IntVector = new IntegerVector (intVector.ToArray());
-
-          return itemPositions;
-        } else {
-          #region Preperations
-          int nrOfBins = solution.IntVector.Count(i => i.Equals (-1)) + 1;
-
-          //Get all indexes of items for every bin according to int vector
-          Dictionary<int, List<int>> unpackedItemIndexesPerBin = new Dictionary<int, List<int>>();
-          Dictionary<int, HashSet<ThreeDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<ThreeDimensionalPacking>>();
-          var occupiedPoints = new List<int[, ,]>();
-
-          int binCounter = 0;
-          unpackedItemIndexesPerBin[binCounter] = new List<int>();
-          for (int i = 0; i < solution.IntVector.Length; i++) {
-            if (solution.IntVector[i].Equals(-1)) {
-              unpackedItemIndexesPerBin[binCounter++] = new List<int>();
-              extremePointsForBin[i] = new HashSet<ThreeDimensionalPacking>();
-              extremePointsForBin[i].Add(new ThreeDimensionalPacking(i, 0, 0, 0, false));
-              occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
-            } else {
-              unpackedItemIndexesPerBin[binCounter].Add(solution.IntVector[i]);
-            }
-
-          }
-
-
-          ObservableDictionary<int, ThreeDimensionalPacking> itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
-          var remainingItems = new List<int>();
-
-          #endregion Preperations
-
-
-
-          //Iterate over all bin-lists
-          for (int binNr = 0; binNr < nrOfBins; binNr++) {
-            //Iterate over the current bin-item-list and find feasible positions in the current bin for each item
-            var unpackedItems = unpackedItemIndexesPerBin[binNr];
-            for (int i = 0; i < unpackedItems.Count; i++) {
-              var itemIndex = unpackedItems[i];
-              var item = itemMeasures[itemIndex];
-
-              extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
-              var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
-              if (positionFound != null) {
-                extremePointsForBin[binNr].Remove(positionFound);
-                itemPositions[itemIndex] = positionFound;
-                occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
-                extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
-              } else
-                remainingItems.Add(itemIndex);
-            }
-          }
-
-
-
-          //Packing of remaining items    
-          //Iterate over all bin-lists
-          for (int binNr = 0; binNr < nrOfBins && remainingItems.Count > 0; binNr++) {
-            var unpackedItems = new List<int>(remainingItems);
-            //Iterate over all the remaining items
-            for (int i = 0; i < unpackedItems.Count; i++) {
-              var itemIndex = unpackedItems[i];
-              var item = itemMeasures[itemIndex];
-
-              extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
-              var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
-              if (positionFound != null) {
-                extremePointsForBin[binNr].Remove(positionFound);
-                InsertItemgeneAfterLastItemgeneOfUsedBin(ref solution, itemIndex, binNr);
-                itemPositions[itemIndex] = positionFound;
-                occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
-                extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
-                remainingItems.Remove(itemIndex);
-              }
-            }
-            if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
-              extremePointsForBin[nrOfBins] = new HashSet<ThreeDimensionalPacking>();
-              extremePointsForBin[nrOfBins].Add(new ThreeDimensionalPacking(nrOfBins, 0, 0, 0, false));
-              occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
-              nrOfBins++;
-            }
-          }
-
-          return itemPositions;
-        }
-    }
-    private static void InsertItemgeneAfterLastItemgeneOfUsedBin(ref PotvinEncoding solution, int itemIndex, int binNr) { 
-      List<int> temp = new List<int> (solution.IntVector);
-      temp.Remove(itemIndex);
-      var delimiterIndexes = temp.Select((value, index) => value == -1).Select((value, index) => index);
-      int insertionIndex = temp.Count; 
-      if (binNr < delimiterIndexes.Count()) {
-        insertionIndex = delimiterIndexes.ElementAt(binNr);
-      }
-      temp.Insert(insertionIndex, itemIndex);
-      solution.IntVector = new IntegerVector (temp.ToArray());
-    }
-
-
     public static ObservableDictionary<int, ThreeDimensionalPacking> ExtremePointBasedPacking(ref MultiComponentVectorEncoding solution, 
         ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures) {
 
       #region Preperations
-      int lowerBound = solution.PackingInformations.Max(x => x.AssignedBin);
-      int nrOfBins = lowerBound + 1;
+      int nrOfBins = solution.NrOfBins;
 
       //Get all indexes of items for every bin according to grouping-vector                      
@@ -176 +31 @@
 
       for (int i = 0; i < nrOfBins; i++) {        
-        unpackedItemIndexesPerBin[i] = solution.PackingInformations
-          .Where(pi => pi.AssignedBin == i)
-          .ToList();
+        unpackedItemIndexesPerBin[i] = new List<PackingInformation> (solution.PackingInformations[i]);
 
         extremePointsForBin[i] = new HashSet<ThreeDimensionalPacking>();
@@ -196 +49 @@
         var unpackedItems = unpackedItemIndexesPerBin[binNr];
         for (int i = 0; i < unpackedItems.Count; i++) {
-          var itemIndex = unpackedItems[i].ItemIndex;
+          var itemIndex = unpackedItems[i].ItemID;
           var item = itemMeasures[itemIndex];
 
@@ -206 +59 @@
             occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
             extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
-          } else
+          } else {
             remainingItems.Add(unpackedItems[i]);
+            solution.PackingInformations[binNr].Remove(unpackedItems[i]);
+          }
         }
       }
@@ -218 +73 @@
         //Iterate over all the remaining items
         for (int i = 0; i < unpackedItems.Count; i++) {
-          var itemIndex = unpackedItems[i].ItemIndex;
+          var itemIndex = unpackedItems[i].ItemID;
           var item = itemMeasures[itemIndex];
 
@@ -227 +82 @@
             itemPositions[itemIndex] = positionFound;
             occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
-            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
+            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);      
             remainingItems.Remove(unpackedItems[i]);
-            if (binNr <= lowerBound) {
-              InsertItemgeneAfterLastItemgeneOfUsedBin(ref solution, itemIndex, binNr);
-            }
+            solution.PackingInformations[binNr].Add(unpackedItems[i]);
           }
         }
@@ -238 +91 @@
           extremePointsForBin[nrOfBins].Add(new ThreeDimensionalPacking(nrOfBins, 0, 0, 0, false));
           occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
+          solution.PackingInformations[nrOfBins] = new ItemList<PackingInformation>();
           nrOfBins++;
         }
@@ -243 +97 @@
 
       return itemPositions;
-    }
-    private static void InsertItemgeneAfterLastItemgeneOfUsedBin(ref MultiComponentVectorEncoding solution, int itemIndex, int binNr) {
-      var itemgene = solution.PackingInformations.Find(pi => pi.ItemIndex == itemIndex);
-      solution.PackingInformations.Remove (itemgene);
-      itemgene.AssignedBin = binNr;
-      int targetIndex = solution.PackingInformations.FindLastIndex(pi => pi.AssignedBin == binNr);
-      solution.PackingInformations.Insert(targetIndex + 1, itemgene);
     }
 
@@ -370 +217 @@
 
 
-    private static ThreeDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures,
+    public static ThreeDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures,
         HashSet<ThreeDimensionalPacking> extremePoints, List<int[, ,]> occupiedPoints, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions) {
           return FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions, false);
     }
-    private static ThreeDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures, 
+    public static ThreeDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures, 
         HashSet<ThreeDimensionalPacking> extremePoints, List<int[,,]> occupiedPoints, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, bool rotated) {
 
@@ -397 +244 @@
       return null;
     }
-    private static List<int[, ,]> IncreaseBinCountForOccupiedPoints(List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
+    public static List<int[, ,]> IncreaseBinCountForOccupiedPoints(List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
       occupiedPoints.Add(new int[binMeasures.Width, binMeasures.Height, binMeasures.Depth]);
       int lastIndex = occupiedPoints.Count - 1;
@@ -409 +256 @@
       return occupiedPoints;
     }
-    private static bool IsStaticStable(int[, ,] occupiedPoints, CuboidPackingItem item, ThreeDimensionalPacking ep) {
+    public static bool IsStaticStable(int[, ,] occupiedPoints, CuboidPackingItem item, ThreeDimensionalPacking ep) {
       //Static stability is given, if item is placed on the ground
       if (ep.Y == 0)
@@ -433 +280 @@
       return false;
     }
-    private static List<int[, ,]>  OccupyPointsForNewItem(List<int[, ,]> occupiedPoints, CuboidPackingItem newItem, ThreeDimensionalPacking position, int itemIndex) {
+    public static List<int[, ,]>  OccupyPointsForNewItem(List<int[, ,]> occupiedPoints, CuboidPackingItem newItem, ThreeDimensionalPacking position, int itemIndex) {
       int width = position.Rotated ? newItem.Depth : newItem.Width; 
       int depth = position.Rotated ? newItem.Width : newItem.Depth;
@@ -445 +292 @@
       return occupiedPoints;
     }
-    private static HashSet<ThreeDimensionalPacking> GenerateNewExtremePointsForNewItem(HashSet<ThreeDimensionalPacking> extremePoints, List<int[, ,]> occupiedPoints, 
+    public static HashSet<ThreeDimensionalPacking> GenerateNewExtremePointsForNewItem(HashSet<ThreeDimensionalPacking> extremePoints, List<int[, ,]> occupiedPoints, 
         CuboidPackingItem newItem, ThreeDimensionalPacking position, CuboidPackingBin binMeasures) {
       int currentBin = position.AssignedBin;
@@ -518 +365 @@
 
 
-    private static HashSet<ThreeDimensionalPacking> OrderExtremePoints(HashSet<ThreeDimensionalPacking> hashSet, List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
+    public static HashSet<ThreeDimensionalPacking> OrderExtremePoints(HashSet<ThreeDimensionalPacking> hashSet, List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
       return new HashSet<ThreeDimensionalPacking>(hashSet.OrderBy(ep => ep.AssignedBin).ThenBy(ep => ep.Z).ThenBy(ep => ep.X).ThenBy(ep => ep.Y).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
     }
-    private static int ShortestPossibleSideFromEP(ThreeDimensionalPacking ep, List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
+    public static int ShortestPossibleSideFromEP(ThreeDimensionalPacking ep, List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
       int shortestSide = int.MaxValue;