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 |
|
---|
22 | using HeuristicLab.Optimization;
|
---|
23 | using HeuristicLab.Core;
|
---|
24 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
25 | using HeuristicLab.Common;
|
---|
26 | using HeuristicLab.Parameters;
|
---|
27 | using HeuristicLab.Data;
|
---|
28 | using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
|
---|
29 | using HeuristicLab.PluginInfrastructure;
|
---|
30 | using System.Linq;
|
---|
31 | using System;
|
---|
32 | using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
|
---|
33 | using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
|
---|
34 | using HeuristicLab.Encodings.PackingEncoding;
|
---|
35 |
|
---|
36 | namespace HeuristicLab.Problems.BinPacking {
|
---|
37 | [Item("BinPackingProblem", "Abstract class that represents a BinPacking Problem")]
|
---|
38 | [StorableClass]
|
---|
39 | public abstract class BinPackingProblem<D, B, I> : SingleObjectiveHeuristicOptimizationProblem<IPackingPlanEvaluationAlgorithm, IPackingSolutionCreator>
|
---|
40 | where D : class, IPackingDimensions
|
---|
41 | where B : PackingShape<D>, new()
|
---|
42 | where I : PackingShape<D>, IPackingItem, new () {
|
---|
43 |
|
---|
44 |
|
---|
45 | #region Parameter Properties
|
---|
46 | public OptionalValueParameter<PackingPlan<D,B,I>> BestKnownSolutionParameter {
|
---|
47 | get { return (OptionalValueParameter<PackingPlan<D, B, I>>)Parameters["BestKnownSolution"]; }
|
---|
48 | }
|
---|
49 | public ValueParameter<ItemList<I>> PackingItemMeasuresParameter {
|
---|
50 | get { return (ValueParameter<ItemList<I>>)Parameters["PackingItemMeasures"]; }
|
---|
51 | }
|
---|
52 | public IFixedValueParameter<IntValue> PackingItemsParameter {
|
---|
53 | get { return (IFixedValueParameter<IntValue>)Parameters["PackingItems"]; }
|
---|
54 | }
|
---|
55 | public IFixedValueParameter<IntValue> LowerBoundParameter {
|
---|
56 | get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
|
---|
57 | }
|
---|
58 | public ValueParameter<IPackingPlanEvaluator> PackingPlanEvaluatorParameter {
|
---|
59 | get { return (ValueParameter<IPackingPlanEvaluator>)Parameters["PackingPlanEvaluator"]; }
|
---|
60 | }
|
---|
61 | public IValueParameter<B> PackingBinMeasuresParameter {
|
---|
62 | get { return (IValueParameter<B>)Parameters["PackingBinMeasures"]; }
|
---|
63 | }
|
---|
64 | public IConstrainedValueParameter<IPackingSolutionDecoder> PackingSolutionDecoderParameter {
|
---|
65 | get { return (IConstrainedValueParameter<IPackingSolutionDecoder>)Parameters["PackingSolutionDecoder"]; }
|
---|
66 | }
|
---|
67 | #endregion
|
---|
68 |
|
---|
69 | #region Properties
|
---|
70 | public PackingPlan<D, B, I> BestKnownSolution {
|
---|
71 | get { return BestKnownSolutionParameter.Value; }
|
---|
72 | set { BestKnownSolutionParameter.Value = value; }
|
---|
73 | }
|
---|
74 | public ItemList<I> PackingItemMeasures {
|
---|
75 | get { return PackingItemMeasuresParameter.Value; }
|
---|
76 | set { PackingItemMeasuresParameter.Value = value; }
|
---|
77 | }
|
---|
78 | public IPackingPlanEvaluator PackingPlanEvaluator {
|
---|
79 | get { return PackingPlanEvaluatorParameter.Value; }
|
---|
80 | set { PackingPlanEvaluatorParameter.Value = value; }
|
---|
81 | }
|
---|
82 | public B PackingBinMeasures {
|
---|
83 | get { return PackingBinMeasuresParameter.Value; }
|
---|
84 | set { PackingBinMeasuresParameter.Value = value; }
|
---|
85 | }
|
---|
86 | public PackingSolutionDecoder<D, B, I> PackingSolutionDecoder {
|
---|
87 | get { return PackingSolutionDecoderParameter.Value as PackingSolutionDecoder<D, B, I>; }
|
---|
88 | set { PackingSolutionDecoderParameter.Value = value; }
|
---|
89 | }
|
---|
90 | #endregion
|
---|
91 |
|
---|
92 |
|
---|
93 | [StorableConstructor]
|
---|
94 | protected BinPackingProblem(bool deserializing) : base(deserializing) { }
|
---|
95 | protected BinPackingProblem(BinPackingProblem<D,B,I> original, Cloner cloner)
|
---|
96 | : base(original, cloner) {
|
---|
97 | InitializeEventHandlers();
|
---|
98 | }
|
---|
99 |
|
---|
100 | protected BinPackingProblem(IPackingPlanEvaluationAlgorithm e) : this(e, new MultiComponentVectorRandomCreator()) { }
|
---|
101 |
|
---|
102 | protected BinPackingProblem(IPackingPlanEvaluationAlgorithm e, IPackingSolutionCreator c) : base (e, c){
|
---|
103 | Parameters.Add(new OptionalValueParameter<PackingPlan<D, B, I>>("BestKnownSolution", "The best known solution of this bin-packing instance."));
|
---|
104 | 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>()));
|
---|
105 |
|
---|
106 | Parameters.Add(new FixedValueParameter<IntValue>("PackingItems", "The number of packing-items used in this bin packing instance.", new IntValue()));
|
---|
107 | 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()));
|
---|
108 | Parameters.Add(new ValueParameter<B>("PackingBinMeasures", "Packing-bin data defining the measures of the used bins.", new B()));
|
---|
109 | Parameters.Add(new ValueParameter<IPackingPlanEvaluator>("PackingPlanEvaluator", "The evaluator is used to determine the quality of a solution.", CreateDefaultEvaluator()));
|
---|
110 | Parameters.Add(new ConstrainedValueParameter<IPackingSolutionDecoder>("PackingSolutionDecoder", "The operator that decodes the representation and creates a packing plan."));
|
---|
111 | this.Maximization.Value = true;
|
---|
112 | InitializeProblemInstance();
|
---|
113 | InitializeOperators();
|
---|
114 | InitializeEventHandlers();
|
---|
115 | }
|
---|
116 |
|
---|
117 | protected abstract void InitializeDecoder();
|
---|
118 | protected virtual void InitializeProblemInstance() {
|
---|
119 | InitializeProblemData();
|
---|
120 | ApplyHorizontalOrientation();
|
---|
121 | SortItems();
|
---|
122 | RemoveTooBigItems();
|
---|
123 | PackingItemsParameter.Value.Value = PackingItemMeasures.Count;
|
---|
124 | LowerBoundParameter.Value.Value = CalculateLowerBound();
|
---|
125 | }
|
---|
126 | protected virtual void InitializeOperators() {
|
---|
127 | Operators.Clear();
|
---|
128 | Operators.Add(new BestBinPackingSolutionAnalyzer<D, B, I>());
|
---|
129 |
|
---|
130 | ApplyEncoding();
|
---|
131 | ParameterizeOperators();
|
---|
132 | }
|
---|
133 | protected virtual void InitializeEventHandlers() {
|
---|
134 | PackingPlanEvaluatorParameter.ValueChanged += PackingPlanEvaluatorParameter_ValueChanged;
|
---|
135 | PackingPlanEvaluator.QualityParameter.ActualNameChanged += PackingPlanEvaluator_QualityParameter_ActualNameChanged;
|
---|
136 | SolutionCreatorParameter.ValueChanged += SolutionCreatorParameter_ValueChanged;
|
---|
137 | SolutionCreator.EncodedSolutionParameter.ActualNameChanged += SolutionCreator_EncodedSolutionParameter_ActualNameChanged;
|
---|
138 | PackingSolutionDecoderParameter.ValueChanged += PackingSolutionDecoderParameter_ValueChanged;
|
---|
139 | if (PackingSolutionDecoder != null) PackingSolutionDecoder.PackingPlanParameter.ActualNameChanged += PackingSolutionDecoder_PackingPlanParameter_ActualNameChanged;
|
---|
140 | }
|
---|
141 |
|
---|
142 |
|
---|
143 | protected abstract void RemoveTooBigItems();
|
---|
144 | protected abstract void InitializeProblemData();
|
---|
145 | protected abstract IPackingPlanEvaluator CreateDefaultEvaluator();
|
---|
146 | protected void ApplyHorizontalOrientation() {
|
---|
147 | PackingBinMeasures.ApplyHorizontalOrientation();
|
---|
148 | foreach (IPackingShape shape in PackingItemMeasures) {
|
---|
149 | shape.ApplyHorizontalOrientation();
|
---|
150 | }
|
---|
151 | }
|
---|
152 | protected void SortItems() {
|
---|
153 | PackingItemMeasures.Sort((x, y) => y.CompareTo(x));
|
---|
154 | }
|
---|
155 | protected int CalculateLowerBound() {
|
---|
156 | //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
|
---|
157 | int items = PackingItemMeasures.Select(x => x.Volume).Sum();
|
---|
158 | int bin = PackingBinMeasures.Volume;
|
---|
159 | return (items + bin - 1) / (bin);
|
---|
160 | }
|
---|
161 |
|
---|
162 | private void ApplyEncoding() {
|
---|
163 | if (SolutionCreator.GetType() == typeof(PackingSequenceRandomCreator)) {
|
---|
164 | Operators.AddRange(ApplicationManager.Manager.GetInstances<IPackingSequenceOperator>());
|
---|
165 | InitializeDecoder();
|
---|
166 | } else if (SolutionCreator.GetType() == typeof(GroupingVectorRandomCreator)) {
|
---|
167 | Operators.AddRange(ApplicationManager.Manager.GetInstances<IGroupingVectorOperator>());
|
---|
168 | InitializeDecoder();
|
---|
169 | } else if (SolutionCreator.GetType() == typeof(MultiComponentVectorRandomCreator)) {
|
---|
170 | Operators.AddRange(ApplicationManager.Manager.GetInstances<IMultiComponentVectorOperator>());
|
---|
171 | InitializeDecoder();
|
---|
172 | }
|
---|
173 | }
|
---|
174 | private void ParameterizeOperators() {
|
---|
175 | foreach (var op in Operators.OfType<BestBinPackingSolutionAnalyzer<D, B, I>>()) {
|
---|
176 | op.QualityParameter.ActualName = PackingPlanEvaluator.QualityParameter.ActualName;
|
---|
177 | }
|
---|
178 |
|
---|
179 | Evaluator.PackingSolutionDecoderParameter.ActualName = PackingSolutionDecoderParameter.Name;
|
---|
180 | Evaluator.PackingSolutionDecoderParameter.Hidden = true;
|
---|
181 | Evaluator.PackingPlanEvaluatorParameter.ActualName = PackingPlanEvaluatorParameter.Name;
|
---|
182 | Evaluator.PackingPlanEvaluatorParameter.Hidden = true;
|
---|
183 | Evaluator.QualityParameter.ActualName = PackingPlanEvaluator.QualityParameter.ActualName;
|
---|
184 | Evaluator.QualityParameter.Hidden = true;
|
---|
185 |
|
---|
186 | if (PackingSolutionDecoder != null)
|
---|
187 | PackingSolutionDecoder.EncodedSolutionParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
|
---|
188 |
|
---|
189 | if (PackingSolutionDecoder != null) {
|
---|
190 | PackingPlanEvaluator.PackingPlanParameter.ActualName = PackingSolutionDecoder.PackingPlanParameter.ActualName;
|
---|
191 | PackingPlanEvaluator.PackingPlanParameter.Hidden = true;
|
---|
192 | } else {
|
---|
193 | PackingPlanEvaluator.PackingPlanParameter.ActualName = PackingPlanEvaluator.PackingPlanParameter.Name;
|
---|
194 | PackingPlanEvaluator.PackingPlanParameter.Hidden = false;
|
---|
195 | }
|
---|
196 |
|
---|
197 | foreach (var op in Operators.OfType<IPackingSolutionManipulator>()) {
|
---|
198 | op.EncodedSolutionParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
|
---|
199 | op.EncodedSolutionParameter.Hidden = true;
|
---|
200 | }
|
---|
201 |
|
---|
202 | foreach (var op in Operators.OfType<IPackingSolutionCrossover>()) {
|
---|
203 | op.ChildParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
|
---|
204 | op.ChildParameter.Hidden = true;
|
---|
205 | op.ParentsParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
|
---|
206 | op.ParentsParameter.Hidden = true;
|
---|
207 | }
|
---|
208 |
|
---|
209 | foreach (var op in Operators.OfType<BestBinPackingSolutionAnalyzer<D, B, I>>()) {
|
---|
210 | op.QualityParameter.ActualName = PackingPlanEvaluator.QualityParameter.ActualName;
|
---|
211 | if (PackingSolutionDecoder != null) {
|
---|
212 | op.PackingPlanParameter.ActualName = PackingSolutionDecoder.PackingPlanParameter.ActualName;
|
---|
213 | op.PackingPlanParameter.Hidden = true;
|
---|
214 | } else {
|
---|
215 | op.PackingPlanParameter.ActualName = op.PackingPlanParameter.Name;
|
---|
216 | op.PackingPlanParameter.Hidden = false;
|
---|
217 | }
|
---|
218 | }
|
---|
219 |
|
---|
220 | }
|
---|
221 |
|
---|
222 | #region Events
|
---|
223 | protected override void OnSolutionCreatorChanged() {
|
---|
224 | InitializeOperators();
|
---|
225 | }
|
---|
226 | protected override void OnEvaluatorChanged() {
|
---|
227 | base.OnEvaluatorChanged();
|
---|
228 | ParameterizeOperators();
|
---|
229 | }
|
---|
230 | private void PackingPlanEvaluatorParameter_ValueChanged(object sender, EventArgs eventArgs) {
|
---|
231 | PackingPlanEvaluator.QualityParameter.ActualNameChanged += PackingPlanEvaluator_QualityParameter_ActualNameChanged;
|
---|
232 | ParameterizeOperators();
|
---|
233 | }
|
---|
234 | private void PackingPlanEvaluator_QualityParameter_ActualNameChanged(object sender, EventArgs eventArgs) {
|
---|
235 | ParameterizeOperators();
|
---|
236 | }
|
---|
237 | private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs eventArgs) {
|
---|
238 | SolutionCreator.EncodedSolutionParameter.ActualNameChanged += SolutionCreator_EncodedSolutionParameter_ActualNameChanged;
|
---|
239 | ParameterizeOperators();
|
---|
240 | }
|
---|
241 | private void SolutionCreator_EncodedSolutionParameter_ActualNameChanged(object sender, EventArgs eventArgs) {
|
---|
242 | ParameterizeOperators();
|
---|
243 | }
|
---|
244 | private void PackingSolutionDecoderParameter_ValueChanged(object sender, EventArgs eventArgs) {
|
---|
245 | if (PackingSolutionDecoder != null) PackingSolutionDecoder.PackingPlanParameter.ActualNameChanged += PackingSolutionDecoder_PackingPlanParameter_ActualNameChanged;
|
---|
246 | ParameterizeOperators();
|
---|
247 | }
|
---|
248 | private void PackingSolutionDecoder_PackingPlanParameter_ActualNameChanged(object sender, EventArgs eventArgs) {
|
---|
249 | ParameterizeOperators();
|
---|
250 | }
|
---|
251 | #endregion
|
---|
252 | }
|
---|
253 | }
|
---|