Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PersistenceOverhaul/HeuristicLab.Problems.Knapsack/3.3/Improvers/KnapsackImprovementOperator.cs @ 13368

Last change on this file since 13368 was 13368, checked in by ascheibe, 8 years ago

#2520 added guids to storable classes

File size: 6.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.BinaryVectorEncoding;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.Problems.Knapsack {
34  /// <summary>
35  /// An operator that improves knapsack solutions.
36  /// </summary>
37  /// <remarks>
38  /// It is implemented as described in Laguna, M. and Martí, R. (2003). Scatter Search: Methodology and Implementations in C. Operations Research/Computer Science Interfaces Series, Vol. 24. Springer.<br />
39  /// The operator first orders the elements of the knapsack according to their value-to-weight ratio, then, if the solution is not feasible, removes the element with the lowest ratio until the solution is feasible and tries to add new elements with the best ratio that are not already included yet until the knapsack is full.
40  /// </remarks>
41  [Item("KnapsackImprovementOperator", "An operator that improves knapsack solutions. It is implemented as described in Laguna, M. and Martí, R. (2003). Scatter Search: Methodology and Implementations in C. Operations Research/Computer Science Interfaces Series, Vol. 24. Springer.")]
42  [StorableClass("AA2BAD0D-6083-4CD2-9B0E-5502DCBD8B86")]
43  public sealed class KnapsackImprovementOperator : SingleSuccessorOperator, ISingleObjectiveImprovementOperator {
44    #region Parameter properties
45    public ScopeParameter CurrentScopeParameter {
46      get { return (ScopeParameter)Parameters["CurrentScope"]; }
47    }
48    public ILookupParameter<IntValue> KnapsackCapacityParameter {
49      get { return (ILookupParameter<IntValue>)Parameters["KnapsackCapacity"]; }
50    }
51    public ILookupParameter<DoubleValue> PenaltyParameter {
52      get { return (ILookupParameter<DoubleValue>)Parameters["Penalty"]; }
53    }
54    public IValueLookupParameter<IItem> SolutionParameter {
55      get { return (IValueLookupParameter<IItem>)Parameters["Solution"]; }
56    }
57    public ILookupParameter<IntArray> ValuesParameter {
58      get { return (ILookupParameter<IntArray>)Parameters["Values"]; }
59    }
60    public ILookupParameter<IntArray> WeightsParameter {
61      get { return (ILookupParameter<IntArray>)Parameters["Weights"]; }
62    }
63    #endregion
64
65    #region Properties
66    private IScope CurrentScope {
67      get { return CurrentScopeParameter.ActualValue; }
68    }
69    private IntValue KnapsackCapacity {
70      get { return KnapsackCapacityParameter.ActualValue; }
71      set { KnapsackCapacityParameter.ActualValue = value; }
72    }
73    private DoubleValue Penalty {
74      get { return PenaltyParameter.ActualValue; }
75      set { PenaltyParameter.ActualValue = value; }
76    }
77    private IntArray Values {
78      get { return ValuesParameter.ActualValue; }
79      set { ValuesParameter.ActualValue = value; }
80    }
81    private IntArray Weights {
82      get { return WeightsParameter.ActualValue; }
83      set { WeightsParameter.ActualValue = value; }
84    }
85    #endregion
86
87    [StorableConstructor]
88    private KnapsackImprovementOperator(bool deserializing) : base(deserializing) { }
89    private KnapsackImprovementOperator(KnapsackImprovementOperator original, Cloner cloner) : base(original, cloner) { }
90    public KnapsackImprovementOperator()
91      : base() {
92      #region Create parameters
93      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope that contains the solution to be improved."));
94      Parameters.Add(new LookupParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack."));
95      Parameters.Add(new LookupParameter<DoubleValue>("Penalty", "The penalty value for each unit of overweight."));
96      Parameters.Add(new ValueLookupParameter<IItem>("Solution", "The solution to be improved. This parameter is used for name translation only."));
97      Parameters.Add(new LookupParameter<IntArray>("Values", "The values of the items."));
98      Parameters.Add(new LookupParameter<IntArray>("Weights", "The weights of the items."));
99      #endregion
100    }
101
102    public override IDeepCloneable Clone(Cloner cloner) {
103      return new KnapsackImprovementOperator(this, cloner);
104    }
105
106    public override IOperation Apply() {
107      BinaryVector sol = CurrentScope.Variables[SolutionParameter.ActualName].Value as BinaryVector;
108      if (sol == null)
109        throw new ArgumentException("Cannot improve solution because it has the wrong type.");
110
111      // calculate value-to-weight ratio
112      double[] ratio = new double[Values.Length];
113      for (int i = 0; i < ratio.Length; i++)
114        ratio[i] = (double)Values[i] / (double)Weights[i];
115
116
117      // calculate order for ratio
118      int[] order = new int[ratio.Length];
119      foreach (var x in ratio.Select((x, index) => new { Value = x, ValueIndex = index })
120                             .OrderByDescending(x => x.Value)
121                             .Select((x, index) => new { ValueIndex = x.ValueIndex, ItemIndex = index })) {
122        order[x.ItemIndex] = x.ValueIndex;
123      }
124
125      int evaluatedSolutions = 0;
126      int j = sol.Length - 1;
127      while (KnapsackEvaluator.Apply(sol, KnapsackCapacity, Penalty, Weights, Values)
128                              .SumWeights.Value > KnapsackCapacity.Value && j >= 0) {
129        sol[order[j--]] = false;
130        evaluatedSolutions++;
131      }
132
133      // calculate weight
134      int weight = 0;
135      for (int i = 0; i < sol.Length; i++)
136        if (sol[i]) weight += Weights[i];
137
138      // improve solution
139      bool feasible = true; j = 0;
140      while (feasible && j < sol.Length) {
141        while (sol[order[j]]) j++;
142        if (weight + Weights[order[j]] <= KnapsackCapacity.Value) {
143          sol[order[j]] = true;
144          weight += Weights[order[j]];
145        } else feasible = false;
146        evaluatedSolutions++;
147      }
148
149      CurrentScope.Variables[SolutionParameter.ActualName].Value = sol;
150      CurrentScope.Variables.Add(new Variable("LocalEvaluatedSolutions", new IntValue(evaluatedSolutions)));
151
152      return base.Apply();
153    }
154  }
155}
Note: See TracBrowser for help on using the repository browser.