Free cookie consent management tool by TermsFeed Policy Generator

source: branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/KnapsackImprovementOperator.cs @ 7775

Last change on this file since 7775 was 7775, checked in by jkarder, 12 years ago

#1331:

  • added operators for TestFunctions problems
  • added more path relinking operators for the TravelingSalesman and the Knapsack problem
  • added 2-tier version of the SolutionPoolUpdateMethod
  • added parameters and adjusted types
  • added some exception handling
  • adjusted event handling
  • updated plugin dependencies
  • minor code improvements
File size: 6.7 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.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;
32using HeuristicLab.Problems.Knapsack;
33
34namespace HeuristicLab.Algorithms.ScatterSearch.Knapsack {
35  /// <summary>
36  /// An operator that improves knapsack solutions.
37  /// </summary>
38  [Item("KnapsackImprovementOperator", "An operator that improves knapsack solutions.")]
39  [StorableClass]
40  public sealed class KnapsackImprovementOperator : SingleSuccessorOperator, ILocalImprovementOperator, IScatterSearchTargetProcessor {
41    #region Problem properties
42    public Type ProblemType {
43      get { return typeof(KnapsackProblem); }
44    }
45    [Storable]
46    private KnapsackProblem problem;
47    public IProblem Problem {
48      get { return problem; }
49      set { problem = (KnapsackProblem)value; }
50    }
51    #endregion
52
53    #region Parameter properties
54    public ScopeParameter CurrentScopeParameter {
55      get { return (ScopeParameter)Parameters["CurrentScope"]; }
56    }
57    public IValueLookupParameter<IntArray> ValuesParameter {
58      get { return (IValueLookupParameter<IntArray>)Parameters["Values"]; }
59    }
60    public IValueLookupParameter<IntArray> WeightsParameter {
61      get { return (IValueLookupParameter<IntArray>)Parameters["Weights"]; }
62    }
63    public IValueLookupParameter<IntValue> KnapsackCapacityParameter {
64      get { return (IValueLookupParameter<IntValue>)Parameters["KnapsackCapacity"]; }
65    }
66    public IValueLookupParameter<IItem> TargetParameter {
67      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
68    }
69    public IValueLookupParameter<DoubleValue> PenaltyParameter {
70      get { return (IValueLookupParameter<DoubleValue>)Parameters["Penalty"]; }
71    }
72    #region ILocalImprovementOperator Parameters
73    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
74      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
75    }
76    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
77      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
78    }
79    public ILookupParameter<ResultCollection> ResultsParameter {
80      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
81    }
82    #endregion
83    #endregion
84
85    #region Properties
86    private IScope CurrentScope {
87      get { return CurrentScopeParameter.ActualValue; }
88    }
89    private IntArray Values {
90      get { return ValuesParameter.ActualValue; }
91      set { ValuesParameter.ActualValue = value; }
92    }
93    private IntArray Weights {
94      get { return WeightsParameter.ActualValue; }
95      set { WeightsParameter.ActualValue = value; }
96    }
97    private IntValue KnapsackCapacity {
98      get { return KnapsackCapacityParameter.ActualValue; }
99      set { KnapsackCapacityParameter.ActualValue = value; }
100    }
101    private IItem Target {
102      get { return TargetParameter.ActualValue; }
103    }
104    private DoubleValue Penalty {
105      get { return PenaltyParameter.ActualValue; }
106      set { PenaltyParameter.ActualValue = value; }
107    }
108    #endregion
109
110    [StorableConstructor]
111    private KnapsackImprovementOperator(bool deserializing) : base(deserializing) { }
112    private KnapsackImprovementOperator(KnapsackImprovementOperator original, Cloner cloner)
113      : base(original, cloner) {
114      this.problem = cloner.Clone(original.problem);
115    }
116    public KnapsackImprovementOperator()
117      : base() {
118      #region Create parameters
119      Parameters.Add(new ScopeParameter("CurrentScope"));
120      Parameters.Add(new ValueLookupParameter<IntArray>("Values"));
121      Parameters.Add(new ValueLookupParameter<IntArray>("Weights"));
122      Parameters.Add(new ValueLookupParameter<IntValue>("KnapsackCapacity"));
123      Parameters.Add(new ValueLookupParameter<IItem>("Target"));
124      Parameters.Add(new ValueLookupParameter<DoubleValue>("Penalty"));
125      #endregion
126      TargetParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
127    }
128
129    public override IDeepCloneable Clone(Cloner cloner) {
130      return new KnapsackImprovementOperator(this, cloner);
131    }
132
133    public override IOperation Apply() {
134      var sol = CurrentScope.Variables[TargetParameter.ActualName].Value as BinaryVector;
135
136      // calculate value-to-weight ratio
137      double[] ratio = new double[Values.Length];
138      for (int i = 0; i < ratio.Length; i++)
139        ratio[i] = (double)Values[i] / (double)Weights[i];
140
141
142      // calculate order for ratio
143      int[] order = new int[ratio.Length];
144      ratio.Select((x, index) => new { Value = x, ValueIndex = index })
145           .OrderBy(x => x.Value)
146           .Select((x, index) => new { ValueIndex = x.ValueIndex, ItemIndex = index }).ToList()
147           .ForEach(x => order[x.ItemIndex] = x.ValueIndex);
148
149      int j = sol.Length - 1;
150      while (KnapsackEvaluator.Apply(sol, KnapsackCapacity, Penalty, Weights, Values)
151                              .SumWeights.Value > KnapsackCapacity.Value && j >= 0)
152        sol[order[j--]] = false;
153
154      // calculate weight
155      int weight = 0;
156      for (int i = 0; i < sol.Length; i++)
157        if (sol[i]) weight += Weights[i];
158
159      // improve solution
160      bool feasible = true; j = 0;
161      while (feasible && j < sol.Length) {
162        while (sol[order[j]]) j++;
163        if (weight + Weights[order[j]] <= KnapsackCapacity.Value) {
164          sol[order[j]] = true;
165          weight += Weights[order[j]];
166        } else feasible = false;
167      }
168
169      CurrentScope.Variables[TargetParameter.ActualName].Value = sol;
170
171      return base.Apply();
172    }
173  }
174}
Note: See TracBrowser for help on using the repository browser.