Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs @ 12087

Last change on this file since 12087 was 12087, checked in by jkarder, 9 years ago

#2332: removed unused similarity analyzer properties
File size: 15.2 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.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    #endregion
85
86    // BackwardsCompatibility3.3
87    #region Backwards compatible code, remove with 3.4
88    [Obsolete]
89    [Storable(Name = "operators")]
90    private IEnumerable<IOperator> oldOperators {
91      get { return null; }
92      set {
93        if (value != null && value.Any())
94          Operators.AddRange(value);
95      }
96    }
97    #endregion
98
99    [StorableConstructor]
100    private KnapsackProblem(bool deserializing) : base(deserializing) { }
101    private KnapsackProblem(KnapsackProblem original, Cloner cloner)
102      : base(original, cloner) {
103      RegisterEventHandlers();
104    }
105    public override IDeepCloneable Clone(Cloner cloner) {
106      return new KnapsackProblem(this, cloner);
107    }
108    public KnapsackProblem()
109      : base(new KnapsackEvaluator(), new RandomBinaryVectorCreator()) {
110      Parameters.Add(new ValueParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack.", new IntValue(0)));
111      Parameters.Add(new ValueParameter<IntArray>("Weights", "The weights of the items.", new IntArray(5)));
112      Parameters.Add(new ValueParameter<IntArray>("Values", "The values of the items.", new IntArray(5)));
113      Parameters.Add(new ValueParameter<DoubleValue>("Penalty", "The penalty value for each unit of overweight.", new DoubleValue(1)));
114      Parameters.Add(new OptionalValueParameter<BinaryVector>("BestKnownSolution", "The best known solution of this Knapsack instance."));
115
116      Maximization.Value = true;
117      MaximizationParameter.Hidden = true;
118
119      SolutionCreator.BinaryVectorParameter.ActualName = "KnapsackSolution";
120
121      InitializeRandomKnapsackInstance();
122
123      ParameterizeSolutionCreator();
124      ParameterizeEvaluator();
125
126      InitializeOperators();
127      RegisterEventHandlers();
128    }
129
130    #region Events
131    protected override void OnSolutionCreatorChanged() {
132      base.OnSolutionCreatorChanged();
133      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
134      ParameterizeSolutionCreator();
135      ParameterizeEvaluator();
136      ParameterizeAnalyzer();
137      ParameterizeOperators();
138    }
139    protected override void OnEvaluatorChanged() {
140      base.OnEvaluatorChanged();
141      ParameterizeEvaluator();
142      ParameterizeAnalyzer();
143    }
144    private void SolutionCreator_BinaryVectorParameter_ActualNameChanged(object sender, EventArgs e) {
145      ParameterizeEvaluator();
146      ParameterizeAnalyzer();
147      ParameterizeOperators();
148    }
149    private void KnapsackCapacityParameter_ValueChanged(object sender, EventArgs e) {
150      ParameterizeEvaluator();
151      ParameterizeAnalyzer();
152    }
153    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
154      ParameterizeEvaluator();
155      ParameterizeAnalyzer();
156      ParameterizeSolutionCreator();
157
158      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
159    }
160    private void WeightsValue_Reset(object sender, EventArgs e) {
161      ParameterizeSolutionCreator();
162
163      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
164        ((IStringConvertibleArray)ValuesParameter.Value).Length = WeightsParameter.Value.Length;
165    }
166    private void ValuesParameter_ValueChanged(object sender, EventArgs e) {
167      ParameterizeEvaluator();
168      ParameterizeAnalyzer();
169      ParameterizeSolutionCreator();
170
171      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
172    }
173    private void ValuesValue_Reset(object sender, EventArgs e) {
174      ParameterizeSolutionCreator();
175
176      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
177        ((IStringConvertibleArray)WeightsParameter.Value).Length = ValuesParameter.Value.Length;
178    }
179    private void PenaltyParameter_ValueChanged(object sender, EventArgs e) {
180      ParameterizeEvaluator();
181    }
182    private void OneBitflipMoveParameter_ActualNameChanged(object sender, EventArgs e) {
183      string name = ((ILookupParameter<OneBitflipMove>)sender).ActualName;
184      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
185        op.OneBitflipMoveParameter.ActualName = name;
186      }
187    }
188    #endregion
189
190    #region Helpers
191    [StorableHook(HookType.AfterDeserialization)]
192    private void AfterDeserialization() {
193      // BackwardsCompatibility3.3
194      #region Backwards compatible code (remove with 3.4)
195      if (Operators.Count == 0) InitializeOperators();
196      #endregion
197      RegisterEventHandlers();
198    }
199
200    private void RegisterEventHandlers() {
201      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
202      KnapsackCapacityParameter.ValueChanged += new EventHandler(KnapsackCapacityParameter_ValueChanged);
203      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
204      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
205      ValuesParameter.ValueChanged += new EventHandler(ValuesParameter_ValueChanged);
206      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
207      PenaltyParameter.ValueChanged += new EventHandler(PenaltyParameter_ValueChanged);
208    }
209    private void ParameterizeSolutionCreator() {
210      if (SolutionCreator.LengthParameter.Value == null ||
211        SolutionCreator.LengthParameter.Value.Value != WeightsParameter.Value.Length)
212        SolutionCreator.LengthParameter.Value = new IntValue(WeightsParameter.Value.Length);
213    }
214    private void ParameterizeEvaluator() {
215      if (Evaluator is KnapsackEvaluator) {
216        KnapsackEvaluator knapsackEvaluator =
217          (KnapsackEvaluator)Evaluator;
218        knapsackEvaluator.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
219        knapsackEvaluator.BinaryVectorParameter.Hidden = true;
220        knapsackEvaluator.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
221        knapsackEvaluator.KnapsackCapacityParameter.Hidden = true;
222        knapsackEvaluator.WeightsParameter.ActualName = WeightsParameter.Name;
223        knapsackEvaluator.WeightsParameter.Hidden = true;
224        knapsackEvaluator.ValuesParameter.ActualName = ValuesParameter.Name;
225        knapsackEvaluator.ValuesParameter.Hidden = true;
226        knapsackEvaluator.PenaltyParameter.ActualName = PenaltyParameter.Name;
227        knapsackEvaluator.PenaltyParameter.Hidden = true;
228      }
229    }
230    private void ParameterizeAnalyzer() {
231      if (BestKnapsackSolutionAnalyzer != null) {
232        BestKnapsackSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
233        BestKnapsackSolutionAnalyzer.MaximizationParameter.Hidden = true;
234        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
235        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.Hidden = true;
236        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
237        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.Hidden = true;
238        BestKnapsackSolutionAnalyzer.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
239        BestKnapsackSolutionAnalyzer.BinaryVectorParameter.Hidden = true;
240        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
241        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.Hidden = true;
242        BestKnapsackSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
243        BestKnapsackSolutionAnalyzer.WeightsParameter.Hidden = true;
244        BestKnapsackSolutionAnalyzer.ValuesParameter.ActualName = ValuesParameter.Name;
245        BestKnapsackSolutionAnalyzer.ValuesParameter.Hidden = true;
246      }
247    }
248    private void InitializeOperators() {
249      Operators.Add(new KnapsackImprovementOperator());
250      Operators.Add(new KnapsackPathRelinker());
251      Operators.Add(new KnapsackSimultaneousPathRelinker());
252      Operators.Add(new KnapsackSimilarityCalculator());
253
254      Operators.Add(new BestKnapsackSolutionAnalyzer());
255      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
256      ParameterizeAnalyzer();
257      foreach (IBinaryVectorOperator op in ApplicationManager.Manager.GetInstances<IBinaryVectorOperator>()) {
258        if (!(op is ISingleObjectiveMoveEvaluator) || (op is IKnapsackMoveEvaluator)) {
259          Operators.Add(op);
260        }
261      }
262      ParameterizeOperators();
263      InitializeMoveGenerators();
264    }
265    private void InitializeMoveGenerators() {
266      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
267        if (op is IMoveGenerator) {
268          op.OneBitflipMoveParameter.ActualNameChanged += new EventHandler(OneBitflipMoveParameter_ActualNameChanged);
269        }
270      }
271    }
272    private void ParameterizeOperators() {
273      foreach (IBinaryVectorCrossover op in Operators.OfType<IBinaryVectorCrossover>()) {
274        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
275        op.ParentsParameter.Hidden = true;
276        op.ChildParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
277        op.ChildParameter.Hidden = true;
278      }
279      foreach (IBinaryVectorManipulator op in Operators.OfType<IBinaryVectorManipulator>()) {
280        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
281        op.BinaryVectorParameter.Hidden = true;
282      }
283      foreach (IBinaryVectorMoveOperator op in Operators.OfType<IBinaryVectorMoveOperator>()) {
284        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
285        op.BinaryVectorParameter.Hidden = true;
286      }
287      foreach (IKnapsackMoveEvaluator op in Operators.OfType<IKnapsackMoveEvaluator>()) {
288        op.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
289        op.KnapsackCapacityParameter.Hidden = true;
290        op.PenaltyParameter.ActualName = PenaltyParameter.Name;
291        op.PenaltyParameter.Hidden = true;
292        op.WeightsParameter.ActualName = WeightsParameter.Name;
293        op.WeightsParameter.Hidden = true;
294        op.ValuesParameter.ActualName = ValuesParameter.Name;
295        op.ValuesParameter.Hidden = true;
296      }
297      foreach (IBinaryVectorMultiNeighborhoodShakingOperator op in Operators.OfType<IBinaryVectorMultiNeighborhoodShakingOperator>()) {
298        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
299        op.BinaryVectorParameter.Hidden = true;
300      }
301      foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
302        op.SolutionParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
303        op.SolutionParameter.Hidden = true;
304      }
305      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
306        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
307        op.ParentsParameter.Hidden = true;
308      }
309      foreach (KnapsackSimilarityCalculator op in Operators.OfType<KnapsackSimilarityCalculator>()) {
310        op.SolutionVariableName = SolutionCreator.BinaryVectorParameter.ActualName;
311        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
312      }
313    }
314    #endregion
315
316    private void InitializeRandomKnapsackInstance() {
317      System.Random rand = new System.Random();
318
319      int itemCount = rand.Next(10, 100);
320      Weights = new IntArray(itemCount);
321      Values = new IntArray(itemCount);
322
323      double totalWeight = 0;
324
325      for (int i = 0; i < itemCount; i++) {
326        int value = rand.Next(1, 10);
327        int weight = rand.Next(1, 10);
328
329        Values[i] = value;
330        Weights[i] = weight;
331        totalWeight += weight;
332      }
333
334      int capacity = (int)Math.Round(0.7 * totalWeight);
335      KnapsackCapacity = new IntValue(capacity);
336    }
337  }
338}
Note: See TracBrowser for help on using the repository browser.