Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 17873 was 17180, checked in by swagner, 5 years ago

#2875: Removed years in copyrights

File size: 15.3 KB
RevLine 
[3070]1#region License Information
2/* HeuristicLab
[17180]3 * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[3070]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;
[8720]25using HeuristicLab.Analysis;
[3070]26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.BinaryVectorEncoding;
30using HeuristicLab.Optimization;
[12102]31using HeuristicLab.Optimization.Operators;
[3070]32using HeuristicLab.Parameters;
[16565]33using HEAL.Attic;
[3070]34using HeuristicLab.PluginInfrastructure;
35
36namespace HeuristicLab.Problems.Knapsack {
[13173]37  [Item("Knapsack Problem (KSP)", "Represents a Knapsack problem.")]
[12504]38  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 200)]
[16565]39  [StorableType("8CEDAFA2-6E0A-4D4B-B6C6-F85CC58B824E")]
[6938]40  public sealed class KnapsackProblem : SingleObjectiveHeuristicOptimizationProblem<IKnapsackEvaluator, IBinaryVectorCreator>, IStorableContent {
[4419]41    public string Filename { get; set; }
42
[3070]43    #region Parameter Properties
44    public ValueParameter<IntValue> KnapsackCapacityParameter {
45      get { return (ValueParameter<IntValue>)Parameters["KnapsackCapacity"]; }
46    }
47    public ValueParameter<IntArray> WeightsParameter {
48      get { return (ValueParameter<IntArray>)Parameters["Weights"]; }
49    }
50    public ValueParameter<IntArray> ValuesParameter {
51      get { return (ValueParameter<IntArray>)Parameters["Values"]; }
52    }
[3109]53    public ValueParameter<DoubleValue> PenaltyParameter {
54      get { return (ValueParameter<DoubleValue>)Parameters["Penalty"]; }
55    }
[3787]56    public OptionalValueParameter<BinaryVector> BestKnownSolutionParameter {
57      get { return (OptionalValueParameter<BinaryVector>)Parameters["BestKnownSolution"]; }
58    }
[3070]59    #endregion
60
61    #region Properties
[3109]62    public IntValue KnapsackCapacity {
63      get { return KnapsackCapacityParameter.Value; }
64      set { KnapsackCapacityParameter.Value = value; }
65    }
66    public IntArray Weights {
67      get { return WeightsParameter.Value; }
68      set { WeightsParameter.Value = value; }
69    }
70    public IntArray Values {
71      get { return ValuesParameter.Value; }
72      set { ValuesParameter.Value = value; }
73    }
74    public DoubleValue Penalty {
75      get { return PenaltyParameter.Value; }
76      set { PenaltyParameter.Value = value; }
77    }
[3787]78    public BinaryVector BestKnownSolution {
79      get { return BestKnownSolutionParameter.Value; }
80      set { BestKnownSolutionParameter.Value = value; }
81    }
[3667]82    private BestKnapsackSolutionAnalyzer BestKnapsackSolutionAnalyzer {
[6938]83      get { return Operators.OfType<BestKnapsackSolutionAnalyzer>().FirstOrDefault(); }
[3641]84    }
[3070]85    #endregion
86
[6938]87    // BackwardsCompatibility3.3
88    #region Backwards compatible code, remove with 3.4
89    [Obsolete]
90    [Storable(Name = "operators")]
91    private IEnumerable<IOperator> oldOperators {
92      get { return null; }
93      set {
94        if (value != null && value.Any())
95          Operators.AddRange(value);
96      }
97    }
98    #endregion
[3125]99
[4098]100    [StorableConstructor]
[16565]101    private KnapsackProblem(StorableConstructorFlag _) : base(_) { }
[4722]102    private KnapsackProblem(KnapsackProblem original, Cloner cloner)
103      : base(original, cloner) {
[7351]104      RegisterEventHandlers();
[4722]105    }
106    public override IDeepCloneable Clone(Cloner cloner) {
107      return new KnapsackProblem(this, cloner);
108    }
[3166]109    public KnapsackProblem()
[6938]110      : base(new KnapsackEvaluator(), new RandomBinaryVectorCreator()) {
[3070]111      Parameters.Add(new ValueParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack.", new IntValue(0)));
112      Parameters.Add(new ValueParameter<IntArray>("Weights", "The weights of the items.", new IntArray(5)));
113      Parameters.Add(new ValueParameter<IntArray>("Values", "The values of the items.", new IntArray(5)));
114      Parameters.Add(new ValueParameter<DoubleValue>("Penalty", "The penalty value for each unit of overweight.", new DoubleValue(1)));
[3787]115      Parameters.Add(new OptionalValueParameter<BinaryVector>("BestKnownSolution", "The best known solution of this Knapsack instance."));
[3070]116
[6938]117      Maximization.Value = true;
[6939]118      MaximizationParameter.Hidden = true;
[3125]119
[6938]120      SolutionCreator.BinaryVectorParameter.ActualName = "KnapsackSolution";
121
[3125]122      InitializeRandomKnapsackInstance();
[5287]123
[3070]124      ParameterizeSolutionCreator();
125      ParameterizeEvaluator();
126
[4098]127      InitializeOperators();
[7351]128      RegisterEventHandlers();
[3070]129    }
130
131    #region Events
[6938]132    protected override void OnSolutionCreatorChanged() {
133      base.OnSolutionCreatorChanged();
[3641]134      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
[3070]135      ParameterizeSolutionCreator();
136      ParameterizeEvaluator();
[3667]137      ParameterizeAnalyzer();
[3070]138      ParameterizeOperators();
139    }
[6938]140    protected override void OnEvaluatorChanged() {
141      base.OnEvaluatorChanged();
[3070]142      ParameterizeEvaluator();
[3667]143      ParameterizeAnalyzer();
[3070]144    }
[6938]145    private void SolutionCreator_BinaryVectorParameter_ActualNameChanged(object sender, EventArgs e) {
[3070]146      ParameterizeEvaluator();
[3667]147      ParameterizeAnalyzer();
[6938]148      ParameterizeOperators();
[3070]149    }
[6938]150    private void KnapsackCapacityParameter_ValueChanged(object sender, EventArgs e) {
[3109]151      ParameterizeEvaluator();
[3667]152      ParameterizeAnalyzer();
[3070]153    }
[6938]154    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
[3109]155      ParameterizeEvaluator();
[3667]156      ParameterizeAnalyzer();
[3110]157      ParameterizeSolutionCreator();
[3111]158
159      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
[3070]160    }
[6938]161    private void WeightsValue_Reset(object sender, EventArgs e) {
[3111]162      ParameterizeSolutionCreator();
[3463]163
164      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
165        ((IStringConvertibleArray)ValuesParameter.Value).Length = WeightsParameter.Value.Length;
[3111]166    }
[6938]167    private void ValuesParameter_ValueChanged(object sender, EventArgs e) {
[3109]168      ParameterizeEvaluator();
[3667]169      ParameterizeAnalyzer();
[3110]170      ParameterizeSolutionCreator();
[3111]171
172      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
[3109]173    }
[6938]174    private void ValuesValue_Reset(object sender, EventArgs e) {
[3111]175      ParameterizeSolutionCreator();
[3463]176
177      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
178        ((IStringConvertibleArray)WeightsParameter.Value).Length = ValuesParameter.Value.Length;
[3111]179    }
[6938]180    private void PenaltyParameter_ValueChanged(object sender, EventArgs e) {
[3109]181      ParameterizeEvaluator();
182    }
[6938]183    private void OneBitflipMoveParameter_ActualNameChanged(object sender, EventArgs e) {
[3124]184      string name = ((ILookupParameter<OneBitflipMove>)sender).ActualName;
185      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
186        op.OneBitflipMoveParameter.ActualName = name;
187      }
188    }
[3070]189    #endregion
190
191    #region Helpers
192    [StorableHook(HookType.AfterDeserialization)]
[4722]193    private void AfterDeserialization() {
[4118]194      // BackwardsCompatibility3.3
195      #region Backwards compatible code (remove with 3.4)
[6939]196      if (Operators.Count == 0) InitializeOperators();
[4118]197      #endregion
[7351]198      RegisterEventHandlers();
[4118]199    }
200
[7351]201    private void RegisterEventHandlers() {
[3641]202      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
[3109]203      KnapsackCapacityParameter.ValueChanged += new EventHandler(KnapsackCapacityParameter_ValueChanged);
204      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
[3111]205      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
[3109]206      ValuesParameter.ValueChanged += new EventHandler(ValuesParameter_ValueChanged);
[3111]207      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
[3109]208      PenaltyParameter.ValueChanged += new EventHandler(PenaltyParameter_ValueChanged);
[3070]209    }
210    private void ParameterizeSolutionCreator() {
[5287]211      if (SolutionCreator.LengthParameter.Value == null ||
[3070]212        SolutionCreator.LengthParameter.Value.Value != WeightsParameter.Value.Length)
213        SolutionCreator.LengthParameter.Value = new IntValue(WeightsParameter.Value.Length);
214    }
215    private void ParameterizeEvaluator() {
216      if (Evaluator is KnapsackEvaluator) {
217        KnapsackEvaluator knapsackEvaluator =
218          (KnapsackEvaluator)Evaluator;
219        knapsackEvaluator.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
[6053]220        knapsackEvaluator.BinaryVectorParameter.Hidden = true;
[3109]221        knapsackEvaluator.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
[6053]222        knapsackEvaluator.KnapsackCapacityParameter.Hidden = true;
[3070]223        knapsackEvaluator.WeightsParameter.ActualName = WeightsParameter.Name;
[6053]224        knapsackEvaluator.WeightsParameter.Hidden = true;
[3070]225        knapsackEvaluator.ValuesParameter.ActualName = ValuesParameter.Name;
[6053]226        knapsackEvaluator.ValuesParameter.Hidden = true;
[3070]227        knapsackEvaluator.PenaltyParameter.ActualName = PenaltyParameter.Name;
[6053]228        knapsackEvaluator.PenaltyParameter.Hidden = true;
[3070]229      }
230    }
[3667]231    private void ParameterizeAnalyzer() {
[8720]232      if (BestKnapsackSolutionAnalyzer != null) {
233        BestKnapsackSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
234        BestKnapsackSolutionAnalyzer.MaximizationParameter.Hidden = true;
235        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
236        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.Hidden = true;
237        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
238        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.Hidden = true;
239        BestKnapsackSolutionAnalyzer.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
240        BestKnapsackSolutionAnalyzer.BinaryVectorParameter.Hidden = true;
241        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
242        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.Hidden = true;
243        BestKnapsackSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
244        BestKnapsackSolutionAnalyzer.WeightsParameter.Hidden = true;
245        BestKnapsackSolutionAnalyzer.ValuesParameter.ActualName = ValuesParameter.Name;
246        BestKnapsackSolutionAnalyzer.ValuesParameter.Hidden = true;
247      }
[3467]248    }
[3070]249    private void InitializeOperators() {
[8334]250      Operators.Add(new KnapsackImprovementOperator());
251      Operators.Add(new KnapsackPathRelinker());
252      Operators.Add(new KnapsackSimultaneousPathRelinker());
[14412]253      Operators.Add(new HammingSimilarityCalculator());
[12126]254      Operators.Add(new QualitySimilarityCalculator());
[8334]255
[6938]256      Operators.Add(new BestKnapsackSolutionAnalyzer());
[12069]257      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
[3667]258      ParameterizeAnalyzer();
[3303]259      foreach (IBinaryVectorOperator op in ApplicationManager.Manager.GetInstances<IBinaryVectorOperator>()) {
260        if (!(op is ISingleObjectiveMoveEvaluator) || (op is IKnapsackMoveEvaluator)) {
[6938]261          Operators.Add(op);
[3127]262        }
[3070]263      }
[3303]264      ParameterizeOperators();
[3124]265      InitializeMoveGenerators();
[3070]266    }
[3124]267    private void InitializeMoveGenerators() {
268      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
269        if (op is IMoveGenerator) {
270          op.OneBitflipMoveParameter.ActualNameChanged += new EventHandler(OneBitflipMoveParameter_ActualNameChanged);
271        }
272      }
273    }
[3070]274    private void ParameterizeOperators() {
275      foreach (IBinaryVectorCrossover op in Operators.OfType<IBinaryVectorCrossover>()) {
276        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
[6053]277        op.ParentsParameter.Hidden = true;
[3070]278        op.ChildParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
[6053]279        op.ChildParameter.Hidden = true;
[3070]280      }
281      foreach (IBinaryVectorManipulator op in Operators.OfType<IBinaryVectorManipulator>()) {
282        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
[6053]283        op.BinaryVectorParameter.Hidden = true;
[3070]284      }
[3124]285      foreach (IBinaryVectorMoveOperator op in Operators.OfType<IBinaryVectorMoveOperator>()) {
286        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
[6053]287        op.BinaryVectorParameter.Hidden = true;
[3124]288      }
289      foreach (IKnapsackMoveEvaluator op in Operators.OfType<IKnapsackMoveEvaluator>()) {
290        op.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
[6053]291        op.KnapsackCapacityParameter.Hidden = true;
[3124]292        op.PenaltyParameter.ActualName = PenaltyParameter.Name;
[6053]293        op.PenaltyParameter.Hidden = true;
[3124]294        op.WeightsParameter.ActualName = WeightsParameter.Name;
[6053]295        op.WeightsParameter.Hidden = true;
[3124]296        op.ValuesParameter.ActualName = ValuesParameter.Name;
[6053]297        op.ValuesParameter.Hidden = true;
[3124]298      }
[8334]299      foreach (IBinaryVectorMultiNeighborhoodShakingOperator op in Operators.OfType<IBinaryVectorMultiNeighborhoodShakingOperator>()) {
[6042]300        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
[6053]301        op.BinaryVectorParameter.Hidden = true;
302      }
[8334]303      foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
304        op.SolutionParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
305        op.SolutionParameter.Hidden = true;
306      }
307      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
308        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
309        op.ParentsParameter.Hidden = true;
310      }
[12126]311      foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
[8334]312        op.SolutionVariableName = SolutionCreator.BinaryVectorParameter.ActualName;
313        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
314      }
[3070]315    }
316    #endregion
[4098]317
318    private void InitializeRandomKnapsackInstance() {
319      System.Random rand = new System.Random();
320
321      int itemCount = rand.Next(10, 100);
322      Weights = new IntArray(itemCount);
323      Values = new IntArray(itemCount);
324
325      double totalWeight = 0;
326
327      for (int i = 0; i < itemCount; i++) {
328        int value = rand.Next(1, 10);
329        int weight = rand.Next(1, 10);
330
331        Values[i] = value;
332        Weights[i] = weight;
333        totalWeight += weight;
334      }
335
336      int capacity = (int)Math.Round(0.7 * totalWeight);
337      KnapsackCapacity = new IntValue(capacity);
338    }
[3070]339  }
340}
Note: See TracBrowser for help on using the repository browser.