source: trunk/sources/HeuristicLab.Problems.TestFunctions/3.3/Improvers/SingleObjectiveTestFunctionImprovementOperator.cs @ 12012

Last change on this file since 12012 was 12012, checked in by ascheibe, 5 years ago

#2212 merged r12008, r12009, r12010 back into trunk

File size: 10.3 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.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Problems.TestFunctions {
33  /// <summary>
34  /// An operator that improves test functions solutions.
35  /// </summary>
36  /// <remarks>
37  /// 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 />
38  /// 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.
39  /// </remarks>
40  [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.")]
41  [StorableClass]
42  public sealed class SingleObjectiveTestFunctionImprovementOperator : SingleSuccessorOperator, ISingleObjectiveImprovementOperator {
43    #region Parameter properties
44    public IValueParameter<DoubleValue> AlphaParameter {
45      get { return (IValueParameter<DoubleValue>)Parameters["Alpha"]; }
46    }
47    public IValueParameter<DoubleValue> BetaParameter {
48      get { return (IValueParameter<DoubleValue>)Parameters["Beta"]; }
49    }
50    public IValueLookupParameter<DoubleMatrix> BoundsParameter {
51      get { return (IValueLookupParameter<DoubleMatrix>)Parameters["Bounds"]; }
52    }
53    public ScopeParameter CurrentScopeParameter {
54      get { return (ScopeParameter)Parameters["CurrentScope"]; }
55    }
56    public IValueParameter<DoubleValue> DeltaParameter {
57      get { return (IValueParameter<DoubleValue>)Parameters["Delta"]; }
58    }
59    public IValueLookupParameter<ISingleObjectiveTestFunctionProblemEvaluator> EvaluatorParameter {
60      get { return (IValueLookupParameter<ISingleObjectiveTestFunctionProblemEvaluator>)Parameters["Evaluator"]; }
61    }
62    public IValueParameter<DoubleValue> GammaParameter {
63      get { return (IValueParameter<DoubleValue>)Parameters["Gamma"]; }
64    }
65    public IValueLookupParameter<IntValue> ImprovementAttemptsParameter {
66      get { return (IValueLookupParameter<IntValue>)Parameters["ImprovementAttempts"]; }
67    }
68    public IValueLookupParameter<IItem> SolutionParameter {
69      get { return (IValueLookupParameter<IItem>)Parameters["Solution"]; }
70    }
71    #endregion
72
73    #region Properties
74    private DoubleValue Alpha {
75      get { return AlphaParameter.Value; }
76    }
77    private DoubleValue Beta {
78      get { return BetaParameter.Value; }
79    }
80    private DoubleMatrix Bounds {
81      get { return BoundsParameter.ActualValue; }
82    }
83    public IScope CurrentScope {
84      get { return CurrentScopeParameter.ActualValue; }
85    }
86    private DoubleValue Delta {
87      get { return DeltaParameter.Value; }
88    }
89    public ISingleObjectiveTestFunctionProblemEvaluator Evaluator {
90      get { return EvaluatorParameter.ActualValue; }
91    }
92    private DoubleValue Gamma {
93      get { return GammaParameter.Value; }
94    }
95    public IntValue ImprovementAttempts {
96      get { return ImprovementAttemptsParameter.ActualValue; }
97    }
98    #endregion
99
100    [StorableConstructor]
101    private SingleObjectiveTestFunctionImprovementOperator(bool deserializing) : base(deserializing) { }
102    private SingleObjectiveTestFunctionImprovementOperator(SingleObjectiveTestFunctionImprovementOperator original, Cloner cloner) : base(original, cloner) { }
103    public SingleObjectiveTestFunctionImprovementOperator()
104      : base() {
105      #region Create parameters
106      Parameters.Add(new ValueParameter<DoubleValue>("Alpha", new DoubleValue(1.0)));
107      Parameters.Add(new ValueParameter<DoubleValue>("Beta", new DoubleValue(2.0)));
108      Parameters.Add(new ValueLookupParameter<DoubleMatrix>("Bounds", "The lower and upper bounds in each dimension."));
109      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope that contains the solution to be improved."));
110      Parameters.Add(new ValueParameter<DoubleValue>("Delta", new DoubleValue(0.5)));
111      Parameters.Add(new ValueLookupParameter<ISingleObjectiveTestFunctionProblemEvaluator>("Evaluator", "The operator used to evaluate solutions."));
112      Parameters.Add(new ValueParameter<DoubleValue>("Gamma", new DoubleValue(0.5)));
113      Parameters.Add(new ValueLookupParameter<IntValue>("ImprovementAttempts", "The number of improvement attempts the operator should perform.", new IntValue(100)));
114      Parameters.Add(new ValueLookupParameter<IItem>("Solution", "The solution to be improved. This parameter is used for name translation only."));
115      #endregion
116    }
117
118    public override IDeepCloneable Clone(Cloner cloner) {
119      return new SingleObjectiveTestFunctionImprovementOperator(this, cloner);
120    }
121
122    public override IOperation Apply() {
123      RealVector bestSol = CurrentScope.Variables[SolutionParameter.ActualName].Value as RealVector;
124      if (bestSol == null)
125        throw new ArgumentException("Cannot improve solution because it has the wrong type.");
126
127      var evaluator = Evaluator;
128
129      double bestSolQuality = evaluator.Evaluate(bestSol);
130
131      // create perturbed solutions
132      RealVector[] simplex = new RealVector[bestSol.Length];
133      for (int i = 0; i < simplex.Length; i++) {
134        simplex[i] = bestSol.Clone() as RealVector;
135        simplex[i][i] += 0.1 * (Bounds[0, 1] - Bounds[0, 0]);
136        if (simplex[i][i] > Bounds[0, 1]) simplex[i][i] = Bounds[0, 1];
137        if (simplex[i][i] < Bounds[0, 0]) simplex[i][i] = Bounds[0, 0];
138      }
139
140      // improve solutions
141      for (int i = 0; i < ImprovementAttempts.Value; i++) {
142        // order according to their objective function value
143        Array.Sort(simplex, (x, y) => evaluator.Evaluate(x).CompareTo(evaluator.Evaluate(y)));
144
145        // calculate centroid
146        RealVector centroid = new RealVector(bestSol.Length);
147        foreach (var vector in simplex)
148          for (int j = 0; j < centroid.Length; j++)
149            centroid[j] += vector[j];
150        for (int j = 0; j < centroid.Length; j++)
151          centroid[j] /= simplex.Length;
152
153        // reflection
154        RealVector reflectionPoint = new RealVector(bestSol.Length);
155        for (int j = 0; j < reflectionPoint.Length; j++)
156          reflectionPoint[j] = centroid[j] + Alpha.Value * (centroid[j] - simplex[simplex.Length - 1][j]);
157        double reflectionPointQuality = evaluator.Evaluate(reflectionPoint);
158        if (evaluator.Evaluate(simplex[0]) <= reflectionPointQuality
159            && reflectionPointQuality < evaluator.Evaluate(simplex[simplex.Length - 2]))
160          simplex[simplex.Length - 1] = reflectionPoint;
161
162        // expansion
163        if (reflectionPointQuality < evaluator.Evaluate(simplex[0])) {
164          RealVector expansionPoint = new RealVector(bestSol.Length);
165          for (int j = 0; j < expansionPoint.Length; j++)
166            expansionPoint[j] = centroid[j] + Beta.Value * (reflectionPoint[j] - centroid[j]);
167          simplex[simplex.Length - 1] = evaluator.Evaluate(expansionPoint) < reflectionPointQuality ? expansionPoint : reflectionPoint;
168        }
169
170        // contraction
171        if (evaluator.Evaluate(simplex[simplex.Length - 2]) <= reflectionPointQuality
172            && reflectionPointQuality < evaluator.Evaluate(simplex[simplex.Length - 1])) {
173          RealVector outsideContractionPoint = new RealVector(bestSol.Length);
174          for (int j = 0; j < outsideContractionPoint.Length; j++)
175            outsideContractionPoint[j] = centroid[j] + Gamma.Value * (reflectionPoint[j] - centroid[j]);
176          if (evaluator.Evaluate(outsideContractionPoint) <= reflectionPointQuality) {
177            simplex[simplex.Length - 1] = outsideContractionPoint;
178            if (evaluator.Evaluate(reflectionPoint) >= evaluator.Evaluate(simplex[simplex.Length - 1])) {
179              RealVector insideContractionPoint = new RealVector(bestSol.Length);
180              for (int j = 0; j < insideContractionPoint.Length; j++)
181                insideContractionPoint[j] = centroid[j] - Gamma.Value * (reflectionPoint[j] - centroid[j]);
182              if (evaluator.Evaluate(insideContractionPoint) < evaluator.Evaluate(simplex[simplex.Length - 1])) simplex[simplex.Length - 1] = insideContractionPoint;
183            }
184          }
185        }
186
187        // reduction
188        for (int j = 1; j < simplex.Length; j++)
189          for (int k = 0; k < simplex[j].Length; k++)
190            simplex[j][k] = simplex[0][k] + Delta.Value * (simplex[j][k] - simplex[0][k]);
191      }
192
193      for (int i = 0; i < simplex[0].Length; i++) {
194        if (simplex[0][i] > Bounds[0, 1]) simplex[0][i] = Bounds[0, 1];
195        if (simplex[0][i] < Bounds[0, 0]) simplex[0][i] = Bounds[0, 0];
196      }
197
198      CurrentScope.Variables[SolutionParameter.ActualName].Value = simplex[0];
199      CurrentScope.Variables.Add(new Variable("LocalEvaluatedSolutions", ImprovementAttempts));
200
201      return base.Apply();
202    }
203  }
204}
Note: See TracBrowser for help on using the repository browser.