Changeset 9473 for branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/MultiComponentVector

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;

Location:

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/MultiComponentVector

Files:

• Moves/ThreeWay/Attributes/ChangePositionMoveAttribute.cs (added)
• Moves/ThreeWay/Attributes/MCVTripleMoveAttribute.cs (added)
• Moves/ThreeWay/Attributes/SingleGroupingMoveAttribute.cs (modified) (2 diffs)
• Moves/ThreeWay/Attributes/SwapPositionMoveAttribute.cs (added)
• Moves/ThreeWay/Attributes/SwapSequenceMoveAttribute.cs (deleted)
• Moves/ThreeWay/ExhaustiveMCVTripleMoveGenerator.cs (added)
• Moves/ThreeWay/ExhaustiveMultiComponentVectorMoveGenerator.cs (modified) (2 diffs)
• Moves/ThreeWay/Moves/ChangePositionMove.cs (added)
• Moves/ThreeWay/Moves/MCVTripleMove.cs (added)
• Moves/ThreeWay/Moves/SingleGroupingMove.cs (modified) (5 diffs)
• Moves/ThreeWay/Moves/SingleItemRotationMove.cs (modified) (2 diffs)
• Moves/ThreeWay/Moves/SwapPositionMove.cs (added)
• Moves/ThreeWay/Moves/SwapSequenceMove.cs (deleted)
• Moves/ThreeWay/MultiComponentVectorMoveGenerator.cs (modified) (6 diffs)
• Moves/ThreeWay/MultiComponentVectorMoveHardTabuCriterion.cs (modified) (3 diffs)
• Moves/ThreeWay/MultiComponentVectorMoveMaker.cs (modified) (1 diff)
• Moves/ThreeWay/MultiComponentVectorMoveSoftTabuCriterion.cs (modified) (5 diffs)
• Moves/ThreeWay/MultiComponentVectorTabuMaker.cs (modified) (1 diff)
• Moves/ThreeWay/StochasticMCVTripleMoveGenerator.cs (added)
• Moves/ThreeWay/StochasticMultiComponentVectorMoveGenerator.cs (modified) (2 diffs)
• MultiComponentVectorEncoding.cs (modified) (2 diffs)
• MultiComponentVectorRandomCreator.cs (modified) (2 diffs)

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

@@ -29 +29 @@
   public class SingleGroupingMoveAttribute : MultiComponentVectorMoveAttribute {
     [Storable]
-    public int ItemIndex { get; protected set; }
+    public int Index { get; protected set; }
     [Storable]
     public int AssignedBin { get; protected set; }
@@ -37 +37 @@
     protected SingleGroupingMoveAttribute(SingleGroupingMoveAttribute original, Cloner cloner)
       : base(original, cloner) {
-      this.ItemIndex = original.ItemIndex;
+      this.Index = original.Index;
       this.AssignedBin = original.AssignedBin;
     }
     public SingleGroupingMoveAttribute() : this(-1, -1, -1) { }
-    public SingleGroupingMoveAttribute(int itemIndex, int assignedBin, double moveQuality)
+    public SingleGroupingMoveAttribute(int index, int assignedBin, double moveQuality)
       : base(moveQuality) {
-      ItemIndex = itemIndex;
+      Index = index;
       AssignedBin = assignedBin;
     }

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

@@ -40 +40 @@
     }
 
