Changeset 13632

Timestamp:

02/24/16 19:09:39 (9 years ago)

Author:

ichiriac

Message:

Implement basic version of differential evolution algorithm

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

File:

• branches/ichiriac/HeuristicLab.Algorithms.DifferentialEvolution/DifferentialEvolution.cs (modified) (10 diffs)

branches/ichiriac/HeuristicLab.Algorithms.DifferentialEvolution/DifferentialEvolution.cs

@@ -10 +10 @@
 using HeuristicLab.Random;
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using System.Threading;
@@ -16 +17 @@
 {
 
-    [Item("Differential Evolution (DE)", "")]
+    [Item("Differential Evolution (DE)", "A differential evolution algorithm.")]
     [StorableClass]
     [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 400)]
-    public class DifferentialEvolution : BasicAlgorithm
+    public class DifferentialEvolution : BasicAlgorithm 
     {
+        public Func<IEnumerable<double>, double> Evaluation;
+
 
         public override Type ProblemType
@@ -32 +35 @@
         }
 
-        private readonly IRandom random = new MersenneTwister();
+        private readonly IRandom _random = new MersenneTwister();
      
         #region ParameterNames
@@ -38 +41 @@
         private const string SeedParameterName = "Seed";
         private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
+        private const string CrossoverProbabilityParameterName = "CrossoverProbability";
+        private const string PopulationSizeParameterName = "PopulationSize";
+        private const string ScalingFactorParameterName = "ScalingFactor";
+
+        RealVector bestSolution = null;
+        double bestSolutionQuality = double.PositiveInfinity;
+        RealVector trialVector = null;
+        RealVector selectionVector = null;
+
+
         #endregion
 
@@ -53 +66 @@
             get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
         }
+        private ValueParameter<IntValue> PopulationSizeParameter
+        {
+            get { return (ValueParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
+        }
+        public ValueParameter<DoubleValue> CrossoverProbabilityParameter
+        {
+            get { return (ValueParameter<DoubleValue>)Parameters[CrossoverProbabilityParameterName]; }
+        }
+        public ValueParameter<DoubleValue> ScalingFactorParameter
+        {
+            get { return (ValueParameter<DoubleValue>)Parameters[ScalingFactorParameterName]; }
+        }
         #endregion
 
@@ -61 +86 @@
             set { MaximumEvaluationsParameter.Value.Value = value; }
         }
+
+        public Double CrossoverProbability
+        {
+            get { return CrossoverProbabilityParameter.Value.Value; }
+            set { CrossoverProbabilityParameter.Value.Value = value; }
+        }
+        public Double ScalingFactor
+        {
+            get { return ScalingFactorParameter.Value.Value; }
+            set { ScalingFactorParameter.Value.Value = value; }
+        }
         public int Seed
         {
@@ -71 +107 @@
             set { SetSeedRandomlyParameter.Value.Value = value; }
         }
+        public IntValue PopulationSize
+        {
+            get { return PopulationSizeParameter.Value; }
+            set { PopulationSizeParameter.Value = value; }
+        }
         #endregion
 
@@ -86 +127 @@
         }
 
