Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14697 was 14086, checked in by ichiriac, 8 years ago

Final revision of the code
File size: 16.7 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
39    [Item("Differential Evolution (DE)", "A differential evolution algorithm.")]
40    [StorableClass]
41    [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 400)]
42    public class DifferentialEvolution : BasicAlgorithm
43    {
44        public Func<IEnumerable<double>, double> Evaluation;
45
46        public override Type ProblemType
47        {
48            get { return typeof(SingleObjectiveTestFunctionProblem); }
49        }
50        public new SingleObjectiveTestFunctionProblem Problem
51        {
52            get { return (SingleObjectiveTestFunctionProblem)base.Problem; }
53            set { base.Problem = value; }
54        }
55
56        private readonly IRandom _random = new MersenneTwister();
57        private int evals;
58
59        #region ParameterNames
60        private const string MaximumEvaluationsParameterName = "Maximum Evaluations";
61        private const string SeedParameterName = "Seed";
62        private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
63        private const string CrossoverProbabilityParameterName = "CrossoverProbability";
64        private const string PopulationSizeParameterName = "PopulationSize";
65        private const string ScalingFactorParameterName = "ScalingFactor";
66        private const string ValueToReachParameterName = "ValueToReach";
67        #endregion
68
69        #region ParameterProperties
70        public IFixedValueParameter<IntValue> MaximumEvaluationsParameter
71        {
72            get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; }
73        }
74        public IFixedValueParameter<IntValue> SeedParameter
75        {
76            get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
77        }
78        public FixedValueParameter<BoolValue> SetSeedRandomlyParameter
79        {
80            get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
81        }
82        private ValueParameter<IntValue> PopulationSizeParameter
83        {
84            get { return (ValueParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
85        }
86        public ValueParameter<DoubleValue> CrossoverProbabilityParameter
87        {
88            get { return (ValueParameter<DoubleValue>)Parameters[CrossoverProbabilityParameterName]; }
89        }
90        public ValueParameter<DoubleValue> ScalingFactorParameter
91        {
92            get { return (ValueParameter<DoubleValue>)Parameters[ScalingFactorParameterName]; }
93        }
94        public ValueParameter<DoubleValue> ValueToReachParameter
95        {
96            get { return (ValueParameter<DoubleValue>)Parameters[ValueToReachParameterName]; }
97        }
98        #endregion
99
100        #region Properties
101        public int MaximumEvaluations
102        {
103            get { return MaximumEvaluationsParameter.Value.Value; }
104            set { MaximumEvaluationsParameter.Value.Value = value; }
105        }
106
107        public Double CrossoverProbability
108        {
109            get { return CrossoverProbabilityParameter.Value.Value; }
110            set { CrossoverProbabilityParameter.Value.Value = value; }
111        }
112        public Double ScalingFactor
113        {
114            get { return ScalingFactorParameter.Value.Value; }
115            set { ScalingFactorParameter.Value.Value = value; }
116        }
117        public int Seed
118        {
119            get { return SeedParameter.Value.Value; }
120            set { SeedParameter.Value.Value = value; }
121        }
122        public bool SetSeedRandomly
123        {
124            get { return SetSeedRandomlyParameter.Value.Value; }
125            set { SetSeedRandomlyParameter.Value.Value = value; }
126        }
127        public IntValue PopulationSize
128        {
129            get { return PopulationSizeParameter.Value; }
130            set { PopulationSizeParameter.Value = value; }
131        }
132        public Double ValueToReach
133        {
134            get { return ValueToReachParameter.Value.Value; }
135            set { ValueToReachParameter.Value.Value = value; }
136        }
137        #endregion
138
139        #region ResultsProperties
140        private double ResultsBestQuality
141        {
142            get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
143            set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }
144        }
145
146        private double VTRBestQuality
147        {
148            get { return ((DoubleValue)Results["VTR"].Value).Value; }
149            set { ((DoubleValue)Results["VTR"].Value).Value = value; }
150        }
151
152        private RealVector ResultsBestSolution
153        {
154            get { return (RealVector)Results["Best Solution"].Value; }
155            set { Results["Best Solution"].Value = value; }
156        }
157
158        private int ResultsEvaluations
159        {
160            get { return ((IntValue)Results["Evaluations"].Value).Value; }
161            set { ((IntValue)Results["Evaluations"].Value).Value = value; }
162        }
163        private int ResultsIterations
164        {
165            get { return ((IntValue)Results["Iterations"].Value).Value; }
166            set { ((IntValue)Results["Iterations"].Value).Value = value; }
167        }
168
169        private DataTable ResultsQualities
170        {
171            get { return ((DataTable)Results["Qualities"].Value); }
172        }
173        private DataRow ResultsQualitiesBest
174        {
175            get { return ResultsQualities.Rows["Best Quality"]; }
176        }
177
178        #endregion
179
180        [StorableConstructor]
181        protected DifferentialEvolution(bool deserializing) : base(deserializing) { }
182
183        protected DifferentialEvolution(DifferentialEvolution original, Cloner cloner)
184          : base(original, cloner)
185        {
186        }
187
188        public override IDeepCloneable Clone(Cloner cloner)
189        {
190            return new DifferentialEvolution(this, cloner);
191        }
192
193        public DifferentialEvolution()
194        {
195            Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(Int32.MaxValue)));
196            Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
197            Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
198            Parameters.Add(new ValueParameter<IntValue>(PopulationSizeParameterName, "The size of the population of solutions.", new IntValue(100)));
199            Parameters.Add(new ValueParameter<DoubleValue>(CrossoverProbabilityParameterName, "The value for crossover rate", new DoubleValue(0.88)));
200            Parameters.Add(new ValueParameter<DoubleValue>(ScalingFactorParameterName, "The value for scaling factor", new DoubleValue(0.47)));
201            Parameters.Add(new ValueParameter<DoubleValue>(ValueToReachParameterName, "Value to reach (VTR) parameter", new DoubleValue(0.00000001)));
202        }
203
204        protected override void Run(CancellationToken cancellationToken)
205        {
206
207            // Set up the results display
208            Results.Add(new Result("Iterations", new IntValue(0)));
209            Results.Add(new Result("Evaluations", new IntValue(0)));
210            Results.Add(new Result("Best Solution", new RealVector()));
211            Results.Add(new Result("Best Quality", new DoubleValue(double.NaN)));
212            Results.Add(new Result("VTR", new DoubleValue(double.NaN)));
213            var table = new DataTable("Qualities");
214            table.Rows.Add(new DataRow("Best Quality"));
215            Results.Add(new Result("Qualities", table));
216
217
218            //problem variables
219            var dim = Problem.ProblemSize.Value;
220            var lb = Problem.Bounds[0, 0];
221            var ub = Problem.Bounds[0, 1];
222            var range = ub - lb;
223            this.evals = 0;
224
225            double[,] populationOld = new double[PopulationSizeParameter.Value.Value, Problem.ProblemSize.Value];
226            double[,] mutationPopulation = new double[PopulationSizeParameter.Value.Value, Problem.ProblemSize.Value];
227            double[,] trialPopulation = new double[PopulationSizeParameter.Value.Value, Problem.ProblemSize.Value];
228            double[] bestPopulation = new double[Problem.ProblemSize.Value];
229            double[] bestPopulationIteration = new double[Problem.ProblemSize.Value];
230
231            //create initial population
232            //population is a matrix of size PopulationSize*ProblemSize
233            for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
234            {
235                for (int j = 0; j < Problem.ProblemSize.Value; j++)
236                {
237                    populationOld[i, j] = _random.NextDouble() * range + lb;
238                }
239            }
240
241            //evaluate the best member after the intialiazation
242            //the idea is to select first member and after that to check the others members from the population
243
244            int best_index = 0;
245            double[] populationRow = new double[Problem.ProblemSize.Value];
246            double[] qualityPopulation = new double[PopulationSizeParameter.Value.Value];
247            bestPopulation = getMatrixRow(populationOld, best_index);
248            RealVector bestPopulationVector = new RealVector(bestPopulation);
249            double bestPopulationValue = Obj(bestPopulationVector);
250            qualityPopulation[best_index] = bestPopulationValue;
251            RealVector selectionVector;
252            RealVector trialVector;
253            double qtrial;
254
255
256            for (var i = 1; i < PopulationSizeParameter.Value.Value; i++)
257            {
258                populationRow = getMatrixRow(populationOld, i);
259                trialVector = new RealVector(populationRow);
260
261                qtrial = Obj(trialVector);
262                qualityPopulation[i] = qtrial;
263
264                if (qtrial > bestPopulationValue)
265                {
266                    bestPopulationVector = new RealVector(populationRow);
267                    bestPopulationValue = qtrial;
268                    best_index = i;
269                }
270            }
271
272            int iterations = 1;
273
274            // Loop until iteration limit reached or canceled.
275            // todo replace with a function
276            // && bestPopulationValue > Problem.BestKnownQuality.Value + ValueToReachParameter.Value.Value
277            while (ResultsEvaluations < MaximumEvaluations
278                && !cancellationToken.IsCancellationRequested
279                && (bestPopulationValue - Problem.BestKnownQuality.Value) > ValueToReachParameter.Value.Value)
280            {
281                //mutation DE/rand/1/bin; classic DE
282                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
283                {
284                    int r0, r1, r2;
285
286                    //assure the selected vectors r0, r1 and r2 are different
287                    do
288                    {
289                        r0 = _random.Next(0, PopulationSizeParameter.Value.Value);
290                    } while (r0 == i);
291                    do
292                    {
293                        r1 = _random.Next(0, PopulationSizeParameter.Value.Value);
294                    } while (r1 == i || r1 == r0);
295                    do
296                    {
297                        r2 = _random.Next(0, PopulationSizeParameter.Value.Value);
298                    } while (r2 == i || r2 == r0 || r2 == r1);
299
300                    for (int j = 0; j < getMatrixRow(mutationPopulation, i).Length; j++)
301                    {
302                        mutationPopulation[i, j] = populationOld[r0, j] +
303                            ScalingFactorParameter.Value.Value * (populationOld[r1, j] - populationOld[r2, j]);
304                        //check the problem upper and lower bounds
305                        if (mutationPopulation[i, j] > ub) mutationPopulation[i, j] = ub;
306                        if (mutationPopulation[i, j] < lb) mutationPopulation[i, j] = lb;
307                    }
308                }
309
310                //uniform crossover
311                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
312                {
313                    double rnbr = _random.Next(0, Problem.ProblemSize.Value);
314                    for (int j = 0; j < getMatrixRow(mutationPopulation, i).Length; j++)
315                    {
316                        if (_random.NextDouble() <= CrossoverProbabilityParameter.Value.Value || j == rnbr)
317                        {
318                            trialPopulation[i, j] = mutationPopulation[i, j];
319                        }
320                        else
321                        {
322                            trialPopulation[i, j] = populationOld[i, j];
323                        }
324                    }
325                }
326
327                //One-to-One Survivor Selection
328                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
329                {
330                    selectionVector = new RealVector(getMatrixRow(populationOld, i));
331                    trialVector = new RealVector(getMatrixRow(trialPopulation, i));
332
333                    var selectionEval = qualityPopulation[i];
334                    var trialEval = Obj(trialVector);
335
336                    if (trialEval < selectionEval)
337                    {
338                        for (int j = 0; j < getMatrixRow(populationOld, i).Length; j++)
339                        {
340                            populationOld[i, j] = trialPopulation[i, j];
341                        }
342                        qualityPopulation[i] = trialEval;
343                    }
344                }
345
346                //update the best candidate
347                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
348                {
349                    selectionVector = new RealVector(getMatrixRow(populationOld, i));
350                    var quality = qualityPopulation[i];
351                    if (quality < bestPopulationValue)
352                    {
353                        bestPopulationVector = (RealVector)selectionVector.Clone();
354                        bestPopulationValue = quality;
355                    }
356                }
357
358                iterations = iterations + 1;
359
360                //update the results
361                ResultsEvaluations = evals;
362                ResultsIterations = iterations;
363                ResultsBestSolution = bestPopulationVector;
364                ResultsBestQuality = bestPopulationValue;
365
366                //update the results in view
367                if (iterations % 10 == 0) ResultsQualitiesBest.Values.Add(bestPopulationValue);
368                if (bestPopulationValue < Problem.BestKnownQuality.Value + ValueToReachParameter.Value.Value)
369                {
370                    VTRBestQuality = bestPopulationValue;
371                }
372            }
373        }
374
375        //evaluate the vector
376        public double Obj(RealVector x)
377        {
378            evals = evals + 1;
379            if (Problem.Maximization.Value)
380                return -Problem.Evaluator.Evaluate(x);
381
382            return Problem.Evaluator.Evaluate(x);
383        }
384
385        // Get ith row from the matrix
386        public double[] getMatrixRow(double[,] Mat, int i)
387        {
388            double[] tmp = new double[Mat.GetUpperBound(1) + 1];
389
390            for (int j = 0; j <= Mat.GetUpperBound(1); j++)
391            {
392                tmp[j] = Mat[i, j];
393            }
394
395            return tmp;
396        }
397    }
398}
Note: See TracBrowser for help on using the repository browser.