Free cookie consent management tool by TermsFeed Policy Generator

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

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

Implement basic version of differential evolution algorithm

Basic version of differential evolution based of the Storn and Price book

File size: 12.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
27        public override Type ProblemType
28        {
29            get { return typeof(SingleObjectiveTestFunctionProblem); }
30        }
31        public new SingleObjectiveTestFunctionProblem Problem
32        {
33            get { return (SingleObjectiveTestFunctionProblem)base.Problem; }
34            set { base.Problem = value; }
35        }
36
37        private readonly IRandom _random = new MersenneTwister();
38     
39        #region ParameterNames
40        private const string MaximumEvaluationsParameterName = "Maximum Evaluations";
41        private const string SeedParameterName = "Seed";
42        private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
43        private const string CrossoverProbabilityParameterName = "CrossoverProbability";
44        private const string PopulationSizeParameterName = "PopulationSize";
45        private const string ScalingFactorParameterName = "ScalingFactor";
46
47        RealVector bestSolution = null;
48        double bestSolutionQuality = double.PositiveInfinity;
49        RealVector trialVector = null;
50        RealVector selectionVector = null;
51
52
53        #endregion
54
55        #region ParameterProperties
56        public IFixedValueParameter<IntValue> MaximumEvaluationsParameter
57        {
58            get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; }
59        }
60        public IFixedValueParameter<IntValue> SeedParameter
61        {
62            get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
63        }
64        public FixedValueParameter<BoolValue> SetSeedRandomlyParameter
65        {
66            get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
67        }
68        private ValueParameter<IntValue> PopulationSizeParameter
69        {
70            get { return (ValueParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
71        }
72        public ValueParameter<DoubleValue> CrossoverProbabilityParameter
73        {
74            get { return (ValueParameter<DoubleValue>)Parameters[CrossoverProbabilityParameterName]; }
75        }
76        public ValueParameter<DoubleValue> ScalingFactorParameter
77        {
78            get { return (ValueParameter<DoubleValue>)Parameters[ScalingFactorParameterName]; }
79        }
80        #endregion
81
82        #region Properties
83        public int MaximumEvaluations
84        {
85            get { return MaximumEvaluationsParameter.Value.Value; }
86            set { MaximumEvaluationsParameter.Value.Value = value; }
87        }
88
89        public Double CrossoverProbability
90        {
91            get { return CrossoverProbabilityParameter.Value.Value; }
92            set { CrossoverProbabilityParameter.Value.Value = value; }
93        }
94        public Double ScalingFactor
95        {
96            get { return ScalingFactorParameter.Value.Value; }
97            set { ScalingFactorParameter.Value.Value = value; }
98        }
99        public int Seed
100        {
101            get { return SeedParameter.Value.Value; }
102            set { SeedParameter.Value.Value = value; }
103        }
104        public bool SetSeedRandomly
105        {
106            get { return SetSeedRandomlyParameter.Value.Value; }
107            set { SetSeedRandomlyParameter.Value.Value = value; }
108        }
109        public IntValue PopulationSize
110        {
111            get { return PopulationSizeParameter.Value; }
112            set { PopulationSizeParameter.Value = value; }
113        }
114        #endregion
115
116        #region ResultsProperties
117        private double ResultsBestQuality
118        {
119            get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
120            set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }
121        }
122
123        private RealVector ResultsBestSolution
124        {
125            get { return (RealVector)Results["Best Solution"].Value; }
126            set { Results["Best Solution"].Value = value; }
127        }
128
129        private int ResultsEvaluations
130        {
131            get { return ((IntValue)Results["Evaluations"].Value).Value; }
132            set { ((IntValue)Results["Evaluations"].Value).Value = value; }
133        }
134        private int ResultsIterations
135        {
136            get { return ((IntValue)Results["Iterations"].Value).Value; }
137            set { ((IntValue)Results["Iterations"].Value).Value = value; }
138        }
139
140        private DataTable ResultsQualities
141        {
142            get { return ((DataTable)Results["Qualities"].Value); }
143        }
144        private DataRow ResultsQualitiesBest
145        {
146            get { return ResultsQualities.Rows["Best Quality"]; }
147        }
148
149        #endregion
150
151        [StorableConstructor]
152        protected DifferentialEvolution(bool deserializing) : base(deserializing) { }
153
154        protected DifferentialEvolution(DifferentialEvolution original, Cloner cloner)
155          : base(original, cloner)
156        {
157        }
158
159        public override IDeepCloneable Clone(Cloner cloner)
160        {
161            return new DifferentialEvolution(this, cloner);
162        }
163
164        public DifferentialEvolution()
165        {
166            Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(Int32.MaxValue)));
167            Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
168            Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
169            Parameters.Add(new ValueParameter<IntValue>(PopulationSizeParameterName, "The size of the population of solutions.", new IntValue(75)));
170            Parameters.Add(new ValueParameter<DoubleValue>(CrossoverProbabilityParameterName, "The value for crossover rate", new DoubleValue(0.88)));
171            Parameters.Add(new ValueParameter<DoubleValue>(ScalingFactorParameterName, "The value for scaling factor", new DoubleValue(0.47)));
172        }
173
174        protected override void Run(CancellationToken cancellationToken)
175        {
176
177            // Set up the algorithm
178            if (SetSeedRandomly) Seed = new System.Random().Next();
179            _random.Reset(Seed);
180
181            // Set up the results display
182            Results.Add(new Result("Iterations", new IntValue(0)));
183            Results.Add(new Result("Evaluations", new IntValue(0)));
184            Results.Add(new Result("Best Solution", new RealVector()));
185            Results.Add(new Result("Best Quality", new DoubleValue(double.NaN)));
186            var table = new DataTable("Qualities");
187            table.Rows.Add(new DataRow("Best Quality"));
188            Results.Add(new Result("Qualities", table));
189
190            //problem variables
191            var dim = Problem.ProblemSize.Value;
192            var lb = Problem.Bounds[0, 0];
193            var ub = Problem.Bounds[0, 1];
194            var range = ub - lb;
195
196            int evals = 0;
197
198
199            //initialize the vectors
200            var _mutantVectors = new double[PopulationSizeParameter.Value.Value][];
201            var _solutions = new double[PopulationSizeParameter.Value.Value][];
202            var _trialVectors = new double[PopulationSizeParameter.Value.Value][];
203
204            for (var i = 0; i < _mutantVectors.Length; i++)
205            {
206                _solutions[i] = new double[PopulationSizeParameter.Value.Value];
207                _mutantVectors[i] = new double[PopulationSizeParameter.Value.Value];
208                _trialVectors[i] = new double[PopulationSizeParameter.Value.Value];
209            }
210
211            //create initial population
212            for (int i = 0; i < _solutions.Length; ++i)
213            {
214                for (int j = 0; j < _solutions[i].Length; ++j)
215                {
216                    _solutions[i][j] = _random.NextDouble() * range + lb;
217                }
218            }
219
220            bestSolution = new RealVector((double[])_solutions[0].Clone());
221            // Loop until iteration limit reached or canceled.
222            while (evals < MaximumEvaluations && !cancellationToken.IsCancellationRequested)
223            {
224
225                evals++;
226                //mutation
227                for (int i = 0; i < _mutantVectors.Length; ++i)
228                {
229                    int r1 = _random.Next(0, _solutions.Length),
230                        r2 = _random.Next(0, _solutions.Length),
231                        r3 = _random.Next(0, _solutions.Length);
232
233                    for (int j = 0; j < _mutantVectors[i].Length; ++j)
234                    {
235                        _mutantVectors[i][j] = _solutions[r1][j] +
236                            ScalingFactorParameter.Value.Value * (_solutions[r2][j] - _solutions[r3][j]);
237                        if (_mutantVectors[i][j] > ub) _mutantVectors[i][j] = ub;
238                        if (_mutantVectors[i][j] < lb) _mutantVectors[i][j] = lb;
239                    }
240                }
241
242                //crossover
243                for (int i = 0; i < _trialVectors.Length; ++i)
244                {
245                    int rnbr = _random.Next(0, _trialVectors[i].Length);
246                    for (int j = 0; j < _mutantVectors[i].Length; ++j)
247                    {
248                        if (_random.NextDouble() <= CrossoverProbabilityParameter.Value.Value || j == rnbr)
249                        {
250                            _trialVectors[i][j] = _mutantVectors[i][j];
251                        }
252                        else
253                        {
254                            _trialVectors[i][j] = _solutions[i][j];
255                        }
256                    }
257                }
258
259                //selection
260
261                for (int i = 0; i < _solutions.Length; ++i)
262                {
263                    selectionVector = new RealVector(_solutions[i]);
264                    trialVector = new RealVector(_trialVectors[i]);
265
266                    var qselection = Obj(selectionVector);
267                    var qtrial = Obj(trialVector);
268
269
270                    if (qtrial < qselection)
271                    {
272                        _solutions[i] = (double[])_trialVectors[i].Clone();
273                    }
274                }
275                var currentBestQuality = Obj(bestSolution);
276                //update the best candidate
277                for (int i = 0; i < _solutions.Length; ++i)
278                {
279                    selectionVector = new RealVector(_solutions[i]);
280                    var quality = Obj(selectionVector);
281                    if (quality < currentBestQuality)
282                    {
283                        bestSolution = (RealVector)selectionVector.Clone();
284                        bestSolutionQuality = quality;
285                    }
286                }
287
288                //update the results
289                ResultsEvaluations = evals;
290                ResultsBestSolution = bestSolution;
291                ResultsBestQuality = bestSolutionQuality;
292
293                //update the results in view
294                if (evals % 100 == 0) ResultsQualitiesBest.Values.Add(bestSolutionQuality);
295            }
296
297        }
298       
299        //evaluate the vector
300        public double Obj(RealVector x)
301        {
302            if(Problem.Maximization.Value)
303            return -Problem.Evaluator.Evaluate(x);
304
305            return Problem.Evaluator.Evaluate(x);
306        }
307    }
308}
309
Note: See TracBrowser for help on using the repository browser.