eckity.multi_objective_evolution.nsga2_front_sorting

  1from collections import defaultdict
  2from typing import List
  3
  4from eckity.individual import Individual
  5from eckity.population import Population
  6
  7
  8class NSGA2FrontSorting():
  9	'''
 10    This class is incharge of setitng the value of selecting only the best individuals
 11    out of the population
 12    (mening that the are dominated by as littel amount of other Individuals as posible)
 13
 14    this class allso set the values of the "front_rank" and "crowding" of each individual
 15    '''
 16
 17	def select_for_population(self, population: Population, new_pop_size=None):
 18		for sub_population in population.sub_populations:
 19			dest_inds = []
 20			dest_inds = self._select(sub_population.individuals, dest_inds, new_pop_size)
 21			sub_population.individuals = dest_inds
 22
 23	def _select(self, source_inds: List[Individual], dest_inds: List[Individual], pop_size: int):
 24		'''
 25
 26        Parameters
 27        ----------
 28        source_inds : list of individuals (sub_population.individuals)
 29        dest_inds: the pareto front
 30        pop_size :  the size we destend the pareto front to be
 31
 32        Returns :  the pareto front
 33        -------
 34
 35        '''
 36		if not pop_size:
 37			pop_size = len(source_inds) // 2
 38
 39		front_rank = 1
 40		self._init_domination_dict(source_inds)
 41		while len(dest_inds) < pop_size:
 42			new_pareto_front = self._pareto_front_finding(source_inds)
 43			self._calc_fronts_crowding(new_pareto_front)
 44			self._update_new_pareto_front_rank(new_pareto_front, front_rank)
 45
 46			total_pareto_size = len(new_pareto_front) + len(dest_inds)
 47			if total_pareto_size > pop_size:
 48				number_solutions_needed = pop_size - len(dest_inds)
 49				new_pareto_front.sort(key=lambda x: x.fitness.crowding, reverse=True)
 50				new_pareto_front = new_pareto_front[
 51								   :int(number_solutions_needed)]  # take the individuals with the largest crowding
 52			dest_inds += new_pareto_front
 53			source_inds = self._remove_pareto_front(source_inds, new_pareto_front)
 54			front_rank += 1
 55		return dest_inds
 56
 57	def _remove_pareto_front(self, source_inds, pareto_front):
 58		for dominating_ind in pareto_front:
 59			for dominated_ind in self.domination_dict[dominating_ind].dominates:
 60				self.domination_dict[dominated_ind].domination_counter -= 1
 61		return list(set(source_inds) - set(pareto_front))
 62
 63	def _update_new_pareto_front_rank(self, new_pareto_front: List[Individual], front_rank: int):
 64		for ind in new_pareto_front:
 65			ind.fitness.front_rank = front_rank
 66
 67	def _calc_fronts_crowding(self, front: List[Individual]):
 68		for ind in front:
 69			ind.fitness.crowding = 0
 70
 71		objectiv_indexes = range(len(front[0].get_pure_fitness()))
 72		for objective_index in objectiv_indexes:
 73			front.sort(key=lambda x: x.get_pure_fitness()[objective_index])  # sort for each objectiv
 74			front[0].fitness.crowding = float("inf")
 75			front[-1].fitness.crowding = float("inf")
 76			for i in range(1, len(front) - 1):
 77				curr_crowding = front[i + 1].get_pure_fitness()[objective_index] - front[i - 1].get_pure_fitness()[
 78					objective_index]
 79				curr_crowding /= (front[-1].get_pure_fitness()[objective_index] - front[0].get_pure_fitness()[
 80					objective_index])
 81				front[i].fitness.crowding += curr_crowding
 82
 83	def _init_domination_dict(self, source_inds: List[Individual]):
 84		self.domination_dict = defaultdict(lambda: DominationCounter())
 85		for i, ind1 in enumerate(source_inds):
 86			for ind2 in source_inds[i + 1:]:
 87				self._habdle_domination(ind1, ind2)
 88
 89	def _habdle_domination(self, ind1, ind2):
 90		if ind2.fitness.dominate(ind2, ind1.fitness, ind1):
 91			self._increase_domination_counter(ind2, ind1)
 92		elif ind1.fitness.dominate(ind1, ind2.fitness, ind2):
 93			self._increase_domination_counter(ind1, ind2)
 94
 95	def _increase_domination_counter(self, dominating, dominated):
 96		self.domination_dict[dominating].dominates.append(dominated)
 97		self.domination_dict[dominated].domination_counter += 1
 98
 99	def _pareto_front_finding(self, source_inds: List[Individual]):
100		pareto_front = [ind for ind in source_inds if self.domination_dict[ind].domination_counter == 0]
101		return pareto_front
102
103
104class DominationCounter:
105	def __init__(self):
106		'''
107        self.dominates : a list of all the individuals this individual dominates
108        self.domination_counter : a counter of how many other individuals dominates this one
109        '''
110		self.dominates = []
111		self.domination_counter = 0