A lightweight genetic algorithm package for optimization
Project description
Genetic Algorithm Class
Now as package: last version
Python implementation of a genetic algorithm to solve optimization problems with n
control variables.
Description
A genetic algorithm (GA) is a search heuristic part of a broader family of algorithms called evolutionary algorithms (EAs). EAs are population-based metaheuristics that integrate mechanisms inspired by biological evolution such as reproduction, mutation, selection. The GA algorithm is used particularly in optimization problems where calculating gradients of an objective function is problematic or not possible.
Steps in GA
- Initialization: initialize a population of individuals or candidate solutions to the problem. This initialization can be done by means of random sampling. Each individual is defined by an encoding which we call genes.
- Selection: calculate the best candidates based on a defined fitness function we want to optimize. We select the best
j
parents which will be combined. The parameterj
is arbitrary. - Crossover: we combine the genes of the parents to produce an offspring. These are
s
new individuals in our population. - Mutation: add randomness to the generated offspring. We can add e.g. a Gausian noise to one of the genes of the offspring for each individual.
- Replacement: select the
l
fittest individuals of the population to evaluate on the next epoch.
We repeat these evolution steps for certain amount of epochs or until an exit condition is met.
GA implementation
Dependencies
- Numpy >= 1.18
Hyperparameters
-
Individuals:
lower_bound
upper_bound
number_of_genes
: dimension of the search space. In this implementation it indicates the shape of the array that represents each individual.
Note: The number of genes of each individual and the fitness function must be congruent -
Population:
n_parents
:j
parents.offspring_size
: thes
new individuals from combiningj
parents.mutation_mean
,mutation_sd
: mean and standard deviation of the Gaussian noise added during the mutation step.size
: maximum size of the population orl
fittest individuals to survive for the next epoch.
-
Evolution:
epochs
: number of times we repet each evolution step.
Example
An example fitness function could be something like this:
def fitness(x, y):
return x*(x-1)*np.cos(2*x-1)*np.sin(2*x-1)*(y-2)
We can limit our search to evaluate individuals within the domain with the ind_parameters
dictionary. Likewise, we control the population parameters with the pop_parameters
.
# example.py
import numpy as np
from ga.evolution import Evolution
# Define a fitness function
def fitness(x, y):
return x * (x - 1) * np.cos(2 * x - 1) * np.sin(2 * x - 1) * (y - 2)
# Define parameter for each individual
ind_parameters = {'lower_bound': -2,
'upper_bound': 2,
'number_of_genes': 2}
# Define parameter for the entire population
pop_parameters = {'n_parents': 6,
'offspring_size':(2, ind_parameters['number_of_genes']),
'mutation_mean': 0.25,
'mutation_sd': 0.5,
'size': 10}
def example():
# Instantiate an evolution
evo = Evolution(pop_parameters, ind_parameters, fitness)
# Repeat evolution step 200 epochs
epochs = 10000
# Record fitness history
history = []
x_history = []
y_history = []
for _ in range(epochs):
print('Epoch {}/{}, Progress: {}%\r'.format(_+1, epochs, np.round(((_+1)/epochs)*100, 2)), end="")
evo.step()
history.append(evo._best_score)
x_history.append(evo._best_individual[0][0])
y_history.append(evo._best_individual[0][1])
print('\nResults:')
print('Best individual:', evo.solution.best_individual)
print('Fitness value of best individual:', evo.solution.best_score)
example()
The results are really close to the global optimum within this domain and the best individual does not change after 50 epochs.
# Output
Epoch 200/200, Progress 100.0%
Results:
Best individual: [-1.52637873, -2. ]
Fitness value of best individual: 7.4697265870418414
References
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for generic-algorithm-light-0.0.0.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | bd5198d16792d6419d26f2d1fab6bdb37f41a662f5b1a7063b0e2a7e6f9ef019 |
|
MD5 | 728ce8334cc93ab9c7ae1d39f4c96593 |
|
BLAKE2b-256 | 135d442246d729723c0b10bc49f26ab2a887a2a9ad7b86999abbf6521d9410b2 |
Hashes for generic_algorithm_light-0.0.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b6f6535d66e44803061e050cabe08009c2712a3c15d3533004a75e1254fdf229 |
|
MD5 | cf33f64cb4f6899f83b3e1aed6e026cc |
|
BLAKE2b-256 | 6e2f78a5f93fc625f80777dc34030086f542fac53335f753ba2156bdee1e2360 |