Changeset 17230

Timestamp:

09/03/19 15:50:35 (5 years ago)

Author:

abeham

Message:

#2521: add multi-objective analysis to all multi-objective encoding-base problems

Location:

branches/2521_ProblemRefactoring

Files:

• HeuristicLab.Analysis.Views/3.3/ParetoFrontScatterPlotViewOfT.cs (modified) (1 diff)
• HeuristicLab.Analysis/3.3/MultiObjective/ParetoFrontScatterPlot.cs (modified) (2 diffs)
• HeuristicLab.Encodings.BinaryVectorEncoding/3.3/BinaryVectorMultiObjectiveProblem.cs (modified) (1 diff)
• HeuristicLab.Encodings.IntegerVectorEncoding/3.3/IntegerVectorMultiObjectiveProblem.cs (modified) (1 diff)
• HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkageMultiObjectiveProblem.cs (modified) (1 diff)
• HeuristicLab.Encodings.PermutationEncoding/3.3/PermutationMultiObjectiveProblem.cs (modified) (1 diff)
• HeuristicLab.Encodings.RealVectorEncoding/3.3/RealVectorMultiObjectiveProblem.cs (modified) (1 diff)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeMultiObjectiveProblem.cs (modified) (2 diffs)
• HeuristicLab.Optimization/3.3/MultiObjective/DominationCalculator.cs (modified) (2 diffs)
• HeuristicLab.Problems.TestFunctions.MultiObjective/3.3/Analyzers/ScatterPlotAnalyzer.cs (modified) (1 diff)

branches/2521_ProblemRefactoring/HeuristicLab.Analysis.Views/3.3/ParetoFrontScatterPlotViewOfT.cs

@@ -177 +177 @@
     }
 
