Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PausableBasicAlgorithm/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs @ 14153

Last change on this file since 14153 was 13173, checked in by abeham, 9 years ago

#2454: added some acronyms
File size: 15.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Analysis;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.BinaryVectorEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Optimization.Operators;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.PluginInfrastructure;
35
36namespace HeuristicLab.Problems.Knapsack {
37  [Item("Knapsack Problem (KSP)", "Represents a Knapsack problem.")]
38  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 200)]
39  [StorableClass]
40  public sealed class KnapsackProblem : SingleObjectiveHeuristicOptimizationProblem<IKnapsackEvaluator, IBinaryVectorCreator>, IStorableContent {
41    public string Filename { get; set; }
42
43    #region Parameter Properties
44    public ValueParameter<IntValue> KnapsackCapacityParameter {
45      get { return (ValueParameter<IntValue>)Parameters["KnapsackCapacity"]; }
46    }
47    public ValueParameter<IntArray> WeightsParameter {
48      get { return (ValueParameter<IntArray>)Parameters["Weights"]; }
49    }
50    public ValueParameter<IntArray> ValuesParameter {
51      get { return (ValueParameter<IntArray>)Parameters["Values"]; }
52    }
53    public ValueParameter<DoubleValue> PenaltyParameter {
54      get { return (ValueParameter<DoubleValue>)Parameters["Penalty"]; }
55    }
56    public OptionalValueParameter<BinaryVector> BestKnownSolutionParameter {
57      get { return (OptionalValueParameter<BinaryVector>)Parameters["BestKnownSolution"]; }
58    }
59    #endregion
60
61    #region Properties
62    public IntValue KnapsackCapacity {
63      get { return KnapsackCapacityParameter.Value; }
64      set { KnapsackCapacityParameter.Value = value; }
65    }
66    public IntArray Weights {
67      get { return WeightsParameter.Value; }
68      set { WeightsParameter.Value = value; }
69    }
70    public IntArray Values {
71      get { return ValuesParameter.Value; }
72      set { ValuesParameter.Value = value; }
73    }
74    public DoubleValue Penalty {
75      get { return PenaltyParameter.Value; }
76      set { PenaltyParameter.Value = value; }
77    }
78    public BinaryVector BestKnownSolution {
79      get { return BestKnownSolutionParameter.Value; }
80      set { BestKnownSolutionParameter.Value = value; }
81    }
82    private BestKnapsackSolutionAnalyzer BestKnapsackSolutionAnalyzer {
83      get { return Operators.OfType<BestKnapsackSolutionAnalyzer>().FirstOrDefault(); }
84    }
85    #endregion
86
87    // BackwardsCompatibility3.3
88    #region Backwards compatible code, remove with 3.4
89    [Obsolete]
90    [Storable(Name = "operators")]
91    private IEnumerable<IOperator> oldOperators {
92      get { return null; }
93      set {
94        if (value != null && value.Any())
95          Operators.AddRange(value);
96      }
97    }
98    #endregion
99
100    [StorableConstructor]
101    private KnapsackProblem(bool deserializing) : base(deserializing) { }
102    private KnapsackProblem(KnapsackProblem original, Cloner cloner)
103      : base(original, cloner) {
104      RegisterEventHandlers();
105    }
106    public override IDeepCloneable Clone(Cloner cloner) {
107      return new KnapsackProblem(this, cloner);
108    }
109    public KnapsackProblem()
110      : base(new KnapsackEvaluator(), new RandomBinaryVectorCreator()) {
111      Parameters.Add(new ValueParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack.", new IntValue(0)));
112      Parameters.Add(new ValueParameter<IntArray>("Weights", "The weights of the items.", new IntArray(5)));
113      Parameters.Add(new ValueParameter<IntArray>("Values", "The values of the items.", new IntArray(5)));
114      Parameters.Add(new ValueParameter<DoubleValue>("Penalty", "The penalty value for each unit of overweight.", new DoubleValue(1)));
115      Parameters.Add(new OptionalValueParameter<BinaryVector>("BestKnownSolution", "The best known solution of this Knapsack instance."));
116
117      Maximization.Value = true;
118      MaximizationParameter.Hidden = true;
119
120      SolutionCreator.BinaryVectorParameter.ActualName = "KnapsackSolution";
121
122      InitializeRandomKnapsackInstance();
123
124      ParameterizeSolutionCreator();
125      ParameterizeEvaluator();
126
127      InitializeOperators();
128      RegisterEventHandlers();
129    }
130
131    #region Events
132    protected override void OnSolutionCreatorChanged() {
133      base.OnSolutionCreatorChanged();
134      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
135      ParameterizeSolutionCreator();
136      ParameterizeEvaluator();
137      ParameterizeAnalyzer();
138      ParameterizeOperators();
139    }
140    protected override void OnEvaluatorChanged() {
141      base.OnEvaluatorChanged();
142      ParameterizeEvaluator();
143      ParameterizeAnalyzer();
144    }
145    private void SolutionCreator_BinaryVectorParameter_ActualNameChanged(object sender, EventArgs e) {
146      ParameterizeEvaluator();
147      ParameterizeAnalyzer();
148      ParameterizeOperators();
149    }
150    private void KnapsackCapacityParameter_ValueChanged(object sender, EventArgs e) {
151      ParameterizeEvaluator();
152      ParameterizeAnalyzer();
153    }
154    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
155      ParameterizeEvaluator();
156      ParameterizeAnalyzer();
157      ParameterizeSolutionCreator();
158
159      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
160    }
161    private void WeightsValue_Reset(object sender, EventArgs e) {
162      ParameterizeSolutionCreator();
163
164      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
165        ((IStringConvertibleArray)ValuesParameter.Value).Length = WeightsParameter.Value.Length;
166    }
167    private void ValuesParameter_ValueChanged(object sender, EventArgs e) {
168      ParameterizeEvaluator();
169      ParameterizeAnalyzer();
170      ParameterizeSolutionCreator();
171
172      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
173    }
174    private void ValuesValue_Reset(object sender, EventArgs e) {
175      ParameterizeSolutionCreator();
176
177      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
178        ((IStringConvertibleArray)WeightsParameter.Value).Length = ValuesParameter.Value.Length;
179    }
180    private void PenaltyParameter_ValueChanged(object sender, EventArgs e) {
181      ParameterizeEvaluator();
182    }
183    private void OneBitflipMoveParameter_ActualNameChanged(object sender, EventArgs e) {
184      string name = ((ILookupParameter<OneBitflipMove>)sender).ActualName;
185      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
186        op.OneBitflipMoveParameter.ActualName = name;
187      }
188    }
189    #endregion
190
191    #region Helpers
192    [StorableHook(HookType.AfterDeserialization)]
193    private void AfterDeserialization() {
194      // BackwardsCompatibility3.3
195      #region Backwards compatible code (remove with 3.4)
196      if (Operators.Count == 0) InitializeOperators();
197      #endregion
198      RegisterEventHandlers();
199    }
200
201    private void RegisterEventHandlers() {
202      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
203      KnapsackCapacityParameter.ValueChanged += new EventHandler(KnapsackCapacityParameter_ValueChanged);
204      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
205      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
206      ValuesParameter.ValueChanged += new EventHandler(ValuesParameter_ValueChanged);
207      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
208      PenaltyParameter.ValueChanged += new EventHandler(PenaltyParameter_ValueChanged);
209    }
210    private void ParameterizeSolutionCreator() {
211      if (SolutionCreator.LengthParameter.Value == null ||
212        SolutionCreator.LengthParameter.Value.Value != WeightsParameter.Value.Length)
213        SolutionCreator.LengthParameter.Value = new IntValue(WeightsParameter.Value.Length);
214    }
215    private void ParameterizeEvaluator() {
216      if (Evaluator is KnapsackEvaluator) {
217        KnapsackEvaluator knapsackEvaluator =
218          (KnapsackEvaluator)Evaluator;
219        knapsackEvaluator.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
220        knapsackEvaluator.BinaryVectorParameter.Hidden = true;
221        knapsackEvaluator.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
222        knapsackEvaluator.KnapsackCapacityParameter.Hidden = true;
223        knapsackEvaluator.WeightsParameter.ActualName = WeightsParameter.Name;
224        knapsackEvaluator.WeightsParameter.Hidden = true;
225        knapsackEvaluator.ValuesParameter.ActualName = ValuesParameter.Name;
226        knapsackEvaluator.ValuesParameter.Hidden = true;
227        knapsackEvaluator.PenaltyParameter.ActualName = PenaltyParameter.Name;
228        knapsackEvaluator.PenaltyParameter.Hidden = true;
229      }
230    }
231    private void ParameterizeAnalyzer() {
232      if (BestKnapsackSolutionAnalyzer != null) {
233        BestKnapsackSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
234        BestKnapsackSolutionAnalyzer.MaximizationParameter.Hidden = true;
235        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
236        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.Hidden = true;
237        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
238        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.Hidden = true;
239        BestKnapsackSolutionAnalyzer.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
240        BestKnapsackSolutionAnalyzer.BinaryVectorParameter.Hidden = true;
241        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
242        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.Hidden = true;
243        BestKnapsackSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
244        BestKnapsackSolutionAnalyzer.WeightsParameter.Hidden = true;
245        BestKnapsackSolutionAnalyzer.ValuesParameter.ActualName = ValuesParameter.Name;
246        BestKnapsackSolutionAnalyzer.ValuesParameter.Hidden = true;
247      }
248    }
249    private void InitializeOperators() {
250      Operators.Add(new KnapsackImprovementOperator());
251      Operators.Add(new KnapsackPathRelinker());
252      Operators.Add(new KnapsackSimultaneousPathRelinker());
253      Operators.Add(new KnapsackSimilarityCalculator());
254      Operators.Add(new QualitySimilarityCalculator());
255      Operators.Add(new NoSimilarityCalculator());
256
257      Operators.Add(new BestKnapsackSolutionAnalyzer());
258      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
259      ParameterizeAnalyzer();
260      foreach (IBinaryVectorOperator op in ApplicationManager.Manager.GetInstances<IBinaryVectorOperator>()) {
261        if (!(op is ISingleObjectiveMoveEvaluator) || (op is IKnapsackMoveEvaluator)) {
262          Operators.Add(op);
263        }
264      }
265      ParameterizeOperators();
266      InitializeMoveGenerators();
267    }
268    private void InitializeMoveGenerators() {
269      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
270        if (op is IMoveGenerator) {
271          op.OneBitflipMoveParameter.ActualNameChanged += new EventHandler(OneBitflipMoveParameter_ActualNameChanged);
272        }
273      }
274    }
275    private void ParameterizeOperators() {
276      foreach (IBinaryVectorCrossover op in Operators.OfType<IBinaryVectorCrossover>()) {
277        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
278        op.ParentsParameter.Hidden = true;
279        op.ChildParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
280        op.ChildParameter.Hidden = true;
281      }
282      foreach (IBinaryVectorManipulator op in Operators.OfType<IBinaryVectorManipulator>()) {
283        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
284        op.BinaryVectorParameter.Hidden = true;
285      }
286      foreach (IBinaryVectorMoveOperator op in Operators.OfType<IBinaryVectorMoveOperator>()) {
287        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
288        op.BinaryVectorParameter.Hidden = true;
289      }
290      foreach (IKnapsackMoveEvaluator op in Operators.OfType<IKnapsackMoveEvaluator>()) {
291        op.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
292        op.KnapsackCapacityParameter.Hidden = true;
293        op.PenaltyParameter.ActualName = PenaltyParameter.Name;
294        op.PenaltyParameter.Hidden = true;
295        op.WeightsParameter.ActualName = WeightsParameter.Name;
296        op.WeightsParameter.Hidden = true;
297        op.ValuesParameter.ActualName = ValuesParameter.Name;
298        op.ValuesParameter.Hidden = true;
299      }
300      foreach (IBinaryVectorMultiNeighborhoodShakingOperator op in Operators.OfType<IBinaryVectorMultiNeighborhoodShakingOperator>()) {
301        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
302        op.BinaryVectorParameter.Hidden = true;
303      }
304      foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
305        op.SolutionParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
306        op.SolutionParameter.Hidden = true;
307      }
308      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
309        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
310        op.ParentsParameter.Hidden = true;
311      }
312      foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
313        op.SolutionVariableName = SolutionCreator.BinaryVectorParameter.ActualName;
314        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
315      }
316    }
317    #endregion
318
319    private void InitializeRandomKnapsackInstance() {
320      System.Random rand = new System.Random();
321
322      int itemCount = rand.Next(10, 100);
323      Weights = new IntArray(itemCount);
324      Values = new IntArray(itemCount);
325
326      double totalWeight = 0;
327
328      for (int i = 0; i < itemCount; i++) {
329        int value = rand.Next(1, 10);
330        int weight = rand.Next(1, 10);
331
332        Values[i] = value;
333        Weights[i] = weight;
334        totalWeight += weight;
335      }
336
337      int capacity = (int)Math.Round(0.7 * totalWeight);
338      KnapsackCapacity = new IntValue(capacity);
339    }
340  }
341}
Note: See TracBrowser for help on using the repository browser.