Changeset 17230


Ignore:
Timestamp:
09/03/19 15:50:35 (3 weeks ago)
Author:
abeham
Message:

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

Location:
branches/2521_ProblemRefactoring
Files:
10 edited

Legend:

Unmodified
Added
Removed
  • branches/2521_ProblemRefactoring/HeuristicLab.Analysis.Views/3.3/ParetoFrontScatterPlotViewOfT.cs

    r17229 r17230  
    177177    }
    178178
    179     private static Point2D<double>[] CreatePoints(IList<double[]> front, T[] solutions, int xDimIndex, int yDimIndex) {
     179    private static Point2D<double>[] CreatePoints(IReadOnlyList<double[]> front, T[] solutions, int xDimIndex, int yDimIndex) {
    180180      if (front == null || front.Count == 0) return new Point2D<double>[0];
    181181     
  • branches/2521_ProblemRefactoring/HeuristicLab.Analysis/3.3/MultiObjective/ParetoFrontScatterPlot.cs

    r17229 r17230  
    4444
    4545    [Storable]
    46     private IList<double[][]> fronts;
    47     public IList<double[][]> Fronts {
     46    private IReadOnlyList<double[][]> fronts;
     47    public IReadOnlyList<double[][]> Fronts {
    4848      get { return fronts; }
    4949    }
    5050
    5151    [Storable]
    52     private IList<T[]> items;
    53     public IList<T[]> Items {
     52    private IReadOnlyList<T[]> items;
     53    public IReadOnlyList<T[]> Items {
    5454      get { return items; }
    5555    }
    5656
    5757    [Storable]
    58     private IList<double[]> bestKnownFront;
    59     public IList<double[]> BestKnownFront {
     58    private IReadOnlyList<double[]> bestKnownFront;
     59    public IReadOnlyList<double[]> BestKnownFront {
    6060      get { return bestKnownFront; }
    6161    }
     
    6464    protected ParetoFrontScatterPlot(StorableConstructorFlag _) : base(_) { }
    6565    public ParetoFrontScatterPlot() { }
    66     public ParetoFrontScatterPlot(IList<double[][]> qualities, IList<T[]> items, IList<double[]> paretoFront, int objectives) {
     66    /// <summary>
     67    /// Provides the data for displaying a multi-objective population in a scatter plot.
     68    /// </summary>
     69    /// <param name="items">The solutions grouped by pareto front (first is best).</param>
     70    /// <param name="qualities">The objective vectors grouped by pareto front (first is best).</param>
     71    /// <param name="objectives">The number of objectives.</param>
     72    /// <param name="bestKnownParetoFront">Optional, the best known front in objective space.</param>
     73    public ParetoFrontScatterPlot(IReadOnlyList<T[]> items, IReadOnlyList<double[][]> qualities, int objectives, IReadOnlyList<double[]> bestKnownParetoFront = null)
     74    {
    6775      this.fronts = qualities;
    6876      this.items = items;
    69       this.bestKnownFront = paretoFront;
     77      this.bestKnownFront = bestKnownParetoFront;
    7078      this.objectives = objectives;
     79    }
     80    /// <summary>
     81    /// Provides the data for displaying a multi-objective population in a scatter plot.
     82    /// </summary>
     83    /// <param name="fronts">The fronts (first is best) with the indices of the solutions and qualities.</param>
     84    /// <param name="items">The solutions.</param>
     85    /// <param name="qualities">The objective vectors for each solution.</param>
     86    /// <param name="objectives">The number of objectives.</param>
     87    /// <param name="bestKnownParetoFront">Optional, the best known front in objective space.</param>
     88    public ParetoFrontScatterPlot(List<List<int>> fronts, IReadOnlyList<T> items, IReadOnlyList<double[]> qualities, int objectives, IReadOnlyList<double[]> bestKnownParetoFront = null)
     89    {
     90      this.fronts = fronts.Select(x => x.Select(y => qualities[y]).ToArray()).ToArray();
     91      this.items = fronts.Select(x => x.Select(y => items[y]).ToArray()).ToArray();
     92      this.bestKnownFront = bestKnownParetoFront;
     93      this.objectives = objectives;
     94
    7195    }
    7296    protected ParetoFrontScatterPlot(ParetoFrontScatterPlot<T> original, Cloner cloner)
  • branches/2521_ProblemRefactoring/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/BinaryVectorMultiObjectiveProblem.cs

    r17226 r17230  
    6161    public override void Analyze(BinaryVector[] individuals, double[][] qualities, ResultCollection results, IRandom random) {
    6262      base.Analyze(individuals, qualities, results, random);
    63       // TODO: Calculate Pareto front and add to results
     63
     64      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(individuals, qualities, Maximization);
     65      var plot = new ParetoFrontScatterPlot<BinaryVector>(fronts, individuals, qualities, Objectives, BestKnownFront);
     66      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
    6467    }
    6568
  • branches/2521_ProblemRefactoring/HeuristicLab.Encodings.IntegerVectorEncoding/3.3/IntegerVectorMultiObjectiveProblem.cs

    r16948 r17230  
    6363    public override void Analyze(IntegerVector[] individuals, double[][] qualities, ResultCollection results, IRandom random) {
    6464      base.Analyze(individuals, qualities, results, random);
    65       // TODO: Calculate Pareto front and add to results
     65
     66      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(individuals, qualities, Maximization);
     67      var plot = new ParetoFrontScatterPlot<IntegerVector>(fronts, individuals, qualities, Objectives, BestKnownFront);
     68      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
    6669    }
    6770
  • branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkageMultiObjectiveProblem.cs

    r17225 r17230  
    6464      base.Analyze(individuals, qualities, results, random);
    6565
    66       var result = DominationCalculator.CalculateBestParetoFront(individuals, qualities, Maximization);
    67       // TODO: Add results
     66      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(individuals, qualities, Maximization);
     67      var plot = new ParetoFrontScatterPlot<LinearLinkage>(fronts, individuals, qualities, Objectives, BestKnownFront);
     68      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
    6869    }
    6970
  • branches/2521_ProblemRefactoring/HeuristicLab.Encodings.PermutationEncoding/3.3/PermutationMultiObjectiveProblem.cs

    r16948 r17230  
    6868    public override void Analyze(Permutation[] individuals, double[][] qualities, ResultCollection results, IRandom random) {
    6969      base.Analyze(individuals, qualities, results, random);
    70       // TODO: Calculate Pareto front and add to results
     70
     71      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(individuals, qualities, Maximization);
     72      var plot = new ParetoFrontScatterPlot<Permutation>(fronts, individuals, qualities, Objectives, BestKnownFront);
     73      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
    7174    }
    7275
  • branches/2521_ProblemRefactoring/HeuristicLab.Encodings.RealVectorEncoding/3.3/RealVectorMultiObjectiveProblem.cs

    r16949 r17230  
    6363    public override void Analyze(RealVector[] individuals, double[][] qualities, ResultCollection results, IRandom random) {
    6464      base.Analyze(individuals, qualities, results, random);
    65       // TODO: Calculate Pareto front and add to results
     65
     66      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(individuals, qualities, Maximization);
     67      var plot = new ParetoFrontScatterPlot<RealVector>(fronts, individuals, qualities, Objectives, BestKnownFront);
     68      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
    6669    }
    6770
  • branches/2521_ProblemRefactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeMultiObjectiveProblem.cs

    r17229 r17230  
    2424using System.Linq;
    2525using HEAL.Attic;
     26using HeuristicLab.Analysis;
    2627using HeuristicLab.Common;
    2728using HeuristicLab.Core;
     
    5253      IRandom random) {
    5354      base.Analyze(trees, qualities, results, random);
    54       var front = DominationCalculator.CalculateBestParetoFront(trees, qualities, Maximization);
    5555
    56       // TODO: Calculate Pareto front and add to results
     56      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(trees, qualities, Maximization);
     57      var plot = new ParetoFrontScatterPlot<ISymbolicExpressionTree>(fronts, trees, qualities, Objectives, BestKnownFront);
     58      results.AddOrUpdateResult("Pareto Front Scatter Plot", plot);
    5759    }
    5860
  • branches/2521_ProblemRefactoring/HeuristicLab.Optimization/3.3/MultiObjective/DominationCalculator.cs

    r17226 r17230  
    2222using System;
    2323using System.Collections.Generic;
     24using System.Linq;
    2425using HEAL.Attic;
    2526
     
    137138
    138139    /// <summary>
     140    /// Calculates all pareto fronts by returning the index of the parameters in each front.
     141    /// The first in the list is the best front.
     142    /// The fast non-dominated sorting algorithm is used as described in
     143    /// Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).
     144    /// A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.
     145    /// IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
     146    /// </summary>
     147    /// <remarks>
     148    /// When there are plateaus in the fitness landscape several solutions might have exactly
     149    /// the same fitness vector. In this case parameter <paramref name="dominateOnEqualQualities"/>
     150    /// can be set to true to avoid plateaus becoming too attractive for the search process.
     151    /// </remarks>
     152    /// <param name="solutions">The solutions of the population.</param>
     153    /// <param name="qualities">The qualities resp. fitness for each solution.</param>
     154    /// <param name="maximization">The objective in each dimension.</param>
     155    /// <param name="dominateOnEqualQualities">Whether solutions of exactly equal quality should dominate one another.</param>
     156    /// <returns>A sorted list of the pareto fronts where each front contains the indices of the <paramref name="solutions"/> and <paramref name="qualities"/>.</returns>
     157    public static List<List<int>> CalculateAllParetoFrontsIndices<T>(T[] solutions, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities = true) {
     158      return CalculateAllParetoFrontsIndices(solutions, qualities, maximization, out var rank, dominateOnEqualQualities);
     159    }
     160
     161    /// <summary>
     162    /// Calculates all pareto fronts by returning the index of the parameters in each front.
     163    /// The first in the list is the best front.
     164    /// The fast non-dominated sorting algorithm is used as described in
     165    /// Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).
     166    /// A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.
     167    /// IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
     168    /// </summary>
     169    /// <remarks>
     170    /// When there are plateaus in the fitness landscape several solutions might have exactly
     171    /// the same fitness vector. In this case parameter <paramref name="dominateOnEqualQualities"/>
     172    /// can be set to true to avoid plateaus becoming too attractive for the search process.
     173    /// </remarks>
     174    /// <param name="solutions">The solutions of the population.</param>
     175    /// <param name="qualities">The qualities resp. fitness for each solution.</param>
     176    /// <param name="maximization">The objective in each dimension.</param>
     177    /// <param name="rank">The rank of each of the solutions, corresponds to the front it is put in.</param>
     178    /// <param name="dominateOnEqualQualities">Whether solutions of exactly equal quality should dominate one another.</param>
     179    /// <returns>A sorted list of the pareto fronts where each front contains the indices of the <paramref name="solutions"/> and <paramref name="qualities"/>.</returns>
     180    public static List<List<int>> CalculateAllParetoFrontsIndices<T>(T[] solutions, double[][] qualities, bool[] maximization, out int[] rank, bool dominateOnEqualQualities = true) {
     181      var populationSize = solutions.Length;
     182
     183      var dominatedIndividuals = Enumerable.Range(0, qualities.Length).Select(x => new List<int>()).ToArray();
     184      var dominationCounter = new int[populationSize];
     185      rank = new int[populationSize];
     186      var fronts = new List<List<int>>();
     187      fronts.Add(CalculateBestFrontIndices(solutions, qualities, maximization, dominateOnEqualQualities, populationSize, dominatedIndividuals, dominationCounter, rank));
     188      var i = 0;
     189      while (i < fronts.Count && fronts[i].Count > 0) {
     190        var nextFront = new List<int>();
     191        foreach (var p in fronts[i]) {
     192          if (dominatedIndividuals[p].Count > 0) {
     193            for (var k = 0; k < dominatedIndividuals[p].Count; k++) {
     194              var dominatedIndividual = dominatedIndividuals[p][k];
     195              dominationCounter[dominatedIndividual] -= 1;
     196              if (dominationCounter[dominatedIndividual] == 0) {
     197                rank[dominatedIndividual] = i + 1;
     198                nextFront.Add(dominatedIndividual);
     199              }
     200            }
     201          }
     202        }
     203        i += 1;
     204        fronts.Add(nextFront);
     205      }
     206      return fronts;
     207    }
     208
     209    private static List<int> CalculateBestFrontIndices<T>(T[] solutions, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities, int populationSize, List<int>[] dominatedIndividuals, int[] dominationCounter, int[] rank) {
     210      var front = new List<int>();
     211      for (var pI = 0; pI < populationSize - 1; pI++) {
     212        var p = solutions[pI];
     213        for (var qI = pI + 1; qI < populationSize; qI++) {
     214          var test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
     215          if (test == DominationResult.Dominates) {
     216            dominatedIndividuals[pI].Add(qI);
     217            dominationCounter[qI] += 1;
     218          } else if (test == DominationResult.IsDominated) {
     219            dominationCounter[pI] += 1;
     220            dominatedIndividuals[qI].Add(pI);
     221          }
     222          if (pI == populationSize - 2
     223            && qI == populationSize - 1
     224            && dominationCounter[qI] == 0) {
     225            rank[qI] = 0;
     226            front.Add(qI);
     227          }
     228        }
     229        if (dominationCounter[pI] == 0) {
     230          rank[pI] = 0;
     231          front.Add(pI);
     232        }
     233      }
     234      return front;
     235    }
     236
     237    /// <summary>
    139238    /// Calculates the domination result of two solutions which are given in form
    140239    /// of their quality resp. fitness vector.
  • branches/2521_ProblemRefactoring/HeuristicLab.Problems.TestFunctions.MultiObjective/3.3/Analyzers/ScatterPlotAnalyzer.cs

    r17229 r17230  
    7070      }
    7171
    72       var fronts = DominationCalculator.CalculateAllParetoFronts(individuals.ToArray(), qualities.Select(x => x.ToArray()).ToArray(), testFunction.Maximization(objectives), out var rank);
    73      
    74       ScatterPlotResultParameter.ActualValue = new ParetoFrontScatterPlot<RealVector>(
    75         fronts.Select(x => x.Select(y => y.Item2).ToArray()).ToArray(),
    76         fronts.Select(x => x.Select(y => y.Item1).ToArray()).ToArray(),
    77         optimalFront, objectives);
     72      var q = qualities.Select(x => x.ToArray()).ToArray();
     73      var s = individuals.ToArray();
     74      var fronts = DominationCalculator.CalculateAllParetoFrontsIndices(s, q, testFunction.Maximization(objectives), out var rank);
     75      ScatterPlotResultParameter.ActualValue = new ParetoFrontScatterPlot<RealVector>(fronts, s, q, objectives, optimalFront);
     76
    7877      return base.Apply();
    7978    }
Note: See TracChangeset for help on using the changeset viewer.