Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/HeuristicLab.Problems.BinPacking2D-3.3.csproj
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/HeuristicLab.Problems.BinPacking2D-3.3.csproj (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/HeuristicLab.Problems.BinPacking2D-3.3.csproj (revision 14050)
@@ -174,5 +174,5 @@
-
+
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingRatioEvaluator.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingRatioEvaluator.cs (revision 14050)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingRatioEvaluator.cs (revision 14050)
@@ -0,0 +1,43 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see .
+ */
+#endregion
+
+
+using HeuristicLab.Core;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.BinPacking;
+
+namespace HeuristicLab.Problems.BinPacking2D {
+ [Item("Packing-Ratio Evaluator (2d)", "Calculates the ratio between packed and unpacked space. Found in Falkenauer:1996")]
+ [StorableClass]
+ public class PackingRatioEvaluator : PackingRatioEvaluator {
+
+ [StorableConstructor]
+ protected PackingRatioEvaluator (bool deserializing) : base(deserializing) { }
+ protected PackingRatioEvaluator (PackingRatioEvaluator original, Cloner cloner)
+ : base(original, cloner) {
+ }
+ public PackingRatioEvaluator() : base() { }
+ public override IDeepCloneable Clone(Cloner cloner) {
+ return new PackingRatioEvaluator(this, cloner);
+ }
+ }
+}
Index: anches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingRatioRectangularIdenticalBinEvaluator.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingRatioRectangularIdenticalBinEvaluator.cs (revision 14049)
+++ (revision )
@@ -1,43 +1,0 @@
-#region License Information
-/* HeuristicLab
- * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
- *
- * This file is part of HeuristicLab.
- *
- * HeuristicLab is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * HeuristicLab is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with HeuristicLab. If not, see .
- */
-#endregion
-
-
-using HeuristicLab.Core;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.BinPacking;
-
-namespace HeuristicLab.Problems.BinPacking2D {
- [Item("Packing-Ratio Rectangular Identical-Bin Evaluator", "Represents an evaluation-algorithm for rectangular-shaped bin-packing problems with identical bins which calculates the ratio between packed and unpacked space. Found in Falkenauer:1996")]
- [StorableClass]
- public class PackingRatioRectangularIdenticalBinEvaluator : PackingRatioRegularIdenticalBinEvaluator {
-
- [StorableConstructor]
- protected PackingRatioRectangularIdenticalBinEvaluator (bool deserializing) : base(deserializing) { }
- protected PackingRatioRectangularIdenticalBinEvaluator (PackingRatioRectangularIdenticalBinEvaluator original, Cloner cloner)
- : base(original, cloner) {
- }
- public PackingRatioRectangularIdenticalBinEvaluator() : base() { }
- public override IDeepCloneable Clone(Cloner cloner) {
- return new PackingRatioRectangularIdenticalBinEvaluator(this, cloner);
- }
- }
-}
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/Problem.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/Problem.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/Problem.cs (revision 14050)
@@ -164,6 +164,6 @@
}
- protected override IPackingPlanEvaluator CreateDefaultEvaluator() {
- return new PackingRatioRectangularIdenticalBinEvaluator();
+ protected override IEvaluator CreateDefaultEvaluator() {
+ return new PackingRatioEvaluator();
}
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/HeuristicLab.Problems.BinPacking3D-3.3.csproj
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/HeuristicLab.Problems.BinPacking3D-3.3.csproj (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/HeuristicLab.Problems.BinPacking3D-3.3.csproj (revision 14050)
@@ -174,5 +174,5 @@
-
+
Index: anches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/PackingRatioCuboidIdenticalBinEvaluator.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/PackingRatioCuboidIdenticalBinEvaluator.cs (revision 14049)
+++ (revision )
@@ -1,42 +1,0 @@
-#region License Information
-/* HeuristicLab
- * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
- *
- * This file is part of HeuristicLab.
- *
- * HeuristicLab is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * HeuristicLab is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with HeuristicLab. If not, see .
- */
-#endregion
-
-using HeuristicLab.Core;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.BinPacking;
-
-namespace HeuristicLab.Problems.BinPacking3D {
- [Item("Packing-Ratio Cuboid Identical-Bin Evaluator", "Represents an evaluation-algorithm for cuboid-shaped bin-packing problems with identical bins which calculates the ratio between packed and unpacked space. Found in Falkenauer:1996")]
- [StorableClass]
- public class PackingRatioCuboidIdenticalBinEvaluator : PackingRatioRegularIdenticalBinEvaluator {
-
- [StorableConstructor]
- protected PackingRatioCuboidIdenticalBinEvaluator(bool deserializing) : base(deserializing) { }
- protected PackingRatioCuboidIdenticalBinEvaluator(PackingRatioCuboidIdenticalBinEvaluator original, Cloner cloner)
- : base(original, cloner) {
- }
- public PackingRatioCuboidIdenticalBinEvaluator() : base() { }
- public override IDeepCloneable Clone(Cloner cloner) {
- return new PackingRatioCuboidIdenticalBinEvaluator(this, cloner);
- }
- }
-}
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/PackingRatioEvaluator.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/PackingRatioEvaluator.cs (revision 14050)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/PackingRatioEvaluator.cs (revision 14050)
@@ -0,0 +1,42 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see .
+ */
+#endregion
+
+using HeuristicLab.Core;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.BinPacking;
+
+namespace HeuristicLab.Problems.BinPacking3D {
+ [Item("Packing-Ratio Evaluator (3d)", "Calculates the ratio between packed and unpacked space. Found in Falkenauer:1996")]
+ [StorableClass]
+ public class PackingRatioEvaluator : PackingRatioEvaluator {
+
+ [StorableConstructor]
+ protected PackingRatioEvaluator(bool deserializing) : base(deserializing) { }
+ protected PackingRatioEvaluator(PackingRatioEvaluator original, Cloner cloner)
+ : base(original, cloner) {
+ }
+ public PackingRatioEvaluator() : base() { }
+ public override IDeepCloneable Clone(Cloner cloner) {
+ return new PackingRatioEvaluator(this, cloner);
+ }
+ }
+}
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Problem.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Problem.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Problem.cs (revision 14050)
@@ -168,6 +168,6 @@
}
- protected override IPackingPlanEvaluator CreateDefaultEvaluator() {
- return new PackingRatioCuboidIdenticalBinEvaluator();
+ protected override IEvaluator CreateDefaultEvaluator() {
+ return new PackingRatioEvaluator();
}
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Analyzers/BestBinPackingSolutionAnalyzer.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Analyzers/BestBinPackingSolutionAnalyzer.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Analyzers/BestBinPackingSolutionAnalyzer.cs (revision 14050)
@@ -93,5 +93,5 @@
}
string binUtilKey = "Overall Bin Utilization";
- DoubleValue binUtil = BinUtilizationRegularIdenticalBinEvaluator.CalculateBinUtilization(bestSolution);
+ DoubleValue binUtil = BinUtilizationEvaluator.CalculateBinUtilization(bestSolution);
if (!results.ContainsKey(binUtilKey))
results.Add(new Result(binUtilKey, binUtil));
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs (revision 14050)
@@ -37,5 +37,5 @@
[Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")]
[StorableClass]
- public abstract class PackingPlan :Item, IPackingPlan
+ public abstract class PackingPlan : Item, IPackingPlan
where D : class, IPackingPosition
where B : PackingShape
@@ -77,23 +77,23 @@
protected PackingPlan(B binMeasures, bool useExtremePoints, bool stackingConstraints)
- : base(){
- BinMeasures = (B)binMeasures.Clone();
- StackingConstraints = stackingConstraints;
- UseExtremePoints = useExtremePoints;
- BinPackings = new ObservableList>();
+ : base() {
+ BinMeasures = (B)binMeasures.Clone();
+ StackingConstraints = stackingConstraints;
+ UseExtremePoints = useExtremePoints;
+ BinPackings = new ObservableList>();
}
[StorableConstructor]
protected PackingPlan(bool deserializing) : base(deserializing) { }
- protected PackingPlan(PackingPlan original, Cloner cloner)
+ protected PackingPlan(PackingPlan original, Cloner cloner)
: base(original, cloner) {
- this.BinPackings = new ObservableList>(original.BinPackings);
- }
-
+ this.BinPackings = new ObservableList>(original.BinPackings);
+ }
+
public abstract BinPacking NewBinPacking();
public void UpdateBinPackings() {
BinPackings.RemoveAll(x => x.ItemPositions.Count == 0);
- BinPackings = new ObservableList>(BinPackings.OrderByDescending (bp => bp.PackingDensity));
+ BinPackings = new ObservableList>(BinPackings.OrderByDescending(bp => bp.PackingDensity));
}
@@ -139,10 +139,10 @@
UpdateBinPackings();
- var newSolution = new ObservableDictionary> ();
+ var newSolution = new ObservableDictionary>();
foreach (var bp in BinPackings) {
int binIndex = newSolution.Count;
newSolution[binIndex] = new ItemList();
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,6 +167,6 @@
var temp = new List(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,5 +195,5 @@
binIndex++;
}
- solution.GroupingVector = new IntegerVector (newSolution);
+ solution.GroupingVector = new IntegerVector(newSolution);
}
public void Pack(PackingSequenceEncoding solution, ItemList itemMeasures) {
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/BinUtilizationRegularIdenticalBinEvaluator.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/BinUtilizationRegularIdenticalBinEvaluator.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/BinUtilizationRegularIdenticalBinEvaluator.cs (revision 14050)
@@ -28,7 +28,7 @@
namespace HeuristicLab.Problems.BinPacking {
- [Item("Bin-Utilization Regular Identical-Bin Evaluator", " Found in Lee:2010")]
+ [Item("Bin-Utilization Evaluator", " Found in Lee:2010")] // TODO
[StorableClass]
- public abstract class BinUtilizationRegularIdenticalBinEvaluator : RegularSimpleRotationIdenticalBinPackingPlanEvaluator
+ public abstract class BinUtilizationEvaluator : EvaluatorBase
where D : class, IPackingPosition
where B : PackingShape
@@ -36,9 +36,9 @@
[StorableConstructor]
- protected BinUtilizationRegularIdenticalBinEvaluator(bool deserializing) : base(deserializing) { }
- protected BinUtilizationRegularIdenticalBinEvaluator(BinUtilizationRegularIdenticalBinEvaluator original, Cloner cloner)
+ protected BinUtilizationEvaluator(bool deserializing) : base(deserializing) { }
+ protected BinUtilizationEvaluator(BinUtilizationEvaluator original, Cloner cloner)
: base(original, cloner) {
}
- public BinUtilizationRegularIdenticalBinEvaluator() : base() { }
+ public BinUtilizationEvaluator() : base() { }
protected override DoubleValue Evaluate() {
@@ -49,4 +49,5 @@
ItemList itemMeasures = PackingItemMeasuresParameter.ActualValue;
+ // TODO: check and remove code
//Check if data is valid
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingPlanEvaluationAlgorithm.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingPlanEvaluationAlgorithm.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingPlanEvaluationAlgorithm.cs (revision 14050)
@@ -44,8 +44,8 @@
get { return PackingSolutionDecoderParameter; }
}
- public IValueLookupParameter PackingPlanEvaluatorParameter {
- get { return (IValueLookupParameter)Parameters["PackingPlanEvaluator"]; }
+ public IValueLookupParameter PackingPlanEvaluatorParameter {
+ get { return (IValueLookupParameter)Parameters["PackingPlanEvaluator"]; }
}
- ILookupParameter IPackingPlanEvaluationAlgorithm.PackingPlanEvaluatorParameter {
+ ILookupParameter IPackingPlanEvaluationAlgorithm.PackingPlanEvaluatorParameter {
get { return PackingPlanEvaluatorParameter; }
}
@@ -62,5 +62,5 @@
: base() {
Parameters.Add(new ValueLookupParameter("PackingSolutionDecoder", "The decoding operator that is used to calculate a packing plan from the used representation."));
- Parameters.Add(new ValueLookupParameter("PackingPlanEvaluator", "The actual packing plan evaluation operator."));
+ Parameters.Add(new ValueLookupParameter("PackingPlanEvaluator", "The actual packing plan evaluation operator."));
Parameters.Add(new LookupParameter("Quality", "The quality value aka fitness value of the solution."));
QualityParameter.Hidden = true;
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingPlanEvaluator.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingPlanEvaluator.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingPlanEvaluator.cs (revision 14050)
@@ -27,10 +27,10 @@
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 : SingleSuccessorOperator, IPackingPlanEvaluator
+ public abstract class EvaluatorBase : SingleSuccessorOperator, IEvaluator
where D : class, IPackingPosition
where B : PackingShape
@@ -52,18 +52,26 @@
get { return (ILookupParameter)Parameters["PackingPlan"]; }
}
+ public ILookupParameter> PackingItemMeasuresParameter {
+ get { return (ILookupParameter>)Parameters["PackingItemMeasures"]; }
+ }
+ public ILookupParameter PackingBinMeasuresParameter {
+ get { return (ILookupParameter)Parameters["PackingBinMeasures"]; }
+ }
#endregion
[StorableConstructor]
- protected PackingPlanEvaluator(bool deserializing) : base(deserializing) { }
- protected PackingPlanEvaluator(PackingPlanEvaluator original, Cloner cloner)
+ protected EvaluatorBase(bool deserializing) : base(deserializing) { }
+ protected EvaluatorBase(EvaluatorBase original, Cloner cloner)
: base(original, cloner) {
}
- public PackingPlanEvaluator()
+ public EvaluatorBase()
: base() {
- Parameters.Add(new LookupParameter("Quality", "The quality value aka fitness value of the solution."));
+ Parameters.Add(new LookupParameter("Quality", "The quality value of the solution."));
Parameters.Add(new LookupParameter("PackingPlan", "The decoded bin-packing solution represented as generalized packing-plan."));
Parameters.Add(new LookupParameter("Random", "The pseudo random number generator."));
+ Parameters.Add(new LookupParameter>("PackingItemMeasures", "Packing-item data taken from the bin-packing problem-instance."));
+ Parameters.Add(new LookupParameter("PackingBinMeasures", "Packing-bin data taken from the bin-packing problem-instance."));
+
}
-
protected abstract DoubleValue Evaluate();
@@ -73,4 +81,23 @@
}
+ protected bool HasOverlappingOrNotContainedItems(ObservableDictionary positions, B binMeasure, ItemList 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;
+ }
}
}
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingRatioEvaluator.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingRatioEvaluator.cs (revision 14050)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingRatioEvaluator.cs (revision 14050)
@@ -0,0 +1,100 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see .
+ */
+#endregion
+
+
+using HeuristicLab.Core;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+using HeuristicLab.Common;
+using HeuristicLab.Encodings.PackingEncoding;
+
+namespace HeuristicLab.Problems.BinPacking {
+ [StorableClass]
+ public abstract class PackingRatioEvaluator : EvaluatorBase
+ where D : class, IPackingPosition
+ where B : PackingShape
+ where I : PackingShape, IPackingItem {
+
+ [StorableConstructor]
+ protected PackingRatioEvaluator(bool deserializing) : base(deserializing) { }
+ protected PackingRatioEvaluator(PackingRatioEvaluator original, Cloner cloner)
+ : base(original, cloner) {
+ }
+ public PackingRatioEvaluator() : base() { }
+
+ protected override DoubleValue Evaluate() {
+ DoubleValue quality = new DoubleValue(0);
+
+ IPackingPlan plan = PackingPlanParameter.ActualValue;
+ B binMeasure = PackingBinMeasuresParameter.ActualValue;
+ ItemList itemMeasures = PackingItemMeasuresParameter.ActualValue;
+
+
+ //Check if data is valid
+ //if (plan.PackingItemPositions.Count != itemMeasures.Count)
+ // throw new Exception("ERROR: ItemMeasures.count does not match packingPosition.count");
+
+
+ ////Check if any items are overlapping or not contained in their bins
+ //bool itemPositionsAreValid = !HasOverlappingOrNotContainedItems(plan.PackingItemPositions, binMeasure, itemMeasures, nrOfBins);
+
+
+
+ //if (itemPositionsAreValid)
+ return CalculatePackingRatio(plan as PackingPlan);
+
+ //return quality;
+ }
+
+ /*
+ Falkenauer:1996 - A Hybrid Grouping Genetic Algorithm for Bin Packing
+
+ fBPP = (SUM[i=1..N](Fi / C)^k)/N
+ N.......the number of bins used in the solution,
+ Fi......the sum of sizes of the items in the bin i (the fill of the bin),
+ C.......the bin capacity and
+ k.......a constant, k>1.
+ */
+ public static DoubleValue CalculatePackingRatio(PackingPlan plan) {
+ int nrOfBins = plan.NrOfBins;
+ double result = 0;
+
+ //C
+ //double usableSpace = binMeasure.MultipliedMeasures;
+ //nrOfBins = N
+ for (int i = 0; i < nrOfBins; i++) {
+ //C
+ //double usableSpace = plan.GetPackingBinMeasuresForBinNr(0).MultipliedMeasures;//plan.GetPackingBinMeasuresForBinNr(i).MultipliedMeasures;
+ //var indexes = plan.PackingItemPositions.Select((Value, Index) => new { Value, Index }).Where(s => s.Value.Value.AssignedBin == i).Select(s => s.Index);
+ //var packedItemsInThisBin = plan.PackingItemMeasures.Select((Value, Index) => new { Value, Index }).Where(s => indexes.Contains(s.Index));
+ //Fi
+ //double usedSpaceInThisBin = packedItemsInThisBin.Select(s => s.Value.MultipliedMeasures).Sum();
+ //k = 2 --> (Fi/C)*(Fi/C)
+ //result += (((usedSpaceInThisBin) / (usableSpace)) * ((usedSpaceInThisBin) / (usableSpace))) / (i*i + 1);
+ var PD = plan.BinPackings[i].PackingDensity;
+ result += (PD * PD) / (i + 1);
+ }
+
+ result = result / nrOfBins;
+ return new DoubleValue(result);
+ }
+ }
+}
Index: anches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingRatioRegularIdenticalBinEvaluator.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/PackingRatioRegularIdenticalBinEvaluator.cs (revision 14049)
+++ (revision )
@@ -1,101 +1,0 @@
-#region License Information
-/* HeuristicLab
- * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
- *
- * This file is part of HeuristicLab.
- *
- * HeuristicLab is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * HeuristicLab is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with HeuristicLab. If not, see .
- */
-#endregion
-
-
-using HeuristicLab.Core;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Data;
-using HeuristicLab.Common;
-using HeuristicLab.Encodings.PackingEncoding;
-
-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 : RegularSimpleRotationIdenticalBinPackingPlanEvaluator
- where D : class, IPackingPosition
- where B : PackingShape
- where I : PackingShape, IPackingItem {
-
- [StorableConstructor]
- protected PackingRatioRegularIdenticalBinEvaluator(bool deserializing) : base(deserializing) { }
- protected PackingRatioRegularIdenticalBinEvaluator(PackingRatioRegularIdenticalBinEvaluator original, Cloner cloner)
- : base(original, cloner) {
- }
- public PackingRatioRegularIdenticalBinEvaluator() : base() { }
-
- protected override DoubleValue Evaluate() {
- DoubleValue quality = new DoubleValue(0);
-
- IPackingPlan plan = PackingPlanParameter.ActualValue;
- B binMeasure = PackingBinMeasuresParameter.ActualValue;
- ItemList itemMeasures = PackingItemMeasuresParameter.ActualValue;
-
-
- //Check if data is valid
- //if (plan.PackingItemPositions.Count != itemMeasures.Count)
- // throw new Exception("ERROR: ItemMeasures.count does not match packingPosition.count");
-
-
- ////Check if any items are overlapping or not contained in their bins
- //bool itemPositionsAreValid = !HasOverlappingOrNotContainedItems(plan.PackingItemPositions, binMeasure, itemMeasures, nrOfBins);
-
-
-
- //if (itemPositionsAreValid)
- return CalculatePackingRatio(plan as PackingPlan);
-
- //return quality;
- }
-
- /*
- Falkenauer:1996 - A Hybrid Grouping Genetic Algorithm for Bin Packing
-
- fBPP = (SUM[i=1..N](Fi / C)^k)/N
- N.......the number of bins used in the solution,
- Fi......the sum of sizes of the items in the bin i (the fill of the bin),
- C.......the bin capacity and
- k.......a constant, k>1.
- */
- public static DoubleValue CalculatePackingRatio(PackingPlan plan) {
- int nrOfBins = plan.NrOfBins;
- double result = 0;
-
- //C
- //double usableSpace = binMeasure.MultipliedMeasures;
- //nrOfBins = N
- for (int i = 0; i < nrOfBins; i++) {
- //C
- //double usableSpace = plan.GetPackingBinMeasuresForBinNr(0).MultipliedMeasures;//plan.GetPackingBinMeasuresForBinNr(i).MultipliedMeasures;
- //var indexes = plan.PackingItemPositions.Select((Value, Index) => new { Value, Index }).Where(s => s.Value.Value.AssignedBin == i).Select(s => s.Index);
- //var packedItemsInThisBin = plan.PackingItemMeasures.Select((Value, Index) => new { Value, Index }).Where(s => indexes.Contains(s.Index));
- //Fi
- //double usedSpaceInThisBin = packedItemsInThisBin.Select(s => s.Value.MultipliedMeasures).Sum();
- //k = 2 --> (Fi/C)*(Fi/C)
- //result += (((usedSpaceInThisBin) / (usableSpace)) * ((usedSpaceInThisBin) / (usableSpace))) / (i*i + 1);
- var PD = plan.BinPackings[i].PackingDensity;
- result += (PD * PD) / (i + 1);
- }
-
- result = result / nrOfBins;
- return new DoubleValue(result);
- }
- }
-}
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/RegularSimpleRotationIdenticalBinPackingPlanEvaluator.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/RegularSimpleRotationIdenticalBinPackingPlanEvaluator.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Evaluators/RegularSimpleRotationIdenticalBinPackingPlanEvaluator.cs (revision 14050)
@@ -54,7 +54,4 @@
}
-
-
-
protected bool HasOverlappingOrNotContainedItems(ObservableDictionary positions, B binMeasure, ItemList itemMeasures, int nrOfBins) {
//TODO: Optimize performance by removing unnecessary allocations..
@@ -73,7 +70,5 @@
}
}
-
}
-
return false;
}
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj (revision 14050)
@@ -254,6 +254,5 @@
-
-
+
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Interfaces/IPackingPlanEvaluationAlgorithm.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Interfaces/IPackingPlanEvaluationAlgorithm.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Interfaces/IPackingPlanEvaluationAlgorithm.cs (revision 14050)
@@ -26,5 +26,5 @@
public interface IPackingPlanEvaluationAlgorithm : ISingleObjectiveEvaluator {
ILookupParameter PackingSolutionDecoderParameter { get; }
- ILookupParameter PackingPlanEvaluatorParameter { get; }
+ ILookupParameter PackingPlanEvaluatorParameter { get; }
}
}
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Interfaces/IPackingPlanEvaluator.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Interfaces/IPackingPlanEvaluator.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Interfaces/IPackingPlanEvaluator.cs (revision 14050)
@@ -24,5 +24,5 @@
namespace HeuristicLab.Problems.BinPacking {
- public interface IPackingPlanEvaluator : ISingleObjectiveEvaluator {
+ public interface IEvaluator : ISingleObjectiveEvaluator {
ILookupParameter PackingPlanParameter { get; }
}
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/PackingMoveEvaluator.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/PackingMoveEvaluator.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/PackingMoveEvaluator.cs (revision 14050)
@@ -55,6 +55,6 @@
get { return (IValueLookupParameter)Parameters["PackingSolutionDecoder"]; }
}
- public IValueLookupParameter PackingPlanEvaluatorParameter {
- get { return (IValueLookupParameter)Parameters["PackingPlanEvaluator"]; }
+ public IValueLookupParameter PackingPlanEvaluatorParameter {
+ get { return (IValueLookupParameter)Parameters["PackingPlanEvaluator"]; }
}
protected ScopeParameter CurrentScopeParameter {
@@ -75,5 +75,5 @@
Parameters.Add(new LookupParameter("PackingBinMeasures", "Packing-bin data taken from the bin-packing problem-instance."));
Parameters.Add(new ValueLookupParameter("PackingSolutionDecoder", "The decoding operator that is used to calculate a packing plan from the used representation."));
- Parameters.Add(new ValueLookupParameter("PackingPlanEvaluator", "The actual packing plan evaluation operator."));
+ Parameters.Add(new ValueLookupParameter("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("PackingMove", "The move to evaluate."));
@@ -93,5 +93,5 @@
CurrentScopeParameter.ActualValue.Variables.Add(new Variable("PackingPlanAfterMove", packingPlan));
- DoubleValue quality = PackingRatioRegularIdenticalBinEvaluator.CalculatePackingRatio(packingPlan);
+ DoubleValue quality = PackingRatioEvaluator.CalculatePackingRatio(packingPlan);
double moveQuality = quality.Value;
Index: /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Problem.cs
===================================================================
--- /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Problem.cs (revision 14049)
+++ /branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Problem.cs (revision 14050)
@@ -55,6 +55,6 @@
get { return (IFixedValueParameter)Parameters["LowerBound"]; }
}
- public ValueParameter PackingPlanEvaluatorParameter {
- get { return (ValueParameter)Parameters["PackingPlanEvaluator"]; }
+ public ValueParameter PackingPlanEvaluatorParameter {
+ get { return (ValueParameter)Parameters["PackingPlanEvaluator"]; }
}
public IValueParameter PackingBinMeasuresParameter {
@@ -75,5 +75,5 @@
set { PackingItemMeasuresParameter.Value = value; }
}
- public IPackingPlanEvaluator PackingPlanEvaluator {
+ public IEvaluator PackingPlanEvaluator {
get { return PackingPlanEvaluatorParameter.Value; }
set { PackingPlanEvaluatorParameter.Value = value; }
@@ -106,5 +106,5 @@
Parameters.Add(new FixedValueParameter("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("PackingBinMeasures", "Packing-bin data defining the measures of the used bins.", new B()));
- Parameters.Add(new ValueParameter("PackingPlanEvaluator", "The evaluator is used to determine the quality of a solution.", CreateDefaultEvaluator()));
+ Parameters.Add(new ValueParameter("PackingPlanEvaluator", "The evaluator is used to determine the quality of a solution.", CreateDefaultEvaluator()));
Parameters.Add(new ConstrainedValueParameter("PackingSolutionDecoder", "The operator that decodes the representation and creates a packing plan."));
this.Maximization.Value = true;
@@ -142,5 +142,5 @@
protected abstract void RemoveTooBigItems();
protected abstract void InitializeProblemData();
- protected abstract IPackingPlanEvaluator CreateDefaultEvaluator();
+ protected abstract IEvaluator CreateDefaultEvaluator();
protected void ApplyHorizontalOrientation() {
PackingBinMeasures.ApplyHorizontalOrientation();