Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 10550 was 9456, checked in by swagner, 12 years ago

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