Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 4118 was 4118, checked in by abeham, 14 years ago

#1090

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