Changeset 13756

Timestamp:

04/13/16 11:47:30 (8 years ago)

Author:

ichiriac

Message:

Add HyperVolume and Spacing calculators

Display hypervolume and spacing in the results

Location:

branches/ichiriac/HeuristicLab.Algorithms.GDE3

Files:

• GDE3.cs (modified) (22 diffs)
• HeuristicLab.Algorithms.GDE3.csproj (modified) (1 diff)

branches/ichiriac/HeuristicLab.Algorithms.GDE3/GDE3.cs

@@ -16 +16 @@
 using HeuristicLab.Random;
 using System.Threading;
+using HeuristicLab.Algorithms.GDE3;
 
 namespace HeuristicLab.Algoritms.GDE3
@@ -23 +24 @@
     [StorableClass]
     [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 400)]
-    public class GDE3 : BasicAlgorithm 
+    public class GDE3 : BasicAlgorithm
     {
-        public Func<IEnumerable<double>, double> Evaluation;
-        private enum DominationResult { Dominates, IsDominated, IsNonDominated };
-        IComparer<RealVector> dominance;
-        public double[] ReferencePoint(int objectives)
-        {
-            return new double[] { 11, 11 };
-        }
-
         public override Type ProblemType
         {
             get { return typeof(MultiObjectiveTestFunctionProblem); }
         }
-         public new MultiObjectiveTestFunctionProblem Problem
+        public new MultiObjectiveTestFunctionProblem Problem
         {
             get { return (MultiObjectiveTestFunctionProblem)base.Problem; }
@@ -55 +48 @@
 
         #region ParameterNames
-        private const string MaximumEvaluationsParameterName = "Maximum Evaluations";
+        private const string MaximumGenerationsParameterName = "Maximum Generations";
         private const string CrossoverProbabilityParameterName = "CrossoverProbability";
         private const string PopulationSizeParameterName = "PopulationSize";
@@ -62 +55 @@
 
         #region ParameterProperties
-        public IFixedValueParameter<IntValue> MaximumEvaluationsParameter
-        {
-            get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; }
+        public IFixedValueParameter<IntValue> MaximumGenerationsParameter
+        {
+            get { return (IFixedValueParameter<IntValue>)Parameters[MaximumGenerationsParameterName]; }
         }
         private ValueParameter<IntValue> PopulationSizeParameter
@@ -83 +76 @@
         public int MaximumEvaluations
         {
-            get { return MaximumEvaluationsParameter.Value.Value; }
-            set { MaximumEvaluationsParameter.Value.Value = value; }
+            get { return MaximumGenerationsParameter.Value.Value; }
+            set { MaximumGenerationsParameter.Value.Value = value; }
         }
 
@@ -111 +104 @@
         }
 
-        private double ResultsGenerationalDistance
+        private double ResultsInvertedGenerationalDistance
         {
             get { return ((DoubleValue)Results["InvertedGenerationalDistance"].Value).Value; }
@@ -119 +112 @@
         private double ResultsHypervolume
         {
-            get { return ((DoubleValue)Results["HipervolumeValue"].Value).Value; }
-            set { ((DoubleValue)Results["HipervolumeValue"].Value).Value = value; }
+            get { return ((DoubleValue)Results["HyperVolumeValue"].Value).Value; }
+            set { ((DoubleValue)Results["HyperVolumeValue"].Value).Value = value; }
         }
 
@@ -134 +127 @@
             set { ((IntValue)Results["Evaluations"].Value).Value = value; }
         }
+        private int ResultsGenerations
+        {
+            get { return ((IntValue)Results["Generations"].Value).Value; }
+            set { ((IntValue)Results["Generations"].Value).Value = value; }
+        }
+        private double ResultsGenerationalDistance
+        {
+            get { return ((DoubleValue)Results["GenerationalDistance"].Value).Value; }
+            set { ((DoubleValue)Results["GenerationalDistance"].Value).Value = value; }
+        }
         private int ResultsIterations
         {
@@ -140 +143 @@
         }
 
-        private DataTable ResultsQualities
-        {
-            get { return ((DataTable)Results["Qualities"].Value); }
-        }
-        private DataRow ResultsQualitiesBest
-        {
-            get { return ResultsQualities.Rows["Best Quality"]; }
+        private double ResultsSpacing
+        {
+            get { return ((DoubleValue)Results["Spacing"].Value).Value; }
+            set { ((DoubleValue)Results["Spacing"].Value).Value = value; }
+        }
+
+        private double ResultsCrowding
+        {
+            get { return ((DoubleValue)Results["Crowding"].Value).Value; }
+            set { ((DoubleValue)Results["Crowding"].Value).Value = value; }
         }
 
         #endregion
-
-        [Storable]
-        private RankBasedParetoFrontAnalyzer paretoFrontAnalyzer;
 
         [StorableConstructor]
@@ -160 +163 @@
           : base(original, cloner)
         {
-            paretoFrontAnalyzer = (RankBasedParetoFrontAnalyzer)cloner.Clone(original.paretoFrontAnalyzer);
         }
 
@@ -170 +172 @@
         public GDE3()
         {
-            Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(Int32.MaxValue)));
+            Parameters.Add(new FixedValueParameter<IntValue>(MaximumGenerationsParameterName, "", new IntValue(1000)));
             Parameters.Add(new ValueParameter<IntValue>(PopulationSizeParameterName, "The size of the population of solutions.", new IntValue(100)));
             Parameters.Add(new ValueParameter<DoubleValue>(CrossoverProbabilityParameterName, "The value for crossover rate", new DoubleValue(0.5)));
@@ -180 +182 @@
         {
             // Set up the results display
-            Results.Add(new Result("Iterations", new IntValue(0)));
+            Results.Add(new Result("Generations", new IntValue(0)));
             Results.Add(new Result("Evaluations", new IntValue(0)));
             Results.Add(new Result("Best Front", new DoubleMatrix()));
+            Results.Add(new Result("Crowding", new DoubleValue(0)));
             Results.Add(new Result("InvertedGenerationalDistance", new DoubleValue(0)));
-            Results.Add(new Result("HipervolumeValue", new DoubleValue(0)));
+            Results.Add(new Result("GenerationalDistance", new DoubleValue(0)));
+            Results.Add(new Result("HyperVolumeValue", new DoubleValue(0)));
+            Results.Add(new Result("Spacing", new DoubleValue(0)));
             Results.Add(new Result("Scatterplot", typeof(IMOFrontModel)));
             var table = new DataTable("Qualities");
@@ -190 +195 @@
             Results.Add(new Result("Qualities", table));
 
-            //create initial population
-            var population = new List<SolutionSet>(PopulationSizeParameter.Value.Value);
-            var offspringPopulation = new List<SolutionSet>(PopulationSizeParameter.Value.Value);
-            var matingPopulation = new List<SolutionSet>();
+            //setup the variables
+            List<SolutionSet> population;
+            List<SolutionSet> offspringPopulation;
+            SolutionSet[] parent;
+            
+            //initialize population
+            population = new List<SolutionSet>(PopulationSizeParameter.Value.Value);
 
             for (int i = 0; i < PopulationSizeParameter.Value.Value; ++i)
@@ -199 +207 @@
                 var m = createIndividual();
                 population.Add(m);
-                var n = createEmptyIndividual();
-                offspringPopulation.Add(n);
             }
 
@@ -206 +212 @@
             int iterations = 1;
 
-            while (ResultsEvaluations < MaximumEvaluations
+            while (ResultsGenerations < MaximumGenerationsParameter.Value.Value
                && !cancellationToken.IsCancellationRequested)
             {
-                matingPopulation = selection(population);
-                offspringPopulation = reproduction(matingPopulation, population, offspringPopulation);
-
-                population = replacement(population, offspringPopulation);
-
-                double[][] qualitiesFinal = new double[PopulationSizeParameter.Value.Value][];
-
-                for (int i = 0; i < PopulationSizeParameter.Value.Value; ++i)
-                {
-                    qualitiesFinal[i] = new double[Problem.Objectives];
-                    for (int j = 0; j < Problem.Objectives; ++j)
+                var populationSize = PopulationSizeParameter.Value.Value;
+
+                // Create the offSpring solutionSet
+                offspringPopulation = new List<SolutionSet>(PopulationSizeParameter.Value.Value * 2);
+
+                for (int i = 0; i < populationSize; i++)
+                {
+                    // Obtain parents. Two parameters are required: the population and the 
+                    //                 index of the current individual
+                    parent = selection(population, i);
+
+                    SolutionSet child;
+                    // Crossover. The parameters are the current individual and the index of the array of parents 
+                    child = reproduction(population[i], parent);
+
+                    child.Quality = Problem.Evaluate(child.Population, _random);
+                    this.updateProgres();
+
+                    // Dominance test
+                    int result;
+                    result = compareDomination(population[i].Quality, child.Quality);
+                    if (result == -1)
+                    { // Solution i dominates child
+                        offspringPopulation.Add(population[i]);
+                    }
+                    else if (result == 1)
+                    { // child dominates
+                        offspringPopulation.Add(child);
+                    }
+                    else
+                    { // the two solutions are non-dominated
+                        offspringPopulation.Add(child);
+                        offspringPopulation.Add(population[i]);
+                    }
+                }
+                // Ranking the offspring population
+                List<SolutionSet>[] ranking = computeRanking(offspringPopulation);
+
+                int remain = populationSize;
+                int index = 0;
+                population.Clear();
+                List<SolutionSet> front = null;
+
+                // Obtain the next front
+                front = ranking[index];
+
+                while ((remain > 0) && (remain >= front.Count))
+                {
+                    //Assign crowding distance to individuals
+                    crowdingDistanceAssignment(front, index);
+                    //Add the individuals of this front
+                    for (int k = 0; k < front.Count; k++)
                     {
-                        qualitiesFinal[i][j] = population[i].Quality[j];
-                    }
-                }
-
-                double[][] populationFinal = new double[PopulationSizeParameter.Value.Value][];
-
-                for (int i = 0; i < PopulationSizeParameter.Value.Value; ++i)
-                {
-                    populationFinal[i] = new double[Problem.ProblemSize];
-                    for (int j = 0; j < Problem.ProblemSize; ++j)
+                        population.Add(front[k]);
+                    } // for
+
+                    //Decrement remain
+                    remain = remain - front.Count;
+
+                    //Obtain the next front
+                    index++;
+                    if (remain > 0)
                     {
-                        populationFinal[i][j] = population[i].Population[j];
-                    }
-                }
-
-                int objectives = Problem.Objectives;
-                var optimalfront = Problem.TestFunction.OptimalParetoFront(objectives);
-
-                IEnumerable<double[]> en = qualitiesFinal;
-
-                double[][] opf = new double[0][];
-                if (optimalfront != null)
-                {
-                    opf = optimalfront.Select(s => s.ToArray()).ToArray();
-                }
-
-                iterations = iterations + 1;
-
-                IEnumerable<double[]> front = NonDominatedSelect.selectNonDominatedVectors(qualitiesFinal, Problem.TestFunction.Maximization(objectives), true);
-                //update the results
-                ResultsEvaluations = evals;
-                ResultsIterations = iterations;
-                ResultsBestFront = new DoubleMatrix(MultiObjectiveTestFunctionProblem.To2D(qualitiesFinal));
-                ResultsGenerationalDistance = InvertedGenerationalDistance.Calculate(en, optimalfront, 1);
-                ResultsHypervolume = Hypervolume.Calculate(front, ReferencePoint(objectives), Problem.TestFunction.Maximization(objectives));
-
-                Results["Scatterplot"].Value = new MOSolution(qualitiesFinal, populationFinal, opf, objectives);
-            }
-        }
-       
+                        front = ranking[index];
+                    }
+                }
+
+                // remain is less than front(index).size, insert only the best one
+                if (remain > 0)
+                {  // front contains individuals to insert
+                    while (front.Count > remain)
+                    {
+                        crowdingDistanceAssignment(front, index);
+                        int indx = getWorstIndex(front);
+                        front.RemoveAt(indx);
+                    }
+                    for (int k = 0; k < front.Count; k++)
+                    {
+                        population.Add(front[k]);
+                    }
+
+                    remain = 0;
+                }
+                iterations++;
+                ResultsGenerations = iterations;
+                displayResults(front);
+            }
+        }
+
+        private void displayResults(List<SolutionSet> population)
+        {
+            //compute the 0 front 
+            // Return the first non-dominated front
+            List<SolutionSet>[] rankingFinal = computeRanking(population);
+
+            int objectives = Problem.Objectives;
+            var optimalfront = Problem.TestFunction.OptimalParetoFront(objectives);
+
+            double[][] opf = new double[0][];
+            if (optimalfront != null)
+            {
+                opf = optimalfront.Select(s => s.ToArray()).ToArray();
+            }
+
+            double[][] qualitiesFinal = new double[rankingFinal[0].Count][];
+
+            for (int i = 0; i < rankingFinal[0].Count; ++i)
+            {
+                qualitiesFinal[i] = new double[Problem.Objectives];
+                for (int j = 0; j < Problem.Objectives; ++j)
+                {
+                    qualitiesFinal[i][j] = rankingFinal[0][i].Quality[j];
+                }
+            }
+
+            double[][] populationFinal = new double[rankingFinal[0].Count][];
+
+            for (int i = 0; i < rankingFinal[0].Count; ++i)
+            {
+                populationFinal[i] = new double[Problem.ProblemSize];
+                for (int j = 0; j < Problem.ProblemSize; ++j)
+                {
+                    populationFinal[i][j] = rankingFinal[0][i].Population[j];
+                }
+            }
+            IEnumerable<double[]> en = qualitiesFinal;
+            IEnumerable<double[]> frontVectors = NonDominatedSelect.selectNonDominatedVectors(qualitiesFinal, Problem.TestFunction.Maximization(objectives), true);
+            //update the results
+
+            ResultsEvaluations = this.evals;
+            ResultsBestFront = new DoubleMatrix(MultiObjectiveTestFunctionProblem.To2D(qualitiesFinal));
+            ResultsCrowding = Crowding.Calculate(qualitiesFinal, Problem.TestFunction.Bounds(objectives));
+            ResultsInvertedGenerationalDistance = InvertedGenerationalDistance.Calculate(en, optimalfront, 1);
+            ResultsHypervolume = Hypervolume.Calculate(frontVectors, Problem.TestFunction.ReferencePoint(objectives), Problem.TestFunction.Maximization(objectives));
+            ResultsGenerationalDistance = GenerationalDistance.Calculate(qualitiesFinal, optimalfront, 1);
+            Results["Scatterplot"].Value = new MOSolution(qualitiesFinal, populationFinal, opf, objectives);
+            ResultsSpacing = Spacing.Calculate(qualitiesFinal);
+        }
+
+        private int getWorstIndex(List<SolutionSet> SolutionsList)
+        {
+            int result = 0;
+
+            if ((SolutionsList == null) || SolutionsList.Count == 0)
+            {
+                result = 0;
+            }
+            else
+            {
+                SolutionSet worstKnown = SolutionsList[0],
+                            candidateSolution;
+                int flag;
+                for (int i = 1; i < SolutionsList.Count; i++)
+                {
+                    candidateSolution = SolutionsList[i];
+                    flag = compareDomination(worstKnown.Quality, candidateSolution.Quality);
+                    if (flag == -1)
+                    {
+                        result = i;
+                        worstKnown = candidateSolution;
+                    }
+                }
+            }
+            return result;
+        }
+
         protected SolutionSet createIndividual()
         {
@@ -296 +416 @@
         protected void updateProgres()
         {
-            this.evals += PopulationSizeParameter.Value.Value;
-        }
-
-        protected List<SolutionSet> selection(List<SolutionSet> population)
-        {
-            List<SolutionSet> parents = new List<SolutionSet>();
-            for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
-            {
-                int r0, r1, r2;
-                //assure the selected vectors r0, r1 and r2 are different
-                do
-                {
-                    r0 = _random.Next(0, PopulationSizeParameter.Value.Value);
-                } while (r0 == i);
-                do
-                {
-                    r1 = _random.Next(0, PopulationSizeParameter.Value.Value);
-                } while (r1 == i || r1 == r0);
-                do
-                {
-                    r2 = _random.Next(0, PopulationSizeParameter.Value.Value);
-                } while (r2 == i || r2 == r0 || r2 == r1);
-
-                parents.Add(population[r0]);
-                parents.Add(population[r1]);
-                parents.Add(population[r2]);
-            }
+            this.evals++;
+        }
+
+        protected SolutionSet[] selection(List<SolutionSet> population, int i)
+        {
+            SolutionSet[] parents = new SolutionSet[3];
+            int r0, r1, r2;
+            //assure the selected vectors r0, r1 and r2 are different
+            do
+            {
+                r0 = _random.Next(0, PopulationSizeParameter.Value.Value);
+            } while (r0 == i);
+            do
+            {
+                r1 = _random.Next(0, PopulationSizeParameter.Value.Value);
+            } while (r1 == i || r1 == r0);
+            do
+            {
+                r2 = _random.Next(0, PopulationSizeParameter.Value.Value);
+            } while (r2 == i || r2 == r0 || r2 == r1);
+
+            parents[0] = population[r0];
+            parents[1] = population[r1];
+            parents[2] = population[r2];
+
             return parents;
         }
 
-        protected List<SolutionSet> reproduction(List<SolutionSet> matingPopulation, List<SolutionSet> parentPopulation, List<SolutionSet> offspringPopulation)
-        {
-            for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
-            {
-                List<SolutionSet> parents = new List<SolutionSet>(3);
-                for (int j = 0; j < 3; j++) {
-                    parents.Add(matingPopulation[0]);
-                    matingPopulation.RemoveAt(0);
-                }
-
-                double rnbr = _random.Next(0, Problem.ProblemSize);
-                for (int m = 0; m < Problem.ProblemSize; m++)
-                {
-                    if (_random.NextDouble() < CrossoverProbabilityParameter.Value.Value || m == rnbr)
-                    {
-                        offspringPopulation[i].Population[m] = parents[2].Population[m] +
-                            ScalingFactorParameter.Value.Value * (parents[1].Population[m] - parents[2].Population[0]);
-                        //check the problem upper and lower bounds
-                        if (offspringPopulation[i].Population[m] > Problem.Bounds[0, 1]) offspringPopulation[i].Population[m] = Problem.Bounds[0, 1];
-                        if (offspringPopulation[i].Population[m] < Problem.Bounds[0, 0]) offspringPopulation[i].Population[m] = Problem.Bounds[0, 0];
-                    }
-                    else
-                    {
-                        offspringPopulation[i].Population[m] = parentPopulation[i].Population[m]; // check again
-                    }
-                }
-                offspringPopulation[i].Quality = Problem.Evaluate(offspringPopulation[i].Population, _random);
-            }
-            this.updateProgres();
-            return offspringPopulation;
+        protected SolutionSet reproduction(SolutionSet parent, SolutionSet[] parentsSolutions)
+        {
+            var individual = createEmptyIndividual();
+            double rnbr = _random.Next(0, Problem.ProblemSize);
+            for (int m = 0; m < Problem.ProblemSize; m++)
+            {
+                if (_random.NextDouble() < CrossoverProbabilityParameter.Value.Value || m == rnbr)
+                {
+                    double value;
+                    value = parentsSolutions[2].Population[m] +
+                        ScalingFactorParameter.Value.Value * (parentsSolutions[0].Population[m] - parentsSolutions[1].Population[m]);
+                    //check the problem upper and lower bounds
+                    if (value > Problem.Bounds[0, 1]) value = Problem.Bounds[0, 1];
+                    if (value < Problem.Bounds[0, 0]) value = Problem.Bounds[0, 0];
+                    individual.Population[m] = value;
+                }
+                else
+                {
+                    double value;
+                    value = parent.Population[m];
+                    individual.Population[m] = value;
+                }
+            }
+            return individual;
         }
 
@@ -380 +492 @@
             }
 
-            List<SolutionSet>[]ranking = computeRanking(tmpList);
+            List<SolutionSet>[] ranking = computeRanking(tmpList);
             List<SolutionSet> finalPopulation = crowdingDistanceSelection(ranking);
             return finalPopulation;
@@ -391 +503 @@
             while (populationIsNotFull(population))
             {
-                if (subFrontFillsIntoThePopulation(ranking, rankingIndex, population)){
+                if (subFrontFillsIntoThePopulation(ranking, rankingIndex, population))
+                {
                     addRankedSolutionToPopulation(ranking, rankingIndex, population);
                     rankingIndex++;
-                } else {
+                }
+                else {
                     crowdingDistanceAssignment(ranking[rankingIndex], rankingIndex);
                     addLastRankedSolutionToPopulation(ranking, rankingIndex, population);
@@ -448 +562 @@
             double distance;
 
-            for (int i = 0; i < Problem.Objectives ; i++)
+            for (int i = 0; i < Problem.Objectives; i++)
             {
                 // Sort the population by Obj n            
@@ -456 +570 @@
 
                 //Set de crowding distance            
-                front[0].CrowdingDistance = double.PositiveInfinity; 
+                front[0].CrowdingDistance = double.PositiveInfinity;
                 front[size - 1].CrowdingDistance = double.PositiveInfinity;
 
@@ -471 +585 @@
         private void addRankedSolutionToPopulation(List<SolutionSet>[] ranking, int rankingIndex, List<SolutionSet> population)
         {
-            foreach(SolutionSet solution in ranking[rankingIndex])
+            foreach (SolutionSet solution in ranking[rankingIndex])
             {
                 population.Add(solution);
@@ -497 +611 @@
             // front[i] contains the list of individuals belonging to the front i
             List<int>[] front = new List<int>[tmpList.Count + 1];
-            int[] solutionsRanks = new int[tmpList.Count];
 
             // flagDominate is an auxiliar encodings.variable

branches/ichiriac/HeuristicLab.Algorithms.GDE3/HeuristicLab.Algorithms.GDE3.csproj

@@ -114 +114 @@
   <ItemGroup>
     <Compile Include="GDE3.cs" />
+    <Compile Include="GenerationalDistanceCalculator.cs" />
     <Compile Include="Plugin.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />