Changeset 14050 for branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking

Timestamp:

07/12/16 20:35:19 (8 years ago)

Author:

gkronber

Message:

#1966: renamed evaluators

Location:

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3

Files:

• Analyzers/BestBinPackingSolutionAnalyzer.cs (modified) (1 diff)
• Encodings/PackingPlans/PackingPlan.cs (modified) (5 diffs)
• Evaluators/BinUtilizationRegularIdenticalBinEvaluator.cs (modified) (3 diffs)
• Evaluators/PackingPlanEvaluationAlgorithm.cs (modified) (2 diffs)
• Evaluators/PackingPlanEvaluator.cs (modified) (3 diffs)
• Evaluators/PackingRatioEvaluator.cs (moved) (moved from branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingRatioRegularIdenticalBinEvaluator.cs) (2 diffs)
• Evaluators/RegularSimpleRotationIdenticalBinPackingPlanEvaluator.cs (modified) (2 diffs)
• HeuristicLab.Problems.BinPacking-3.3.csproj (modified) (1 diff)
• Interfaces/IPackingPlanEvaluationAlgorithm.cs (modified) (1 diff)
• Interfaces/IPackingPlanEvaluator.cs (modified) (1 diff)
• PackingMoveEvaluator.cs (modified) (3 diffs)
• Problem.cs (modified) (4 diffs)

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Analyzers/BestBinPackingSolutionAnalyzer.cs

@@ -93 +93 @@
       }
       string binUtilKey = "Overall Bin Utilization";
-      DoubleValue binUtil = BinUtilizationRegularIdenticalBinEvaluator<D, B, I>.CalculateBinUtilization(bestSolution);
+      DoubleValue binUtil = BinUtilizationEvaluator<D, B, I>.CalculateBinUtilization(bestSolution);
       if (!results.ContainsKey(binUtilKey))
         results.Add(new Result(binUtilKey, binUtil));

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs

