Changeset 13849

Timestamp:

05/18/16 11:27:21 (9 years ago)

Author:

ichiriac

Message:

Constrained test function

Check for constrained test function and evaluated the constraints violations
Add to dominance comparator also constraints violations

Location:

branches/ichiriac/HeuristicLab.Algorithms.GDE3

Files:

• GDE3.cs (modified) (25 diffs)
• SolutionSet.cs (modified) (2 diffs)

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

@@ -46 +46 @@
         private readonly IRandom _random = new MersenneTwister();
         private int evals;
+        private double IGDSumm;
 
         #region ParameterNames
@@ -52 +53 @@
         private const string PopulationSizeParameterName = "PopulationSize";
         private const string ScalingFactorParameterName = "ScalingFactor";
+
         #endregion
 
@@ -104 +106 @@
         }
 
+        private double ResultsIGDMean
+        {
+            get { return ((DoubleValue)Results["IGDMeanValue"].Value).Value; }
+            set { ((DoubleValue)Results["IGDMeanValue"].Value).Value = value; }
+        }
+
+        private double ResultsIGDBest
+        {
+            get { return ((DoubleValue)Results["IGDBestValue"].Value).Value; }
+            set { ((DoubleValue)Results["IGDBestValue"].Value).Value = value; }
+        }
+
+        private double ResultsIGDWorst
+        {
+            get { return ((DoubleValue)Results["IGDWorstValue"].Value).Value; }
+            set { ((DoubleValue)Results["IGDWorstValue"].Value).Value = value; }
+        }
+
         private double ResultsInvertedGenerationalDistance
         {
@@ -136 +156 @@
             get { return ((DoubleValue)Results["GenerationalDistance"].Value).Value; }
             set { ((DoubleValue)Results["GenerationalDistance"].Value).Value = value; }
-        }
-        private int ResultsIterations
-        {
-            get { return ((IntValue)Results["Iterations"].Value).Value; }
-            set { ((IntValue)Results["Iterations"].Value).Value = value; }
         }
 
@@ -189 +204 @@
             Results.Add(new Result("GenerationalDistance", new DoubleValue(0)));
             Results.Add(new Result("HyperVolumeValue", new DoubleValue(0)));
+            Results.Add(new Result("IGDMeanValue", new DoubleValue(0)));
+            Results.Add(new Result("IGDBestValue", new DoubleValue(Int32.MaxValue)));
+            Results.Add(new Result("IGDWorstValue", new DoubleValue(0)));
+
             Results.Add(new Result("Spacing", new DoubleValue(0)));
             Results.Add(new Result("Scatterplot", typeof(IMOFrontModel)));
@@ -199 +218 @@
             List<SolutionSet> offspringPopulation;
             SolutionSet[] parent;
+            double IGDSumm = 0;
             
             //initialize population
@@ -206 +226 @@
             {
                 var m = createIndividual();
+                m.Quality = Problem.Evaluate(m.Population, _random);
+                //the test function is constrained
+                if (m.Quality.Length > Problem.Objectives)
+                {
+                    m.OverallConstrainViolation = m.Quality[Problem.Objectives];
+                } else {
+                    m.OverallConstrainViolation = 0;
+                }
                 population.Add(m);
             }
 
             this.initProgress();
-            int iterations = 1;
+            int generations = 1;
 
             while (ResultsGenerations < MaximumGenerationsParameter.Value.Value
@@ -231 +259 @@
 
                     child.Quality = Problem.Evaluate(child.Population, _random);
+
                     this.updateProgres();
+
+                    //the test function is constrained
+                    if (child.Quality.Length > Problem.Objectives)
+                    {
+                        child.OverallConstrainViolation = child.Quality[Problem.Objectives];
+                    } else {
+                        child.OverallConstrainViolation = 0;
+                    }
 
                     // Dominance test
                     int result;
-                    result = compareDomination(population[i].Quality, child.Quality);
+                    result = compareDomination(population[i], child);
+
                     if (result == -1)
                     { // Solution i dominates child
@@ -250 +288 @@
                     }
                 }
+
                 // 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++)
-                    {
-                        population.Add(front[k]);
-                    } // for
-
-                    //Decrement remain
-                    remain = remain - front.Count;
-
-                    //Obtain the next front
-                    index++;
-                    if (remain > 0)
-                    {
-                        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);
+                population = crowdingDistanceSelection(ranking);
+                generations++;
+                ResultsGenerations = generations;
+                displayResults(population);
             }
         }
