Changeset 14146 for branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingSequenceProblem.cs

Timestamp:

07/21/16 10:19:55 (8 years ago)

Author:

gkronber

Message:

#1966: new implementation for 2d bin packing problem with permutation encoding

File:

• branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingSequenceProblem.cs (modified) (2 diffs)

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingSequenceProblem.cs

@@ -23 +23 @@
 
 using System;
-using System.CodeDom;
+using System.Collections.Generic;
 using System.Linq;
-using System.Text;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -31 +30 @@
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.BinPacking;
 using HeuristicLab.Problems.BinPacking2D;
+using HeuristicLab.Problems.Instances;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.BinPacking2d {
+  [Item("Bin Packing Problem (2D, permutation encoding) (BPP)", "Represents a two-dimensional bin-packing problem using only bins with identical measures and bins/items with rectangular shapes.")]
   [StorableClass]
   [Creatable(Category = CreatableAttribute.Categories.CombinatorialProblems, Priority = 300)]
-  public class PackingSequenceProblem : PackingSequenceProblem<Permutation, PermutationEncoding> {
+  public sealed class PackingSequenceProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<BPPData>, IProblemInstanceExporter<BPPData> {
+    private readonly string SolutionEvaluatorParameterName = "SolutionEvaluator";
+    #region Default Instance
+    private static readonly BPPData DefaultInstance = new BPPData() {
+      Name = "2D BPP Default Instance",
+      Description = "The default instance for 2D Bin Packing.",
+      BinShape = new PackingShape(20, 16),
+      Items = new PackingItem[] {
+        new PackingItem(3,  8, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
+        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0}
+      },
+    };
+    #endregion
+
+    #region parameter properties
+    public IValueParameter<IPermutationDecoder> DecoderParameter {
+      get { return (IValueParameter<IPermutationDecoder>)Parameters["Decoder"]; }
+    }
+    public IValueParameter<BinPacking2D.IEvaluator> SolutionEvaluatorParameter {
+      get { return (IValueParameter<BinPacking2D.IEvaluator>)Parameters[SolutionEvaluatorParameterName]; }
+    }
+    public IValueParameter<ReadOnlyItemList<PackingItem>> ItemsParameter {
+      get { return (IValueParameter<ReadOnlyItemList<PackingItem>>)Parameters["Items"]; }
+    }
+    public IValueParameter<PackingShape> BinShapeParameter {
+      get { return (IValueParameter<PackingShape>)Parameters["BinShape"]; }
+    }
+    public IValueParameter<Solution> BestKnownSolutionParameter {
+      get { return (IValueParameter<Solution>)Parameters["BestKnownSolution"]; }
+    }
+    public IFixedValueParameter<IntValue> LowerBoundParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
+    }
+    #endregion
+
+    #region properties
+    public IPermutationDecoder Decoder {
+      get { return DecoderParameter.Value; }
+      set { DecoderParameter.Value = value; }
+    }
+    public new BinPacking2D.IEvaluator SolutionEvaluator {
+      get { return SolutionEvaluatorParameter.Value; }
+      set { SolutionEvaluatorParameter.Value = value; }
+    }
+    public ReadOnlyItemList<PackingItem> Items {
+      get { return ItemsParameter.Value; }
+      set { ItemsParameter.Value = value; }
+    }
+    public PackingShape BinShape {
+      get { return BinShapeParameter.Value; }
+      set { BinShapeParameter.Value = value; }
+    }
+    public Solution BestKnownSolution {
+      get { return BestKnownSolutionParameter.Value; }
+      set { BestKnownSolutionParameter.Value = value; }
+    }
+    public int LowerBound {
+      get { return LowerBoundParameter.Value.Value; }
+    }
+    public int NumberOfItems {
+      get { return Items == null ? 0 : Items.Count; }
+    }
+    #endregion
 
     // persistence
     [StorableConstructor]
-    protected PackingSequenceProblem(bool deserializing) : base(deserializing) { }
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() { }
-
-    public override bool Maximization {
-      get { return true; }
-    }
-
+    private PackingSequenceProblem(bool deserializing) : base(deserializing) { }
 
     // cloning
-    protected PackingSequenceProblem(PackingSequenceProblem original, Cloner cloner)
+    private PackingSequenceProblem(PackingSequenceProblem original, Cloner cloner)
       : base(original, cloner) {
-    }
-
-    protected PackingSequenceProblem() : base() { }
-
-
+      RegisterEventHandlers();
+    }
+
+    public PackingSequenceProblem()
+      : base() {
+      var defaultEvaluator = new PackingRatioEvaluator();
+      var defaultDecoder = new ExtremePointPermutationDecoder();
+      Parameters.Add(new ValueParameter<IPermutationDecoder>("Decoder", "The decoder translates a permutation to a packing solution candidiates", defaultDecoder));
+      Parameters.Add(new ValueParameter<BinPacking2D.IEvaluator>(SolutionEvaluatorParameterName, "The evaluator calculates qualities of solution candidates", defaultEvaluator));
+      Parameters.Add(new ValueParameter<ReadOnlyItemList<PackingItem>>("Items", "The items which must be packed into bins"));
+      Parameters.Add(new ValueParameter<PackingShape>("BinShape", "The size of bins into which items must be packed"));
+      Parameters.Add(new OptionalValueParameter<Solution>("BestKnownSolution", "The best solution found so far"));
+      Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "A lower bound for the number of bins that is necessary to pack all items"));
+
+      Load(DefaultInstance);
+
+      Encoding = new PermutationEncoding("PackingSequence", Items.Count, PermutationTypes.Absolute);
+      AddOperators();
+      RegisterEventHandlers();
+    }
     public override IDeepCloneable Clone(Cloner cloner) {
       return new PackingSequenceProblem(this, cloner);
     }
 
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      RegisterEventHandlers();
+    }
+
+
+    private void AddOperators() {
+      Operators.Add(new StochasticInsertionMultiMoveGenerator());
+      Operators.Add(new ExhaustiveInsertionMoveGenerator());
+      Operators.Add(new TranslocationMoveMaker());
+      Operators.Add(new TranslocationMoveEvaluator());
+      Operators.Add(new TranslocationMoveTabuMaker());
+
+      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
+      Operators.RemoveAll(x => x is SingleObjectiveMoveMaker);
+      Operators.RemoveAll(x => x is SingleObjectiveMoveEvaluator);
+
+      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
+    }
+
+    private void RegisterEventHandlers() {
+      // update encoding length when number of items is changed
+      ItemsParameter.ValueChanged += (sender, args) => Encoding.Length = Items.Count;
+    }
+
+    public override bool Maximization { get { return true; } }
+
 
     public override double Evaluate(Individual individual, IRandom random) {
-      var permutation = individual.Permutation();
-      var decoder = new ExtremePointPackingSequenceDecoder2D();
-      var packingPlan = decoder.CreatePackingPlanFromEncoding(permutation, Bin, Items);
-      var ratio = PackingRatioEvaluator.CalculatePackingRatio(packingPlan);
-      return ratio.Value;
+      var permutation = individual.Permutation("PackingSequence");
+      var decoder = Decoder;
+      var solution = decoder.Decode(permutation, BinShape, Items);
+      return SolutionEvaluator.Evaluate(solution);
     }
 
     public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
       base.Analyze(individuals, qualities, results, random);