@@ -37 +37 @@
   [Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")]
   [StorableClass]
-  public abstract class PackingPlan<D, B, I> :Item, IPackingPlan
+  public abstract class PackingPlan<D, B, I> : Item, IPackingPlan
     where D : class, IPackingPosition
     where B : PackingShape<D>
@@ -77 +77 @@
 
     protected PackingPlan(B binMeasures, bool useExtremePoints, bool stackingConstraints)
-      : base(){
-        BinMeasures = (B)binMeasures.Clone();
-        StackingConstraints = stackingConstraints;
-        UseExtremePoints = useExtremePoints;
-        BinPackings = new ObservableList<BinPacking<D, B, I>>();
+      : base() {
+      BinMeasures = (B)binMeasures.Clone();
+      StackingConstraints = stackingConstraints;
+      UseExtremePoints = useExtremePoints;
+      BinPackings = new ObservableList<BinPacking<D, B, I>>();
     }
 
     [StorableConstructor]
     protected PackingPlan(bool deserializing) : base(deserializing) { }
-    protected PackingPlan(PackingPlan<D,B,I> original, Cloner cloner)
+    protected PackingPlan(PackingPlan<D, B, I> original, Cloner cloner)
       : base(original, cloner) {
-        this.BinPackings = new ObservableList<BinPacking<D, B, I>>(original.BinPackings);
-    }
-    
+      this.BinPackings = new ObservableList<BinPacking<D, B, I>>(original.BinPackings);
+    }
+
 
     public abstract BinPacking<D, B, I> NewBinPacking();
     public void UpdateBinPackings() {
       BinPackings.RemoveAll(x => x.ItemPositions.Count == 0);
-      BinPackings = new ObservableList<BinPacking<D, B, I>>(BinPackings.OrderByDescending (bp => bp.PackingDensity));
+      BinPackings = new ObservableList<BinPacking<D, B, I>>(BinPackings.OrderByDescending(bp => bp.PackingDensity));
     }
 
@@ -139 +139 @@
       UpdateBinPackings();
 
-      var newSolution = new ObservableDictionary<int,ItemList<PackingInformation>> ();
+      var newSolution = new ObservableDictionary<int, ItemList<PackingInformation>>();
       foreach (var bp in BinPackings) {
         int binIndex = newSolution.Count;
         newSolution[binIndex] = new ItemList<PackingInformation>();
         foreach (var entry in bp.ItemPositions)
-          newSolution[binIndex].Add(new PackingInformation (entry.Key, entry.Value.Rotated));
+          newSolution[binIndex].Add(new PackingInformation(entry.Key, entry.Value.Rotated));
       }
       solution.PackingInformations = newSolution;
@@ -167 +167 @@
       var temp = new List<int>(remainingIDs);
       foreach (int id in temp) {
-        foreach (var bp in BinPackings) {  
-          var position = UseExtremePoints ? bp.FindExtremePointForItem (itemMeasures[id], false, StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], false);
+        foreach (var bp in BinPackings) {
+          var position = UseExtremePoints ? bp.FindExtremePointForItem(itemMeasures[id], false, StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], false);
           if (position != null) {
             bp.PackItem(id, itemMeasures[id], position);
@@ -195 +195 @@
         binIndex++;
       }
-      solution.GroupingVector = new IntegerVector (newSolution);
+      solution.GroupingVector = new IntegerVector(newSolution);
     }
     public void Pack(PackingSequenceEncoding solution, ItemList<I> itemMeasures) {

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/BinUtilizationRegularIdenticalBinEvaluator.cs

@@ -28 +28 @@
 
 namespace HeuristicLab.Problems.BinPacking {
-  [Item("Bin-Utilization Regular Identical-Bin Evaluator", "<Description missing> Found in Lee:2010")]
+  [Item("Bin-Utilization Evaluator", "<Description missing> Found in Lee:2010")] // TODO
   [StorableClass]
-  public abstract class BinUtilizationRegularIdenticalBinEvaluator<D, B, I> : RegularSimpleRotationIdenticalBinPackingPlanEvaluator<D, B, I>
+  public abstract class BinUtilizationEvaluator<D, B, I> : EvaluatorBase<D, B, I>
     where D : class, IPackingPosition
     where B : PackingShape<D>
@@ -36 +36 @@
 
     [StorableConstructor]
-    protected BinUtilizationRegularIdenticalBinEvaluator(bool deserializing) : base(deserializing) { }
-    protected BinUtilizationRegularIdenticalBinEvaluator(BinUtilizationRegularIdenticalBinEvaluator<D, B, I> original, Cloner cloner)
+    protected BinUtilizationEvaluator(bool deserializing) : base(deserializing) { }
+    protected BinUtilizationEvaluator(BinUtilizationEvaluator<D, B, I> original, Cloner cloner)
       : base(original, cloner) {
     }
-    public BinUtilizationRegularIdenticalBinEvaluator() : base() { }
+    public BinUtilizationEvaluator() : base() { }
 
     protected override DoubleValue Evaluate() {
@@ -49 +49 @@
       ItemList<I> itemMeasures = PackingItemMeasuresParameter.ActualValue;
 
+      // TODO: check and remove code
 
       //Check if data is valid

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingPlanEvaluationAlgorithm.cs

@@ -44 +44 @@
       get { return PackingSolutionDecoderParameter; }
     }
-    public IValueLookupParameter<IPackingPlanEvaluator> PackingPlanEvaluatorParameter {
-      get { return (IValueLookupParameter<IPackingPlanEvaluator>)Parameters["PackingPlanEvaluator"]; }
+    public IValueLookupParameter<IEvaluator> PackingPlanEvaluatorParameter {
+      get { return (IValueLookupParameter<IEvaluator>)Parameters["PackingPlanEvaluator"]; }
     }
-    ILookupParameter<IPackingPlanEvaluator> IPackingPlanEvaluationAlgorithm.PackingPlanEvaluatorParameter {
+    ILookupParameter<IEvaluator> IPackingPlanEvaluationAlgorithm.PackingPlanEvaluatorParameter {
       get { return PackingPlanEvaluatorParameter; }
     }
@@ -62 +62 @@
       : base() {
         Parameters.Add(new ValueLookupParameter<IPackingSolutionDecoder>("PackingSolutionDecoder", "The decoding operator that is used to calculate a packing plan from the used representation."));
-        Parameters.Add(new ValueLookupParameter<IPackingPlanEvaluator>("PackingPlanEvaluator", "The actual packing plan evaluation operator."));
+        Parameters.Add(new ValueLookupParameter<IEvaluator>("PackingPlanEvaluator", "The actual packing plan evaluation operator."));
         Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value aka fitness value of the solution."));
         QualityParameter.Hidden = true;

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingPlanEvaluator.cs

@@ -27 +27 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Data;
-
+using HeuristicLab.Collections;
 
 namespace HeuristicLab.Problems.BinPacking {
   [Item("Packingplan Evaluator", "Represents a evaluator class for standard bin-packing problems.")]
   [StorableClass]
-  public abstract class PackingPlanEvaluator<D,B,I> : SingleSuccessorOperator, IPackingPlanEvaluator
+  public abstract class EvaluatorBase<D,B,I> : SingleSuccessorOperator, IEvaluator
     where D : class, IPackingPosition
     where B : PackingShape<D>
@@ -52 +52 @@
       get { return (ILookupParameter<IPackingPlan>)Parameters["PackingPlan"]; }
     }
+    public ILookupParameter<ItemList<I>> PackingItemMeasuresParameter {
+      get { return (ILookupParameter<ItemList<I>>)Parameters["PackingItemMeasures"]; }
+    }
+    public ILookupParameter<B> PackingBinMeasuresParameter {
+      get { return (ILookupParameter<B>)Parameters["PackingBinMeasures"]; }
+    }
     #endregion
 
     [StorableConstructor]
-    protected PackingPlanEvaluator(bool deserializing) : base(deserializing) { }
-    protected PackingPlanEvaluator(PackingPlanEvaluator<D,B,I> original, Cloner cloner)
+    protected EvaluatorBase(bool deserializing) : base(deserializing) { }
+    protected EvaluatorBase(EvaluatorBase<D,B,I> original, Cloner cloner)
       : base(original, cloner) {
     }
-    public PackingPlanEvaluator()
+    public EvaluatorBase()
       : base() {
-      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value aka fitness value of the solution."));
+      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value of the solution."));
       Parameters.Add(new LookupParameter<IPackingPlan>("PackingPlan", "The decoded bin-packing solution represented as generalized packing-plan."));
       Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
+      Parameters.Add(new LookupParameter<ItemList<I>>("PackingItemMeasures", "Packing-item data taken from the bin-packing problem-instance."));
+      Parameters.Add(new LookupParameter<B>("PackingBinMeasures", "Packing-bin data taken from the bin-packing problem-instance."));
+
     }
-
 
     protected abstract DoubleValue Evaluate();                                                                        
@@ -73 +81 @@
     }
 
+    protected bool HasOverlappingOrNotContainedItems(ObservableDictionary<int, D> positions, B binMeasure, ItemList<I> itemMeasures, int nrOfBins) {
+      //TODO: Optimize performance by removing unnecessary allocations..
+      for (int i = 0; i < itemMeasures.Count; i++) {
+        I packingItem = itemMeasures[i];
+        D currentPosition = positions[i];
+        if (!binMeasure.Encloses(currentPosition, packingItem))
+          return true;
+
+        for (int j = 0; j < itemMeasures.Count; j++) {
+          D checkedPosition = positions[j];
+          if (i != j && currentPosition.AssignedBin == checkedPosition.AssignedBin) {
+            I checkedItem = itemMeasures[j];
+            if (packingItem.Overlaps(currentPosition, checkedPosition, checkedItem))
+              return true;
+          }
+        }
+      }
+      return false;
+    }
   }
 }

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingRatioEvaluator.cs

@@ -28 +28 @@
 
 namespace HeuristicLab.Problems.BinPacking {
-  [Item("Packing-Ratio Regular Identical-Bin Evaluator", "Represents an evaluation-algorithm for regular-shaped bin-packing problems with identical bins which calculates the ratio between packed and unpacked space. Found in Falkenauer:1996")]
   [StorableClass]
-  public abstract class PackingRatioRegularIdenticalBinEvaluator<D, B, I> : RegularSimpleRotationIdenticalBinPackingPlanEvaluator<D, B, I>
+  public abstract class PackingRatioEvaluator<D, B, I> : EvaluatorBase<D, B, I>
     where D : class, IPackingPosition
     where B : PackingShape<D>
@@ -36 +35 @@
 
     [StorableConstructor]
-    protected PackingRatioRegularIdenticalBinEvaluator(bool deserializing) : base(deserializing) { }
-    protected PackingRatioRegularIdenticalBinEvaluator(PackingRatioRegularIdenticalBinEvaluator<D, B, I> original, Cloner cloner)
+    protected PackingRatioEvaluator(bool deserializing) : base(deserializing) { }
+    protected PackingRatioEvaluator(PackingRatioEvaluator<D, B, I> original, Cloner cloner)
       : base(original, cloner) {
     }
-    public PackingRatioRegularIdenticalBinEvaluator() : base() { }
+    public PackingRatioEvaluator() : base() { }
 
     protected override DoubleValue Evaluate() {

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/RegularSimpleRotationIdenticalBinPackingPlanEvaluator.cs

@@ -54 +54 @@
     }
 
-
-
-
     protected bool HasOverlappingOrNotContainedItems(ObservableDictionary<int, D> positions, B binMeasure, ItemList<I> itemMeasures, int nrOfBins) {
       //TODO: Optimize performance by removing unnecessary allocations..
@@ -73 +70 @@
           }
         }
-
       }
-
       return false;
     }

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

@@ -254 +254 @@
     <Compile Include="Evaluators\PackingPlanEvaluationAlgorithm.cs" />
     <Compile Include="Evaluators\PackingPlanEvaluator.cs" />
-    <Compile Include="Evaluators\PackingRatioRegularIdenticalBinEvaluator.cs" />
-    <Compile Include="Evaluators\RegularSimpleRotationIdenticalBinPackingPlanEvaluator.cs" />
+    <Compile Include="Evaluators\PackingRatioEvaluator.cs" />
     <Compile Include="Instances\BPPData.cs" />
     <Compile Include="Instances\BPPInstanceProvider.cs" />

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Interfaces/IPackingPlanEvaluationAlgorithm.cs

@@ -26 +26 @@
   public interface IPackingPlanEvaluationAlgorithm : ISingleObjectiveEvaluator {
     ILookupParameter<IPackingSolutionDecoder> PackingSolutionDecoderParameter { get; }
-    ILookupParameter<IPackingPlanEvaluator> PackingPlanEvaluatorParameter { get; }
+    ILookupParameter<IEvaluator> PackingPlanEvaluatorParameter { get; }
   }
 }

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Interfaces/IPackingPlanEvaluator.cs

