Free cookie consent management tool by TermsFeed Policy Generator

source: branches/ichiriac/HeuristicLab.Algorithms.DifferentialEvolution/DifferentialEvolution.cs @ 15802

Last change on this file since 15802 was 14700, checked in by gkronber, 8 years ago

#2646: fixed compile errors in DifferentialEvolution + reformatting + svn:ignore
File size: 14.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 * Implementation is based on jMetal framework https://github.com/jMetal/jMetal
7 *
8 * HeuristicLab is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * HeuristicLab is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
20 */
21#endregion
22using HeuristicLab.Analysis;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.RealVectorEncoding;
27using HeuristicLab.Optimization;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Problems.TestFunctions;
31using HeuristicLab.Random;
32using System;
33using System.Collections.Generic;
34using System.Threading;
35
36namespace HeuristicLab.Algorithms.DifferentialEvolution {
37
38  [Item("Differential Evolution (DE)", "A differential evolution algorithm.")]
39  [StorableClass]
40  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 400)]
41  public class DifferentialEvolution : BasicAlgorithm {
42    public Func<IEnumerable<double>, double> Evaluation;
43
44    public override Type ProblemType {
45      get { return typeof(SingleObjectiveTestFunctionProblem); }
46    }
47    public new SingleObjectiveTestFunctionProblem Problem {
48      get { return (SingleObjectiveTestFunctionProblem)base.Problem; }
49      set { base.Problem = value; }
50    }
51
52    private readonly IRandom _random = new MersenneTwister();
53    private int evals;
54
55    #region ParameterNames
56    private const string MaximumEvaluationsParameterName = "Maximum Evaluations";
57    private const string SeedParameterName = "Seed";
58    private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
59    private const string CrossoverProbabilityParameterName = "CrossoverProbability";
60    private const string PopulationSizeParameterName = "PopulationSize";
61    private const string ScalingFactorParameterName = "ScalingFactor";
62    private const string ValueToReachParameterName = "ValueToReach";
63    #endregion
64
65    #region ParameterProperties
66    public IFixedValueParameter<IntValue> MaximumEvaluationsParameter {
67      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; }
68    }
69    public IFixedValueParameter<IntValue> SeedParameter {
70      get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
71    }
72    public FixedValueParameter<BoolValue> SetSeedRandomlyParameter {
73      get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
74    }
75    private ValueParameter<IntValue> PopulationSizeParameter {
76      get { return (ValueParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
77    }
78    public ValueParameter<DoubleValue> CrossoverProbabilityParameter {
79      get { return (ValueParameter<DoubleValue>)Parameters[CrossoverProbabilityParameterName]; }
80    }
81    public ValueParameter<DoubleValue> ScalingFactorParameter {
82      get { return (ValueParameter<DoubleValue>)Parameters[ScalingFactorParameterName]; }
83    }
84    public ValueParameter<DoubleValue> ValueToReachParameter {
85      get { return (ValueParameter<DoubleValue>)Parameters[ValueToReachParameterName]; }
86    }
87    #endregion
88
89    #region Properties
90    public int MaximumEvaluations {
91      get { return MaximumEvaluationsParameter.Value.Value; }
92      set { MaximumEvaluationsParameter.Value.Value = value; }
93    }
94
95    public Double CrossoverProbability {
96      get { return CrossoverProbabilityParameter.Value.Value; }
97      set { CrossoverProbabilityParameter.Value.Value = value; }
98    }
99    public Double ScalingFactor {
100      get { return ScalingFactorParameter.Value.Value; }
101      set { ScalingFactorParameter.Value.Value = value; }
102    }
103    public int Seed {
104      get { return SeedParameter.Value.Value; }
105      set { SeedParameter.Value.Value = value; }
106    }
107    public bool SetSeedRandomly {
108      get { return SetSeedRandomlyParameter.Value.Value; }
109      set { SetSeedRandomlyParameter.Value.Value = value; }
110    }
111    public IntValue PopulationSize {
112      get { return PopulationSizeParameter.Value; }
113      set { PopulationSizeParameter.Value = value; }
114    }
115    public Double ValueToReach {
116      get { return ValueToReachParameter.Value.Value; }
117      set { ValueToReachParameter.Value.Value = value; }
118    }
119    #endregion
120
121    #region ResultsProperties
122    private double ResultsBestQuality {
123      get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
124      set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }
125    }
126
127    private double VTRBestQuality {
128      get { return ((DoubleValue)Results["VTR"].Value).Value; }
129      set { ((DoubleValue)Results["VTR"].Value).Value = value; }
130    }
131
132    private RealVector ResultsBestSolution {
133      get { return (RealVector)Results["Best Solution"].Value; }
134      set { Results["Best Solution"].Value = value; }
135    }
136
137    private int ResultsEvaluations {
138      get { return ((IntValue)Results["Evaluations"].Value).Value; }
139      set { ((IntValue)Results["Evaluations"].Value).Value = value; }
140    }
141    private int ResultsIterations {
142      get { return ((IntValue)Results["Iterations"].Value).Value; }
143      set { ((IntValue)Results["Iterations"].Value).Value = value; }
144    }
145
146    private DataTable ResultsQualities {
147      get { return ((DataTable)Results["Qualities"].Value); }
148    }
149    private DataRow ResultsQualitiesBest {
150      get { return ResultsQualities.Rows["Best Quality"]; }
151    }
152
153    #endregion
154
155    [StorableConstructor]
156    protected DifferentialEvolution(bool deserializing) : base(deserializing) { }
157
158    protected DifferentialEvolution(DifferentialEvolution original, Cloner cloner)
159      : base(original, cloner) {
160    }
161
162    public override IDeepCloneable Clone(Cloner cloner) {
163      return new DifferentialEvolution(this, cloner);
164    }
165
166    public DifferentialEvolution() {
167      Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(Int32.MaxValue)));
168      Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
169      Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
170      Parameters.Add(new ValueParameter<IntValue>(PopulationSizeParameterName, "The size of the population of solutions.", new IntValue(100)));
171      Parameters.Add(new ValueParameter<DoubleValue>(CrossoverProbabilityParameterName, "The value for crossover rate", new DoubleValue(0.88)));
172      Parameters.Add(new ValueParameter<DoubleValue>(ScalingFactorParameterName, "The value for scaling factor", new DoubleValue(0.47)));
173      Parameters.Add(new ValueParameter<DoubleValue>(ValueToReachParameterName, "Value to reach (VTR) parameter", new DoubleValue(0.00000001)));
174    }
175
176    protected override void Run(CancellationToken cancellationToken) {
177
178      // Set up the results display
179      Results.Add(new Result("Iterations", new IntValue(0)));
180      Results.Add(new Result("Evaluations", new IntValue(0)));
181      Results.Add(new Result("Best Solution", new RealVector()));
182      Results.Add(new Result("Best Quality", new DoubleValue(double.NaN)));
183      Results.Add(new Result("VTR", new DoubleValue(double.NaN)));
184      var table = new DataTable("Qualities");
185      table.Rows.Add(new DataRow("Best Quality"));
186      Results.Add(new Result("Qualities", table));
187
188
189      //problem variables
190      var dim = Problem.ProblemSize.Value;
191      var lb = Problem.Bounds[0, 0];
192      var ub = Problem.Bounds[0, 1];
193      var range = ub - lb;
194      this.evals = 0;
195
196      double[,] populationOld = new double[PopulationSizeParameter.Value.Value, Problem.ProblemSize.Value];
197      double[,] mutationPopulation = new double[PopulationSizeParameter.Value.Value, Problem.ProblemSize.Value];
198      double[,] trialPopulation = new double[PopulationSizeParameter.Value.Value, Problem.ProblemSize.Value];
199      double[] bestPopulation = new double[Problem.ProblemSize.Value];
200      double[] bestPopulationIteration = new double[Problem.ProblemSize.Value];
201
202      //create initial population
203      //population is a matrix of size PopulationSize*ProblemSize
204      for(int i = 0; i < PopulationSizeParameter.Value.Value; i++) {
205        for(int j = 0; j < Problem.ProblemSize.Value; j++) {
206          populationOld[i, j] = _random.NextDouble() * range + lb;
207        }
208      }
209
210      //evaluate the best member after the intialiazation
211      //the idea is to select first member and after that to check the others members from the population
212
213      int best_index = 0;
214      double[] populationRow = new double[Problem.ProblemSize.Value];
215      double[] qualityPopulation = new double[PopulationSizeParameter.Value.Value];
216      bestPopulation = getMatrixRow(populationOld, best_index);
217      RealVector bestPopulationVector = new RealVector(bestPopulation);
218      double bestPopulationValue = Obj(bestPopulationVector);
219      qualityPopulation[best_index] = bestPopulationValue;
220      RealVector selectionVector;
221      RealVector trialVector;
222      double qtrial;
223
224
225      for(var i = 1; i < PopulationSizeParameter.Value.Value; i++) {
226        populationRow = getMatrixRow(populationOld, i);
227        trialVector = new RealVector(populationRow);
228
229        qtrial = Obj(trialVector);
230        qualityPopulation[i] = qtrial;
231
232        if(qtrial > bestPopulationValue) {
233          bestPopulationVector = new RealVector(populationRow);
234          bestPopulationValue = qtrial;
235          best_index = i;
236        }
237      }
238
239      int iterations = 1;
240
241      // Loop until iteration limit reached or canceled.
242      // todo replace with a function
243      // && bestPopulationValue > Problem.BestKnownQuality.Value + ValueToReachParameter.Value.Value
244      while(ResultsEvaluations < MaximumEvaluations
245          && !cancellationToken.IsCancellationRequested
246          && (bestPopulationValue - Problem.BestKnownQuality.Value) > ValueToReachParameter.Value.Value) {
247        //mutation DE/rand/1/bin; classic DE
248        for(int i = 0; i < PopulationSizeParameter.Value.Value; i++) {
249          int r0, r1, r2;
250
251          //assure the selected vectors r0, r1 and r2 are different
252          do {
253            r0 = _random.Next(0, PopulationSizeParameter.Value.Value);
254          } while(r0 == i);
255          do {
256            r1 = _random.Next(0, PopulationSizeParameter.Value.Value);
257          } while(r1 == i || r1 == r0);
258          do {
259            r2 = _random.Next(0, PopulationSizeParameter.Value.Value);
260          } while(r2 == i || r2 == r0 || r2 == r1);
261
262          for(int j = 0; j < getMatrixRow(mutationPopulation, i).Length; j++) {
263            mutationPopulation[i, j] = populationOld[r0, j] +
264                ScalingFactorParameter.Value.Value * (populationOld[r1, j] - populationOld[r2, j]);
265            //check the problem upper and lower bounds
266            if(mutationPopulation[i, j] > ub) mutationPopulation[i, j] = ub;
267            if(mutationPopulation[i, j] < lb) mutationPopulation[i, j] = lb;
268          }
269        }
270
271        //uniform crossover
272        for(int i = 0; i < PopulationSizeParameter.Value.Value; i++) {
273          double rnbr = _random.Next(0, Problem.ProblemSize.Value);
274          for(int j = 0; j < getMatrixRow(mutationPopulation, i).Length; j++) {
275            if(_random.NextDouble() <= CrossoverProbabilityParameter.Value.Value || j == rnbr) {
276              trialPopulation[i, j] = mutationPopulation[i, j];
277            } else {
278              trialPopulation[i, j] = populationOld[i, j];
279            }
280          }
281        }
282
283        //One-to-One Survivor Selection
284        for(int i = 0; i < PopulationSizeParameter.Value.Value; i++) {
285          selectionVector = new RealVector(getMatrixRow(populationOld, i));
286          trialVector = new RealVector(getMatrixRow(trialPopulation, i));
287
288          var selectionEval = qualityPopulation[i];
289          var trialEval = Obj(trialVector);
290
291          if(trialEval < selectionEval) {
292            for(int j = 0; j < getMatrixRow(populationOld, i).Length; j++) {
293              populationOld[i, j] = trialPopulation[i, j];
294            }
295            qualityPopulation[i] = trialEval;
296          }
297        }
298
299        //update the best candidate
300        for(int i = 0; i < PopulationSizeParameter.Value.Value; i++) {
301          selectionVector = new RealVector(getMatrixRow(populationOld, i));
302          var quality = qualityPopulation[i];
303          if(quality < bestPopulationValue) {
304            bestPopulationVector = (RealVector)selectionVector.Clone();
305            bestPopulationValue = quality;
306          }
307        }
308
309        iterations = iterations + 1;
310
311        //update the results
312        ResultsEvaluations = evals;
313        ResultsIterations = iterations;
314        ResultsBestSolution = bestPopulationVector;
315        ResultsBestQuality = bestPopulationValue;
316
317        //update the results in view
318        if(iterations % 10 == 0) ResultsQualitiesBest.Values.Add(bestPopulationValue);
319        if(bestPopulationValue < Problem.BestKnownQuality.Value + ValueToReachParameter.Value.Value) {
320          VTRBestQuality = bestPopulationValue;
321        }
322      }
323    }
324
325    public override bool SupportsPause { get { return false; } } // XXX is pause actually supported?
326
327    //evaluate the vector
328    public double Obj(RealVector x) {
329      evals = evals + 1;
330      if(Problem.Maximization.Value)
331        return -Problem.Evaluator.Evaluate(x);
332
333      return Problem.Evaluator.Evaluate(x);
334    }
335
336    // Get ith row from the matrix
337    public double[] getMatrixRow(double[,] Mat, int i) {
338      double[] tmp = new double[Mat.GetUpperBound(1) + 1];
339
340      for(int j = 0; j <= Mat.GetUpperBound(1); j++) {
341        tmp[j] = Mat[i, j];
342      }
343
344      return tmp;
345    }
346  }
347}
Note: See TracBrowser for help on using the repository browser.