Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2695_dataset-ids/HeuristicLab.Problems.BinPacking/3.3/3D/ProblemBase.cs @ 16881

Last change on this file since 16881 was 15276, checked in by abeham, 7 years ago

#2762:

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