1__author__ = 'Justin Bayer, Tom Schaul, {justin,tom}@idsia.ch'
2
3
4from scipy import array
5
6from pybrain.optimization.populationbased.ga import GA
7from pybrain.tools.nondominated import non_dominated_front, crowding_distance, non_dominated_sort
8
9# TODO: not very elegant, because of the conversions between tuples and arrays all the time...
10
11
12class MultiObjectiveGA(GA):
13    """ Multi-objective Genetic Algorithm: the fitness is a vector with one entry per objective.
14    By default we use NSGA-II selection. """
15
16    topProportion = 0.5
17    elitism = True
18
19    populationSize = 100
20    mutationStdDev = 1.
21
22    allowEquality = True
23
24    mustMaximize = True
25
26    def _learnStep(self):
27        """ do one generation step """
28        # evaluate fitness
29        """ added by JPQ """
30        if isinstance(self.fitnesses,dict):
31            oldfitnesses = self.fitnesses
32            self.fitnesses = dict()
33            for indiv in self.currentpop:
34                if tuple(indiv) in oldfitnesses:
35                    self.fitnesses[tuple(indiv)] = oldfitnesses[tuple(indiv)]
36                else:
37                    self.fitnesses[tuple(indiv)] = self._oneEvaluation(indiv)
38            del oldfitnesses
39        else:
40        # ---
41            self.fitnesses = dict([(tuple(indiv), self._oneEvaluation(indiv)) for indiv in self.currentpop])
42
43        if self.storeAllPopulations:
44            self._allGenerations.append((self.currentpop, self.fitnesses))
45
46        if self.elitism:
47            self.bestEvaluable = list(non_dominated_front(list(map(tuple, self.currentpop)),
48                                                          key=lambda x: self.fitnesses[x],
49                                                          allowequality = self.allowEquality))
50        else:
51            self.bestEvaluable = list(non_dominated_front(list(map(tuple, self.currentpop))+self.bestEvaluable,
52                                                          key=lambda x: self.fitnesses[x],
53                                                          allowequality = self.allowEquality))
54        self.bestEvaluation = [self.fitnesses[indiv] for indiv in self.bestEvaluable]
55
56        self.produceOffspring()
57
58    def select(self):
59        return list(map(array, nsga2select(list(map(tuple, self.currentpop)), self.fitnesses,
60                                      self.selectionSize, self.allowEquality)))
61
62
63
64def nsga2select(population, fitnesses, survivors, allowequality = True):
65    """The NSGA-II selection strategy (Deb et al., 2002).
66    The number of individuals that survive is given by the survivors parameter."""
67    fronts = non_dominated_sort(population,
68                                key=lambda x: fitnesses[x],
69                                allowequality = allowequality)
70
71    individuals = set()
72    for front in fronts:
73        remaining = survivors - len(individuals)
74        if not remaining > 0:
75            break
76        if len(front) > remaining:
77            # If the current front does not fit in the spots left, use those
78            # that have the biggest crowding distance.
79            crowd_dist = crowding_distance(front, fitnesses)
80            front = sorted(front, key=lambda x: crowd_dist[x], reverse=True)
81            front = set(front[:remaining])
82        individuals |= front
83
84    return list(individuals)
85