source: branches/ProblemRefactoring/HeuristicLab.Problems.TestFunctions/3.3/Improvers/SingleObjectiveTestFunctionImprovementOperator.cs @ 13403

Last change on this file since 13403 was 13403, checked in by abeham, 4 years ago

#2521:

  • Adapted single-objective test function problem to new problem infrastructure
  • Added additional interfaces to RealVectorEncoding
  • Fixed IParticleUpdater interface (must implement IStochasticOperator if it contains a Random parameter)
File size: 9.8 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 HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.RealVectorEncoding;
27using HeuristicLab.Operators;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Problems.TestFunctions {
32  /// <summary>
33  /// An operator that improves test functions solutions.
34  /// </summary>
35  /// <remarks>
36  /// 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 />
37  /// The operator uses an implementation of the Nelder-Mead method with adaptive parameters as described in Gao, F. and Han, L. (2010). Implementing the Nelder-Mead simplex algorithm with adaptive parameters. Computational Optimization and Applications, Vol. 51. Springer. and conducts relection, expansion, contraction and reduction on the test functions solution.
38  /// </remarks>
39  [Item("SingleObjectiveTestFunctionImprovementOperator", "An operator that improves test functions 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.")]
40  [StorableClass]
41  public sealed class SingleObjectiveTestFunctionImprovementOperator : SingleSuccessorOperator, ISingleObjectiveTestFunctionImprovementOperator {
42    #region Parameter properties
43    public IValueParameter<DoubleValue> AlphaParameter {
44      get { return (IValueParameter<DoubleValue>)Parameters["Alpha"]; }
45    }
46    public IValueParameter<DoubleValue> BetaParameter {
47      get { return (IValueParameter<DoubleValue>)Parameters["Beta"]; }
48    }
49    public IValueLookupParameter<DoubleMatrix> BoundsParameter {
50      get { return (IValueLookupParameter<DoubleMatrix>)Parameters["Bounds"]; }
51    }
52    public IValueParameter<DoubleValue> DeltaParameter {
53      get { return (IValueParameter<DoubleValue>)Parameters["Delta"]; }
54    }
55    public IValueLookupParameter<ISingleObjectiveTestFunction> TestFunctionParameter {
56      get { return (IValueLookupParameter<ISingleObjectiveTestFunction>)Parameters["TestFunction"]; }
57    }
58    public IValueParameter<DoubleValue> GammaParameter {
59      get { return (IValueParameter<DoubleValue>)Parameters["Gamma"]; }
60    }
61    public IValueLookupParameter<IntValue> ImprovementAttemptsParameter {
62      get { return (IValueLookupParameter<IntValue>)Parameters["ImprovementAttempts"]; }
63    }
64    public IValueLookupParameter<IItem> SolutionParameter {
65      get { return (IValueLookupParameter<IItem>)Parameters["Solution"]; }
66    }
67    #endregion
68
69    #region Properties
70    private DoubleValue Alpha {
71      get { return AlphaParameter.Value; }
72    }
73    private DoubleValue Beta {
74      get { return BetaParameter.Value; }
75    }
76    private DoubleValue Delta {
77      get { return DeltaParameter.Value; }
78    }
79    private DoubleValue Gamma {
80      get { return GammaParameter.Value; }
81    }
82    #endregion
83
84    [StorableConstructor]
85    private SingleObjectiveTestFunctionImprovementOperator(bool deserializing) : base(deserializing) { }
86    private SingleObjectiveTestFunctionImprovementOperator(SingleObjectiveTestFunctionImprovementOperator original, Cloner cloner) : base(original, cloner) { }
87    public SingleObjectiveTestFunctionImprovementOperator()
88      : base() {
89      #region Create parameters
90      Parameters.Add(new ValueParameter<DoubleValue>("Alpha", new DoubleValue(1.0)));
91      Parameters.Add(new ValueParameter<DoubleValue>("Beta", new DoubleValue(2.0)));
92      Parameters.Add(new ValueParameter<DoubleValue>("Delta", new DoubleValue(0.5)));
93      Parameters.Add(new ValueParameter<DoubleValue>("Gamma", new DoubleValue(0.5)));
94      Parameters.Add(new ValueLookupParameter<ISingleObjectiveTestFunction>("TestFunction", "The operator used to evaluate solutions."));
95      Parameters.Add(new ValueLookupParameter<DoubleMatrix>("Bounds", "The lower and upper bounds in each dimension."));
96      Parameters.Add(new ValueLookupParameter<IntValue>("ImprovementAttempts", "The number of improvement attempts the operator should perform.", new IntValue(100)));
97      Parameters.Add(new ValueLookupParameter<IItem>("Solution", "The solution to be improved. This parameter is used for name translation only.")); // TODO: Problematic, this cannot be wired! IImprovementOperators need to be generic
98      #endregion
99    }
100
101    public override IDeepCloneable Clone(Cloner cloner) {
102      return new SingleObjectiveTestFunctionImprovementOperator(this, cloner);
103    }
104
105    public override IOperation Apply() {
106      RealVector bestSol = ExecutionContext.Scope.Variables[SolutionParameter.ActualName].Value as RealVector;
107      if (bestSol == null)
108        throw new ArgumentException("Cannot improve solution because it has the wrong type.");
109
110      var bounds = BoundsParameter.ActualValue;
111      var function = TestFunctionParameter.ActualValue;
112      var maxIterations = ImprovementAttemptsParameter.ActualValue.Value;
113
114      double bestSolQuality = function.Evaluate(bestSol);
115
116      // create perturbed solutions
117      RealVector[] simplex = new RealVector[bestSol.Length];
118      for (int i = 0; i < simplex.Length; i++) {
119        simplex[i] = bestSol.Clone() as RealVector;
120        simplex[i][i] += 0.1 * (bounds[0, 1] - bounds[0, 0]);
121        if (simplex[i][i] > bounds[0, 1]) simplex[i][i] = bounds[0, 1];
122        if (simplex[i][i] < bounds[0, 0]) simplex[i][i] = bounds[0, 0];
123      }
124
125      // improve solutions
126      for (int i = 0; i < maxIterations; i++) {
127        // order according to their objective function value
128        Array.Sort(simplex, (x, y) => function.Evaluate(x).CompareTo(function.Evaluate(y)));
129
130        // calculate centroid
131        RealVector centroid = new RealVector(bestSol.Length);
132        foreach (var vector in simplex)
133          for (int j = 0; j < centroid.Length; j++)
134            centroid[j] += vector[j];
135        for (int j = 0; j < centroid.Length; j++)
136          centroid[j] /= simplex.Length;
137
138        // reflection
139        RealVector reflectionPoint = new RealVector(bestSol.Length);
140        for (int j = 0; j < reflectionPoint.Length; j++)
141          reflectionPoint[j] = centroid[j] + Alpha.Value * (centroid[j] - simplex[simplex.Length - 1][j]);
142        double reflectionPointQuality = function.Evaluate(reflectionPoint);
143        if (function.Evaluate(simplex[0]) <= reflectionPointQuality
144            && reflectionPointQuality < function.Evaluate(simplex[simplex.Length - 2]))
145          simplex[simplex.Length - 1] = reflectionPoint;
146
147        // expansion
148        if (reflectionPointQuality < function.Evaluate(simplex[0])) {
149          RealVector expansionPoint = new RealVector(bestSol.Length);
150          for (int j = 0; j < expansionPoint.Length; j++)
151            expansionPoint[j] = centroid[j] + Beta.Value * (reflectionPoint[j] - centroid[j]);
152          simplex[simplex.Length - 1] = function.Evaluate(expansionPoint) < reflectionPointQuality ? expansionPoint : reflectionPoint;
153        }
154
155        // contraction
156        if (function.Evaluate(simplex[simplex.Length - 2]) <= reflectionPointQuality
157            && reflectionPointQuality < function.Evaluate(simplex[simplex.Length - 1])) {
158          RealVector outsideContractionPoint = new RealVector(bestSol.Length);
159          for (int j = 0; j < outsideContractionPoint.Length; j++)
160            outsideContractionPoint[j] = centroid[j] + Gamma.Value * (reflectionPoint[j] - centroid[j]);
161          if (function.Evaluate(outsideContractionPoint) <= reflectionPointQuality) {
162            simplex[simplex.Length - 1] = outsideContractionPoint;
163            if (function.Evaluate(reflectionPoint) >= function.Evaluate(simplex[simplex.Length - 1])) {
164              RealVector insideContractionPoint = new RealVector(bestSol.Length);
165              for (int j = 0; j < insideContractionPoint.Length; j++)
166                insideContractionPoint[j] = centroid[j] - Gamma.Value * (reflectionPoint[j] - centroid[j]);
167              if (function.Evaluate(insideContractionPoint) < function.Evaluate(simplex[simplex.Length - 1])) simplex[simplex.Length - 1] = insideContractionPoint;
168            }
169          }
170        }
171
172        // reduction
173        for (int j = 1; j < simplex.Length; j++)
174          for (int k = 0; k < simplex[j].Length; k++)
175            simplex[j][k] = simplex[0][k] + Delta.Value * (simplex[j][k] - simplex[0][k]);
176      }
177
178      for (int i = 0; i < simplex[0].Length; i++) {
179        if (simplex[0][i] > bounds[0, 1]) simplex[0][i] = bounds[0, 1];
180        if (simplex[0][i] < bounds[0, 0]) simplex[0][i] = bounds[0, 0];
181      }
182
183      ExecutionContext.Scope.Variables[SolutionParameter.ActualName].Value = simplex[0];
184      ExecutionContext.Scope.Variables.Add(new Variable("LocalEvaluatedSolutions", new IntValue(maxIterations)));
185
186      return base.Apply();
187    }
188  }
189}
Note: See TracBrowser for help on using the repository browser.