Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
06/24/17 22:36:02 (7 years ago)
Author:
abeham
Message:

#2783:

  • Implemented GetBestIndividual as public static and protected method in SingleObjectiveBasicProblem
  • Impblemented GetParetorFronts as public static and protected method in MultiObjectiveBasicProblem
  • Implemented AddOrUpdateResult as public method in ResultCollection
Location:
trunk/sources/HeuristicLab.Optimization/3.3/BasicProblems
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Optimization/3.3/BasicProblems/MultiObjectiveBasicProblem.cs

    r14185 r15051  
    2020#endregion
    2121
     22using System;
     23using System.Collections.Generic;
    2224using System.Linq;
    2325using HeuristicLab.Common;
     
    5759    public abstract double[] Evaluate(Individual individual, IRandom random);
    5860    public virtual void Analyze(Individual[] individuals, double[][] qualities, ResultCollection results, IRandom random) { }
     61
     62    protected List<List<Tuple<Individual, double[]>>> GetParetoFronts(Individual[] individuals, double[][] qualities, bool dominateOnEqualQualities = true) {
     63      return GetParetoFronts(individuals, qualities, Maximization, dominateOnEqualQualities);
     64    }
     65    public static List<List<Tuple<Individual, double[]>>> GetParetoFronts(Individual[] individuals, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities = true) {
     66      int populationSize = individuals.Length;
     67
     68      var fronts = new List<List<Tuple<Individual, double[]>>>();
     69      fronts.Add(new List<Tuple<Individual, double[]>>());
     70      Dictionary<Individual, List<int>> dominatedIndividuals = new Dictionary<Individual, List<int>>();
     71      int[] dominationCounter = new int[populationSize];
     72      ItemArray<IntValue> rank = new ItemArray<IntValue>(populationSize);
     73
     74      for (int pI = 0; pI < populationSize - 1; pI++) {
     75        var p = individuals[pI];
     76        List<int> dominatedIndividualsByp;
     77        if (!dominatedIndividuals.TryGetValue(p, out dominatedIndividualsByp))
     78          dominatedIndividuals[p] = dominatedIndividualsByp = new List<int>();
     79        for (int qI = pI + 1; qI < populationSize; qI++) {
     80          var test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
     81          if (test == 1) {
     82            dominatedIndividualsByp.Add(qI);
     83            dominationCounter[qI] += 1;
     84          } else if (test == -1) {
     85            dominationCounter[pI] += 1;
     86            if (!dominatedIndividuals.ContainsKey(individuals[qI]))
     87              dominatedIndividuals.Add(individuals[qI], new List<int>());
     88            dominatedIndividuals[individuals[qI]].Add(pI);
     89          }
     90          if (pI == populationSize - 2
     91            && qI == populationSize - 1
     92            && dominationCounter[qI] == 0) {
     93            rank[qI] = new IntValue(0);
     94            fronts[0].Add(Tuple.Create(individuals[qI], qualities[qI]));
     95          }
     96        }
     97        if (dominationCounter[pI] == 0) {
     98          rank[pI] = new IntValue(0);
     99          fronts[0].Add(Tuple.Create(p, qualities[pI]));
     100        }
     101      }
     102      int i = 0;
     103      while (i < fronts.Count && fronts[i].Count > 0) {
     104        var nextFront = new List<Tuple<Individual, double[]>>();
     105        foreach (var p in fronts[i]) {
     106          List<int> dominatedIndividualsByp;
     107          if (dominatedIndividuals.TryGetValue(p.Item1, out dominatedIndividualsByp)) {
     108            for (int k = 0; k < dominatedIndividualsByp.Count; k++) {
     109              int dominatedIndividual = dominatedIndividualsByp[k];
     110              dominationCounter[dominatedIndividual] -= 1;
     111              if (dominationCounter[dominatedIndividual] == 0) {
     112                rank[dominatedIndividual] = new IntValue(i + 1);
     113                nextFront.Add(Tuple.Create(individuals[dominatedIndividual], qualities[dominatedIndividual]));
     114              }
     115            }
     116          }
     117        }
     118        i += 1;
     119        fronts.Add(nextFront);
     120      }
     121      return fronts;
     122    }
     123
     124    private static int Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
     125      //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
     126      if (dominateOnEqualQualities) {
     127        var equal = true;
     128        for (int i = 0; i < left.Length; i++) {
     129          if (left[i] != right[i]) {
     130            equal = false;
     131            break;
     132          }
     133        }
     134        if (equal) return 1;
     135      }
     136
     137      bool leftIsBetter = false, rightIsBetter = false;
     138      for (int i = 0; i < left.Length; i++) {
     139        if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
     140        else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
     141        if (leftIsBetter && rightIsBetter) break;
     142      }
     143
     144      if (leftIsBetter && !rightIsBetter) return 1;
     145      if (!leftIsBetter && rightIsBetter) return -1;
     146      return 0;
     147    }
     148
     149    private static bool IsDominated(double left, double right, bool maximization) {
     150      return maximization && left < right
     151        || !maximization && left > right;
     152    }
    59153
    60154    protected override void OnOperatorsChanged() {
  • trunk/sources/HeuristicLab.Optimization/3.3/BasicProblems/SingleObjectiveBasicProblem.cs

    r14185 r15051  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using System.Linq;
     
    8485    }
    8586
     87    protected Tuple<Individual, double> GetBestIndividual(Individual[] individuals, double[] qualities) {
     88      return GetBestIndividual(individuals, qualities, Maximization);
     89    }
     90    public static Tuple<Individual, double> GetBestIndividual(Individual[] individuals, double[] qualities, bool maximization) {
     91      var zipped = individuals.Zip(qualities, (i, q) => new { Individual = i, Quality = q });
     92      var best = (maximization ? zipped.OrderByDescending(z => z.Quality) : zipped.OrderBy(z => z.Quality)).First();
     93      return Tuple.Create(best.Individual, best.Quality);
     94    }
     95
    8696    protected override void OnOperatorsChanged() {
    8797      base.OnOperatorsChanged();
Note: See TracChangeset for help on using the changeset viewer.