- Timestamp:
- 06/28/17 22:05:14 (7 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
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();
Note: See TracChangeset
for help on using the changeset viewer.