-        
         private int ResultsEvaluations
         {
@@ -127 +167 @@
             Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
             Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
-        }
-
-
+            Parameters.Add(new ValueParameter<IntValue>(PopulationSizeParameterName, "The size of the population of solutions.", new IntValue(75)));
+            Parameters.Add(new ValueParameter<DoubleValue>(CrossoverProbabilityParameterName, "The value for crossover rate", new DoubleValue(0.88)));
+            Parameters.Add(new ValueParameter<DoubleValue>(ScalingFactorParameterName, "The value for scaling factor", new DoubleValue(0.47)));
+        }
 
         protected override void Run(CancellationToken cancellationToken)
         {
-     
+
             // Set up the algorithm
             if (SetSeedRandomly) Seed = new System.Random().Next();
-            random.Reset(Seed);
+            _random.Reset(Seed);
 
             // Set up the results display
@@ -147 +188 @@
             Results.Add(new Result("Qualities", table));
 
+            //problem variables
             var dim = Problem.ProblemSize.Value;
             var lb = Problem.Bounds[0, 0];
             var ub = Problem.Bounds[0, 1];
             var range = ub - lb;
-            var randomEnumerable = Enumerable.Range(0, dim).Select(_ => random.NextDouble()*range + lb);
+
             int evals = 0;
-            double bestSolutionQuality = double.PositiveInfinity;
-            RealVector cand = new RealVector(randomEnumerable.ToArray());
-            RealVector bestSolution = cand;
+
+
+            //initialize the vectors
+            var _mutantVectors = new double[PopulationSizeParameter.Value.Value][];
+            var _solutions = new double[PopulationSizeParameter.Value.Value][];
+            var _trialVectors = new double[PopulationSizeParameter.Value.Value][];
+
+            for (var i = 0; i < _mutantVectors.Length; i++)
+            {
+                _solutions[i] = new double[PopulationSizeParameter.Value.Value];
+                _mutantVectors[i] = new double[PopulationSizeParameter.Value.Value];
+                _trialVectors[i] = new double[PopulationSizeParameter.Value.Value];
+            }
+
+            //create initial population
+            for (int i = 0; i < _solutions.Length; ++i)
+            {
+                for (int j = 0; j < _solutions[i].Length; ++j)
+                {
+                    _solutions[i][j] = _random.NextDouble() * range + lb;
+                }
+            }
+
+            bestSolution = new RealVector((double[])_solutions[0].Clone());
             // Loop until iteration limit reached or canceled.
-            while (evals < MaximumEvaluations  && !cancellationToken.IsCancellationRequested)
+            while (evals < MaximumEvaluations && !cancellationToken.IsCancellationRequested)
             {
-                cand = new RealVector(randomEnumerable.ToArray());
-                var q = Obj(cand);
+
                 evals++;
-                if (q < bestSolutionQuality) {
-                    bestSolutionQuality = q;
-                    bestSolution = cand;
-                }
-                // cancellationToken.ThrowIfCancellationRequested();
-                if(evals % 1000 == 0) ResultsQualitiesBest.Values.Add(bestSolutionQuality);
+                //mutation
+                for (int i = 0; i < _mutantVectors.Length; ++i)
+                {
+                    int r1 = _random.Next(0, _solutions.Length),
+                        r2 = _random.Next(0, _solutions.Length),
+                        r3 = _random.Next(0, _solutions.Length);
+
+                    for (int j = 0; j < _mutantVectors[i].Length; ++j)
+                    {
+                        _mutantVectors[i][j] = _solutions[r1][j] +
+                            ScalingFactorParameter.Value.Value * (_solutions[r2][j] - _solutions[r3][j]);
+                        if (_mutantVectors[i][j] > ub) _mutantVectors[i][j] = ub;
+                        if (_mutantVectors[i][j] < lb) _mutantVectors[i][j] = lb;
+                    }
+                }
+
+                //crossover
+                for (int i = 0; i < _trialVectors.Length; ++i)
+                {
+                    int rnbr = _random.Next(0, _trialVectors[i].Length);
+                    for (int j = 0; j < _mutantVectors[i].Length; ++j)
+                    {
+                        if (_random.NextDouble() <= CrossoverProbabilityParameter.Value.Value || j == rnbr)
+                        {
+                            _trialVectors[i][j] = _mutantVectors[i][j];
+                        }
+                        else
+                        {
+                            _trialVectors[i][j] = _solutions[i][j];
+                        }
+                    }
+                }
+
+                //selection
+
+                for (int i = 0; i < _solutions.Length; ++i)
+                {
+                    selectionVector = new RealVector(_solutions[i]);
+                    trialVector = new RealVector(_trialVectors[i]);
+
+                    var qselection = Obj(selectionVector);
+                    var qtrial = Obj(trialVector);
+
+
+                    if (qtrial < qselection)
+                    {
+                        _solutions[i] = (double[])_trialVectors[i].Clone();
+                    }
+                }
+                var currentBestQuality = Obj(bestSolution);
+                //update the best candidate
+                for (int i = 0; i < _solutions.Length; ++i)
+                {
+                    selectionVector = new RealVector(_solutions[i]);
+                    var quality = Obj(selectionVector);
+                    if (quality < currentBestQuality)
+                    {
+                        bestSolution = (RealVector)selectionVector.Clone();
+                        bestSolutionQuality = quality;
+                    }
+                }
+
+                //update the results
+                ResultsEvaluations = evals;
+                ResultsBestSolution = bestSolution;
+                ResultsBestQuality = bestSolutionQuality; 
+
+                //update the results in view
+                if (evals % 100 == 0) ResultsQualitiesBest.Values.Add(bestSolutionQuality);
             }
-            ResultsEvaluations = evals;
-            ResultsBestSolution = bestSolution;
-            ResultsBestQuality = bestSolutionQuality;
-         }
+
+        }
         
+        //evaluate the vector
         public double Obj(RealVector x)
         {