Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.BinPacking/3.3/3D/ProblemBase.cs @ 15230

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

#2762: integrated bin packing extension into trunk

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 = items.AsReadOnly();
239
240      ApplyHorizontalOrientation();
241      LowerBoundParameter.Value.Value = CalculateLowerBound();
242    }
243
244
245    public BPPData Export() {
246      return new BPPData {
247        Name = Name,
248        Description = Description,
249        BinShape = BinShape,
250        Items = Items.ToArray()
251      };
252    }
253    #endregion
254
255
256    #region helpers
257    private void ApplyHorizontalOrientation() {
258      BinShape.ApplyHorizontalOrientation();
259      foreach (var shape in Items) {
260        shape.ApplyHorizontalOrientation();
261      }
262    }
263
264    private int CalculateLowerBound() {
265      //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
266      int itemsVol = Items.Select(x => x.Volume).Sum();
267      int binVol = BinShape.Volume;
268      return (itemsVol + binVol - 1) / (binVol);
269    }
270
271    #endregion
272  }
273}
Note: See TracBrowser for help on using the repository browser.