Changeset 13674


Ignore:
Timestamp:
03/09/16 16:01:34 (5 years ago)
Author:
ichiriac
Message:

Improve calculation of evaluations

Save the best value less that "ValueToReach"

File:
1 edited

Legend:

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

    r13632 r13674  
    2424        public Func<IEnumerable<double>, double> Evaluation;
    2525
    26 
    2726        public override Type ProblemType
    2827        {
     
    4443        private const string PopulationSizeParameterName = "PopulationSize";
    4544        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 
     45        private const string ValueToReachParameterName = "ValueToReach";
    5346        #endregion
    5447
     
    7871            get { return (ValueParameter<DoubleValue>)Parameters[ScalingFactorParameterName]; }
    7972        }
     73        public ValueParameter<DoubleValue> ValueToReachParameter
     74        {
     75            get { return (ValueParameter<DoubleValue>)Parameters[ValueToReachParameterName]; }
     76        }
    8077        #endregion
    8178
     
    112109            set { PopulationSizeParameter.Value = value; }
    113110        }
     111        public Double ValueToReach
     112        {
     113            get { return ValueToReachParameter.Value.Value; }
     114            set { ValueToReachParameter.Value.Value = value; }
     115        }
    114116        #endregion
    115117
     
    119121            get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
    120122            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; }
    121129        }
    122130
     
    170178            Parameters.Add(new ValueParameter<DoubleValue>(CrossoverProbabilityParameterName, "The value for crossover rate", new DoubleValue(0.88)));
    171179            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)));
    172181        }
    173182
    174183        protected override void Run(CancellationToken cancellationToken)
    175184        {
    176 
    177             // Set up the algorithm
    178             if (SetSeedRandomly) Seed = new System.Random().Next();
    179             _random.Reset(Seed);
    180185
    181186            // Set up the results display
     
    184189            Results.Add(new Result("Best Solution", new RealVector()));
    185190            Results.Add(new Result("Best Quality", new DoubleValue(double.NaN)));
     191            Results.Add(new Result("VTR", new DoubleValue(double.NaN)));
    186192            var table = new DataTable("Qualities");
    187193            table.Rows.Add(new DataRow("Best Quality"));
    188194            Results.Add(new Result("Qualities", table));
     195
    189196
    190197            //problem variables
     
    194201            var range = ub - lb;
    195202
    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++)
     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++)
    205213            {
    206                 _solutions[i] = new double[PopulationSizeParameter.Value.Value];
    207                 _mutantVectors[i] = new double[PopulationSizeParameter.Value.Value];
    208                 _trialVectors[i] = new double[PopulationSizeParameter.Value.Value];
     214                for (int j = 0; j < Problem.ProblemSize.Value; ++j)
     215                  {
     216                    populationOld[i, j] = _random.NextDouble() * range + lb;
     217                }
    209218            }
    210219
    211             //create initial population
    212             for (int i = 0; i < _solutions.Length; ++i)
     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++)
    213235            {
    214                 for (int j = 0; j < _solutions[i].Length; ++j)
    215                 {
    216                     _solutions[i][j] = _random.NextDouble() * range + lb;
     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;
    217246                }
    218247            }
    219248
    220             bestSolution = new RealVector((double[])_solutions[0].Clone());
     249            int iterations = 1;
     250
    221251            // Loop until iteration limit reached or canceled.
    222             while (evals < MaximumEvaluations && !cancellationToken.IsCancellationRequested)
     252            //todo replace with a function
     253            while (evals < MaximumEvaluations
     254                && !cancellationToken.IsCancellationRequested
     255                && bestPopulationValue > Problem.BestKnownQuality.Value + ValueToReachParameter.Value.Value)
    223256            {
    224257
    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)
     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++)
    234266                    {
    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;
     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;
    239272                    }
    240273                }
    241274
    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)
     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++)
    247280                    {
    248281                        if (_random.NextDouble() <= CrossoverProbabilityParameter.Value.Value || j == rnbr)
    249282                        {
    250                             _trialVectors[i][j] = _mutantVectors[i][j];
     283                            trialPopulation[i,j] = mutationPopulation[i,j];
    251284                        }
    252285                        else
    253286                        {
    254                             _trialVectors[i][j] = _solutions[i][j];
     287                            trialPopulation[i,j] = populationOld[i,j];
    255288                        }
    256289                    }
    257290                }
    258291
    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)
     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)
    271303                    {
    272                         _solutions[i] = (double[])_trialVectors[i].Clone();
     304                        for (int j = 0; j < Get_ith_row(populationOld, i).Length; j++)
     305                        {
     306                            populationOld[i, j] = trialPopulation[i, j];
     307                        }
    273308                    }
    274309                }
    275                 var currentBestQuality = Obj(bestSolution);
     310
    276311                //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)
     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)
    282318                    {
    283                         bestSolution = (RealVector)selectionVector.Clone();
    284                         bestSolutionQuality = quality;
     319                        bestPopulationVector = (RealVector)selectionVector.Clone();
     320                        bestPopulationValue = quality;
    285321                    }
    286322                }
     323
     324                iterations = iterations + 1;
    287325
    288326                //update the results
    289327                ResultsEvaluations = evals;
    290                 ResultsBestSolution = bestSolution;
    291                 ResultsBestQuality = bestSolutionQuality;
     328                ResultsIterations = iterations;
     329                ResultsBestSolution = bestPopulationVector;
     330                ResultsBestQuality = bestPopulationValue;
    292331
    293332                //update the results in view
    294                 if (evals % 100 == 0) ResultsQualitiesBest.Values.Add(bestSolutionQuality);
     333                if (evals % 100 == 0 ) ResultsQualitiesBest.Values.Add(bestPopulationValue);
     334                if (bestPopulationValue < Problem.BestKnownQuality.Value + ValueToReachParameter.Value.Value)
     335                {
     336                    VTRBestQuality = bestPopulationValue;
     337                }
    295338            }
    296339
     
    298341       
    299342        //evaluate the vector
    300         public double Obj(RealVector x)
    301         {
     343        public double Obj(RealVector x, int evals)
     344        {
     345            evals = evals + 1;
    302346            if(Problem.Maximization.Value)
    303347            return -Problem.Evaluator.Evaluate(x);
     
    305349            return Problem.Evaluator.Evaluate(x);
    306350        }
     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        }
    307364    }
    308365}
Note: See TracChangeset for help on using the changeset viewer.