Changeset 15080 for trunk/sources/HeuristicLab.Optimization.Operators/3.3
- Timestamp:
- 06/28/17 22:05:14 (7 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.Optimization.Operators/3.3/MultiObjective/FastNonDominatedSort.cs
r14185 r15080 39 39 [StorableClass] 40 40 public class FastNonDominatedSort : SingleSuccessorOperator, IMultiObjectiveOperator { 41 private enum DominationResult { Dominates, IsDominated, IsNonDominated };42 41 43 42 #region Parameter properties … … 75 74 int populationSize = scope.SubScopes.Count; 76 75 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); 81 78 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))); 131 80 132 81 scope.SubScopes.Clear(); 133 82 134 for ( i = 0; i < fronts.Count; i++) {83 for (var i = 0; i < fronts.Count; i++) { 135 84 Scope frontScope = new Scope("Front " + i); 136 85 foreach (var p in fronts[i]) 137 frontScope.SubScopes.Add(p );86 frontScope.SubScopes.Add(p.Item1); 138 87 if (frontScope.SubScopes.Count > 0) 139 88 scope.SubScopes.Add(frontScope); 140 89 } 141 90 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 reasons146 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 < right171 || !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);177 91 } 178 92
Note: See TracChangeset
for help on using the changeset viewer.