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

Last change on this file since 13674 was 13674, checked in by ichiriac, 5 years ago

Improve calculation of evaluations

Save the best value less that "ValueToReach"

File size: 15.2 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.Linq;
14using System.Threading;
15
16namespace HeuristicLab.Algorithms.DifferentialEvolution
17{
18
19    [Item("Differential Evolution (DE)", "A differential evolution algorithm.")]
20    [StorableClass]
21    [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 400)]
22    public class DifferentialEvolution : BasicAlgorithm
23    {
24        public Func<IEnumerable<double>, double> Evaluation;
25
26        public override Type ProblemType
27        {
28            get { return typeof(SingleObjectiveTestFunctionProblem); }
29        }
30        public new SingleObjectiveTestFunctionProblem Problem
31        {
32            get { return (SingleObjectiveTestFunctionProblem)base.Problem; }
33            set { base.Problem = value; }
34        }
35
36        private readonly IRandom _random = new MersenneTwister();
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
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            int evals = 0; // number of function evaluations
209
210            //create initial population
211            //population is a matrix of size PopulationSize*ProblemSize
212            for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
213            {
214                for (int j = 0; j < Problem.ProblemSize.Value; ++j)
215                  {
216                    populationOld[i, j] = _random.NextDouble() * range + lb;
217                }
218            }
219
220            //evaluate the best member after the intialiazation
221            //the idea is to select first member and after that to check the others members from the population
222
223            int best_index = 0;
224            double[] populationRow = new double[Problem.ProblemSize.Value];
225
226            bestPopulation = Get_ith_row(populationOld, best_index);
227            RealVector bestPopulationVector = new RealVector(bestPopulation);
228            double bestPopulationValue = Obj(bestPopulationVector, evals);
229            RealVector selectionVector;
230            RealVector trialVector;
231            double qtrial;
232
233
234            for (var i = 0; i < PopulationSizeParameter.Value.Value; i++)
235            {
236                populationRow = Get_ith_row(populationOld, i);
237                trialVector = new RealVector(populationRow);
238
239                qtrial = Obj(trialVector, evals);
240
241                if (qtrial > bestPopulationValue)
242                {
243                    bestPopulationVector = new RealVector(populationRow);
244                    bestPopulationValue = Obj(bestPopulationVector, evals);
245                    best_index = i;
246                }
247            }
248
249            int iterations = 1;
250
251            // Loop until iteration limit reached or canceled.
252            //todo replace with a function
253            while (evals < MaximumEvaluations
254                && !cancellationToken.IsCancellationRequested
255                && bestPopulationValue > Problem.BestKnownQuality.Value + ValueToReachParameter.Value.Value)
256            {
257
258                //mutation DE/rand/1/bin; classic DE
259                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
260                {
261                    int r1 = _random.Next(0, PopulationSizeParameter.Value.Value),
262                        r2 = _random.Next(0, PopulationSizeParameter.Value.Value),
263                        r3 = _random.Next(0, PopulationSizeParameter.Value.Value);
264
265                    for (int j = 0; j < Get_ith_row(mutationPopulation, i).Length; j++)
266                    {
267                        mutationPopulation[i,j] = populationOld[r1,j] +
268                            ScalingFactorParameter.Value.Value * (populationOld[r2,j] - populationOld[r3,j]);
269                        //check the problem upper and lower bounds
270                        if (mutationPopulation[i,j] > ub) mutationPopulation[i,j] = ub;
271                        if (mutationPopulation[i,j] < lb) mutationPopulation[i,j] = lb;
272                    }
273                }
274
275                //uniform crossover
276                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
277                {
278                    double rnbr = Math.Floor(_random.NextDouble() * Problem.ProblemSize.Value);
279                    for (int j = 0; j < Get_ith_row(mutationPopulation, i).Length; j++)
280                    {
281                        if (_random.NextDouble() <= CrossoverProbabilityParameter.Value.Value || j == rnbr)
282                        {
283                            trialPopulation[i,j] = mutationPopulation[i,j];
284                        }
285                        else
286                        {
287                            trialPopulation[i,j] = populationOld[i,j];
288                        }
289                    }
290                }
291
292                //One-to-One Survivor Selection
293                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
294                {
295                    selectionVector = new RealVector(Get_ith_row(populationOld, i));
296                    trialVector = new RealVector(Get_ith_row(trialPopulation, i));
297
298                    var selectionEval = Obj(selectionVector, evals);
299                    var trailEval = Obj(trialVector, evals);
300
301
302                    if (trailEval < selectionEval)
303                    {
304                        for (int j = 0; j < Get_ith_row(populationOld, i).Length; j++)
305                        {
306                            populationOld[i, j] = trialPopulation[i, j];
307                        }
308                    }
309                }
310
311                //update the best candidate
312                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
313                {
314                    evals = evals + 1;
315                    selectionVector = new RealVector(Get_ith_row(populationOld, i));
316                    var quality = Obj(selectionVector, evals);
317                    if (quality < bestPopulationValue)
318                    {
319                        bestPopulationVector = (RealVector)selectionVector.Clone();
320                        bestPopulationValue = quality;
321                    }
322                }
323
324                iterations = iterations + 1;
325
326                //update the results
327                ResultsEvaluations = evals;
328                ResultsIterations = iterations;
329                ResultsBestSolution = bestPopulationVector;
330                ResultsBestQuality = bestPopulationValue;
331
332                //update the results in view
333                if (evals % 100 == 0 ) ResultsQualitiesBest.Values.Add(bestPopulationValue);
334                if (bestPopulationValue < Problem.BestKnownQuality.Value + ValueToReachParameter.Value.Value)
335                {
336                    VTRBestQuality = bestPopulationValue;
337                }
338            }
339
340        }
341       
342        //evaluate the vector
343        public double Obj(RealVector x, int evals)
344        {
345            evals = evals + 1;
346            if(Problem.Maximization.Value)
347            return -Problem.Evaluator.Evaluate(x);
348
349            return Problem.Evaluator.Evaluate(x);
350        }
351
352        // Get ith row from the matrix
353        public double[] Get_ith_row(double[,] Mat, int i)
354        {
355            double[] tmp = new double[Mat.GetUpperBound(1) + 1];
356
357            for (int j = 0; j <= Mat.GetUpperBound(1); j++)
358            {
359                tmp[j] = Mat[i, j];
360            }
361
362            return tmp;
363        }
364    }
365}
366
Note: See TracBrowser for help on using the repository browser.