@@ -24 +24 @@
 
 namespace HeuristicLab.Problems.BinPacking {
-  public interface IPackingPlanEvaluator : ISingleObjectiveEvaluator {
+  public interface IEvaluator : ISingleObjectiveEvaluator {
      ILookupParameter<IPackingPlan> PackingPlanParameter { get; }
   }

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/PackingMoveEvaluator.cs

@@ -55 +55 @@
       get { return (IValueLookupParameter<IPackingSolutionDecoder>)Parameters["PackingSolutionDecoder"]; }
     }
-    public IValueLookupParameter<IPackingPlanEvaluator> PackingPlanEvaluatorParameter {
-      get { return (IValueLookupParameter<IPackingPlanEvaluator>)Parameters["PackingPlanEvaluator"]; }
+    public IValueLookupParameter<IEvaluator> PackingPlanEvaluatorParameter {
+      get { return (IValueLookupParameter<IEvaluator>)Parameters["PackingPlanEvaluator"]; }
     }
     protected ScopeParameter CurrentScopeParameter {
@@ -75 +75 @@
       Parameters.Add(new LookupParameter<B>("PackingBinMeasures", "Packing-bin data taken from the bin-packing problem-instance."));
       Parameters.Add(new ValueLookupParameter<IPackingSolutionDecoder>("PackingSolutionDecoder", "The decoding operator that is used to calculate a packing plan from the used representation."));
-      Parameters.Add(new ValueLookupParameter<IPackingPlanEvaluator>("PackingPlanEvaluator", "The actual packing plan evaluation operator."));
+      Parameters.Add(new ValueLookupParameter<IEvaluator>("PackingPlanEvaluator", "The actual packing plan evaluation operator."));
       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope where the decoded solution should be added to."));
       Parameters.Add(new LookupParameter<IPackingMove>("PackingMove", "The move to evaluate."));
@@ -93 +93 @@
       CurrentScopeParameter.ActualValue.Variables.Add(new Variable("PackingPlanAfterMove", packingPlan));
 
-      DoubleValue quality = PackingRatioRegularIdenticalBinEvaluator<D, B, I>.CalculatePackingRatio(packingPlan);
+      DoubleValue quality = PackingRatioEvaluator<D, B, I>.CalculatePackingRatio(packingPlan);
 
       double moveQuality = quality.Value;

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Problem.cs

@@ -55 +55 @@
       get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
     }
-    public ValueParameter<IPackingPlanEvaluator> PackingPlanEvaluatorParameter {
-      get { return (ValueParameter<IPackingPlanEvaluator>)Parameters["PackingPlanEvaluator"]; }
+    public ValueParameter<IEvaluator> PackingPlanEvaluatorParameter {
+      get { return (ValueParameter<IEvaluator>)Parameters["PackingPlanEvaluator"]; }
     }
     public IValueParameter<B> PackingBinMeasuresParameter {
@@ -75 +75 @@
       set { PackingItemMeasuresParameter.Value = value; } 
     }
-    public IPackingPlanEvaluator PackingPlanEvaluator {
+    public IEvaluator PackingPlanEvaluator {
       get { return PackingPlanEvaluatorParameter.Value; }
       set { PackingPlanEvaluatorParameter.Value = value; }
@@ -106 +106 @@
       Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "The lower possible number of bins needed to solve this problem (taken from Dell'Amico, Martello and Vigo; 2002)", new IntValue()));
       Parameters.Add(new ValueParameter<B>("PackingBinMeasures", "Packing-bin data defining the measures of the used bins.", new B()));
-      Parameters.Add(new ValueParameter<IPackingPlanEvaluator>("PackingPlanEvaluator", "The evaluator is used to determine the quality of a solution.", CreateDefaultEvaluator()));
+      Parameters.Add(new ValueParameter<IEvaluator>("PackingPlanEvaluator", "The evaluator is used to determine the quality of a solution.", CreateDefaultEvaluator()));
       Parameters.Add(new ConstrainedValueParameter<IPackingSolutionDecoder>("PackingSolutionDecoder", "The operator that decodes the representation and creates a packing plan."));
       this.Maximization.Value = true;
@@ -142 +142 @@
     protected abstract void RemoveTooBigItems();
     protected abstract void InitializeProblemData();
-    protected abstract IPackingPlanEvaluator CreateDefaultEvaluator();
+    protected abstract IEvaluator CreateDefaultEvaluator();
     protected void ApplyHorizontalOrientation() {
       PackingBinMeasures.ApplyHorizontalOrientation();