-
     public static MultiComponentVectorMove[] Apply(MultiComponentVectorEncoding multiComponentVector) {
-      //NrOfMoves = nrOfRotationMoves + nrOfSingleGroupingMoves + nrOfSwapSequenceMoves
+      //NrOfMoves = nrOfRotationMoves + nrOfSingleGroupingMoves + nrOfSwapPositionMoves
       //  nrOfRotationMoves       = nrOfItems
       //  nrOfSingleGroupingMoves = nrOfItems * (nrOfBins - 1)
-      //  nrOfSwapSequenceMoves   = SUM(foreach binNr: !nrOfItemsInBin)
-
-      int lastBinNr = 0;
-      foreach (var pi in multiComponentVector.PackingInformations) {
-        if (pi.AssignedBin > lastBinNr)
-          lastBinNr = pi.AssignedBin;
-      }
-      int nrOfBins = lastBinNr + 1;
-
-      int nrOfRotationMoves = multiComponentVector.PackingInformations.Count;
-      int nrOfSingleGroupingMoves = nrOfRotationMoves * (nrOfBins - 1);
-
-      int[] itemsPerBin = new int[nrOfBins];
-      foreach (var pi in multiComponentVector.PackingInformations) {
-        itemsPerBin[pi.AssignedBin]++;
-      }
-      int nrOfSwapSequenceMoves = 0;
-      foreach (int items in itemsPerBin) {
-        nrOfSwapSequenceMoves += (items * (items - 1)) / 2;
-      }
-
-      int totalMoves = nrOfRotationMoves + nrOfSingleGroupingMoves + nrOfSwapSequenceMoves;
+      //  nrOfSwapPositionMoves   = SUM(foreach binNr: !nrOfItemsInBin)
+      int totalMoves = 
+        NrOfRotationMoves(multiComponentVector) +
+        NrOfSingleGroupingMoves(multiComponentVector) +
+        NrOfSwapPositionMoves(multiComponentVector) +
+        NrOfChangePositionMoves(multiComponentVector);
       MultiComponentVectorMove[] moves = new MultiComponentVectorMove[totalMoves];
       int count = 0;
@@ -75 +58 @@
         moves[count++] = move;
       }
-      foreach (MultiComponentVectorMove move in GenerateSwapSequenceMoves(multiComponentVector)) {
+      foreach (MultiComponentVectorMove move in GenerateSwapPositionMoves(multiComponentVector)) {
+        moves[count++] = move;
+      }
+      foreach (MultiComponentVectorMove move in GenerateChangePositionMoves(multiComponentVector)) {
         moves[count++] = move;
       }
       return moves;
-    }    
+    }  
 
     protected override MultiComponentVectorMove[] GenerateMoves(MultiComponentVectorEncoding multiComponentVector) {

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

@@ -30 +30 @@
   public class SingleGroupingMove : MultiComponentVectorMove {
     [Storable]
-    public int ItemIndex { get; protected set; }
+    public int Index { get; protected set; }
     [Storable]
     public int NewGroup { get; protected set; }
@@ -38 +38 @@
     protected SingleGroupingMove(SingleGroupingMove original, Cloner cloner)
       : base(original, cloner) {
-      this.ItemIndex = original.ItemIndex;
+      this.Index = original.Index;
       this.NewGroup = original.NewGroup;
     }
     public SingleGroupingMove(int index, int newGroup, MultiComponentVectorEncoding multiComponentVector)
       : base(multiComponentVector) {
-      ItemIndex = index;
+      Index = index;
       NewGroup = newGroup;
     }
@@ -52 +52 @@
 
     public override MultiComponentVectorEncoding GetVectorAfterMove() {
-      //var result = new MultiComponentVectorEncoding();
-      //result.PackingInformations = new ItemList<PackingInformation>(this.MultiComponentVector.PackingInformations);
-      //result.PackingInformations[ItemIndex].AssignedBin = NewGroup;
-      //return result;
-      return InsertItemgeneAfterLastItemgeneOfUsedBin(MultiComponentVector, ItemIndex, NewGroup);
+      return GetVectorAfterMove(MultiComponentVector, Index, NewGroup);
     }
-    private MultiComponentVectorEncoding InsertItemgeneAfterLastItemgeneOfUsedBin(MultiComponentVectorEncoding solution, int itemIndex, int binNr) {
+    public static MultiComponentVectorEncoding GetVectorAfterMove(MultiComponentVectorEncoding originalSolution, int itemIndex, int binNr) {
+      var solution = originalSolution.Clone (new Cloner()) as MultiComponentVectorEncoding;
       var itemgene = solution.PackingInformations[itemIndex];
       solution.PackingInformations.Remove(itemgene);
@@ -64 +61 @@
       int targetIndex = solution.PackingInformations.FindLastIndex(pi => pi.AssignedBin == binNr);
       solution.PackingInformations.Insert(targetIndex + 1, itemgene);
+      //solution.PackingInformations[itemIndex].AssignedBin = binNr;
       return solution;
     }
@@ -70 +68 @@
       return typeof(SingleGroupingMoveAttribute);
     }
+
+    public override string ToString() {
+      return "GM(i="+Index+",g="+NewGroup+")";
+    }
   }
 }

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