-    private static Point2D<double>[] CreatePoints(IList<double[]> front, T[] solutions, int xDimIndex, int yDimIndex) {
+    private static Point2D<double>[] CreatePoints(IReadOnlyList<double[]> front, T[] solutions, int xDimIndex, int yDimIndex) {
       if (front == null || front.Count == 0) return new Point2D<double>[0];
       

branches/2521_ProblemRefactoring/HeuristicLab.Analysis/3.3/MultiObjective/ParetoFrontScatterPlot.cs

@@ -44 +44 @@
 
     [Storable]
-    private IList<double[][]> fronts;
-    public IList<double[][]> Fronts {
+    private IReadOnlyList<double[][]> fronts;
+    public IReadOnlyList<double[][]> Fronts {
       get { return fronts; }
     }
 
     [Storable]
-    private IList<T[]> items;
-    public IList<T[]> Items {
+    private IReadOnlyList<T[]> items;
+    public IReadOnlyList<T[]> Items {
       get { return items; }
     }
 
     [Storable]
-    private IList<double[]> bestKnownFront;
-    public IList<double[]> BestKnownFront {
+    private IReadOnlyList<double[]> bestKnownFront;
+    public IReadOnlyList<double[]> BestKnownFront {
       get { return bestKnownFront; }
     }
@@ -64 +64 @@
     protected ParetoFrontScatterPlot(StorableConstructorFlag _) : base(_) { }
     public ParetoFrontScatterPlot() { }
-    public ParetoFrontScatterPlot(IList<double[][]> qualities, IList<T[]> items, IList<double[]> paretoFront, int objectives) {
+    /// <summary>
+    /// Provides the data for displaying a multi-objective population in a scatter plot.
+    /// </summary>
+    /// <param name="items">The solutions grouped by pareto front (first is best).</param>
+    /// <param name="qualities">The objective vectors grouped by pareto front (first is best).</param>
+    /// <param name="objectives">The number of objectives.</param>
+    /// <param name="bestKnownParetoFront">Optional, the best known front in objective space.</param>
+    public ParetoFrontScatterPlot(IReadOnlyList<T[]> items, IReadOnlyList<double[][]> qualities, int objectives, IReadOnlyList<double[]> bestKnownParetoFront = null)
+    {
       this.fronts = qualities;
       this.items = items;
-      this.bestKnownFront = paretoFront;
+      this.bestKnownFront = bestKnownParetoFront;
       this.objectives = objectives;
+    }
+    /// <summary>
+    /// Provides the data for displaying a multi-objective population in a scatter plot.
+    /// </summary>
+    /// <param name="fronts">The fronts (first is best) with the indices of the solutions and qualities.</param>
+    /// <param name="items">The solutions.</param>
+    /// <param name="qualities">The objective vectors for each solution.</param>
+    /// <param name="objectives">The number of objectives.</param>
+    /// <param name="bestKnownParetoFront">Optional, the best known front in objective space.</param>
+    public ParetoFrontScatterPlot(List<List<int>> fronts, IReadOnlyList<T> items, IReadOnlyList<double[]> qualities, int objectives, IReadOnlyList<double[]> bestKnownParetoFront = null)
+    {
+      this.fronts = fronts.Select(x => x.Select(y => qualities[y]).ToArray()).ToArray();
+      this.items = fronts.Select(x => x.Select(y => items[y]).ToArray()).ToArray();
+      this.bestKnownFront = bestKnownParetoFront;
+      this.objectives = objectives;
+
     }
     protected ParetoFrontScatterPlot(ParetoFrontScatterPlot<T> original, Cloner cloner)

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/BinaryVectorMultiObjectiveProblem.cs

@@ -61 +61 @@
     public override void Analyze(BinaryVector[] individuals, double[][] qualities, ResultCollection results, IRandom random) {
       base.Analyze(individuals, qualities, results, random);
-      // TODO: Calculate Pareto front and add to results
+
+      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(individuals, qualities, Maximization);
+      var plot = new ParetoFrontScatterPlot<BinaryVector>(fronts, individuals, qualities, Objectives, BestKnownFront);
+      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
     }
 

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.IntegerVectorEncoding/3.3/IntegerVectorMultiObjectiveProblem.cs

@@ -63 +63 @@
     public override void Analyze(IntegerVector[] individuals, double[][] qualities, ResultCollection results, IRandom random) {
       base.Analyze(individuals, qualities, results, random);
-      // TODO: Calculate Pareto front and add to results
+
+      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(individuals, qualities, Maximization);
+      var plot = new ParetoFrontScatterPlot<IntegerVector>(fronts, individuals, qualities, Objectives, BestKnownFront);
+      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
     }
 

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkageMultiObjectiveProblem.cs

@@ -64 +64 @@
       base.Analyze(individuals, qualities, results, random);
 
-      var result = DominationCalculator.CalculateBestParetoFront(individuals, qualities, Maximization);
-      // TODO: Add results
+      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(individuals, qualities, Maximization);
+      var plot = new ParetoFrontScatterPlot<LinearLinkage>(fronts, individuals, qualities, Objectives, BestKnownFront);
+      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
     }
 

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.PermutationEncoding/3.3/PermutationMultiObjectiveProblem.cs

@@ -68 +68 @@
     public override void Analyze(Permutation[] individuals, double[][] qualities, ResultCollection results, IRandom random) {
       base.Analyze(individuals, qualities, results, random);
-      // TODO: Calculate Pareto front and add to results
+
+      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(individuals, qualities, Maximization);
+      var plot = new ParetoFrontScatterPlot<Permutation>(fronts, individuals, qualities, Objectives, BestKnownFront);
+      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
     }
 

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.RealVectorEncoding/3.3/RealVectorMultiObjectiveProblem.cs

@@ -63 +63 @@
     public override void Analyze(RealVector[] individuals, double[][] qualities, ResultCollection results, IRandom random) {
       base.Analyze(individuals, qualities, results, random);
-      // TODO: Calculate Pareto front and add to results
+
+      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(individuals, qualities, Maximization);
+      var plot = new ParetoFrontScatterPlot<RealVector>(fronts, individuals, qualities, Objectives, BestKnownFront);
+      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
     }
 

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeMultiObjectiveProblem.cs

@@ -24 +24 @@
 using System.Linq;
 using HEAL.Attic;
+using HeuristicLab.Analysis;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -52 +53 @@
       IRandom random) {
       base.Analyze(trees, qualities, results, random);
-      var front = DominationCalculator.CalculateBestParetoFront(trees, qualities, Maximization);
 
-      // TODO: Calculate Pareto front and add to results
+      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(trees, qualities, Maximization);
+      var plot = new ParetoFrontScatterPlot<ISymbolicExpressionTree>(fronts, trees, qualities, Objectives, BestKnownFront);
+      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
     }
 

branches/2521_ProblemRefactoring/HeuristicLab.Optimization/3.3/MultiObjective/DominationCalculator.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Linq;
 using HEAL.Attic;
 
@@ -137 +138 @@
 
     /// <summary>
+    /// Calculates all pareto fronts by returning the index of the parameters in each front.
+    /// The first in the list is the best front.
+    /// The fast non-dominated sorting algorithm is used as described in
+    /// Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).
+    /// A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.
+    /// IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
+    /// </summary>
+    /// <remarks>
+    /// When there are plateaus in the fitness landscape several solutions might have exactly
+    /// the same fitness vector. In this case parameter <paramref name="dominateOnEqualQualities"/>
+    /// can be set to true to avoid plateaus becoming too attractive for the search process.
+    /// </remarks>
+    /// <param name="solutions">The solutions of the population.</param>
+    /// <param name="qualities">The qualities resp. fitness for each solution.</param>
+    /// <param name="maximization">The objective in each dimension.</param>
+    /// <param name="dominateOnEqualQualities">Whether solutions of exactly equal quality should dominate one another.</param>
+    /// <returns>A sorted list of the pareto fronts where each front contains the indices of the <paramref name="solutions"/> and <paramref name="qualities"/>.</returns>
+    public static List<List<int>> CalculateAllParetoFrontsIndices<T>(T[] solutions, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities = true) {
+      return CalculateAllParetoFrontsIndices(solutions, qualities, maximization, out var rank, dominateOnEqualQualities);
+    }
+
+    /// <summary>
+    /// Calculates all pareto fronts by returning the index of the parameters in each front.
+    /// The first in the list is the best front.
+    /// The fast non-dominated sorting algorithm is used as described in
+    /// Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).
+    /// A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.
+    /// IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
+    /// </summary>
+    /// <remarks>
+    /// When there are plateaus in the fitness landscape several solutions might have exactly
+    /// the same fitness vector. In this case parameter <paramref name="dominateOnEqualQualities"/>
+    /// can be set to true to avoid plateaus becoming too attractive for the search process.
+    /// </remarks>
+    /// <param name="solutions">The solutions of the population.</param>
+    /// <param name="qualities">The qualities resp. fitness for each solution.</param>
+    /// <param name="maximization">The objective in each dimension.</param>
+    /// <param name="rank">The rank of each of the solutions, corresponds to the front it is put in.</param>
+    /// <param name="dominateOnEqualQualities">Whether solutions of exactly equal quality should dominate one another.</param>
+    /// <returns>A sorted list of the pareto fronts where each front contains the indices of the <paramref name="solutions"/> and <paramref name="qualities"/>.</returns>
+    public static List<List<int>> CalculateAllParetoFrontsIndices<T>(T[] solutions, double[][] qualities, bool[] maximization, out int[] rank, bool dominateOnEqualQualities = true) {
+      var populationSize = solutions.Length;
+
+      var dominatedIndividuals = Enumerable.Range(0, qualities.Length).Select(x => new List<int>()).ToArray();
+      var dominationCounter = new int[populationSize];
+      rank = new int[populationSize];
+      var fronts = new List<List<int>>();
+      fronts.Add(CalculateBestFrontIndices(solutions, qualities, maximization, dominateOnEqualQualities, populationSize, dominatedIndividuals, dominationCounter, rank));
+      var i = 0;
+      while (i < fronts.Count && fronts[i].Count > 0) {
+        var nextFront = new List<int>();
+        foreach (var p in fronts[i]) {
+          if (dominatedIndividuals[p].Count > 0) {
+            for (var k = 0; k < dominatedIndividuals[p].Count; k++) {
+              var dominatedIndividual = dominatedIndividuals[p][k];
+              dominationCounter[dominatedIndividual] -= 1;
+              if (dominationCounter[dominatedIndividual] == 0) {
+                rank[dominatedIndividual] = i + 1;
+                nextFront.Add(dominatedIndividual);
+              }
+            }
+          }
+        }
+        i += 1;
+        fronts.Add(nextFront);
+      }
+      return fronts;
+    }
+
+    private static List<int> CalculateBestFrontIndices<T>(T[] solutions, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities, int populationSize, List<int>[] dominatedIndividuals, int[] dominationCounter, int[] rank) {
+      var front = new List<int>();
+      for (var pI = 0; pI < populationSize - 1; pI++) {
+        var p = solutions[pI];
+        for (var qI = pI + 1; qI < populationSize; qI++) {
+          var test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
+          if (test == DominationResult.Dominates) {
+            dominatedIndividuals[pI].Add(qI);
+            dominationCounter[qI] += 1;
+          } else if (test == DominationResult.IsDominated) {
+            dominationCounter[pI] += 1;
+            dominatedIndividuals[qI].Add(pI);
+          }
+          if (pI == populationSize - 2
+            && qI == populationSize - 1
+            && dominationCounter[qI] == 0) {
+            rank[qI] = 0;
+            front.Add(qI);
+          }
+        }
+        if (dominationCounter[pI] == 0) {
+          rank[pI] = 0;
+          front.Add(pI);
+        }
+      }
+      return front;
+    }
+
+    /// <summary>
     /// Calculates the domination result of two solutions which are given in form
     /// of their quality resp. fitness vector.

branches/2521_ProblemRefactoring/HeuristicLab.Problems.TestFunctions.MultiObjective/3.3/Analyzers/ScatterPlotAnalyzer.cs

@@ -70 +70 @@
       }
 
-      var fronts = DominationCalculator.CalculateAllParetoFronts(individuals.ToArray(), qualities.Select(x => x.ToArray()).ToArray(), testFunction.Maximization(objectives), out var rank);
-      
-      ScatterPlotResultParameter.ActualValue = new ParetoFrontScatterPlot<RealVector>(
-        fronts.Select(x => x.Select(y => y.Item2).ToArray()).ToArray(),
-        fronts.Select(x => x.Select(y => y.Item1).ToArray()).ToArray(),
-        optimalFront, objectives);
+      var q = qualities.Select(x => x.ToArray()).ToArray();
+      var s = individuals.ToArray();
+      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(s, q, testFunction.Maximization(objectives), out var rank);
+      ScatterPlotResultParameter.ActualValue = new ParetoFrontScatterPlot<RealVector>(fronts, s, q, objectives, optimalFront);
+
       return base.Apply();
     }