Ignore:
Timestamp:
06/28/17 22:05:14 (4 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.Operators/3.3/MultiObjective/FastNonDominatedSort.cs

    r14185 r15080  
    3939  [StorableClass]
    4040  public class FastNonDominatedSort : SingleSuccessorOperator, IMultiObjectiveOperator {
    41     private enum DominationResult { Dominates, IsDominated, IsNonDominated };
    4241
    4342    #region Parameter properties
     
    7574      int populationSize = scope.SubScopes.Count;
    7675
    77       List<ScopeList> fronts = new List<ScopeList>();
    78       Dictionary<IScope, List<int>> dominatedScopes = new Dictionary<IScope, List<int>>();
    79       int[] dominationCounter = new int[populationSize];
    80       ItemArray<IntValue> rank = new ItemArray<IntValue>(populationSize);
     76      int[] rank;
     77      var fronts = DominationCalculator<IScope>.CalculateAllParetoFronts(scope.SubScopes.ToArray(), qualities, maximization, out rank, dominateOnEqualQualities);
    8178
    82       for (int pI = 0; pI < populationSize - 1; pI++) {
    83         IScope p = scope.SubScopes[pI];
    84         List<int> dominatedScopesByp;
    85         if (!dominatedScopes.TryGetValue(p, out dominatedScopesByp))
    86           dominatedScopes[p] = dominatedScopesByp = new List<int>();
    87         for (int qI = pI + 1; qI < populationSize; qI++) {
    88           DominationResult test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
    89           if (test == DominationResult.Dominates) {
    90             dominatedScopesByp.Add(qI);
    91             dominationCounter[qI] += 1;
    92           } else if (test == DominationResult.IsDominated) {
    93             dominationCounter[pI] += 1;
    94             if (!dominatedScopes.ContainsKey(scope.SubScopes[qI]))
    95               dominatedScopes.Add(scope.SubScopes[qI], new List<int>());
    96             dominatedScopes[scope.SubScopes[qI]].Add(pI);
    97           }
    98           if (pI == populationSize - 2
    99             && qI == populationSize - 1
    100             && dominationCounter[qI] == 0) {
    101             rank[qI] = new IntValue(0);
    102             AddToFront(scope.SubScopes[qI], fronts, 0);
    103           }
    104         }
    105         if (dominationCounter[pI] == 0) {
    106           rank[pI] = new IntValue(0);
    107           AddToFront(p, fronts, 0);
    108         }
    109       }
    110       int i = 0;
    111       while (i < fronts.Count && fronts[i].Count > 0) {
    112         ScopeList nextFront = new ScopeList();
    113         foreach (IScope p in fronts[i]) {
    114           List<int> dominatedScopesByp;
    115           if (dominatedScopes.TryGetValue(p, out dominatedScopesByp)) {
    116             for (int k = 0; k < dominatedScopesByp.Count; k++) {
    117               int dominatedScope = dominatedScopesByp[k];
    118               dominationCounter[dominatedScope] -= 1;
    119               if (dominationCounter[dominatedScope] == 0) {
    120                 rank[dominatedScope] = new IntValue(i + 1);
    121                 nextFront.Add(scope.SubScopes[dominatedScope]);
    122               }
    123             }
    124           }
    125         }
    126         i += 1;
    127         fronts.Add(nextFront);
    128       }
    129 
    130       RankParameter.ActualValue = rank;
     79      RankParameter.ActualValue = new ItemArray<IntValue>(rank.Select(x => new IntValue(x)));
    13180
    13281      scope.SubScopes.Clear();
    13382
    134       for (i = 0; i < fronts.Count; i++) {
     83      for (var i = 0; i < fronts.Count; i++) {
    13584        Scope frontScope = new Scope("Front " + i);
    13685        foreach (var p in fronts[i])
    137           frontScope.SubScopes.Add(p);
     86          frontScope.SubScopes.Add(p.Item1);
    13887        if (frontScope.SubScopes.Count > 0)
    13988          scope.SubScopes.Add(frontScope);
    14089      }
    14190      return base.Apply();
    142     }
    143 
    144     private static DominationResult Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
    145       //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
    146       if (dominateOnEqualQualities) {
    147         var equal = true;
    148         for (int i = 0; i < left.Length; i++) {
    149           if (left[i] != right[i]) {
    150             equal = false;
    151             break;
    152           }
    153         }
    154         if (equal) return DominationResult.Dominates;
    155       }
    156 
    157       bool leftIsBetter = false, rightIsBetter = false;
    158       for (int i = 0; i < left.Length; i++) {
    159         if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
    160         else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
    161         if (leftIsBetter && rightIsBetter) break;
    162       }
    163 
    164       if (leftIsBetter && !rightIsBetter) return DominationResult.Dominates;
    165       if (!leftIsBetter && rightIsBetter) return DominationResult.IsDominated;
    166       return DominationResult.IsNonDominated;
    167     }
    168 
    169     private static bool IsDominated(double left, double right, bool maximization) {
    170       return maximization && left < right
    171         || !maximization && left > right;
    172     }
    173 
    174     private static void AddToFront(IScope p, List<ScopeList> fronts, int i) {
    175       if (i == fronts.Count) fronts.Add(new ScopeList());
    176       fronts[i].Add(p);
    17791    }
    17892
Note: See TracChangeset for help on using the changeset viewer.