Adapt - danielwilczak101/EasyGA GitHub Wiki
On its own, the GA will usually find good solutions quickly but struggle to improve the solutions, especially over large search spaces. To help it overcome this, an adapt function is built-in and broken down into two parts. The first part adapts the probabilities to help encourage better crossover or mutations to find the last solution. The second part adapts the population so that the chromosomes are not too far apart (largely useless) or too close (cannot help produce new values).
Adapt probabilities tends to be useful in general, where the best probabilities are not known or may change depending on the population.
Adapt population tends to be useful for problems where an accurate distance between chromosomes may be defined and a weighted crossover method is capable of accurately producing chromosomes which are a weighted combination of their distances.
ga.adapt() # Adapts both probabilities and population
ga.adapt_probabilities() # Modifies the selection probability and mutation rates
ga.adapt_population() # Modifies the chromosomes in the population
Code:
def adapt(self):
"""Adapts the ga to hopefully get better results."""
self.adapt_probabilities()
self.adapt_population()
Adapt Rate
The adapt rate determines the frequency the ga will adapt. The default is 0.05, or adapting for 5% of the generations (every 20th generation). An adapt rate of either 0 or None will disable adapting.
ga.adapt_rate = 0.05 # Default
Distance
The distance between two chromosomes is used to determine how similar two chromosomes are. The default distance method is defined using the square root of the differences of the fitness values.
# Default
ga.dist = lambda chromosome_1, chromosome_2:\
math.sqrt(abs(chromosome_1.fitness - chromosome_2.fitness))
# Useful for numerical problems:
ga.dist = lambda chromosome_1, chromosome_2:\
math.sqrt(sum((gene_1.value - gene_2.value)**2 for gene_1, gene_2 in zip(chromosome_1, chromosome_2)))
Adapt Probabilities
Adapt probabilities will modify the selection probability and mutation rates in an attempt to balance out the population. If too many chromosomes are close together, the mutation rates are increased to encourage new values and the selection probability is lowered to encourage crossing with the mutated chromosomes. If too many chromosomes are far apart, the mutation rates are decreased since the chromosomes are already different and the selection probability is raised to encourage making the population more similar to the best chromosomes.
def adapt_probabilities(self):
"""Modifies the parent ratio and mutation rates
based on the adapt rate and percent converged.
Attempts to balance out so that a portion of the
population gradually approaches the solution.
"""
# Don't adapt
if self.adapt_probability_rate is None or self.adapt_probability_rate <= 0:
return
# Amount of the population desired to converge (default 50%)
amount_converged = round(self.percent_converged*len(self.population))
# Difference between best and i-th chromosomes
best_chromosome = self.population[0]
tol = lambda i: self.dist(best_chromosome, self.population[i])
# Too few converged: cross more and mutate less
if tol(amount_converged//2) > tol(amount_converged//4)*2:
self.selection_probability = sum((
self.adapt_probability_rate * self.max_selection_probability,
(1-self.adapt_probability_rate) * self.selection_probability
))
self.chromosome_mutation_rate = sum((
self.adapt_probability_rate * self.min_chromosome_mutation_rate,
(1-self.adapt_probability_rate) * self.chromosome_mutation_rate
))
self.gene_mutation_rate = sum((
self.adapt_probability_rate * self.min_gene_mutation_rate,
(1-self.adapt_probability_rate) * self.gene_mutation_rate
))
# Too many converged: cross less and mutate more
else:
self.selection_probability = sum((
self.adapt_probability_rate * self.min_selection_probability,
(1-self.adapt_probability_rate) * self.selection_probability
))
self.chromosome_mutation_rate = sum((
self.adapt_probability_rate * self.max_chromosome_mutation_rate,
(1-self.adapt_probability_rate) * self.chromosome_mutation_rate
))
self.gene_mutation_rate = sum((
self.adapt_probability_rate * self.max_gene_mutation_rate,
(1-self.adapt_probability_rate) * self.gene_mutation_rate
))
Adapt Probability Rate
The adapt probability rate determines how quickly the selection probability and mutation rates or modified. The smaller the value, the slower the probabilities are changed, and the higher the value, the faster the probabilities are changed. The adapt probability rate must be between 0 and 1. If the rate is set to 0 or None then nothing is changed.
ga.adapt_probability_rate = 0.05 # Default
Min/Max Rates
To avoid changing the initial rates too drastically, the rates may be bounded.
# Defaults
ga.max_selection_probability = 0.75
ga.min_selection_probability = 0.25
ga.max_chromosome_mutation_rate = min(ga.chromosome_mutation_rate*2, (1+ga.chromosome_mutation_rate)/2)
ga.min_chromosome_mutation_rate = ga.chromosome_mutation_rate/2
ga.max_gene_mutation_rate = 1.00
ga.min_gene_mutation_rate = 0.00
Adapt Population
Adapt population uses the distance function to attempt to make most of the chromosomes in the population a useful distance from the best chromosome. Chromosomes which are too close to the best chromosome are pushed away to encourage genetic diversity. Chromosomes which are too far from the best chromosome are pulled in so that potentially useful genes are not ignored.
def adapt_population(self):
"""
Performs weighted crossover between the best chromosome and
the rest of the chromosomes, using negative weights to push
away chromosomes that are too similar and small positive
weights to pull in chromosomes that are too different.
"""
# Don't adapt the population.
if self.adapt_population_flag == False:
return
# Amount of the population desired to converge (default 50%)
amount_converged = round(self.percent_converged*len(self.population))
# Difference between best and i-th chromosomes
best_chromosome = self.population[0]
tol = lambda i: self.dist(best_chromosome, self.population[i])
# First non-zero tolerance after amount_converged/4
for i in range(amount_converged//4, len(self.population)):
if (tol_i := tol(i)) > 0:
break
# First significantly different tolerance
for j in range(i, len(self.population)):
if (tol_j := tol(j)) > 2*tol_i:
break
# Strongly cross the best chromosome with the worst chromosomes
for n in range(i, len(self.population)):
# Strongly cross with the best chromosome
# May reject negative weight or division by 0
try:
self.population[n] = self.crossover_individual_impl(
self,
self.population[n],
best_chromosome,
min(0.25, 2 * tol_j / (tol(n) - tol_j))
)
# If negative weights can't be used,
# Cross with j-th chromosome instead
except:
self.population[n] = self.crossover_individual_impl(
self,
self.population[n],
self.population[j],
0.75
)
# Update fitnesses
self.population[n].fitness = self.fitness_function_impl(self.population[n])
# Update best chromosome
if self.target_fitness_type == 'max':
cond = (self.population[n].fitness > best_chromosome.fitness)
if self.target_fitness_type == 'min':
cond = (self.population[n].fitness < best_chromosome.fitness)
if cond:
tol_j = tol(j)
best_chromosome = self.population[n]
self.population.sort_by_best_fitness(self)
Adapt Population Flag
The adapt population flag allows one to enable or disable the adapt population method. The flag is set to true by default, but if the flag is set to false then the population will not be adapted.
ga.adapt_population_flag = True # Default