Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs @ 16126

Last change on this file since 16126 was 15584, checked in by swagner, 7 years ago

#2640: Updated year of copyrights in license headers on stable
File size: 15.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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 HammingSimilarityCalculator());
254      Operators.Add(new QualitySimilarityCalculator());
255
256      Operators.Add(new BestKnapsackSolutionAnalyzer());
257      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
258      ParameterizeAnalyzer();
259      foreach (IBinaryVectorOperator op in ApplicationManager.Manager.GetInstances<IBinaryVectorOperator>()) {
260        if (!(op is ISingleObjectiveMoveEvaluator) || (op is IKnapsackMoveEvaluator)) {
261          Operators.Add(op);
262        }
263      }
264      ParameterizeOperators();
265      InitializeMoveGenerators();
266    }
267    private void InitializeMoveGenerators() {
268      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
269        if (op is IMoveGenerator) {
270          op.OneBitflipMoveParameter.ActualNameChanged += new EventHandler(OneBitflipMoveParameter_ActualNameChanged);
271        }
272      }
273    }
274    private void ParameterizeOperators() {
275      foreach (IBinaryVectorCrossover op in Operators.OfType<IBinaryVectorCrossover>()) {
276        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
277        op.ParentsParameter.Hidden = true;
278        op.ChildParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
279        op.ChildParameter.Hidden = true;
280      }
281      foreach (IBinaryVectorManipulator op in Operators.OfType<IBinaryVectorManipulator>()) {
282        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
283        op.BinaryVectorParameter.Hidden = true;
284      }
285      foreach (IBinaryVectorMoveOperator op in Operators.OfType<IBinaryVectorMoveOperator>()) {
286        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
287        op.BinaryVectorParameter.Hidden = true;
288      }
289      foreach (IKnapsackMoveEvaluator op in Operators.OfType<IKnapsackMoveEvaluator>()) {
290        op.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
291        op.KnapsackCapacityParameter.Hidden = true;
292        op.PenaltyParameter.ActualName = PenaltyParameter.Name;
293        op.PenaltyParameter.Hidden = true;
294        op.WeightsParameter.ActualName = WeightsParameter.Name;
295        op.WeightsParameter.Hidden = true;
296        op.ValuesParameter.ActualName = ValuesParameter.Name;
297        op.ValuesParameter.Hidden = true;
298      }
299      foreach (IBinaryVectorMultiNeighborhoodShakingOperator op in Operators.OfType<IBinaryVectorMultiNeighborhoodShakingOperator>()) {
300        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
301        op.BinaryVectorParameter.Hidden = true;
302      }
303      foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
304        op.SolutionParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
305        op.SolutionParameter.Hidden = true;
306      }
307      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
308        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
309        op.ParentsParameter.Hidden = true;
310      }
311      foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
312        op.SolutionVariableName = SolutionCreator.BinaryVectorParameter.ActualName;
313        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
314      }
315    }
316    #endregion
317
318    private void InitializeRandomKnapsackInstance() {
319      System.Random rand = new System.Random();
320
321      int itemCount = rand.Next(10, 100);
322      Weights = new IntArray(itemCount);
323      Values = new IntArray(itemCount);
324
325      double totalWeight = 0;
326
327      for (int i = 0; i < itemCount; i++) {
328        int value = rand.Next(1, 10);
329        int weight = rand.Next(1, 10);
330
331        Values[i] = value;
332        Weights[i] = weight;
333        totalWeight += weight;
334      }
335
336      int capacity = (int)Math.Round(0.7 * totalWeight);
337      KnapsackCapacity = new IntValue(capacity);
338    }
339  }
340}
Note: See TracBrowser for help on using the repository browser.