Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 13770 was 13770, checked in by ichiriac, 6 years ago

Fix the calculation of evaluation number

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