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