Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 3818 was 3797, checked in by mkommend, 14 years ago

corrected namespaces and removed resources files in HL 3.3 solution (ticket #893)
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;
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    private List<IOperator> operators;
129    public IEnumerable<IOperator> Operators {
130      get { return operators.Cast<IOperator>(); }
131    }
132    private BestKnapsackSolutionAnalyzer BestKnapsackSolutionAnalyzer {
133      get { return operators.OfType<BestKnapsackSolutionAnalyzer>().FirstOrDefault(); }
134    }
135    #endregion
136
137    private void InitializeRandomKnapsackInstance() {
138      System.Random rand = new System.Random();
139
140      int itemCount = rand.Next(10, 100);
141      Weights = new IntArray(itemCount);
142      Values = new IntArray(itemCount);
143
144      double totalWeight = 0;
145
146      for (int i = 0; i < itemCount; i++ ) {
147        int value = rand.Next(1, 10);
148        int weight = rand.Next(1, 10);
149
150        Values[i] = value;
151        Weights[i] = weight;
152        totalWeight += weight;
153      }
154
155      int capacity = (int)Math.Round(0.7 * totalWeight);
156      KnapsackCapacity = new IntValue(capacity);
157    }
158
159    public KnapsackProblem()
160      : base() {
161      RandomBinaryVectorCreator creator = new RandomBinaryVectorCreator();
162      KnapsackEvaluator evaluator = new KnapsackEvaluator();
163
164      Parameters.Add(new ValueParameter<BoolValue>("Maximization", "Set to true as the Knapsack Problem is a maximization problem.", new BoolValue(true)));
165      Parameters.Add(new ValueParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack.", new IntValue(0)));
166      Parameters.Add(new ValueParameter<IntArray>("Weights", "The weights of the items.", new IntArray(5)));
167      Parameters.Add(new ValueParameter<IntArray>("Values", "The values of the items.", new IntArray(5)));
168      Parameters.Add(new ValueParameter<DoubleValue>("Penalty", "The penalty value for each unit of overweight.", new DoubleValue(1)));
169      Parameters.Add(new ValueParameter<IBinaryVectorCreator>("SolutionCreator", "The operator which should be used to create new Knapsack solutions.", creator));
170      Parameters.Add(new ValueParameter<IKnapsackEvaluator>("Evaluator", "The operator which should be used to evaluate Knapsack solutions.", evaluator));
171      Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this Knapsack instance."));
172      Parameters.Add(new OptionalValueParameter<BinaryVector>("BestKnownSolution", "The best known solution of this Knapsack instance."));
173
174      creator.BinaryVectorParameter.ActualName = "KnapsackSolution";
175
176      InitializeRandomKnapsackInstance();
177     
178      ParameterizeSolutionCreator();
179      ParameterizeEvaluator();
180
181      Initialize();
182    }
183
184    [StorableConstructor]
185    private KnapsackProblem(bool deserializing) : base() { }
186
187    public override IDeepCloneable Clone(Cloner cloner) {
188      KnapsackProblem clone = (KnapsackProblem)base.Clone(cloner);
189      clone.Initialize();
190      return clone;
191    }
192
193    #region Events
194    public event EventHandler SolutionCreatorChanged;
195    private void OnSolutionCreatorChanged() {
196      EventHandler handler = SolutionCreatorChanged;
197      if (handler != null) handler(this, EventArgs.Empty);
198    }
199    public event EventHandler EvaluatorChanged;
200    private void OnEvaluatorChanged() {
201      EventHandler handler = EvaluatorChanged;
202      if (handler != null) handler(this, EventArgs.Empty);
203    }
204    public event EventHandler OperatorsChanged;
205    private void OnOperatorsChanged() {
206      EventHandler handler = OperatorsChanged;
207      if (handler != null) handler(this, EventArgs.Empty);
208    }
209    public event EventHandler Reset;
210    private void OnReset() {
211      EventHandler handler = Reset;
212      if (handler != null) handler(this, EventArgs.Empty);
213    }
214
215    private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs e) {
216      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
217      ParameterizeSolutionCreator();
218      ParameterizeEvaluator();
219      ParameterizeAnalyzer();
220      ParameterizeOperators();
221      OnSolutionCreatorChanged();
222    }
223    private void SolutionCreator_BinaryVectorParameter_ActualNameChanged(object sender, EventArgs e) {
224      ParameterizeEvaluator();
225      ParameterizeAnalyzer();
226      ParameterizeOperators();
227    }
228    private void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
229      ParameterizeEvaluator();
230      ParameterizeAnalyzer();
231      OnEvaluatorChanged();
232    }
233    void KnapsackCapacityParameter_ValueChanged(object sender, EventArgs e) {
234      ParameterizeEvaluator();
235      ParameterizeAnalyzer();
236    }
237    void WeightsParameter_ValueChanged(object sender, EventArgs e) {
238      ParameterizeEvaluator();
239      ParameterizeAnalyzer();
240      ParameterizeSolutionCreator();
241
242      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
243    }
244    void WeightsValue_Reset(object sender, EventArgs e) {
245      ParameterizeSolutionCreator();
246
247      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
248        ((IStringConvertibleArray)ValuesParameter.Value).Length = WeightsParameter.Value.Length;
249    }
250    void ValuesParameter_ValueChanged(object sender, EventArgs e) {
251      ParameterizeEvaluator();
252      ParameterizeAnalyzer();
253      ParameterizeSolutionCreator();
254
255      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
256    }
257    void ValuesValue_Reset(object sender, EventArgs e) {
258      ParameterizeSolutionCreator();
259
260      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
261        ((IStringConvertibleArray)WeightsParameter.Value).Length = ValuesParameter.Value.Length;
262    }
263    void PenaltyParameter_ValueChanged(object sender, EventArgs e) {
264      ParameterizeEvaluator();
265    }
266    void OneBitflipMoveParameter_ActualNameChanged(object sender, EventArgs e) {
267      string name = ((ILookupParameter<OneBitflipMove>)sender).ActualName;
268      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
269        op.OneBitflipMoveParameter.ActualName = name;
270      }
271    }
272    #endregion
273
274    #region Helpers
275    [StorableHook(HookType.AfterDeserialization)]
276    private void Initialize() {
277      InitializeOperators();
278      SolutionCreatorParameter.ValueChanged += new EventHandler(SolutionCreatorParameter_ValueChanged);
279      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
280      EvaluatorParameter.ValueChanged += new EventHandler(EvaluatorParameter_ValueChanged);
281      KnapsackCapacityParameter.ValueChanged += new EventHandler(KnapsackCapacityParameter_ValueChanged);
282      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
283      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
284      ValuesParameter.ValueChanged += new EventHandler(ValuesParameter_ValueChanged);
285      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
286      PenaltyParameter.ValueChanged += new EventHandler(PenaltyParameter_ValueChanged);
287    }
288    private void ParameterizeSolutionCreator() {
289      if(SolutionCreator.LengthParameter.Value == null ||
290        SolutionCreator.LengthParameter.Value.Value != WeightsParameter.Value.Length)
291        SolutionCreator.LengthParameter.Value = new IntValue(WeightsParameter.Value.Length);
292    }
293    private void ParameterizeEvaluator() {
294      if (Evaluator is KnapsackEvaluator) {
295        KnapsackEvaluator knapsackEvaluator =
296          (KnapsackEvaluator)Evaluator;
297        knapsackEvaluator.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
298        knapsackEvaluator.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
299        knapsackEvaluator.WeightsParameter.ActualName = WeightsParameter.Name;
300        knapsackEvaluator.ValuesParameter.ActualName = ValuesParameter.Name;
301        knapsackEvaluator.PenaltyParameter.ActualName = PenaltyParameter.Name;
302      }
303    }
304    private void ParameterizeAnalyzer() {
305      BestKnapsackSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
306      BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
307      BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
308      BestKnapsackSolutionAnalyzer.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
309      BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
310      BestKnapsackSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
311      BestKnapsackSolutionAnalyzer.ValuesParameter.ActualName = ValuesParameter.Name;
312      BestKnapsackSolutionAnalyzer.ResultsParameter.ActualName = "Results";
313    }
314    private void InitializeOperators() {
315      operators = new List<IOperator>();
316      operators.Add(new BestKnapsackSolutionAnalyzer());
317      ParameterizeAnalyzer();
318      foreach (IBinaryVectorOperator op in ApplicationManager.Manager.GetInstances<IBinaryVectorOperator>()) {
319        if (!(op is ISingleObjectiveMoveEvaluator) || (op is IKnapsackMoveEvaluator)) {
320          operators.Add(op);
321        }
322      }
323      ParameterizeOperators();
324      InitializeMoveGenerators();
325    }
326    private void InitializeMoveGenerators() {
327      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
328        if (op is IMoveGenerator) {
329          op.OneBitflipMoveParameter.ActualNameChanged += new EventHandler(OneBitflipMoveParameter_ActualNameChanged);
330        }
331      }
332    }
333    private void ParameterizeOperators() {
334      foreach (IBinaryVectorCrossover op in Operators.OfType<IBinaryVectorCrossover>()) {
335        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
336        op.ChildParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
337      }
338      foreach (IBinaryVectorManipulator op in Operators.OfType<IBinaryVectorManipulator>()) {
339        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
340      }
341      foreach (IBinaryVectorMoveOperator op in Operators.OfType<IBinaryVectorMoveOperator>()) {
342        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
343      }
344      foreach (IKnapsackMoveEvaluator op in Operators.OfType<IKnapsackMoveEvaluator>()) {
345        op.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
346        op.PenaltyParameter.ActualName = PenaltyParameter.Name;
347        op.WeightsParameter.ActualName = WeightsParameter.Name;
348        op.ValuesParameter.ActualName = ValuesParameter.Name;
349      }
350    }
351    #endregion
352  }
353}
Note: See TracBrowser for help on using the repository browser.