Add normalization of crowding distance in assignCrowdingDist.

The normalization is done as in the original C code of NSGA-II: each measure of distance for an objective i is divided by the number of objectives and the difference between the value for objective i of the front extrema. This modification changes the results obtain with selNSGA2 and therefore breaks reproducibility of results made with previous version of DEAP. --HG-- branch : dev
falconzyx · Dec 12, 2012 · aaba40b · aaba40b
1 parent a1ee992
commit aaba40b
Showing 1 changed file with 13 additions and 11 deletions.
diff --git a/deap/tools.py b/deap/tools.py
@@ -1630,17 +1630,19 @@ def assignCrowdingDist(individuals):
         return
 
     distances = [0.0] * len(individuals)
-    crowding = [(ind.fitness.values, i) for i, ind in enumerate(individuals)]
-
-    number_objectives = len(individuals[0].fitness.values)
-
-    for i in xrange(number_objectives):
-        crowding.sort(key=lambda element: element[0][i])
-        distances[crowding[0][1]] = float("inf")
-        distances[crowding[-1][1]] = float("inf")
-        for j in xrange(1, len(crowding) - 1):
-            distances[crowding[j][1]] += crowding[j + 1][0][i] - \
-                                         crowding[j - 1][0][i]
+    crowd = [(ind.fitness.values, i) for i, ind in enumerate(individuals)]
+
+    nobj = len(individuals[0].fitness.values)
+
+    for i in xrange(nobj):
+        crowd.sort(key=lambda element: element[0][i])
+        distances[crowd[0][1]] = float("inf")
+        distances[crowd[-1][1]] = float("inf")
+        if crowd[-1][0][i] == crowd[0][0][i]:
+            continue
+        norm = nobj * float(crowd[-1][0][i] - crowd[0][0][i])
+        for prev, cur, next in zip(crowd[:-2], crowd[1:-1], crowd[2:]):
+            distances[cur[1]] += (next[0][i] - prev[0][i]) / norm
 
     for i, dist in enumerate(distances):
         individuals[i].fitness.crowding_dist = dist