import copy
import random
from typing import List
from jmetal.core.operator import Crossover
from jmetal.core.solution import (
BinarySolution,
CompositeSolution,
FloatSolution,
IntegerSolution,
PermutationSolution,
Solution,
)
from jmetal.util.ckecking import Check
"""
.. module:: crossover
:platform: Unix, Windows
:synopsis: Module implementing crossover operators.
.. moduleauthor:: Antonio J. Nebro <antonio@lcc.uma.es>, Antonio Benítez-Hidalgo <antonio.b@uma.es>
"""
[docs]
class NullCrossover(Crossover[Solution, Solution]):
def __init__(self):
super(NullCrossover, self).__init__(probability=0.0)
[docs]
def execute(self, parents: List[Solution]) -> List[Solution]:
if len(parents) != 2:
raise Exception("The number of parents is not two: {}".format(len(parents)))
return parents
[docs]
def get_number_of_parents(self) -> int:
return 2
[docs]
def get_number_of_children(self) -> int:
return 2
[docs]
def get_name(self):
return "Null crossover"
[docs]
class PMXCrossover(Crossover[PermutationSolution, PermutationSolution]):
def __init__(self, probability: float):
super(PMXCrossover, self).__init__(probability=probability)
[docs]
def execute(self, parents: List[PermutationSolution]) -> List[PermutationSolution]:
if len(parents) != 2:
raise Exception("The number of parents is not two: {}".format(len(parents)))
offspring = copy.deepcopy(parents)
permutation_length = len(offspring[0].variables)
rand = random.random()
if rand <= self.probability:
cross_points = sorted([random.randint(0, permutation_length) for _ in range(2)])
def _repeated(element, collection):
c = 0
for e in collection:
if e == element:
c += 1
return c > 1
def _swap(data_a, data_b, cross_points):
c1, c2 = cross_points
new_a = data_a[:c1] + data_b[c1:c2] + data_a[c2:]
new_b = data_b[:c1] + data_a[c1:c2] + data_b[c2:]
return new_a, new_b
def _map(swapped, cross_points):
n = len(swapped[0])
c1, c2 = cross_points
s1, s2 = swapped
map_ = s1[c1:c2], s2[c1:c2]
for i_chromosome in range(n):
if not c1 < i_chromosome < c2:
for i_son in range(2):
while _repeated(swapped[i_son][i_chromosome], swapped[i_son]):
map_index = map_[i_son].index(swapped[i_son][i_chromosome])
swapped[i_son][i_chromosome] = map_[1 - i_son][map_index]
return s1, s2
swapped = _swap(offspring[0].variables, offspring[1].variables, cross_points)
mapped = _map(swapped, cross_points)
offspring[0].variables, offspring[1].variables = mapped
return offspring
[docs]
def get_number_of_parents(self) -> int:
return 2
[docs]
def get_number_of_children(self) -> int:
return 2
[docs]
def get_name(self):
return "Partially Matched crossover"
[docs]
class CXCrossover(Crossover[PermutationSolution, PermutationSolution]):
def __init__(self, probability: float):
super(CXCrossover, self).__init__(probability=probability)
[docs]
def execute(self, parents: List[PermutationSolution]) -> List[PermutationSolution]:
if len(parents) != 2:
raise Exception("The number of parents is not two: {}".format(len(parents)))
offspring = copy.deepcopy(parents[::-1])
rand = random.random()
if rand <= self.probability:
idx = random.randint(0, len(parents[0].variables) - 1)
curr_idx = idx
cycle = []
while True:
cycle.append(curr_idx)
curr_idx = parents[0].variables.index(parents[1].variables[curr_idx])
if curr_idx == idx:
break
for j in range(len(parents[0].variables)):
if j in cycle:
offspring[0].variables[j] = parents[0].variables[j]
offspring[1].variables[j] = parents[1].variables[j]
return offspring
[docs]
def get_number_of_parents(self) -> int:
return 2
[docs]
def get_number_of_children(self) -> int:
return 2
[docs]
def get_name(self):
return "Cycle crossover"
[docs]
class SBXCrossover(Crossover[FloatSolution, FloatSolution]):
__EPS = 1.0e-14
def __init__(self, probability: float, distribution_index: float = 20.0):
super(SBXCrossover, self).__init__(probability=probability)
self.distribution_index = distribution_index
if distribution_index < 0:
raise Exception("The distribution index is negative: " + str(distribution_index))
[docs]
def execute(self, parents: List[FloatSolution]) -> List[FloatSolution]:
Check.that(issubclass(type(parents[0]), FloatSolution), "Solution type invalid: " + str(type(parents[0])))
Check.that(issubclass(type(parents[1]), FloatSolution), "Solution type invalid")
Check.that(len(parents) == 2, "The number of parents is not two: {}".format(len(parents)))
offspring = copy.deepcopy(parents)
rand = random.random()
if rand <= self.probability:
for i in range(len(parents[0].variables)):
value_x1, value_x2 = parents[0].variables[i], parents[1].variables[i]
if random.random() <= 0.5:
if abs(value_x1 - value_x2) > self.__EPS:
if value_x1 < value_x2:
y1, y2 = value_x1, value_x2
else:
y1, y2 = value_x2, value_x1
lower_bound, upper_bound = parents[0].lower_bound[i], parents[1].upper_bound[i]
beta = 1.0 + (2.0 * (y1 - lower_bound) / (y2 - y1))
alpha = 2.0 - pow(beta, -(self.distribution_index + 1.0))
rand = random.random()
if rand <= (1.0 / alpha):
betaq = pow(rand * alpha, (1.0 / (self.distribution_index + 1.0)))
else:
betaq = pow(1.0 / (2.0 - rand * alpha), 1.0 / (self.distribution_index + 1.0))
c1 = 0.5 * (y1 + y2 - betaq * (y2 - y1))
beta = 1.0 + (2.0 * (upper_bound - y2) / (y2 - y1))
alpha = 2.0 - pow(beta, -(self.distribution_index + 1.0))
if rand <= (1.0 / alpha):
betaq = pow((rand * alpha), (1.0 / (self.distribution_index + 1.0)))
else:
betaq = pow(1.0 / (2.0 - rand * alpha), 1.0 / (self.distribution_index + 1.0))
c2 = 0.5 * (y1 + y2 + betaq * (y2 - y1))
if c1 < lower_bound:
c1 = lower_bound
if c2 < lower_bound:
c2 = lower_bound
if c1 > upper_bound:
c1 = upper_bound
if c2 > upper_bound:
c2 = upper_bound
if random.random() <= 0.5:
offspring[0].variables[i] = c2
offspring[1].variables[i] = c1
else:
offspring[0].variables[i] = c1
offspring[1].variables[i] = c2
else:
offspring[0].variables[i] = value_x1
offspring[1].variables[i] = value_x2
else:
offspring[0].variables[i] = value_x1
offspring[1].variables[i] = value_x2
return offspring
[docs]
def get_number_of_parents(self) -> int:
return 2
[docs]
def get_number_of_children(self) -> int:
return 2
[docs]
def get_name(self) -> str:
return "SBX crossover"
[docs]
class IntegerSBXCrossover(Crossover[IntegerSolution, IntegerSolution]):
__EPS = 1.0e-14
def __init__(self, probability: float, distribution_index: float = 20.0):
super(IntegerSBXCrossover, self).__init__(probability=probability)
self.distribution_index = distribution_index
[docs]
def execute(self, parents: List[IntegerSolution]) -> List[IntegerSolution]:
Check.that(issubclass(type(parents[0]), IntegerSolution), "Solution type invalid")
Check.that(issubclass(type(parents[1]), IntegerSolution), "Solution type invalid")
Check.that(len(parents) == 2, "The number of parents is not two: {}".format(len(parents)))
offspring = copy.deepcopy(parents)
rand = random.random()
if rand <= self.probability:
for i in range(len(parents[0].variables)):
value_x1, value_x2 = parents[0].variables[i], parents[1].variables[i]
if random.random() <= 0.5:
if abs(value_x1 - value_x2) > self.__EPS:
if value_x1 < value_x2:
y1, y2 = value_x1, value_x2
else:
y1, y2 = value_x2, value_x1
lower_bound, upper_bound = parents[0].lower_bound[i], parents[1].upper_bound[i]
beta = 1.0 + (2.0 * (y1 - lower_bound) / (y2 - y1))
alpha = 2.0 - pow(beta, -(self.distribution_index + 1.0))
rand = random.random()
if rand <= (1.0 / alpha):
betaq = pow(rand * alpha, (1.0 / (self.distribution_index + 1.0)))
else:
betaq = pow(1.0 / (2.0 - rand * alpha), 1.0 / (self.distribution_index + 1.0))
c1 = 0.5 * (y1 + y2 - betaq * (y2 - y1))
beta = 1.0 + (2.0 * (upper_bound - y2) / (y2 - y1))
alpha = 2.0 - pow(beta, -(self.distribution_index + 1.0))
if rand <= (1.0 / alpha):
betaq = pow((rand * alpha), (1.0 / (self.distribution_index + 1.0)))
else:
betaq = pow(1.0 / (2.0 - rand * alpha), 1.0 / (self.distribution_index + 1.0))
c2 = 0.5 * (y1 + y2 + betaq * (y2 - y1))
if c1 < lower_bound:
c1 = lower_bound
if c2 < lower_bound:
c2 = lower_bound
if c1 > upper_bound:
c1 = upper_bound
if c2 > upper_bound:
c2 = upper_bound
if random.random() <= 0.5:
offspring[0].variables[i] = int(c2)
offspring[1].variables[i] = int(c1)
else:
offspring[0].variables[i] = int(c1)
offspring[1].variables[i] = int(c2)
else:
offspring[0].variables[i] = value_x1
offspring[1].variables[i] = value_x2
else:
offspring[0].variables[i] = value_x1
offspring[1].variables[i] = value_x2
return offspring
[docs]
def get_number_of_parents(self) -> int:
return 2
[docs]
def get_number_of_children(self) -> int:
return 2
[docs]
def get_name(self) -> str:
return "Integer SBX crossover"
[docs]
class SPXCrossover(Crossover[BinarySolution, BinarySolution]):
def __init__(self, probability: float):
super(SPXCrossover, self).__init__(probability=probability)
[docs]
def execute(self, parents: List[BinarySolution]) -> List[BinarySolution]:
Check.that(type(parents[0]) is BinarySolution, "Solution type invalid")
Check.that(type(parents[1]) is BinarySolution, "Solution type invalid")
Check.that(len(parents) == 2, "The number of parents is not two: {}".format(len(parents)))
offspring = copy.deepcopy(parents)
rand = random.random()
if rand <= self.probability:
# 1. Get the total number of bits
total_number_of_bits = parents[0].get_total_number_of_bits()
# 2. Calculate the point to make the crossover
crossover_point = random.randrange(0, total_number_of_bits)
# 3. Compute the variable containing the crossover bit
variable_to_cut = 0
bits_count = len(parents[1].variables[variable_to_cut])
while bits_count < (crossover_point + 1):
variable_to_cut += 1
bits_count += len(parents[1].variables[variable_to_cut])
# 4. Compute the bit into the selected variable
diff = bits_count - crossover_point
crossover_point_in_variable = len(parents[1].variables[variable_to_cut]) - diff
# 5. Apply the crossover to the variable
bitset1 = copy.copy(parents[0].variables[variable_to_cut])
bitset2 = copy.copy(parents[1].variables[variable_to_cut])
for i in range(crossover_point_in_variable, len(bitset1)):
swap = bitset1[i]
bitset1[i] = bitset2[i]
bitset2[i] = swap
offspring[0].variables[variable_to_cut] = bitset1
offspring[1].variables[variable_to_cut] = bitset2
# 6. Apply the crossover to the other variables
for i in range(variable_to_cut + 1, len(parents[0].variables)):
offspring[0].variables[i] = copy.deepcopy(parents[1].variables[i])
offspring[1].variables[i] = copy.deepcopy(parents[0].variables[i])
return offspring
[docs]
def get_number_of_parents(self) -> int:
return 2
[docs]
def get_number_of_children(self) -> int:
return 2
[docs]
def get_name(self) -> str:
return "Single point crossover"
[docs]
class DifferentialEvolutionCrossover(Crossover[FloatSolution, FloatSolution]):
"""This operator receives two parameters: the current individual and an array of three parent individuals. The
best and rand variants depends on the third parent, according whether it represents the current of the "best"
individual or a random_search one. The implementation of both variants are the same, due to that the parent selection is
external to the crossover operator.
"""
def __init__(self, CR: float, F: float, K: float = 0.5):
super(DifferentialEvolutionCrossover, self).__init__(probability=1.0)
self.CR = CR
self.F = F
self.K = K
self.current_individual: FloatSolution = None
[docs]
def execute(self, parents: List[FloatSolution]) -> List[FloatSolution]:
"""Execute the differential evolution crossover ('best/1/bin' variant in jMetal)."""
if len(parents) != self.get_number_of_parents():
raise Exception("The number of parents is not {}: {}".format(self.get_number_of_parents(), len(parents)))
child = copy.deepcopy(self.current_individual)
number_of_variables = len(parents[0].variables)
rand = random.randint(0, number_of_variables - 1)
for i in range(number_of_variables):
if random.random() < self.CR or i == rand:
value = parents[2].variables[i] + self.F * (parents[0].variables[i] - parents[1].variables[i])
if value < child.lower_bound[i]:
value = child.lower_bound[i]
if value > child.upper_bound[i]:
value = child.upper_bound[i]
else:
value = child.variables[i]
child.variables[i] = value
return [child]
[docs]
def get_number_of_parents(self) -> int:
return 3
[docs]
def get_number_of_children(self) -> int:
return 1
[docs]
def get_name(self) -> str:
return "Differential Evolution crossover"
[docs]
class CompositeCrossover(Crossover[CompositeSolution, CompositeSolution]):
__EPS = 1.0e-14
def __init__(self, crossover_operator_list: [Crossover]):
super(CompositeCrossover, self).__init__(probability=1.0)
Check.is_not_none(crossover_operator_list)
Check.collection_is_not_empty(crossover_operator_list)
self.crossover_operators_list = []
for operator in crossover_operator_list:
Check.that(issubclass(operator.__class__, Crossover), "Object is not a subclass of Crossover")
self.crossover_operators_list.append(operator)
[docs]
def execute(self, solutions: List[CompositeSolution]) -> List[CompositeSolution]:
Check.is_not_none(solutions)
Check.that(len(solutions) == 2, "The number of parents is not two: " + str(len(solutions)))
offspring1 = []
offspring2 = []
number_of_solutions_in_composite_solution = len(solutions[0].variables)
for i in range(number_of_solutions_in_composite_solution):
parents = [solutions[0].variables[i], solutions[1].variables[i]]
children = self.crossover_operators_list[i].execute(parents)
offspring1.append(children[0])
offspring2.append(children[1])
return [CompositeSolution(offspring1), CompositeSolution(offspring2)]
[docs]
def get_number_of_parents(self) -> int:
return 2
[docs]
def get_number_of_children(self) -> int:
return 2
[docs]
def get_name(self) -> str:
return "Composite crossover"
