Changeset 13674 for branches/ichiriac/HeuristicLab.Algorithms.DifferentialEvolution

Timestamp:

03/09/16 16:01:34 (9 years ago)

Author:

ichiriac

Message:

Improve calculation of evaluations

Save the best value less that "ValueToReach"

File:

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

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

@@ -24 +24 @@
         public Func<IEnumerable<double>, double> Evaluation;
 
-
         public override Type ProblemType
         {
@@ -44 +43 @@
         private const string PopulationSizeParameterName = "PopulationSize";
         private const string ScalingFactorParameterName = "ScalingFactor";
-
-        RealVector bestSolution = null;
-        double bestSolutionQuality = double.PositiveInfinity;
-        RealVector trialVector = null;
-        RealVector selectionVector = null;
-
-
+        private const string ValueToReachParameterName = "ValueToReach";
         #endregion
 
@@ -78 +71 @@
             get { return (ValueParameter<DoubleValue>)Parameters[ScalingFactorParameterName]; }
         }
+        public ValueParameter<DoubleValue> ValueToReachParameter
+        {
+            get { return (ValueParameter<DoubleValue>)Parameters[ValueToReachParameterName]; }
+        }
         #endregion
 
@@ -112 +109 @@
             set { PopulationSizeParameter.Value = value; }
         }
+        public Double ValueToReach
+        {
+            get { return ValueToReachParameter.Value.Value; }
+            set { ValueToReachParameter.Value.Value = value; }
+        }
         #endregion
 
@@ -119 +121 @@
             get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
             set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }
+        }
+
+        private double VTRBestQuality
+        {
+            get { return ((DoubleValue)Results["VTR"].Value).Value; }
+            set { ((DoubleValue)Results["VTR"].Value).Value = value; }
         }
 
@@ -170 +178 @@
             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)));
