source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingSequenceProblem.cs @ 14147

Last change on this file since 14147 was 14147, checked in by gkronber, 5 years ago

#1966: finished implementation of 2d bin packing problem using permutation encoding

File size: 13.6 KB
Line 
1#region License Information
2
3/* HeuristicLab
4 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
5 *
6 * This file is part of HeuristicLab.
7 *
8 * HeuristicLab is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * HeuristicLab is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#endregion
23
24using System;
25using System.Collections.Generic;
26using System.Linq;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Encodings.PermutationEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.Problems.BinPacking;
35using HeuristicLab.Problems.BinPacking2D;
36using HeuristicLab.Problems.Instances;
37using HeuristicLab.Random;
38
39namespace HeuristicLab.Problems.BinPacking2d {
40  [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.")]
41  [StorableClass]
42  [Creatable(Category = CreatableAttribute.Categories.CombinatorialProblems, Priority = 300)]
43  public sealed class PackingSequenceProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<BPPData>, IProblemInstanceExporter<BPPData> {
44    private readonly string SolutionEvaluatorParameterName = "SolutionEvaluator";
45    #region Default Instance
46    private static readonly BPPData DefaultInstance = new BPPData() {
47      Name = "2D BPP Default Instance",
48      Description = "The default instance for 2D Bin Packing.",
49      BinShape = new PackingShape(20, 16),
50      Items = new PackingItem[] {
51        new PackingItem(3,  8, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
52        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
53        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
54        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
55        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
56        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
57        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
58        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
59        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
60        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
61        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
62        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
63        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
64        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
65        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
66        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
67        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
68        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
69        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
70        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
71        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
72        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
73        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
74        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
75        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
76        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
77        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
78        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
79        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
80        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
81        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
82        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
83        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
84        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
85        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
86        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
87        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0}
88      },
89    };
90    #endregion
91
92    #region parameter properties
93    public IValueParameter<IPermutationDecoder> DecoderParameter {
94      get { return (IValueParameter<IPermutationDecoder>)Parameters["Decoder"]; }
95    }
96    public IValueParameter<BinPacking2D.IEvaluator> SolutionEvaluatorParameter {
97      get { return (IValueParameter<BinPacking2D.IEvaluator>)Parameters[SolutionEvaluatorParameterName]; }
98    }
99    public IValueParameter<ReadOnlyItemList<PackingItem>> ItemsParameter {
100      get { return (IValueParameter<ReadOnlyItemList<PackingItem>>)Parameters["Items"]; }
101    }
102    public IValueParameter<PackingShape> BinShapeParameter {
103      get { return (IValueParameter<PackingShape>)Parameters["BinShape"]; }
104    }
105    public IValueParameter<Solution> BestKnownSolutionParameter {
106      get { return (IValueParameter<Solution>)Parameters["BestKnownSolution"]; }
107    }
108    public IFixedValueParameter<IntValue> LowerBoundParameter {
109      get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
110    }
111    #endregion
112
113    #region properties
114    public IPermutationDecoder Decoder {
115      get { return DecoderParameter.Value; }
116      set { DecoderParameter.Value = value; }
117    }
118    public new BinPacking2D.IEvaluator SolutionEvaluator {
119      get { return SolutionEvaluatorParameter.Value; }
120      set { SolutionEvaluatorParameter.Value = value; }
121    }
122    public ReadOnlyItemList<PackingItem> Items {
123      get { return ItemsParameter.Value; }
124      set { ItemsParameter.Value = value; }
125    }
126    public PackingShape BinShape {
127      get { return BinShapeParameter.Value; }
128      set { BinShapeParameter.Value = value; }
129    }
130    public Solution BestKnownSolution {
131      get { return BestKnownSolutionParameter.Value; }
132      set { BestKnownSolutionParameter.Value = value; }
133    }
134    public int LowerBound {
135      get { return LowerBoundParameter.Value.Value; }
136    }
137    public int NumberOfItems {
138      get { return Items == null ? 0 : Items.Count; }
139    }
140    #endregion
141
142    // persistence
143    [StorableConstructor]
144    private PackingSequenceProblem(bool deserializing) : base(deserializing) { }
145
146    // cloning
147    private PackingSequenceProblem(PackingSequenceProblem original, Cloner cloner)
148      : base(original, cloner) {
149      RegisterEventHandlers();
150    }
151
152    public PackingSequenceProblem()
153      : base() {
154      var defaultEvaluator = new PackingRatioEvaluator();
155      var defaultDecoder = new ExtremePointPermutationDecoder();
156      Parameters.Add(new ValueParameter<IPermutationDecoder>("Decoder", "The decoder translates a permutation to a packing solution candidiates", defaultDecoder));
157      Parameters.Add(new ValueParameter<BinPacking2D.IEvaluator>(SolutionEvaluatorParameterName, "The evaluator calculates qualities of solution candidates", defaultEvaluator));
158      Parameters.Add(new ValueParameter<ReadOnlyItemList<PackingItem>>("Items", "The items which must be packed into bins"));
159      Parameters.Add(new ValueParameter<PackingShape>("BinShape", "The size of bins into which items must be packed"));
160      Parameters.Add(new OptionalValueParameter<Solution>("BestKnownSolution", "The best solution found so far"));
161      Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "A lower bound for the number of bins that is necessary to pack all items"));
162
163      Load(DefaultInstance);
164
165      Encoding = new PermutationEncoding("PackingSequence", Items.Count, PermutationTypes.Absolute);
166      AddOperators();
167      RegisterEventHandlers();
168    }
169    public override IDeepCloneable Clone(Cloner cloner) {
170      return new PackingSequenceProblem(this, cloner);
171    }
172
173    [StorableHook(HookType.AfterDeserialization)]
174    private void AfterDeserialization() {
175      RegisterEventHandlers();
176    }
177
178
179    private void AddOperators() {
180      Operators.Add(new TranslocationMoveEvaluator());
181      Operators.Add(new Swap2MoveEvaluator());
182
183      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
184      Operators.RemoveAll(x => x is SingleObjectiveMoveMaker);
185      Operators.RemoveAll(x => x is SingleObjectiveMoveEvaluator);
186
187      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
188    }
189
190    private void RegisterEventHandlers() {
191      // update encoding length when number of items is changed
192      ItemsParameter.ValueChanged += (sender, args) => Encoding.Length = Items.Count;
193    }
194
195    public override bool Maximization { get { return true; } }
196
197
198    public override double Evaluate(Individual individual, IRandom random) {
199      var permutation = individual.Permutation("PackingSequence");
200      var decoder = Decoder;
201      var solution = decoder.Decode(permutation, BinShape, Items);
202      return SolutionEvaluator.Evaluate(solution);
203    }
204
205    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
206      base.Analyze(individuals, qualities, results, random);
207      Analyze(individuals.Select(i => i.Permutation("PackingSequence")).ToArray(), qualities, results, random);
208    }
209
210    public void Analyze(Permutation[] individuals, double[] qualities, ResultCollection results, IRandom random) {
211      var bestSolutionResultName = "Best Packing Solution";
212      var numContainersResultName = "Nr of Containers";
213      var binUtilResultName = "Overall Bin Utilization";
214
215      if (!results.ContainsKey(bestSolutionResultName)) results.Add(new Result(bestSolutionResultName, typeof(Solution)));
216      if (!results.ContainsKey(numContainersResultName)) results.Add(new Result(numContainersResultName, typeof(IntValue)));
217      if (!results.ContainsKey(binUtilResultName)) results.Add(new Result(binUtilResultName, typeof(DoubleValue)));
218
219
220      // find index of item with max quality
221      int bestIdx = 0;
222      for (int j = 1; j < qualities.Length; j++)
223        if (qualities[j] > qualities[bestIdx]) bestIdx = j;
224
225
226      // update best solution so far
227      var bestSolution = results[bestSolutionResultName].Value as Solution;
228      if (bestSolution == null ||
229        bestSolution.Quality.Value < qualities[bestIdx]) {
230
231        var newBestSolution = Decoder.Decode(individuals[bestIdx], BinShape, Items);
232        newBestSolution.Quality = new DoubleValue(qualities[bestIdx]);
233        results[bestSolutionResultName].Value = newBestSolution;
234        results[numContainersResultName].Value = new IntValue(newBestSolution.NrOfBins);
235        results[binUtilResultName].Value = new DoubleValue(BinUtilizationEvaluator.CalculateBinUtilization(newBestSolution));
236
237        // update best known solution
238        var bestKnownQuality = BestKnownQualityParameter.Value;
239        if (bestKnownQuality == null ||
240            bestKnownQuality.Value < qualities[bestIdx]) {
241          BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[bestIdx]);
242          BestKnownSolutionParameter.ActualValue = newBestSolution;
243        }
244      }
245    }
246
247
248    #region Problem instance handling
249    public void Load(BPPData data) {
250      BestKnownSolutionParameter.Value = null;
251      BestKnownQualityParameter.Value = null;
252
253      if (data.BestKnownQuality.HasValue)
254        BestKnownQuality = data.BestKnownQuality.Value;
255
256      BinShape = data.BinShape;
257      var items = new ItemList<PackingItem>(data.Items);
258      items.Sort((x, y) => y.CompareTo(x));
259      Items = items.AsReadOnly();
260
261      ApplyHorizontalOrientation();
262      LowerBoundParameter.Value.Value = CalculateLowerBound();
263    }
264
265
266    public BPPData Export() {
267      return new BPPData {
268        Name = Name,
269        Description = Description,
270        BinShape = BinShape,
271        Items = Items.ToArray()
272      };
273    }
274    #endregion
275
276
277    #region helpers
278    private void ApplyHorizontalOrientation() {
279      BinShape.ApplyHorizontalOrientation();
280      foreach (var shape in Items) {
281        shape.ApplyHorizontalOrientation();
282      }
283    }
284
285    private int CalculateLowerBound() {
286      //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
287      int itemsVol = Items.Select(x => x.Volume).Sum();
288      int binVol = BinShape.Volume;
289      return (itemsVol + binVol - 1) / (binVol);
290    }
291
292    #endregion
293  }
294}
Note: See TracBrowser for help on using the repository browser.