Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
06/28/17 22:05:14 (7 years ago)
Author:
abeham
Message:

#2783: Moved pareto front calculation from MultiObjectiveBasicProblem to a new class DominationCalculator<T>. Changed FastNonDominatedSort to use the new class.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Optimization/3.3/BasicProblems/MultiObjectiveBasicProblem.cs

    r15051 r15080  
    5959    public abstract double[] Evaluate(Individual individual, IRandom random);
    6060    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     }
    153 
     61   
    15462    protected override void OnOperatorsChanged() {
    15563      base.OnOperatorsChanged();
Note: See TracChangeset for help on using the changeset viewer.