-      Analyze(individuals.Select(i => i.Permutation()).ToArray(), qualities, results, random);
-    }
+      Analyze(individuals.Select(i => i.Permutation("PackingSequence")).ToArray(), qualities, results, random);
+    }
+
+    public void Analyze(Permutation[] individuals, double[] qualities, ResultCollection results, IRandom random) {
+      var bestSolutionResultName = "Best Packing Solution";
+      var numContainersResultName = "Nr of Containers";
+      var binUtilResultName = "Overall Bin Utilization";
+
+      if (!results.ContainsKey(bestSolutionResultName)) results.Add(new Result(bestSolutionResultName, typeof(Solution)));
+      if (!results.ContainsKey(numContainersResultName)) results.Add(new Result(numContainersResultName, typeof(IntValue)));
+      if (!results.ContainsKey(binUtilResultName)) results.Add(new Result(binUtilResultName, typeof(DoubleValue)));
+
+
+      // find index of item with max quality
+      int bestIdx = 0;
+      for (int j = 1; j < qualities.Length; j++)
+        if (qualities[j] > qualities[bestIdx]) bestIdx = j;
+
+
+      // update best solution so far
+      var bestSolution = results[bestSolutionResultName].Value as Solution;
+      if (bestSolution == null ||
+        bestSolution.Quality.Value < qualities[bestIdx]) {
+
+        var newBestSolution = Decoder.Decode(individuals[bestIdx], BinShape, Items);
+        newBestSolution.Quality = new DoubleValue(qualities[bestIdx]);
+        results[bestSolutionResultName].Value = newBestSolution;
+        results[numContainersResultName].Value = new IntValue(newBestSolution.NrOfBins);
+        results[binUtilResultName].Value = new DoubleValue(BinUtilizationEvaluator.CalculateBinUtilization(newBestSolution));
+
+        // update best known solution
+        var bestKnownQuality = BestKnownQualityParameter.Value;
+        if (bestKnownQuality == null ||
+            bestKnownQuality.Value < qualities[bestIdx]) {
+          BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[bestIdx]);
+          BestKnownSolutionParameter.ActualValue = newBestSolution;
+        }
+      }
+    }
+
+
+    #region Problem instance handling
+    public void Load(BPPData data) {
+      BestKnownSolutionParameter.Value = null;
+      BestKnownQualityParameter.Value = null;
+
+      if (data.BestKnownQuality.HasValue)
+        BestKnownQuality = data.BestKnownQuality.Value;
+
+      BinShape = data.BinShape;
+      var items = new ItemList<PackingItem>(data.Items);
+      items.Sort((x, y) => y.CompareTo(x));
+      Items = items.AsReadOnly();
+
+      ApplyHorizontalOrientation();
+      LowerBoundParameter.Value.Value = CalculateLowerBound();
+    }
+
+
+    public BPPData Export() {
+      return new BPPData {
+        Name = Name,
+        Description = Description,
+        BinShape = BinShape,
+        Items = Items.ToArray()
+      };
+    }
+    #endregion
+
+
+    #region helpers
+    private void ApplyHorizontalOrientation() {
+      BinShape.ApplyHorizontalOrientation();
+      foreach (var shape in Items) {
+        shape.ApplyHorizontalOrientation();
+      }
+    }
+
+    private int CalculateLowerBound() {
+      //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
+      int itemsVol = Items.Select(x => x.Volume).Sum();
+      int binVol = BinShape.Volume;
+      return (itemsVol + binVol - 1) / (binVol);
+    }
+
+    #endregion
   }
 }