@@ -48 +48 @@
 
     public override MultiComponentVectorEncoding GetVectorAfterMove() {
-      var result = new MultiComponentVectorEncoding();
-      result.PackingInformations = new ItemList<PackingInformation>(this.MultiComponentVector.PackingInformations);
-      result.PackingInformations[ItemIndex].Rotated = !result.PackingInformations[ItemIndex].Rotated;
+      return GetVectorAfterMove (MultiComponentVector, ItemIndex);
+    }
+    public static MultiComponentVectorEncoding GetVectorAfterMove(MultiComponentVectorEncoding multiComponentVector, int itemIndex) {
+      var result = multiComponentVector.Clone(new Cloner()) as MultiComponentVectorEncoding;
+      result.PackingInformations[itemIndex].Rotated = !result.PackingInformations[itemIndex].Rotated;
       return result;
     }
@@ -57 +59 @@
       return typeof(SingleItemRotationMoveAttribute);
     }
+
+    public override string ToString() {
+      return "RM(i=" + ItemIndex+")";
+    }
   }
 }

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() {

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

@@ -94 +94 @@
     private bool IsMoveTabu(ItemList<IItem> tabuList, MultiComponentVectorMove move, MultiComponentVectorEncoding multiComponentVector, double moveQuality, bool maximization, bool useAspiration) {
       bool isTabu = false;
-      SingleItemRotationMove sirm = move as SingleItemRotationMove;  
-      SingleGroupingMove sgm = move as SingleGroupingMove;   
-      SwapSequenceMove ssm = move as SwapSequenceMove;
+      SingleItemRotationMove sirm = move as SingleItemRotationMove;
+      SingleGroupingMove sgm = move as SingleGroupingMove;
+      SwapPositionMove spm = move as SwapPositionMove;
+      ChangePositionMove cpm = move as ChangePositionMove;
+      MCVTripleMove tm = move as MCVTripleMove;
       var attributes = tabuList.FindAll(ta => ta.GetType().Equals(move.GetMoveAttributeType()));
 
@@ -102 +104 @@
         foreach (IItem tabuMove in attributes) {
           SingleItemRotationMoveAttribute sirmAttr = (tabuMove as SingleItemRotationMoveAttribute);
+          if (sirmAttr.MoveQuality.Equals(moveQuality))
+            return true;
           if (sirmAttr != null
             && (!useAspiration
@@ -114 +118 @@
         foreach (IItem tabuMove in attributes) {
           SingleGroupingMoveAttribute sgmAttr = (tabuMove as SingleGroupingMoveAttribute);
+          if (sgmAttr.MoveQuality.Equals(moveQuality))
+            return true;
           if (sgmAttr != null
             && (!useAspiration
                 || maximization && moveQuality <= sgmAttr.MoveQuality
                 || !maximization && moveQuality >= sgmAttr.MoveQuality)) {
-                  if (sgm.ItemIndex == sgmAttr.ItemIndex || multiComponentVector.PackingInformations[sgm.ItemIndex].AssignedBin == sgmAttr.AssignedBin)
+                  if ( multiComponentVector.PackingInformations[sgm.Index].ItemIndex ==  multiComponentVector.PackingInformations[sgmAttr.Index].ItemIndex
+                    || multiComponentVector.PackingInformations[sgm.Index].AssignedBin == sgmAttr.AssignedBin)
                     isTabu = true;
           }
           if (isTabu) break;
         }
-      } else if (ssm != null) {
+      } else if (spm != null) {
         foreach (IItem tabuMove in attributes) {
-          SwapSequenceMoveAttribute ssmAttr = (tabuMove as SwapSequenceMoveAttribute);
-          if (ssmAttr != null
+          SwapPositionMoveAttribute spmAttr = (tabuMove as SwapPositionMoveAttribute);
+          if (spmAttr.MoveQuality.Equals(moveQuality))
+            return true;
+          if (spmAttr != null
             && (!useAspiration
-                || maximization && moveQuality <= ssmAttr.MoveQuality
-                || !maximization && moveQuality >= ssmAttr.MoveQuality)) {
-                  if (ssm.Index1 == ssmAttr.Index1
-                    || ssm.Index2 == ssmAttr.Index2
-                    || multiComponentVector.PackingInformations[ssm.Index1].ItemIndex == ssmAttr.ItemIndex1
-                    || multiComponentVector.PackingInformations[ssm.Index2].ItemIndex == ssmAttr.ItemIndex2)
+                || maximization && moveQuality <= spmAttr.MoveQuality
+                || !maximization && moveQuality >= spmAttr.MoveQuality)) {
+            if (spm.Index1 == spmAttr.Index1
+              || spm.Index2 == spmAttr.Index2
+              || multiComponentVector.PackingInformations[spm.Index1].ItemIndex == spmAttr.ItemIndex1
+              || multiComponentVector.PackingInformations[spm.Index2].ItemIndex == spmAttr.ItemIndex2)
+              isTabu = true;
+          }
+          if (isTabu) break;
+        }
+      } else if (cpm != null) {
+        foreach (IItem tabuMove in attributes) {
+          ChangePositionMoveAttribute cpmAttr = (tabuMove as ChangePositionMoveAttribute);
+          if (cpmAttr.MoveQuality.Equals(moveQuality))
+            return true;
+          if (cpmAttr != null
+            && (!useAspiration
+                || maximization && moveQuality <= cpmAttr.MoveQuality
+                || !maximization && moveQuality >= cpmAttr.MoveQuality)) {
+            if (cpm.Index == cpmAttr.Index
+        || cpm.TargetIndex == cpmAttr.TargetIndex
+        || multiComponentVector.PackingInformations[cpm.Index].ItemIndex == cpmAttr.ItemIndex)
+              isTabu = true;
+          }
+          if (isTabu) break;
+        }
+      } else if (tm != null) {
+        foreach (IItem tabuMove in attributes) {
+          MCVTripleMoveAttribute tmAttr = (tabuMove as MCVTripleMoveAttribute);
+          if (tmAttr.MoveQuality.Equals(moveQuality))
+            return true;
+          if (tmAttr != null
+            && (!useAspiration
+                || maximization && moveQuality <= tmAttr.MoveQuality
+                || !maximization && moveQuality >= tmAttr.MoveQuality)) {
+                  if ((tm.Index == tmAttr.Index && tm.TargetIndex == tmAttr.TargetIndex)
+                      || tm.Index == tmAttr.Index
+                      || multiComponentVector.PackingInformations[tm.Index].ItemIndex == tmAttr.ItemIndex
+                    )
               isTabu = true;
           }

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

@@ -66 +66 @@
     public override IOperation Apply() {
       MultiComponentVectorMove move = MultiComponentVectorMoveParameter.ActualValue;
-      MultiComponentVectorEncoding MultiComponentVector = MultiComponentVectorParameter.ActualValue;
+      MultiComponentVectorEncoding multiComponentVector = MultiComponentVectorParameter.ActualValue;
       DoubleValue moveQuality = MoveQualityParameter.ActualValue;
       DoubleValue quality = QualityParameter.ActualValue;
 
-      MultiComponentVector = move.GetVectorAfterMove();
+      multiComponentVector.PackingInformations = move.GetVectorAfterMove().PackingInformations;
 
       quality.Value = moveQuality.Value;

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

@@ -65 +65 @@
     public MultiComponentVectorMoveSoftTabuCriterion()
       : base() {
-        Parameters.Add(new LookupParameter<MultiComponentVectorMove>("MultiComponentVectorMove", "The move to evaluate."));
+      Parameters.Add(new LookupParameter<MultiComponentVectorMove>("MultiComponentVectorMove", "The move to evaluate."));
       Parameters.Add(new LookupParameter<MultiComponentVectorEncoding>("MultiComponentVector", "The solution to evaluate."));
       Parameters.Add(new LookupParameter<BoolValue>("MoveTabu", "The variable to store if a move was tabu."));
@@ -94 +94 @@
     private bool IsMoveTabu(ItemList<IItem> tabuList, MultiComponentVectorMove move, MultiComponentVectorEncoding multiComponentVector, double moveQuality, bool maximization, bool useAspiration) {
       bool isTabu = false;
-      SingleItemRotationMove sirm = move as SingleItemRotationMove;  
-      SingleGroupingMove sgm = move as SingleGroupingMove;   
-      SwapSequenceMove ssm = move as SwapSequenceMove;
+
+      SingleItemRotationMove sirm = move as SingleItemRotationMove;
+      SingleGroupingMove sgm = move as SingleGroupingMove;
+      SwapPositionMove spm = move as SwapPositionMove;
+      ChangePositionMove cpm = move as ChangePositionMove;
+      MCVTripleMove tm = move as MCVTripleMove;
       var attributes = tabuList.FindAll(ta => ta.GetType().Equals(move.GetMoveAttributeType()));
 
@@ -106 +109 @@
                 || maximization && moveQuality <= sirmAttr.MoveQuality
                 || !maximization && moveQuality >= sirmAttr.MoveQuality)) {
-                  if (sirm.ItemIndex == sirmAttr.ItemIndex && multiComponentVector.PackingInformations[sirm.ItemIndex].Rotated == sirmAttr.ItemRotation)
-                    isTabu = true;
+            if (sirm.ItemIndex == sirmAttr.ItemIndex && multiComponentVector.PackingInformations[sirm.ItemIndex].Rotated == sirmAttr.ItemRotation)
+              isTabu = true;
           }
           if (isTabu) break;
@@ -118 +121 @@
                 || maximization && moveQuality <= sgmAttr.MoveQuality
                 || !maximization && moveQuality >= sgmAttr.MoveQuality)) {
-                  if (sgm.ItemIndex == sgmAttr.ItemIndex && multiComponentVector.PackingInformations[sgm.ItemIndex].AssignedBin == sgmAttr.AssignedBin)
-                    isTabu = true;
+                  if (multiComponentVector.PackingInformations[sgm.Index].ItemIndex == multiComponentVector.PackingInformations[sgmAttr.Index].ItemIndex 
+              && multiComponentVector.PackingInformations[sgm.Index].AssignedBin == sgmAttr.AssignedBin)
+              isTabu = true;
           }
           if (isTabu) break;
         }
-      } else if (ssm != null) {
+      } else if (spm != null) {
         foreach (IItem tabuMove in attributes) {
-          SwapSequenceMoveAttribute ssmAttr = (tabuMove as SwapSequenceMoveAttribute);
-          if (ssmAttr != null
+          SwapPositionMoveAttribute spmAttr = (tabuMove as SwapPositionMoveAttribute);
+          if (spmAttr != null
             && (!useAspiration
-                || maximization && moveQuality <= ssmAttr.MoveQuality
-                || !maximization && moveQuality >= ssmAttr.MoveQuality)) {
-                  if (ssm.Index1 == ssmAttr.Index1
-                    && ssm.Index2 == ssmAttr.Index2
-                    && multiComponentVector.PackingInformations[ssm.Index1].ItemIndex == ssmAttr.ItemIndex1
-                    && multiComponentVector.PackingInformations[ssm.Index2].ItemIndex == ssmAttr.ItemIndex2)
+                || maximization && moveQuality <= spmAttr.MoveQuality
+                || !maximization && moveQuality >= spmAttr.MoveQuality)) {
+            if (spm.Index1 == spmAttr.Index1
+              && spm.Index2 == spmAttr.Index2
+              && multiComponentVector.PackingInformations[spm.Index1].ItemIndex == spmAttr.ItemIndex1
+              && multiComponentVector.PackingInformations[spm.Index2].ItemIndex == spmAttr.ItemIndex2)
+              isTabu = true;
+          }
+          if (isTabu) break;
+        }
+      } else if (cpm != null) {
+        foreach (IItem tabuMove in attributes) {
+          ChangePositionMoveAttribute cpmAttr = (tabuMove as ChangePositionMoveAttribute);
+          if (cpmAttr != null
+            && (!useAspiration
+                || maximization && moveQuality <= cpmAttr.MoveQuality
+                || !maximization && moveQuality >= cpmAttr.MoveQuality)) {
+            if (cpm.Index == cpmAttr.Index
+        && cpm.TargetIndex == cpmAttr.TargetIndex
+        && multiComponentVector.PackingInformations[cpm.Index].ItemIndex == cpmAttr.ItemIndex)
+              isTabu = true;
+          }
+          if (isTabu) break;
+        }
+      } else if (tm != null) {
+        foreach (IItem tabuMove in attributes) {
+          MCVTripleMoveAttribute tmAttr = (tabuMove as MCVTripleMoveAttribute);
+          if (tmAttr != null
+            && (!useAspiration
+                || maximization && moveQuality <= tmAttr.MoveQuality
+                || !maximization && moveQuality >= tmAttr.MoveQuality)) {
+            if ((tm.Index == tmAttr.Index && tm.TargetIndex == tmAttr.TargetIndex)
+                && multiComponentVector.PackingInformations[tm.Index].ItemIndex == tmAttr.ItemIndex
+                && tm.Rotation == !(tmAttr.RotationAfter.Equals(tmAttr.RotationBefore))
+                && (tm.Group == tmAttr.GroupAfter && multiComponentVector.PackingInformations[tm.Index].AssignedBin == tmAttr.GroupBefore)
+              )
               isTabu = true;
           }
@@ -140 +174 @@
       } 
 
-      
+
 
       return isTabu;

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

@@ -64 +64 @@
       SingleGroupingMove sgm = move as SingleGroupingMove;
       if (sgm != null)
-        return new SingleGroupingMoveAttribute(sgm.ItemIndex, solution.PackingInformations[sgm.ItemIndex].AssignedBin, baseQuality);
-      SwapSequenceMove ssm = move as SwapSequenceMove;
-      if (ssm != null)
-        return new SwapSequenceMoveAttribute(ssm.Index1, ssm.Index2, solution.PackingInformations[ssm.Index1].ItemIndex, solution.PackingInformations[ssm.Index2].ItemIndex, baseQuality);
+        return new SingleGroupingMoveAttribute(sgm.Index, solution.PackingInformations[sgm.Index].AssignedBin, baseQuality);
+      SwapPositionMove spm = move as SwapPositionMove;
+      if (spm != null)
+        return new SwapPositionMoveAttribute(spm.Index1, spm.Index2, solution.PackingInformations[spm.Index1].ItemIndex, solution.PackingInformations[spm.Index2].ItemIndex, baseQuality);
+      ChangePositionMove cpm = move as ChangePositionMove;
+      if (cpm != null)
+        return new ChangePositionMoveAttribute(cpm.Index, cpm.TargetIndex, solution.PackingInformations[cpm.Index].ItemIndex, baseQuality);
+      MCVTripleMove tm = move as MCVTripleMove;
+      if (tm != null)
+        return new MCVTripleMoveAttribute(
+          tm.Index, 
+          tm.TargetIndex,
+          solution.PackingInformations[tm.Index].ItemIndex,
+          solution.PackingInformations[tm.Index].Rotated,
+          tm.Rotation ^ solution.PackingInformations[tm.Index].Rotated,
+          solution.PackingInformations[tm.Index].AssignedBin,
+          tm.Group,
+          baseQuality);
 
       else return solution;

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

@@ -60 +60 @@
       MultiComponentVectorMove[] moves = new MultiComponentVectorMove[sampleSize];
       var rm = new List<MultiComponentVectorMove> (GenerateRotationMoves(multiComponentVector));
-      var gm = new List<MultiComponentVectorMove> (GenerateSingleGroupingMoves(multiComponentVector));
-      var sm = new List<MultiComponentVectorMove> (GenerateSwapSequenceMoves(multiComponentVector));
+      var gm = new List<MultiComponentVectorMove>(GenerateSingleGroupingMoves(multiComponentVector));
+      var sm = new List<MultiComponentVectorMove>(GenerateSwapPositionMoves(multiComponentVector));
+      var cpm = new List<MultiComponentVectorMove>(GenerateChangePositionMoves(multiComponentVector));
 
       for (int i = 0; i < sampleSize; i++) {
-        int typeDecision = random.Next(3);
+        int typeDecision = random.Next(4);
         switch (typeDecision) {
           case 0: moves[i] = rm[random.Next(rm.Count)];
@@ -71 +72 @@
             break;
           case 2: moves[i] = sm[random.Next(sm.Count)];
+            break;
+          case 3: moves[i] = cpm[random.Next(cpm.Count)];
             break;
           default:

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/MultiComponentVector/MultiComponentVectorEncoding.cs

@@ -68 +68 @@
       MultiComponentVectorEncoding mce = obj as MultiComponentVectorEncoding;
       if (mce != null && mce.PackingInformations != null && mce.PackingInformations.Count == this.PackingInformations.Count) {
-        for (int i = 0; i <= mce.PackingInformations.Count; i++) {
+        for (int i = 0; i < mce.PackingInformations.Count; i++) {
           if (mce.PackingInformations[i] != this.PackingInformations[i])
             return false;
@@ -134 +134 @@
       var result = new ItemList<PackingInformation>();
       foreach (int itemIndex in permutation) {
-        result.Add(new PackingInformation (itemIndex, random.Next(0, lowerBound + 1), random.Next(0,100) > 60 ? true : false));
+        result.Add(new PackingInformation(itemIndex, random.Next(0, lowerBound + 1), random.Next(0, 100) > 60 ? true : false));
+      }
+      return result;
+    }
+
+    public static ItemList<PackingInformation> CreateListRandomlyWithSortedSequence(int items, int lowerBound, IRandom random) {
+      Permutation permutation = new Permutation(PermutationTypes.Absolute, items);
+      var result = new ItemList<PackingInformation>();
+      foreach (int itemIndex in permutation) {
+        result.Add(new PackingInformation(itemIndex, random.Next(0, lowerBound + 1), false));
       }
       return result;

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/MultiComponentVector/MultiComponentVectorRandomCreator.cs

@@ -43 +43 @@
       get { return (IValueLookupParameter<IntValue>)Parameters["LowerBound"]; }
     }
+    public IValueParameter<BoolValue> SortedSequenceParameter {
+      get { return (IValueParameter<BoolValue>)Parameters["SortedSequence"]; }
+    }
 
     [StorableConstructor]
@@ -52 +55 @@
     }
 
-    public MultiComponentVectorRandomCreator()
+    public MultiComponentVectorRandomCreator()
       : base() {
       Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
       Parameters.Add(new ValueLookupParameter<IntValue>("PackingItems", "The number of packing-items handled in this problem instance."));
       Parameters.Add(new ValueLookupParameter<IntValue>("LowerBound", "The lower possible number of bins needed to solve this problem (taken from Dell'Amico, Martello and Vigo; 2002)"));
+      Parameters.Add(new ValueParameter<BoolValue>("SortedSequence", "Determines if the items of the created instances are to be sorted by their size."));
 
       EncodedSolutionParameter.ActualName = "MultiComponentVector";
+      SortedSequenceParameter.ActualValue = new BoolValue(false);
     }
 
 
-    public static MultiComponentVectorEncoding Apply(int items, int lowerBound, IRandom random) {
+    public static MultiComponentVectorEncoding Apply(int items, int lowerBound, IRandom random, bool sortedSequence) {
       var solution = new MultiComponentVectorEncoding();
-      solution.PackingInformations = PackingInformation.CreateListRandomly(items, lowerBound, random);
+      if (sortedSequence)
+        solution.PackingInformations = PackingInformation.CreateListRandomlyWithSortedSequence(items, lowerBound, random);
+      else
+        solution.PackingInformations = PackingInformation.CreateListRandomly(items, lowerBound, random);
       return solution;
     }
 
     protected override IPackingSolutionEncoding CreateSolution() {
-      return Apply(PackingItemsParameter.ActualValue.Value, LowerBoundParameter.ActualValue.Value, RandomParameter.ActualValue);
+      return Apply(PackingItemsParameter.ActualValue.Value, LowerBoundParameter.ActualValue.Value, RandomParameter.ActualValue, SortedSequenceParameter.Value.Value);
     }
   }