Free cookie consent management tool by TermsFeed Policy Generator

source: branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs @ 7887

Last change on this file since 7887 was 7789, checked in by jkarder, 13 years ago

#1331:

  • added Scatter Search algorithm
  • added problem specific operators for improvement, path relinking and similarity calculation
  • adjusted event handling
File size: 14.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.BinaryVectorEncoding;
29using HeuristicLab.Optimization;
30using HeuristicLab.Optimization.Operators;
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      BestKnapsackSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
232      BestKnapsackSolutionAnalyzer.MaximizationParameter.Hidden = true;
233      BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
234      BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.Hidden = true;
235      BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
236      BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.Hidden = true;
237      BestKnapsackSolutionAnalyzer.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
238      BestKnapsackSolutionAnalyzer.BinaryVectorParameter.Hidden = true;
239      BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
240      BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.Hidden = true;
241      BestKnapsackSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
242      BestKnapsackSolutionAnalyzer.WeightsParameter.Hidden = true;
243      BestKnapsackSolutionAnalyzer.ValuesParameter.ActualName = ValuesParameter.Name;
244      BestKnapsackSolutionAnalyzer.ValuesParameter.Hidden = true;
245    }
246    private void InitializeOperators() {
247      Operators.Add(new KnapsackImprovementOperator());
248      Operators.Add(new KnapsackMultipleGuidesPathRelinker());
249      Operators.Add(new KnapsackPathRelinker());
250      Operators.Add(new KnapsackSimultaneousPathRelinker());
251      Operators.Add(new KnapsackSimilarityCalculator());
252
253      Operators.Add(new BestKnapsackSolutionAnalyzer());
254      ParameterizeAnalyzer();
255      foreach (IBinaryVectorOperator op in ApplicationManager.Manager.GetInstances<IBinaryVectorOperator>()) {
256        if (!(op is ISingleObjectiveMoveEvaluator) || (op is IKnapsackMoveEvaluator)) {
257          Operators.Add(op);
258        }
259      }
260      ParameterizeOperators();
261      InitializeMoveGenerators();
262    }
263    private void InitializeMoveGenerators() {
264      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
265        if (op is IMoveGenerator) {
266          op.OneBitflipMoveParameter.ActualNameChanged += new EventHandler(OneBitflipMoveParameter_ActualNameChanged);
267        }
268      }
269    }
270    private void ParameterizeOperators() {
271      foreach (IBinaryVectorCrossover op in Operators.OfType<IBinaryVectorCrossover>()) {
272        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
273        op.ParentsParameter.Hidden = true;
274        op.ChildParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
275        op.ChildParameter.Hidden = true;
276      }
277      foreach (IBinaryVectorManipulator op in Operators.OfType<IBinaryVectorManipulator>()) {
278        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
279        op.BinaryVectorParameter.Hidden = true;
280      }
281      foreach (IBinaryVectorMoveOperator op in Operators.OfType<IBinaryVectorMoveOperator>()) {
282        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
283        op.BinaryVectorParameter.Hidden = true;
284      }
285      foreach (IKnapsackMoveEvaluator op in Operators.OfType<IKnapsackMoveEvaluator>()) {
286        op.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
287        op.KnapsackCapacityParameter.Hidden = true;
288        op.PenaltyParameter.ActualName = PenaltyParameter.Name;
289        op.PenaltyParameter.Hidden = true;
290        op.WeightsParameter.ActualName = WeightsParameter.Name;
291        op.WeightsParameter.Hidden = true;
292        op.ValuesParameter.ActualName = ValuesParameter.Name;
293        op.ValuesParameter.Hidden = true;
294      }
295      foreach (var op in Operators.OfType<IBinaryVectorMultiNeighborhoodShakingOperator>()) {
296        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
297        op.BinaryVectorParameter.Hidden = true;
298      }
299      foreach (IImprovementOperator op in Operators.OfType<IImprovementOperator>()) {
300        op.TargetParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
301        op.TargetParameter.Hidden = true;
302      }
303      foreach (IPathRelinker op in Operators.OfType<IPathRelinker>()) {
304        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
305        op.ParentsParameter.Hidden = true;
306      }
307      foreach (ISimilarityCalculator op in Operators.OfType<ISimilarityCalculator>()) {
308        op.TargetParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
309        op.TargetParameter.Hidden = true;
310      }
311    }
312    #endregion
313
314    private void InitializeRandomKnapsackInstance() {
315      System.Random rand = new System.Random();
316
317      int itemCount = rand.Next(10, 100);
318      Weights = new IntArray(itemCount);
319      Values = new IntArray(itemCount);
320
321      double totalWeight = 0;
322
323      for (int i = 0; i < itemCount; i++) {
324        int value = rand.Next(1, 10);
325        int weight = rand.Next(1, 10);
326
327        Values[i] = value;
328        Weights[i] = weight;
329        totalWeight += weight;
330      }
331
332      int capacity = (int)Math.Round(0.7 * totalWeight);
333      KnapsackCapacity = new IntValue(capacity);
334    }
335  }
336}
Note: See TracBrowser for help on using the repository browser.