@@ -306 +300 @@
         private void displayResults(List<SolutionSet> population)
         {
-            //compute the 0 front 
-            // Return the first non-dominated front
             List<SolutionSet>[] rankingFinal = computeRanking(population);
 
@@ -319 +311 @@
             }
 
+            //compute the final qualities and population
             double[][] qualitiesFinal = new double[rankingFinal[0].Count][];
+            double[][] populationFinal = new double[rankingFinal[0].Count][];
 
             for (int i = 0; i < rankingFinal[0].Count; ++i)
             {
                 qualitiesFinal[i] = new double[Problem.Objectives];
+                populationFinal[i] = new double[Problem.Objectives];
                 for (int j = 0; j < Problem.Objectives; ++j)
                 {
+                    populationFinal[i][j] = rankingFinal[0][i].Population[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];
                 }
             }
@@ -352 +337 @@
             Results["Scatterplot"].Value = new MOSolution(qualitiesFinal, populationFinal, opf, objectives);
             ResultsSpacing = Spacing.Calculate(qualitiesFinal);
+
+            if (ResultsIGDBest > ResultsInvertedGenerationalDistance) {
+                ResultsIGDBest = ResultsInvertedGenerationalDistance;
+            }
+            if (ResultsIGDWorst < ResultsInvertedGenerationalDistance)
+            {
+                ResultsIGDWorst = ResultsInvertedGenerationalDistance;
+            }
+            this.IGDSumm += ResultsInvertedGenerationalDistance;
+            ResultsIGDMean = this.IGDSumm / ResultsGenerations;
         }
 
@@ -370 +365 @@
                 {
                     candidateSolution = SolutionsList[i];
-                    flag = compareDomination(worstKnown.Quality, candidateSolution.Quality);
+                    flag = compareDomination(worstKnown, candidateSolution);
                     if (flag == -1)
                     {
@@ -395 +390 @@
 
             }
-            var m = new RealVector(v);
-            solutionObject.Population = m;
-            solutionObject.Quality = Problem.Evaluate(m, _random);
+            solutionObject.createSolution(v);
             return solutionObject;
         }
@@ -470 +463 @@
         }
 
-        private List<SolutionSet> replacement(List<SolutionSet> population, List<SolutionSet> offspringPopulation)
-        {
-            List<SolutionSet> tmpList = new List<SolutionSet>();
-            for (int i = 0; i < PopulationSizeParameter.Value.Value; i++)
-            {
-                int result;
-                result = compareDomination(population[i].Quality, offspringPopulation[i].Quality);
-                if (result == -1)
-                { // Solution i dominates child
-                    tmpList.Add(population[i]);
-                }
-                else if (result == 1)
-                { // child dominates
-                    tmpList.Add(offspringPopulation[i]);
-                }
-                else
-                { // the two solutions are non-dominated
-                    tmpList.Add(offspringPopulation[i]);
-                    tmpList.Add(population[i]);
-                }
-            }
-
-            List<SolutionSet>[] ranking = computeRanking(tmpList);
-            List<SolutionSet> finalPopulation = crowdingDistanceSelection(ranking);
-            return finalPopulation;
-        }
-
         private List<SolutionSet> crowdingDistanceSelection(List<SolutionSet>[] ranking)
         {
@@ -509 +475 @@
                 }
                 else {
-                    crowdingDistanceAssignment(ranking[rankingIndex], rankingIndex);
+                    crowdingDistanceAssignment(ranking[rankingIndex]);
                     addLastRankedSolutionToPopulation(ranking, rankingIndex, population);
                 }
@@ -519 +485 @@
         {
             List<SolutionSet> currentRankedFront = ranking[rankingIndex];
-            currentRankedFront.Sort((x, y) => x.CrowdingDistance.CompareTo(y.CrowdingDistance));
+            //descending sort and add the front with highest crowding distance to the population
+            currentRankedFront.Sort((x, y) => -x.CrowdingDistance.CompareTo(y.CrowdingDistance));
             int i = 0;
             while (population.Count < PopulationSizeParameter.Value.Value)
@@ -528 +495 @@
         }
 
