- Timestamp:
- 06/28/17 22:05:14 (7 years ago)
- Location:
- trunk/sources
- Files:
-
- 2 added
- 3 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 -
trunk/sources/HeuristicLab.Optimization/3.3/BasicProblems/MultiObjectiveBasicProblem.cs
r15051 r15080 59 59 public abstract double[] Evaluate(Individual individual, IRandom random); 60 60 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 154 62 protected override void OnOperatorsChanged() { 155 63 base.OnOperatorsChanged(); -
trunk/sources/HeuristicLab.Optimization/3.3/HeuristicLab.Optimization-3.3.csproj
r14071 r15080 156 156 <Compile Include="Interfaces\ILocalImprovementAlgorithmOperator.cs" /> 157 157 <Compile Include="Interfaces\IMultiObjectiveOperator.cs" /> 158 <Compile Include="MultiObjective\DominationCalculator.cs" /> 158 159 <Compile Include="Results\IResultParameter.cs" /> 159 160 <Compile Include="Interfaces\ISingleObjectiveOperator.cs" />
Note: See TracChangeset
for help on using the changeset viewer.