source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Problem.cs @ 14054

Last change on this file since 14054 was 14054, checked in by gkronber, 3 years ago

#1966: renamed *EvaluationAlgorithm to *DecodingEvaluator

File size: 12.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HeuristicLab.Optimization;
23using HeuristicLab.Core;
24using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
25using HeuristicLab.Common;
26using HeuristicLab.Parameters;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
29using HeuristicLab.PluginInfrastructure;
30using System.Linq;
31using System;
32using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
33using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
34using HeuristicLab.Encodings.PackingEncoding;
35
36namespace HeuristicLab.Problems.BinPacking {
37  [StorableClass]
38  public abstract class Problem<D, B, I> : SingleObjectiveHeuristicOptimizationProblem<IDecodingEvaluator, IPackingSolutionCreator>
39    where D : class, IPackingPosition
40    where B : PackingShape<D>, new()
41    where I : PackingShape<D>, IPackingItem, new() {
42
43
44    #region Parameter Properties
45    public OptionalValueParameter<PackingPlan<D, B, I>> BestKnownSolutionParameter {
46      get { return (OptionalValueParameter<PackingPlan<D, B, I>>)Parameters["BestKnownSolution"]; }
47    }
48    public ValueParameter<ItemList<I>> PackingItemMeasuresParameter {
49      get { return (ValueParameter<ItemList<I>>)Parameters["PackingItemMeasures"]; }
50    }
51    public IFixedValueParameter<IntValue> PackingItemsParameter {
52      get { return (IFixedValueParameter<IntValue>)Parameters["PackingItems"]; }
53    }
54    public IFixedValueParameter<IntValue> LowerBoundParameter {
55      get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
56    }
57    public ValueParameter<IEvaluator> PackingPlanEvaluatorParameter {
58      get { return (ValueParameter<IEvaluator>)Parameters["PackingPlanEvaluator"]; }
59    }
60    public IValueParameter<B> PackingBinMeasuresParameter {
61      get { return (IValueParameter<B>)Parameters["PackingBinMeasures"]; }
62    }
63    public IConstrainedValueParameter<IPackingSolutionDecoder> PackingSolutionDecoderParameter {
64      get { return (IConstrainedValueParameter<IPackingSolutionDecoder>)Parameters["PackingSolutionDecoder"]; }
65    }
66    #endregion
67
68    #region Properties
69    public PackingPlan<D, B, I> BestKnownSolution {
70      get { return BestKnownSolutionParameter.Value; }
71      set { BestKnownSolutionParameter.Value = value; }
72    }
73    public ItemList<I> PackingItemMeasures {
74      get { return PackingItemMeasuresParameter.Value; }
75      set { PackingItemMeasuresParameter.Value = value; }
76    }
77    public IEvaluator PackingPlanEvaluator {
78      get { return PackingPlanEvaluatorParameter.Value; }
79      set { PackingPlanEvaluatorParameter.Value = value; }
80    }
81    public B PackingBinMeasures {
82      get { return PackingBinMeasuresParameter.Value; }
83      set { PackingBinMeasuresParameter.Value = value; }
84    }
85    public PackingSolutionDecoder<D, B, I> PackingSolutionDecoder {
86      get { return PackingSolutionDecoderParameter.Value as PackingSolutionDecoder<D, B, I>; }
87      set { PackingSolutionDecoderParameter.Value = value; }
88    }
89    #endregion
90
91
92    [StorableConstructor]
93    protected Problem(bool deserializing) : base(deserializing) { }
94    protected Problem(Problem<D, B, I> original, Cloner cloner)
95      : base(original, cloner) {
96      InitializeEventHandlers();
97    }
98
99    protected Problem(IDecodingEvaluator e) : this(e, new MultiComponentVectorRandomCreator()) { }
100
101    protected Problem(IDecodingEvaluator e, IPackingSolutionCreator c) : base(e, c) {
102      Parameters.Add(new OptionalValueParameter<PackingPlan<D, B, I>>("BestKnownSolution", "The best known solution of this bin-packing instance."));
103      Parameters.Add(new ValueParameter<ItemList<I>>("PackingItemMeasures", "Packing-item data defining the measures of the different items that need to be packed.", new ItemList<I>()));
104
105      Parameters.Add(new FixedValueParameter<IntValue>("PackingItems", "The number of packing-items used in this bin packing instance.", new IntValue()));
106      Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "The lower possible number of bins needed to solve this problem (taken from Dell'Amico, Martello and Vigo; 2002)", new IntValue()));
107      Parameters.Add(new ValueParameter<B>("PackingBinMeasures", "Packing-bin data defining the measures of the used bins.", new B()));
108      Parameters.Add(new ValueParameter<IEvaluator>("PackingPlanEvaluator", "The evaluator is used to determine the quality of a solution.", CreateDefaultEvaluator()));
109      Parameters.Add(new ConstrainedValueParameter<IPackingSolutionDecoder>("PackingSolutionDecoder", "The operator that decodes the representation and creates a packing plan."));
110      this.Maximization.Value = true;
111      InitializeProblemInstance();
112      InitializeOperators();
113      InitializeEventHandlers();
114    }
115
116    protected abstract void InitializeDecoder();
117    protected virtual void InitializeProblemInstance() {
118      InitializeProblemData();
119      ApplyHorizontalOrientation();
120      SortItems();
121      RemoveTooBigItems();
122      PackingItemsParameter.Value.Value = PackingItemMeasures.Count;
123      LowerBoundParameter.Value.Value = CalculateLowerBound();
124    }
125    protected virtual void InitializeOperators() {
126      Operators.Clear();
127      Operators.Add(new BestBinPackingSolutionAnalyzer<D, B, I>());
128
129      ApplyEncoding();
130      ParameterizeOperators();
131    }
132    protected virtual void InitializeEventHandlers() {
133      PackingPlanEvaluatorParameter.ValueChanged += PackingPlanEvaluatorParameter_ValueChanged;
134      PackingPlanEvaluator.QualityParameter.ActualNameChanged += PackingPlanEvaluator_QualityParameter_ActualNameChanged;
135      SolutionCreatorParameter.ValueChanged += SolutionCreatorParameter_ValueChanged;
136      SolutionCreator.EncodedSolutionParameter.ActualNameChanged += SolutionCreator_EncodedSolutionParameter_ActualNameChanged;
137      PackingSolutionDecoderParameter.ValueChanged += PackingSolutionDecoderParameter_ValueChanged;
138      if (PackingSolutionDecoder != null) PackingSolutionDecoder.PackingPlanParameter.ActualNameChanged += PackingSolutionDecoder_PackingPlanParameter_ActualNameChanged;
139    }
140
141
142    protected abstract void RemoveTooBigItems();
143    protected abstract void InitializeProblemData();
144    protected abstract IEvaluator CreateDefaultEvaluator();
145    protected void ApplyHorizontalOrientation() {
146      PackingBinMeasures.ApplyHorizontalOrientation();
147      foreach (IPackingShape shape in PackingItemMeasures) {
148        shape.ApplyHorizontalOrientation();
149      }
150    }
151    protected void SortItems() {
152      PackingItemMeasures.Sort((x, y) => y.CompareTo(x));
153    }
154    protected int CalculateLowerBound() {
155      //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
156      int items = PackingItemMeasures.Select(x => x.Volume).Sum();
157      int bin = PackingBinMeasures.Volume;
158      return (items + bin - 1) / (bin);
159    }
160
161    private void ApplyEncoding() {
162      if (SolutionCreator.GetType() == typeof(PackingSequenceRandomCreator)) {
163        Operators.AddRange(ApplicationManager.Manager.GetInstances<IPackingSequenceOperator>());
164        InitializeDecoder();
165      } else if (SolutionCreator.GetType() == typeof(GroupingVectorRandomCreator)) {
166        Operators.AddRange(ApplicationManager.Manager.GetInstances<IGroupingVectorOperator>());
167        InitializeDecoder();
168      } else if (SolutionCreator.GetType() == typeof(MultiComponentVectorRandomCreator)) {
169        Operators.AddRange(ApplicationManager.Manager.GetInstances<IMultiComponentVectorOperator>());
170        InitializeDecoder();
171      }
172    }
173    private void ParameterizeOperators() {
174      foreach (var op in Operators.OfType<BestBinPackingSolutionAnalyzer<D, B, I>>()) {
175        op.QualityParameter.ActualName = PackingPlanEvaluator.QualityParameter.ActualName;
176      }
177
178      Evaluator.PackingSolutionDecoderParameter.ActualName = PackingSolutionDecoderParameter.Name;
179      Evaluator.PackingSolutionDecoderParameter.Hidden = true;
180      Evaluator.PackingPlanEvaluatorParameter.ActualName = PackingPlanEvaluatorParameter.Name;
181      Evaluator.PackingPlanEvaluatorParameter.Hidden = true;
182      Evaluator.QualityParameter.ActualName = PackingPlanEvaluator.QualityParameter.ActualName;
183      Evaluator.QualityParameter.Hidden = true;
184
185      if (PackingSolutionDecoder != null)
186        PackingSolutionDecoder.EncodedSolutionParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
187
188      if (PackingSolutionDecoder != null) {
189        PackingPlanEvaluator.PackingPlanParameter.ActualName = PackingSolutionDecoder.PackingPlanParameter.ActualName;
190        PackingPlanEvaluator.PackingPlanParameter.Hidden = true;
191      } else {
192        PackingPlanEvaluator.PackingPlanParameter.ActualName = PackingPlanEvaluator.PackingPlanParameter.Name;
193        PackingPlanEvaluator.PackingPlanParameter.Hidden = false;
194      }
195
196      foreach (var op in Operators.OfType<IPackingSolutionManipulator>()) {
197        op.EncodedSolutionParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
198        op.EncodedSolutionParameter.Hidden = true;
199      }
200
201      foreach (var op in Operators.OfType<IPackingSolutionCrossover>()) {
202        op.ChildParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
203        op.ChildParameter.Hidden = true;
204        op.ParentsParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
205        op.ParentsParameter.Hidden = true;
206      }
207
208      foreach (var op in Operators.OfType<BestBinPackingSolutionAnalyzer<D, B, I>>()) {
209        op.QualityParameter.ActualName = PackingPlanEvaluator.QualityParameter.ActualName;
210        if (PackingSolutionDecoder != null) {
211          op.PackingPlanParameter.ActualName = PackingSolutionDecoder.PackingPlanParameter.ActualName;
212          op.PackingPlanParameter.Hidden = true;
213        } else {
214          op.PackingPlanParameter.ActualName = op.PackingPlanParameter.Name;
215          op.PackingPlanParameter.Hidden = false;
216        }
217      }
218
219    }
220
221    #region Events
222    protected override void OnSolutionCreatorChanged() {
223      InitializeOperators();
224    }
225    protected override void OnEvaluatorChanged() {
226      base.OnEvaluatorChanged();
227      ParameterizeOperators();
228    }
229    private void PackingPlanEvaluatorParameter_ValueChanged(object sender, EventArgs eventArgs) {
230      PackingPlanEvaluator.QualityParameter.ActualNameChanged += PackingPlanEvaluator_QualityParameter_ActualNameChanged;
231      ParameterizeOperators();
232    }
233    private void PackingPlanEvaluator_QualityParameter_ActualNameChanged(object sender, EventArgs eventArgs) {
234      ParameterizeOperators();
235    }
236    private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs eventArgs) {
237      SolutionCreator.EncodedSolutionParameter.ActualNameChanged += SolutionCreator_EncodedSolutionParameter_ActualNameChanged;
238      ParameterizeOperators();
239    }
240    private void SolutionCreator_EncodedSolutionParameter_ActualNameChanged(object sender, EventArgs eventArgs) {
241      ParameterizeOperators();
242    }
243    private void PackingSolutionDecoderParameter_ValueChanged(object sender, EventArgs eventArgs) {
244      if (PackingSolutionDecoder != null) PackingSolutionDecoder.PackingPlanParameter.ActualNameChanged += PackingSolutionDecoder_PackingPlanParameter_ActualNameChanged;
245      ParameterizeOperators();
246    }
247    private void PackingSolutionDecoder_PackingPlanParameter_ActualNameChanged(object sender, EventArgs eventArgs) {
248      ParameterizeOperators();
249    }
250    #endregion
251  }
252}
Note: See TracBrowser for help on using the repository browser.