import random
from typing import List, TypeVar
import numpy as np
from jmetal.core.operator import Selection
from jmetal.util.density_estimator import CrowdingDistance
from jmetal.util.ranking import FastNonDominatedRanking
from jmetal.util.comparator import Comparator, DominanceComparator
S = TypeVar('S')
"""
.. module:: selection
:platform: Unix, Windows
:synopsis: Module implementing selection operators.
.. moduleauthor:: Antonio J. Nebro <antonio@lcc.uma.es>, Antonio Benítez-Hidalgo <antonio.b@uma.es>
"""
[docs]class RouletteWheelSelection(Selection[List[S], S]):
"""Performs roulette wheel selection.
"""
def __init__(self):
super(RouletteWheelSelection).__init__()
[docs] def execute(self, front: List[S]) -> S:
if front is None:
raise Exception('The front is null')
elif len(front) == 0:
raise Exception('The front is empty')
maximum = sum([solution.objectives[0] for solution in front])
rand = random.uniform(0.0, maximum)
value = 0.0
for solution in front:
value += solution.objectives[0]
if value > rand:
return solution
return None
[docs] def get_name(self) -> str:
return 'Roulette wheel selection'
[docs]class BinaryTournamentSelection(Selection[List[S], S]):
def __init__(self, comparator: Comparator = DominanceComparator()):
super(BinaryTournamentSelection, self).__init__()
self.comparator = comparator
[docs] def execute(self, front: List[S]) -> S:
if front is None:
raise Exception('The front is null')
elif len(front) == 0:
raise Exception('The front is empty')
if len(front) == 1:
result = front[0]
else:
# Sampling without replacement
i, j = random.sample(range(0, len(front)), 2)
solution1 = front[i]
solution2 = front[j]
flag = self.comparator.compare(solution1, solution2)
if flag == -1:
result = solution1
elif flag == 1:
result = solution2
else:
result = [solution1, solution2][random.random() < 0.5]
return result
[docs] def get_name(self) -> str:
return 'Binary tournament selection'
[docs]class BestSolutionSelection(Selection[List[S], S]):
def __init__(self):
super(BestSolutionSelection, self).__init__()
[docs] def execute(self, front: List[S]) -> S:
if front is None:
raise Exception('The front is null')
elif len(front) == 0:
raise Exception('The front is empty')
result = front[0]
for solution in front[1:]:
if DominanceComparator().compare(solution, result) < 0:
result = solution
return result
[docs] def get_name(self) -> str:
return 'Best solution selection'
[docs]class NaryRandomSolutionSelection(Selection[List[S], S]):
def __init__(self, number_of_solutions_to_be_returned: int = 1):
super(NaryRandomSolutionSelection, self).__init__()
if number_of_solutions_to_be_returned < 0:
raise Exception('The number of solutions to be returned must be positive integer')
self.number_of_solutions_to_be_returned = number_of_solutions_to_be_returned
[docs] def execute(self, front: List[S]) -> S:
if front is None:
raise Exception('The front is null')
if len(front) == 0:
raise Exception('The front is empty')
if len(front) < self.number_of_solutions_to_be_returned:
raise Exception('The front contains less elements than required')
# random_search sampling without replacement
return random.sample(front, self.number_of_solutions_to_be_returned)
[docs] def get_name(self) -> str:
return 'Nary random_search solution selection'
[docs]class DifferentialEvolutionSelection(Selection[List[S], List[S]]):
def __init__(self):
super(DifferentialEvolutionSelection, self).__init__()
self.index_to_exclude = None
[docs] def execute(self, front: List[S]) -> List[S]:
if front is None:
raise Exception('The front is null')
elif len(front) == 0:
raise Exception('The front is empty')
elif len(front) < 4:
raise Exception('The front has less than four solutions: ' + str(len(front)))
selected_indexes = random.sample(range(len(front)), 3)
while self.index_to_exclude in selected_indexes:
selected_indexes = random.sample(range(len(front)), 3)
return [front[i] for i in selected_indexes]
[docs] def set_index_to_exclude(self, index: int):
self.index_to_exclude = index
[docs] def get_name(self) -> str:
return "Differential evolution selection"
[docs]class RandomSolutionSelection(Selection[List[S], S]):
def __init__(self):
super(RandomSolutionSelection, self).__init__()
[docs] def execute(self, front: List[S]) -> S:
if front is None:
raise Exception('The front is null')
elif len(front) == 0:
raise Exception('The front is empty')
return random.choice(front)
[docs] def get_name(self) -> str:
return 'Random solution selection'
[docs]class RankingAndCrowdingDistanceSelection(Selection[List[S], List[S]]):
def __init__(self, max_population_size: int, dominance_comparator: Comparator = DominanceComparator()):
super(RankingAndCrowdingDistanceSelection, self).__init__()
self.max_population_size = max_population_size
self.dominance_comparator = dominance_comparator
[docs] def execute(self, front: List[S]) -> List[S]:
if front is None:
raise Exception('The front is null')
elif len(front) == 0:
raise Exception('The front is empty')
ranking = FastNonDominatedRanking(self.dominance_comparator)
crowding_distance = CrowdingDistance()
ranking.compute_ranking(front)
ranking_index = 0
new_solution_list = []
while len(new_solution_list) < self.max_population_size:
if len(ranking.get_subfront(ranking_index)) < (self.max_population_size - len(new_solution_list)):
new_solution_list = new_solution_list + ranking.get_subfront(ranking_index)
ranking_index += 1
else:
subfront = ranking.get_subfront(ranking_index)
crowding_distance.compute_density_estimator(subfront)
sorted_subfront = sorted(subfront, key=lambda x: x.attributes['crowding_distance'], reverse=True)
for i in range((self.max_population_size - len(new_solution_list))):
new_solution_list.append(sorted_subfront[i])
return new_solution_list
[docs] def get_name(self) -> str:
return 'Ranking and crowding distance selection'
[docs]class RankingAndFitnessSelection(Selection[List[S], List[S]]):
def __init__(self,
max_population_size: int, reference_point: S,
dominance_comparator: Comparator = DominanceComparator()):
super(RankingAndFitnessSelection, self).__init__()
self.max_population_size = max_population_size
self.dominance_comparator = dominance_comparator
self.reference_point = reference_point
[docs] def hypesub(self, l, A, actDim, bounds, pvec, alpha, k):
h = [0 for _ in range(l)]
Adim = [a[actDim - 1] for a in A]
indices_sort = sorted(range(len(Adim)), key=Adim.__getitem__)
S = [A[j] for j in indices_sort]
pvec = [pvec[j] for j in indices_sort]
for i in range(1, len(S) + 1):
if i < len(S):
extrusion = S[i][actDim - 1] - S[i - 1][actDim - 1]
else:
extrusion = bounds[actDim - 1] - S[i - 1][actDim - 1]
if actDim == 1:
if i > k:
break
if all(alpha) >= 0:
for p in pvec[0:i]:
h[p] = h[p] + extrusion * alpha[i - 1]
else:
if extrusion > 0:
h = [h[j] + extrusion * self.hypesub(l, S[0:i], actDim - 1, bounds, pvec[0:i], alpha, k)[j] for j in
range(l)]
return h
[docs] def compute_hypervol_fitness_values(self, population: List[S], reference_point: S, k: int):
points = [ind.objectives for ind in population]
bounds = reference_point.objectives
population_size = len(points)
if k < 0:
k = population_size
actDim = len(bounds)
pvec = range(population_size)
alpha = []
for i in range(1, k + 1):
alpha.append(np.prod([float(k - j) / (population_size - j) for j in range(1, i)]) / i)
f = self.hypesub(population_size, points, actDim, bounds, pvec, alpha, k)
for i in range(len(population)):
population[i].attributes['fitness'] = f[i]
return population
[docs] def execute(self, front: List[S]) -> List[S]:
if front is None:
raise Exception('The front is null')
elif len(front) == 0:
raise Exception('The front is empty')
ranking = FastNonDominatedRanking(self.dominance_comparator)
ranking.compute_ranking(front)
ranking_index = 0
new_solution_list = []
while len(new_solution_list) < self.max_population_size:
if len(ranking.get_subfront(ranking_index)) < self.max_population_size - len(new_solution_list):
subfront = ranking.get_subfront(ranking_index)
new_solution_list = new_solution_list + subfront
ranking_index += 1
else:
subfront = ranking.get_subfront(ranking_index)
parameter_K = len(subfront) - (self.max_population_size - len(new_solution_list))
while parameter_K > 0:
subfront = self.compute_hypervol_fitness_values(subfront, self.reference_point, parameter_K)
subfront = sorted(subfront, key=lambda x: x.attributes['fitness'], reverse=True)
subfront = subfront[:-1]
parameter_K = parameter_K - 1
new_solution_list = new_solution_list + subfront
return new_solution_list
[docs] def get_name(self) -> str:
return 'Ranking and fitness selection'
[docs]class BinaryTournament2Selection(Selection[List[S], S]):
def __init__(self, comparator_list: List[Comparator]):
super(BinaryTournament2Selection, self).__init__()
self.comparator_list = comparator_list
[docs] def execute(self, front: List[S]) -> S:
if front is None:
raise Exception('The front is null')
elif len(front) == 0:
raise Exception('The front is empty')
elif not self.comparator_list:
raise Exception('The comparators\' list is empty')
winner = None
if len(front) == 1:
winner = front[0]
else:
for comparator in self.comparator_list:
winner = self.__winner(front, comparator)
if winner is not None:
break
if not winner:
i = random.randrange(0, len(front))
winner = front[i]
return winner
def __winner(self, front: List[S], comparator: Comparator):
# Sampling without replacement
i, j = random.sample(range(0, len(front)), 2)
solution1 = front[i]
solution2 = front[j]
flag = comparator.compare(solution1, solution2)
if flag == -1:
result = solution1
elif flag == 1:
result = solution2
else:
result = None
return result
[docs] def get_name(self) -> str:
return 'Binary tournament selection (experimental)'
