source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ProblemBase.cs @ 15473

Last change on this file since 15473 was 15473, checked in by rhanghof, 22 months ago

#2817

  • Added unit tests
  • Refactoring of bp 3D
File size: 12.3 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.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Problems.Instances;
32using HeuristicLab.Problems.BinPacking3D.Encoding;
33using HeuristicLab.Problems.BinPacking3D.Evaluators;
34using HeuristicLab.Problems.BinPacking3D.Instances;
35
36namespace HeuristicLab.Problems.BinPacking3D {
37  // in comparison to the 2d problem the 3d problem implementation also supports checking stacking constraints
38  [StorableClass]
39  public abstract class ProblemBase<TEnc, TSol> :
40    SingleObjectiveBasicProblem<TEnc>, IProblemInstanceConsumer<BPPData>, IProblemInstanceExporter<BPPData>
41    where TEnc : class, IEncoding
42    where TSol : class, IItem {
43    protected readonly string SolutionEvaluatorParameterName = "SolutionEvaluator";
44    protected readonly string UseStackingConstraintsParameterName = "UseStackingConstraints";
45
46    public readonly string EncodedSolutionName = "EncodedSolution";
47    #region Default Instance
48    private readonly BPPData defaultInstance = new BPPData() {
49      Name = "3D BPP Default Instance",
50      Description = "The default instance for 3D Bin Packing.",
51      BinShape = new PackingShape(25, 25, 35),
52      Items = new PackingItem[] {
53        new PackingItem(12,5,10, new PackingShape(25,25,35)),
54        new PackingItem(10,18,20, new PackingShape(25,25,35)),
55        new PackingItem(9,7,7, new PackingShape(25,25,35)),
56        new PackingItem(21,12,4, new PackingShape(25,25,35)),
57        new PackingItem(8,8,12, new PackingShape(25,25,35)),
58        new PackingItem(3,6,14, new PackingShape(25,25,35)),
59        new PackingItem(20,4,9, new PackingShape(25,25,35)),
60        new PackingItem(5,9,8, new PackingShape(25,25,35)),
61        new PackingItem(7,17,3, new PackingShape(25,25,35)),
62        new PackingItem(13,20,15, new PackingShape(25,25,35)),
63        new PackingItem(9,11,9, new PackingShape(25,25,35)),
64        new PackingItem(10,18,20, new PackingShape(25,25,35)),
65        new PackingItem(9,7,7, new PackingShape(25,25,35)),
66        new PackingItem(21,12,4, new PackingShape(25,25,35)),
67        new PackingItem(8,8,12, new PackingShape(25,25,35)),
68        new PackingItem(3,6,14, new PackingShape(25,25,35)),
69        new PackingItem(20,4,9, new PackingShape(25,25,35)),
70        new PackingItem(5,9,8, new PackingShape(25,25,35)),
71        new PackingItem(7,17,3, new PackingShape(25,25,35)),
72        new PackingItem(13,20,15, new PackingShape(25,25,35)),
73        new PackingItem(9,11,9, new PackingShape(25,25,35)),
74        new PackingItem(10,18,20, new PackingShape(25,25,35)),
75        new PackingItem(9,7,7, new PackingShape(25,25,35)),
76        new PackingItem(21,12,4, new PackingShape(25,25,35)),
77        new PackingItem(8,8,12, new PackingShape(25,25,35)),
78        new PackingItem(3,6,14, new PackingShape(25,25,35)),
79        new PackingItem(20,4,9, new PackingShape(25,25,35)),
80        new PackingItem(5,9,8, new PackingShape(25,25,35)),
81        new PackingItem(7,17,3, new PackingShape(25,25,35)),
82        new PackingItem(13,20,15, new PackingShape(25,25,35)),
83        new PackingItem(9,11, 9,new PackingShape(25,25,35)),
84        new PackingItem(10,18,20, new PackingShape(25,25,35)),
85        new PackingItem(9,7,7, new PackingShape(25,25,35)),
86        new PackingItem(21,12,4, new PackingShape(25,25,35)),
87        new PackingItem(8,8,12, new PackingShape(25,25,35)),
88        new PackingItem(3,6,14, new PackingShape(25,25,35)),
89        new PackingItem(20,4,9, new PackingShape(25,25,35)),
90        new PackingItem(5,9,8, new PackingShape(25,25,35)),
91        new PackingItem(7,17,3, new PackingShape(25,25,35)),
92        new PackingItem(13,20,15, new PackingShape(25,25,35)),
93        new PackingItem(9,11,9, new PackingShape(25,25,35))
94      },
95    };
96    #endregion
97
98    #region parameter properties
99    public IValueParameter<IDecoder<TSol>> DecoderParameter {
100      get { return (IValueParameter<IDecoder<TSol>>)Parameters["Decoder"]; }
101    }
102    public IValueParameter<IEvaluator> SolutionEvaluatorParameter {
103      get { return (IValueParameter<IEvaluator>)Parameters[SolutionEvaluatorParameterName]; }
104    }
105    public IFixedValueParameter<BoolValue> UseStackingConstraintsParameter {
106      get { return (IFixedValueParameter<BoolValue>)Parameters[UseStackingConstraintsParameterName]; }
107    }
108    public IValueParameter<ReadOnlyItemList<PackingItem>> ItemsParameter {
109      get { return (IValueParameter<ReadOnlyItemList<PackingItem>>)Parameters["Items"]; }
110    }
111    public IValueParameter<PackingShape> BinShapeParameter {
112      get { return (IValueParameter<PackingShape>)Parameters["BinShape"]; }
113    }
114    public IValueParameter<Solution> BestKnownSolutionParameter {
115      get { return (IValueParameter<Solution>)Parameters["BestKnownSolution"]; }
116    }
117    public IFixedValueParameter<IntValue> LowerBoundParameter {
118      get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
119    }
120    #endregion
121
122    #region properties
123    public IDecoder<TSol> Decoder {
124      get { return DecoderParameter.Value; }
125      set { DecoderParameter.Value = value; }
126    }
127    public IEvaluator SolutionEvaluator {
128      get { return SolutionEvaluatorParameter.Value; }
129      set { SolutionEvaluatorParameter.Value = value; }
130    }
131    public bool UseStackingConstraints {
132      get { return UseStackingConstraintsParameter.Value.Value; }
133      set { UseStackingConstraintsParameter.Value.Value = value; }
134    }
135    public ReadOnlyItemList<PackingItem> Items {
136      get { return ItemsParameter.Value; }
137      set { ItemsParameter.Value = value; }
138    }
139    public PackingShape BinShape {
140      get { return BinShapeParameter.Value; }
141      set { BinShapeParameter.Value = value; }
142    }
143    public Solution BestKnownSolution {
144      get { return BestKnownSolutionParameter.Value; }
145      set { BestKnownSolutionParameter.Value = value; }
146    }
147    public int LowerBound {
148      get { return LowerBoundParameter.Value.Value; }
149    }
150    public int NumberOfItems {
151      get { return Items == null ? 0 : Items.Count; }
152    }
153    #endregion
154
155    // persistence
156    [StorableConstructor]
157    protected ProblemBase(bool deserializing) : base(deserializing) { }
158
159    // cloning
160    protected ProblemBase(ProblemBase<TEnc, TSol> original, Cloner cloner)
161      : base(original, cloner) {
162    }
163
164    protected ProblemBase()
165      : base() {
166      var defaultEvaluator = new PackingRatioEvaluator();
167      Parameters.Add(new ValueParameter<IDecoder<TSol>>("Decoder", "The decoder translates a permutation to a packing solution candidiates"));
168      Parameters.Add(new ValueParameter<IEvaluator>(SolutionEvaluatorParameterName, "The evaluator calculates qualities of solution candidates", defaultEvaluator));
169      Parameters.Add(new FixedValueParameter<BoolValue>(UseStackingConstraintsParameterName, "A flag that determines if stacking constraints are considered when solving the problem.", new BoolValue(false)));
170      Parameters.Add(new ValueParameter<ReadOnlyItemList<PackingItem>>("Items", "The items which must be packed into bins"));
171      Parameters.Add(new ValueParameter<PackingShape>("BinShape", "The size of bins into which items must be packed"));
172      Parameters.Add(new OptionalValueParameter<Solution>("BestKnownSolution", "The best solution found so far"));
173      Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "A lower bound for the number of bins that is necessary to pack all items"));
174
175      Load(defaultInstance);
176    }
177
178    public override bool Maximization { get { return true; } }
179
180    public override double Evaluate(Individual individual, IRandom random) {
181      var encodedSolutionCand = (TSol)individual[EncodedSolutionName];
182      var decoder = Decoder;
183      var solution = decoder.Decode(encodedSolutionCand, BinShape, Items, UseStackingConstraints);
184      return SolutionEvaluator.Evaluate(solution);
185    }
186
187    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
188      base.Analyze(individuals, qualities, results, random);
189      Analyze(individuals.Select(i => (TSol)i[EncodedSolutionName]).ToArray(), qualities, results, random);
190    }
191
192    // NOTE: same implementation as for 2d problem
193    public virtual void Analyze(TSol[] individuals, double[] qualities, ResultCollection results, IRandom random) {
194      var bestSolutionResultName = "Best Packing Solution";
195      var numContainersResultName = "Nr of Containers";
196      var binUtilResultName = "Overall Bin Utilization";
197
198      if (!results.ContainsKey(bestSolutionResultName)) results.Add(new Result(bestSolutionResultName, typeof(Solution)));
199      if (!results.ContainsKey(numContainersResultName)) results.Add(new Result(numContainersResultName, typeof(IntValue)));
200      if (!results.ContainsKey(binUtilResultName)) results.Add(new Result(binUtilResultName, typeof(DoubleValue)));
201
202
203      // find index of item with max quality
204      int bestIdx = 0;
205      for (int j = 1; j < qualities.Length; j++)
206        if (qualities[j] > qualities[bestIdx]) bestIdx = j;
207
208
209      // update best solution so far
210      var bestSolution = results[bestSolutionResultName].Value as Solution;
211      if (bestSolution == null ||
212        bestSolution.Quality.Value < qualities[bestIdx]) {
213
214        var newBestSolution = Decoder.Decode(individuals[bestIdx], BinShape, Items, UseStackingConstraints);
215        newBestSolution.Quality = new DoubleValue(qualities[bestIdx]);
216        results[bestSolutionResultName].Value = newBestSolution;
217        results[numContainersResultName].Value = new IntValue(newBestSolution.NrOfBins);
218        results[binUtilResultName].Value = new DoubleValue(BinUtilizationEvaluator.CalculateBinUtilization(newBestSolution));
219
220        // update best known solution
221        var bestKnownQuality = BestKnownQualityParameter.Value;
222        if (bestKnownQuality == null ||
223            bestKnownQuality.Value < qualities[bestIdx]) {
224          BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[bestIdx]);
225          BestKnownSolutionParameter.ActualValue = newBestSolution;
226        }
227      }
228    }
229
230
231    #region Problem instance handling
232    public void Load(BPPData data) {
233      BestKnownSolutionParameter.Value = null;
234      BestKnownQualityParameter.Value = null;
235
236      if (data.BestKnownQuality.HasValue)
237        BestKnownQuality = data.BestKnownQuality.Value;
238
239      BinShape = data.BinShape;
240      var items = new ItemList<PackingItem>(data.Items);
241      Items = items.AsReadOnly();
242
243      ApplyHorizontalOrientation();
244      LowerBoundParameter.Value.Value = CalculateLowerBound();
245    }
246
247
248    public BPPData Export() {
249      return new BPPData {
250        Name = Name,
251        Description = Description,
252        BinShape = BinShape,
253        Items = Items.ToArray()
254      };
255    }
256    #endregion
257
258
259    #region helpers
260    private void ApplyHorizontalOrientation() {
261      BinShape.ApplyHorizontalOrientation();
262      foreach (var shape in Items) {
263        shape.ApplyHorizontalOrientation();
264      }
265    }
266
267    private int CalculateLowerBound() {
268      //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
269      int itemsVol = Items.Select(x => x.Volume).Sum();
270      int binVol = BinShape.Volume;
271      return (itemsVol + binVol - 1) / (binVol);
272    }
273
274    #endregion
275  }
276}
Note: See TracBrowser for help on using the repository browser.