Free cookie consent management tool by TermsFeed Policy Generator

source: branches/3.2/sources/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs @ 3580

Last change on this file since 3580 was 3537, checked in by svonolfe, 15 years ago

Implemented reviewers comments for the KnapsackProblem (#917)

File size: 15.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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.Drawing;
25using System.Linq;
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;
34using HeuristicLab.Problems.Knapsack.Visualizers;
35
36namespace HeuristicLab.Problems.Knapsack {
37  [Item("Knapsack Problem", "Represents a Knapsack Problem.")]
38  [Creatable("Problems")]
39  [StorableClass]
40  public sealed class KnapsackProblem : ParameterizedNamedItem, ISingleObjectiveProblem {
41    public override Image ItemImage {
42      get { return HeuristicLab.Common.Resources.VS2008ImageLibrary.Type; }
43    }
44
45    #region Parameter Properties
46    public ValueParameter<BoolValue> MaximizationParameter {
47      get { return (ValueParameter<BoolValue>)Parameters["Maximization"]; }
48    }
49    IParameter ISingleObjectiveProblem.MaximizationParameter {
50      get { return MaximizationParameter; }
51    }
52    public ValueParameter<IntValue> KnapsackCapacityParameter {
53      get { return (ValueParameter<IntValue>)Parameters["KnapsackCapacity"]; }
54    }
55    public ValueParameter<IntArray> WeightsParameter {
56      get { return (ValueParameter<IntArray>)Parameters["Weights"]; }
57    }
58    public ValueParameter<IntArray> ValuesParameter {
59      get { return (ValueParameter<IntArray>)Parameters["Values"]; }
60    }
61    public ValueParameter<DoubleValue> PenaltyParameter {
62      get { return (ValueParameter<DoubleValue>)Parameters["Penalty"]; }
63    }
64    public ValueParameter<IBinaryVectorCreator> SolutionCreatorParameter {
65      get { return (ValueParameter<IBinaryVectorCreator>)Parameters["SolutionCreator"]; }
66    }
67    IParameter IProblem.SolutionCreatorParameter {
68      get { return SolutionCreatorParameter; }
69    }
70    public ValueParameter<IKnapsackEvaluator> EvaluatorParameter {
71      get { return (ValueParameter<IKnapsackEvaluator>)Parameters["Evaluator"]; }
72    }
73    IParameter IProblem.EvaluatorParameter {
74      get { return EvaluatorParameter; }
75    }
76    public OptionalValueParameter<IKnapsackSolutionsVisualizer> VisualizerParameter {
77      get { return (OptionalValueParameter<IKnapsackSolutionsVisualizer>)Parameters["Visualizer"]; }
78    }
79    IParameter IProblem.VisualizerParameter {
80      get { return VisualizerParameter; }
81    } 
82    public OptionalValueParameter<DoubleValue> BestKnownQualityParameter {
83      get { return (OptionalValueParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
84    }
85    IParameter ISingleObjectiveProblem.BestKnownQualityParameter {
86      get { return BestKnownQualityParameter; }
87    }
88    #endregion
89
90    #region Properties
91    public IntValue KnapsackCapacity {
92      get { return KnapsackCapacityParameter.Value; }
93      set { KnapsackCapacityParameter.Value = value; }
94    }
95    public IntArray Weights {
96      get { return WeightsParameter.Value; }
97      set { WeightsParameter.Value = value; }
98    }
99    public IntArray Values {
100      get { return ValuesParameter.Value; }
101      set { ValuesParameter.Value = value; }
102    }
103    public DoubleValue Penalty {
104      get { return PenaltyParameter.Value; }
105      set { PenaltyParameter.Value = value; }
106    }
107    public IBinaryVectorCreator SolutionCreator {
108      get { return SolutionCreatorParameter.Value; }
109      set { SolutionCreatorParameter.Value = value; }
110    }
111    ISolutionCreator IProblem.SolutionCreator {
112      get { return SolutionCreatorParameter.Value; }
113    }
114    public IKnapsackEvaluator Evaluator {
115      get { return EvaluatorParameter.Value; }
116      set { EvaluatorParameter.Value = value; }
117    }
118    ISingleObjectiveEvaluator ISingleObjectiveProblem.Evaluator {
119      get { return EvaluatorParameter.Value; }
120    }
121    IEvaluator IProblem.Evaluator {
122      get { return EvaluatorParameter.Value; }
123    }
124    public IKnapsackSolutionsVisualizer Visualizer {
125      get { return VisualizerParameter.Value; }
126      set { VisualizerParameter.Value = value; }
127    }
128    ISolutionsVisualizer IProblem.Visualizer {
129      get { return VisualizerParameter.Value; }
130    }
131    public DoubleValue BestKnownQuality {
132      get { return BestKnownQualityParameter.Value; }
133      set { BestKnownQualityParameter.Value = value; }
134    }
135    private List<IBinaryVectorOperator> operators;
136    public IEnumerable<IOperator> Operators {
137      get { return operators.Cast<IOperator>(); }
138    }
139    #endregion
140
141    private void InitializeRandomKnapsackInstance() {
142      System.Random rand = new System.Random();
143
144      int itemCount = rand.Next(10, 100);
145      Weights = new IntArray(itemCount);
146      Values = new IntArray(itemCount);
147
148      double totalWeight = 0;
149
150      for (int i = 0; i < itemCount; i++ ) {
151        int value = rand.Next(1, 10);
152        int weight = rand.Next(1, 10);
153
154        Values[i] = value;
155        Weights[i] = weight;
156        totalWeight += weight;
157      }
158
159      int capacity = (int)Math.Round(0.7 * totalWeight);
160      KnapsackCapacity = new IntValue(capacity);
161    }
162
163    public KnapsackProblem()
164      : base() {
165      RandomBinaryVectorCreator creator = new RandomBinaryVectorCreator();
166      KnapsackEvaluator evaluator = new KnapsackEvaluator();
167      IKnapsackSolutionsVisualizer visualizer = new BestKnapsackVisualizer();
168
169      Parameters.Add(new ValueParameter<BoolValue>("Maximization", "Set to true as the Knapsack Problem is a maximization problem.", new BoolValue(true)));
170      Parameters.Add(new ValueParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack.", new IntValue(0)));
171      Parameters.Add(new ValueParameter<IntArray>("Weights", "The weights of the items.", new IntArray(5)));
172      Parameters.Add(new ValueParameter<IntArray>("Values", "The values of the items.", new IntArray(5)));
173      Parameters.Add(new ValueParameter<DoubleValue>("Penalty", "The penalty value for each unit of overweight.", new DoubleValue(1)));
174      Parameters.Add(new ValueParameter<IBinaryVectorCreator>("SolutionCreator", "The operator which should be used to create new Knapsack solutions.", creator));
175      Parameters.Add(new ValueParameter<IKnapsackEvaluator>("Evaluator", "The operator which should be used to evaluate Knapsack solutions.", evaluator));
176      Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this Knapsack instance."));
177      Parameters.Add(new ValueParameter<IKnapsackSolutionsVisualizer>("Visualizer", "The operator which should be used to visualize Knapsack solutions.", visualizer));
178
179      creator.BinaryVectorParameter.ActualName = "KnapsackSolution";
180
181      InitializeRandomKnapsackInstance();
182     
183      ParameterizeSolutionCreator();
184      ParameterizeEvaluator();
185      ParameterizeVisualizer();
186
187      Initialize();
188    }
189
190    [StorableConstructor]
191    private KnapsackProblem(bool deserializing) : base() { }
192
193    public override IDeepCloneable Clone(Cloner cloner) {
194      KnapsackProblem clone = (KnapsackProblem)base.Clone(cloner);
195      clone.Initialize();
196      return clone;
197    }
198
199    #region Events
200    public event EventHandler SolutionCreatorChanged;
201    private void OnSolutionCreatorChanged() {
202      if (SolutionCreatorChanged != null)
203        SolutionCreatorChanged(this, EventArgs.Empty);
204    }
205    public event EventHandler EvaluatorChanged;
206    private void OnEvaluatorChanged() {
207      if (EvaluatorChanged != null)
208        EvaluatorChanged(this, EventArgs.Empty);
209    }
210    public event EventHandler VisualizerChanged;
211    private void OnVisualizerChanged() {
212      if (VisualizerChanged != null)
213        VisualizerChanged(this, EventArgs.Empty);
214    }
215
216    public event EventHandler OperatorsChanged;
217    private void OnOperatorsChanged() {
218      if (OperatorsChanged != null)
219        OperatorsChanged(this, EventArgs.Empty);
220    }
221
222    private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs e) {
223      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
224      ParameterizeSolutionCreator();
225      ParameterizeEvaluator();
226      ParameterizeVisualizer();
227      ParameterizeOperators();
228      OnSolutionCreatorChanged();
229    }
230    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
231      ParameterizeEvaluator();
232      ParameterizeVisualizer();
233      ParameterizeOperators();
234    }
235    private void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
236      ParameterizeEvaluator();
237      ParameterizeVisualizer();
238      OnEvaluatorChanged();
239    }
240    void KnapsackCapacityParameter_ValueChanged(object sender, EventArgs e) {
241      ParameterizeEvaluator();
242      ParameterizeVisualizer();
243    }
244    void WeightsParameter_ValueChanged(object sender, EventArgs e) {
245      ParameterizeEvaluator();
246      ParameterizeVisualizer();
247      ParameterizeSolutionCreator();
248
249      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
250    }
251    void WeightsValue_Reset(object sender, EventArgs e) {
252      ParameterizeSolutionCreator();
253
254      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
255        ((IStringConvertibleArray)ValuesParameter.Value).Length = WeightsParameter.Value.Length;
256    }
257    void ValuesParameter_ValueChanged(object sender, EventArgs e) {
258      ParameterizeEvaluator();
259      ParameterizeVisualizer();
260      ParameterizeSolutionCreator();
261
262      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
263    }
264    void ValuesValue_Reset(object sender, EventArgs e) {
265      ParameterizeSolutionCreator();
266
267      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
268        ((IStringConvertibleArray)WeightsParameter.Value).Length = ValuesParameter.Value.Length;
269    }
270    void PenaltyParameter_ValueChanged(object sender, EventArgs e) {
271      ParameterizeEvaluator();
272    }
273    void VisualizerParameter_ValueChanged(object sender, EventArgs e) {
274      OnVisualizerChanged();
275    }
276    void OneBitflipMoveParameter_ActualNameChanged(object sender, EventArgs e) {
277      string name = ((ILookupParameter<OneBitflipMove>)sender).ActualName;
278      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
279        op.OneBitflipMoveParameter.ActualName = name;
280      }
281    }
282    #endregion
283
284    #region Helpers
285    [StorableHook(HookType.AfterDeserialization)]
286    private void Initialize() {
287      InitializeOperators();
288      SolutionCreatorParameter.ValueChanged += new EventHandler(SolutionCreatorParameter_ValueChanged);
289      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
290      EvaluatorParameter.ValueChanged += new EventHandler(EvaluatorParameter_ValueChanged);
291      KnapsackCapacityParameter.ValueChanged += new EventHandler(KnapsackCapacityParameter_ValueChanged);
292      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
293      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
294      ValuesParameter.ValueChanged += new EventHandler(ValuesParameter_ValueChanged);
295      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
296      PenaltyParameter.ValueChanged += new EventHandler(PenaltyParameter_ValueChanged);
297      VisualizerParameter.ValueChanged += new EventHandler(VisualizerParameter_ValueChanged);
298    }
299    private void ParameterizeSolutionCreator() {
300      if(SolutionCreator.LengthParameter.Value == null ||
301        SolutionCreator.LengthParameter.Value.Value != WeightsParameter.Value.Length)
302        SolutionCreator.LengthParameter.Value = new IntValue(WeightsParameter.Value.Length);
303    }
304    private void ParameterizeEvaluator() {
305      if (Evaluator is KnapsackEvaluator) {
306        KnapsackEvaluator knapsackEvaluator =
307          (KnapsackEvaluator)Evaluator;
308        knapsackEvaluator.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
309        knapsackEvaluator.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
310        knapsackEvaluator.WeightsParameter.ActualName = WeightsParameter.Name;
311        knapsackEvaluator.ValuesParameter.ActualName = ValuesParameter.Name;
312        knapsackEvaluator.PenaltyParameter.ActualName = PenaltyParameter.Name;
313      }
314    }
315    private void ParameterizeVisualizer() {
316      if (Visualizer is IKnapsackSolutionsVisualizer) {
317        IKnapsackSolutionsVisualizer visualizer =
318          (IKnapsackSolutionsVisualizer)Visualizer;
319        visualizer.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
320        visualizer.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
321        visualizer.WeightsParameter.ActualName = WeightsParameter.Name;
322        visualizer.ValuesParameter.ActualName = ValuesParameter.Name;
323      }
324    }
325    private void InitializeOperators() {
326      operators = new List<IBinaryVectorOperator>();
327      foreach (IBinaryVectorOperator op in ApplicationManager.Manager.GetInstances<IBinaryVectorOperator>()) {
328        if (!(op is ISingleObjectiveMoveEvaluator) || (op is IKnapsackMoveEvaluator)) {
329          operators.Add(op);
330        }
331      }
332      ParameterizeOperators();
333      InitializeMoveGenerators();
334    }
335    private void InitializeMoveGenerators() {
336      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
337        if (op is IMoveGenerator) {
338          op.OneBitflipMoveParameter.ActualNameChanged += new EventHandler(OneBitflipMoveParameter_ActualNameChanged);
339        }
340      }
341    }
342    private void ParameterizeOperators() {
343      foreach (IBinaryVectorCrossover op in Operators.OfType<IBinaryVectorCrossover>()) {
344        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
345        op.ChildParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
346      }
347      foreach (IBinaryVectorManipulator op in Operators.OfType<IBinaryVectorManipulator>()) {
348        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
349      }
350      foreach (IBinaryVectorMoveOperator op in Operators.OfType<IBinaryVectorMoveOperator>()) {
351        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
352      }
353      foreach (IKnapsackMoveEvaluator op in Operators.OfType<IKnapsackMoveEvaluator>()) {
354        op.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
355        op.PenaltyParameter.ActualName = PenaltyParameter.Name;
356        op.WeightsParameter.ActualName = WeightsParameter.Name;
357        op.ValuesParameter.ActualName = ValuesParameter.Name;
358      }
359    }
360    #endregion
361  }
362}
Note: See TracBrowser for help on using the repository browser.