-        public void crowdingDistanceAssignment(List<SolutionSet> rankingSubfront, int index)
+        public void crowdingDistanceAssignment(List<SolutionSet> rankingSubfront)
         {
             int size = rankingSubfront.Count;
@@ -556 +523 @@
 
             for (int i = 0; i < size; i++)
-                rankingSubfront[i].CrowdingDistance = 0.0;
+                front[i].CrowdingDistance = 0.0;
 
             double objetiveMaxn;
@@ -564 +531 @@
             for (int i = 0; i < Problem.Objectives; i++)
             {
-                // Sort the population by Obj n            
+                // Sort the front population by the objective i          
                 front.Sort((x, y) => x.Quality[i].CompareTo(y.Quality[i]));
                 objetiveMinn = front[0].Quality[i];
                 objetiveMaxn = front[front.Count - 1].Quality[i];
 
-                //Set de crowding distance            
+                //Set crowding distance for the current front           
                 front[0].CrowdingDistance = double.PositiveInfinity;
                 front[size - 1].CrowdingDistance = double.PositiveInfinity;
@@ -627 +594 @@
                 // Initialize the list of individuals that i dominate and the number
                 // of individuals that dominate me
-                iDominate[p] = new List<int>();
+                iDominate[p] = new List<int>(); 
                 dominateMe[p] = 0;
             }
@@ -635 +602 @@
                 for (int q = p + 1; q < tmpList.Count; q++)
                 {
-                    flagDominate = compareDomination(tmpList[p].Quality, tmpList[q].Quality);
+                    flagDominate = compareConstraintsViolation(tmpList[p], tmpList[q]);
+                    if (flagDominate == 0) { 
+                        flagDominate = compareDomination(tmpList[p], tmpList[q]);
+                    }
                     if (flagDominate == -1)
                     {
@@ -693 +663 @@
         }
 
-        private int compareDomination(double[] solution1, double[] solution2)
+        private int compareDomination(SolutionSet solution1, SolutionSet solution2)
         {
             int dominate1; // dominate1 indicates if some objective of solution1 
@@ -704 +674 @@
             int flag; //stores the result of the comparison
 
+            // Test to determine whether at least a solution violates some constraint
+            if (needToCompareViolations(solution1, solution2))
+            {
+                return compareConstraintsViolation(solution1, solution2);
+            }
+
             // Equal number of violated constraints. Applying a dominance Test then
             double value1, value2;
             for (int i = 0; i < Problem.Objectives; i++)
             {
-                value1 = solution1[i];
-                value2 = solution2[i];
+                value1 = solution1.Quality[i];
+                value2 = solution2.Quality[i];
                 if (value1 < value2)
                 {
                     flag = -1;
                 }
-                else if (value1 > value2)
+                else if (value2 < value1)
                 {
                     flag = 1;
@@ -743 +719 @@
             }
             return 1;    // solution2 dominate   
+        }
+
+        private bool needToCompareViolations(SolutionSet solution1, SolutionSet solution2)
+        {
+            bool needToCompare;
+            needToCompare = (solution1.OverallConstrainViolation < 0) || (solution2.OverallConstrainViolation < 0);
+
+            return needToCompare;
+        }
+
+        private int compareConstraintsViolation(SolutionSet solution1, SolutionSet solution2)
+        {
+            int result;
+            double overall1, overall2;
+            overall1 = solution1.OverallConstrainViolation;
+            overall2 = solution2.OverallConstrainViolation;
+
+            if ((overall1 < 0) && (overall2 < 0))
+            {
+                if (overall1 > overall2)
+                {
+                    result = -1;
+                }
+                else if (overall2 > overall1)
+                {
+                    result = 1;
+                }
+                else
+                {
+                    result = 0;
+                }
+            }
+            else if ((overall1 == 0) && (overall2 < 0))
+            {
+                result = -1;
+            }
+            else if ((overall1 < 0) && (overall2 == 0))
+            {
+                result = 1;
+            }
+            else
+            {
+                result = 0;
+            }
+            return result;
         }
     }

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

@@ -12 +12 @@
         private double crowdingDistance;
         private double rank;
+        private double overallConstrainViolation;
+        public int populationSize;
+
+        //constructor set size equal with population size
+        public SolutionSet(int populationSize)
+        {
+            this.populationSize = populationSize;
+        }
 
         public double CrowdingDistance
@@ -37 +45 @@
         }
 
-
-        public int populationSize;
-        public SolutionSet(int populationSize) {
-            this.populationSize = populationSize;
+        public double OverallConstrainViolation
+        {
+            get { return overallConstrainViolation; }
+            set { overallConstrainViolation = value; }
         }