Changeset 13632


Ignore:
Timestamp:
02/24/16 19:09:39 (4 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:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/ichiriac/HeuristicLab.Algorithms.DifferentialEvolution/DifferentialEvolution.cs

    r13619 r13632  
    1010using HeuristicLab.Random;
    1111using System;
     12using System.Collections.Generic;
    1213using System.Linq;
    1314using System.Threading;
     
    1617{
    1718
    18     [Item("Differential Evolution (DE)", "")]
     19    [Item("Differential Evolution (DE)", "A differential evolution algorithm.")]
    1920    [StorableClass]
    2021    [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 400)]
    21     public class DifferentialEvolution : BasicAlgorithm
     22    public class DifferentialEvolution : BasicAlgorithm 
    2223    {
     24        public Func<IEnumerable<double>, double> Evaluation;
     25
    2326
    2427        public override Type ProblemType
     
    3235        }
    3336
    34         private readonly IRandom random = new MersenneTwister();
     37        private readonly IRandom _random = new MersenneTwister();
    3538     
    3639        #region ParameterNames
     
    3841        private const string SeedParameterName = "Seed";
    3942        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
    4053        #endregion
    4154
     
    5366            get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
    5467        }
     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        }
    5580        #endregion
    5681
     
    6186            set { MaximumEvaluationsParameter.Value.Value = value; }
    6287        }
     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        }
    6399        public int Seed
    64100        {
     
    71107            set { SetSeedRandomlyParameter.Value.Value = value; }
    72108        }
     109        public IntValue PopulationSize
     110        {
     111            get { return PopulationSizeParameter.Value; }
     112            set { PopulationSizeParameter.Value = value; }
     113        }
    73114        #endregion
    74115
     
    86127        }
    87128
    88        
    89129        private int ResultsEvaluations
    90130        {
     
    127167            Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
    128168            Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
    129         }
    130 
    131 
     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        }
    132173
    133174        protected override void Run(CancellationToken cancellationToken)
    134175        {
    135      
     176
    136177            // Set up the algorithm
    137178            if (SetSeedRandomly) Seed = new System.Random().Next();
    138             random.Reset(Seed);
     179            _random.Reset(Seed);
    139180
    140181            // Set up the results display
     
    147188            Results.Add(new Result("Qualities", table));
    148189
     190            //problem variables
    149191            var dim = Problem.ProblemSize.Value;
    150192            var lb = Problem.Bounds[0, 0];
    151193            var ub = Problem.Bounds[0, 1];
    152194            var range = ub - lb;
    153             var randomEnumerable = Enumerable.Range(0, dim).Select(_ => random.NextDouble()*range + lb);
     195
    154196            int evals = 0;
    155             double bestSolutionQuality = double.PositiveInfinity;
    156             RealVector cand = new RealVector(randomEnumerable.ToArray());
    157             RealVector bestSolution = cand;
     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());
    158221            // Loop until iteration limit reached or canceled.
    159             while (evals < MaximumEvaluations  && !cancellationToken.IsCancellationRequested)
     222            while (evals < MaximumEvaluations && !cancellationToken.IsCancellationRequested)
    160223            {
    161                 cand = new RealVector(randomEnumerable.ToArray());
    162                 var q = Obj(cand);
     224
    163225                evals++;
    164                 if (q < bestSolutionQuality) {
    165                     bestSolutionQuality = q;
    166                     bestSolution = cand;
    167                 }
    168                 // cancellationToken.ThrowIfCancellationRequested();
    169                 if(evals % 1000 == 0) ResultsQualitiesBest.Values.Add(bestSolutionQuality);
     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);
    170295            }
    171             ResultsEvaluations = evals;
    172             ResultsBestSolution = bestSolution;
    173             ResultsBestQuality = bestSolutionQuality;
    174          }
     296
     297        }
    175298       
     299        //evaluate the vector
    176300        public double Obj(RealVector x)
    177301        {
Note: See TracChangeset for help on using the changeset viewer.