+            Parameters.Add(new ValueParameter<DoubleValue>(ValueToReachParameterName, "Value to reach (VTR) parameter", new DoubleValue(0.000001)));
         }
 
         protected override void Run(CancellationToken cancellationToken)
         {
-
-            // Set up the algorithm
-            if (SetSeedRandomly) Seed = new System.Random().Next();
-            _random.Reset(Seed);
 
             // Set up the results display
@@ -184 +189 @@
             Results.Add(new Result("Best Solution", new RealVector()));
             Results.Add(new Result("Best Quality", new DoubleValue(double.NaN)));
+            Results.Add(new Result("VTR", new DoubleValue(double.NaN)));
             var table = new DataTable("Qualities");
             table.Rows.Add(new DataRow("Best Quality"));
             Results.Add(new Result("Qualities", table));
+
 
             //problem variables
@@ -194 +201 @@
             var range = ub - lb;
 
-            int evals = 0;
-
-
-            //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++)
+            double[,] populationOld = new double[PopulationSizeParameter.Value.Value, Problem.ProblemSize.Value];
+            double[,] mutationPopulation = new double[PopulationSizeParameter.Value.Value, Problem.ProblemSize.Value];
+            double[,] trialPopulation = new double[PopulationSizeParameter.Value.Value, Problem.ProblemSize.Value];
+            double[] bestPopulation = new double[Problem.ProblemSize.Value];
+            double[] bestPopulationIteration = new double[Problem.ProblemSize.Value];
+            int evals = 0; // number of function evaluations
+
+            //create initial population
+            //population is a matrix of size PopulationSize*ProblemSize
+            for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
             {
-                _solutions[i] = new double[PopulationSizeParameter.Value.Value];
-                _mutantVectors[i] = new double[PopulationSizeParameter.Value.Value];
-                _trialVectors[i] = new double[PopulationSizeParameter.Value.Value];
+                for (int j = 0; j < Problem.ProblemSize.Value; ++j)
+                  {
+                    populationOld[i, j] = _random.NextDouble() * range + lb;
+                }
             }
 
-            //create initial population
-            for (int i = 0; i < _solutions.Length; ++i)
+            //evaluate the best member after the intialiazation
+            //the idea is to select first member and after that to check the others members from the population
+
+            int best_index = 0;
+            double[] populationRow = new double[Problem.ProblemSize.Value];
+
+            bestPopulation = Get_ith_row(populationOld, best_index);
+            RealVector bestPopulationVector = new RealVector(bestPopulation);
+            double bestPopulationValue = Obj(bestPopulationVector, evals);
+            RealVector selectionVector;
+            RealVector trialVector;
+            double qtrial;
+
+
+            for (var i = 0; i < PopulationSizeParameter.Value.Value; i++)
             {
-                for (int j = 0; j < _solutions[i].Length; ++j)
-                {
-                    _solutions[i][j] = _random.NextDouble() * range + lb;
+                populationRow = Get_ith_row(populationOld, i);
+                trialVector = new RealVector(populationRow);
+
+                qtrial = Obj(trialVector, evals);
+
+                if (qtrial > bestPopulationValue)
+                {
+                    bestPopulationVector = new RealVector(populationRow);
+                    bestPopulationValue = Obj(bestPopulationVector, evals);
+                    best_index = i;
                 }
             }
 
-            bestSolution = new RealVector((double[])_solutions[0].Clone());
+            int iterations = 1;
+
             // Loop until iteration limit reached or canceled.
-            while (evals < MaximumEvaluations && !cancellationToken.IsCancellationRequested)
+            //todo replace with a function
+            while (evals < MaximumEvaluations 
+                && !cancellationToken.IsCancellationRequested 
+                && bestPopulationValue > Problem.BestKnownQuality.Value + ValueToReachParameter.Value.Value)
             {
 
-                evals++;
-                //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)
+                //mutation DE/rand/1/bin; classic DE
+                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
+                {
+                    int r1 = _random.Next(0, PopulationSizeParameter.Value.Value),
+                        r2 = _random.Next(0, PopulationSizeParameter.Value.Value),
+                        r3 = _random.Next(0, PopulationSizeParameter.Value.Value);
+
+                    for (int j = 0; j < Get_ith_row(mutationPopulation, 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;
+                        mutationPopulation[i,j] = populationOld[r1,j] +
+                            ScalingFactorParameter.Value.Value * (populationOld[r2,j] - populationOld[r3,j]);
+                        //check the problem upper and lower bounds
+                        if (mutationPopulation[i,j] > ub) mutationPopulation[i,j] = ub;
+                        if (mutationPopulation[i,j] < lb) mutationPopulation[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)
+                //uniform crossover
+                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
+                {
+                    double rnbr = Math.Floor(_random.NextDouble() * Problem.ProblemSize.Value);
+                    for (int j = 0; j < Get_ith_row(mutationPopulation, i).Length; j++)
                     {
                         if (_random.NextDouble() <= CrossoverProbabilityParameter.Value.Value || j == rnbr)
                         {
-                            _trialVectors[i][j] = _mutantVectors[i][j];
+                            trialPopulation[i,j] = mutationPopulation[i,j];
                         }
                         else
                         {
-                            _trialVectors[i][j] = _solutions[i][j];
+                            trialPopulation[i,j] = populationOld[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)
+                //One-to-One Survivor Selection
+                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
+                {
+                    selectionVector = new RealVector(Get_ith_row(populationOld, i));
+                    trialVector = new RealVector(Get_ith_row(trialPopulation, i));
+
+                    var selectionEval = Obj(selectionVector, evals);
+                    var trailEval = Obj(trialVector, evals);
+
+
+                    if (trailEval < selectionEval)
                     {
-                        _solutions[i] = (double[])_trialVectors[i].Clone();
+                        for (int j = 0; j < Get_ith_row(populationOld, i).Length; j++)
+                        {
+                            populationOld[i, j] = trialPopulation[i, j];
+                        }
                     }
                 }
-                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)
+                for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
+                {
+                    evals = evals + 1;
+                    selectionVector = new RealVector(Get_ith_row(populationOld, i));
+                    var quality = Obj(selectionVector, evals);
+                    if (quality < bestPopulationValue)
                     {
-                        bestSolution = (RealVector)selectionVector.Clone();
-                        bestSolutionQuality = quality;
+                        bestPopulationVector = (RealVector)selectionVector.Clone();
+                        bestPopulationValue = quality;
                     }
                 }
+
+                iterations = iterations + 1;
 
                 //update the results
                 ResultsEvaluations = evals;
-                ResultsBestSolution = bestSolution;
-                ResultsBestQuality = bestSolutionQuality; 
+                ResultsIterations = iterations;
+                ResultsBestSolution = bestPopulationVector;
+                ResultsBestQuality = bestPopulationValue; 
 
                 //update the results in view
-                if (evals % 100 == 0) ResultsQualitiesBest.Values.Add(bestSolutionQuality);
+                if (evals % 100 == 0 ) ResultsQualitiesBest.Values.Add(bestPopulationValue);
+                if (bestPopulationValue < Problem.BestKnownQuality.Value + ValueToReachParameter.Value.Value)
+                {
+                    VTRBestQuality = bestPopulationValue;
+                }
             }
 
@@ -298 +341 @@
         
         //evaluate the vector
-        public double Obj(RealVector x)
-        {
+        public double Obj(RealVector x, int evals)
+        {
+            evals = evals + 1;
             if(Problem.Maximization.Value)
             return -Problem.Evaluator.Evaluate(x);
@@ -305 +349 @@
             return Problem.Evaluator.Evaluate(x);
         }
+
+        // Get ith row from the matrix
+        public double[] Get_ith_row(double[,] Mat, int i)
+        {
+            double[] tmp = new double[Mat.GetUpperBound(1) + 1];
+
+            for (int j = 0; j <= Mat.GetUpperBound(1); j++)
+            {
+                tmp[j] = Mat[i, j];
+            }
+
+            return tmp;
+        }
     }
 }