Implementation of genetic algorithm.
Project description
hello-genetic-algorithm
A basic implementation of genetic algorithm. It fits for small scale experiments like college labs or GA beginners.
Use this command to install
pip install hello-genetic-algorithm
Algorithm Parameters
- Essential parameters (must set up by user)
- Individual class
- Fitness function
- Optional parameters (with default value if not set)
- Mutation ratio
- Crossover
- Constraints
- Selection ratio
- Execution parameters (config stop criteria or logging level)
- Max iteration
- Max generation
- Environment Capacity
- Logging level
Introduction by example
Formulate the Problem
Assume we have 12 goods to be packed into a travel suitcase. The suitcase can hold at list 250 kg goods. We have measured the weights for each of the goods and define importance so that we should packed more important goods as much as possible in the limit of weight constraint.
Define the chromosome as a 0-1 vector to represent each box. The problem is to find out a vector that maximize sum of box Importance where sum of box Weights are less than or equal to 250. eq.
$$ \max \sum_{i}{I_i} \quad where \quad i \in {0, \dots, 11} $$
$$ s.t. \sum_{i}{W_i} <= 250 $$
Formulation to parameters
This formulation can be mapping to
- a
BinaryIndividual
class to represent whether to select a goods - a predefined
WeightedSumFitness
: - a user-defined
constraints
: total weights of goods should be less or equal to 250.
Algorithm Steps
- Initialize: input parameters and create algorithm instance
- Calculate fitness: calculate fitness value for every individual
- Select: keep only the individuals fulfill the constrants
- Reproduce: generate new individuals by mutation and crossover operator
- Exit criteria: check if stop criteria is fulfilled. If yes, stop the progress, otherwise repeat from step 2.
Example Code
from helloga.environment import Environment
from helloga.individual import BinaryIndividual
from helloga.crossover import SinglePointCrossOver
from helloga.selector import LeadingSelector
from helloga.fitness import WeightedSumFitness
# Define fitness importence and contraint weights
box_importance = [6, 5, 8, 7, 6, 9, 4, 5, 4, 9, 2, 1]
box_weights = [20, 30, 60, 90, 50, 70, 30, 30, 70, 20, 20, 60]
# Define constraints
def total_size_lt250(individual, size=np.array([])) :
def total_size(individual, size=np.array([])) :
chr_arr = np.array(individual.chromosome)
siz_arr = np.array(size)
total = np.dot(chr_arr, siz_arr.T)
return total
total = total_size(individual, size)
return total <= 250
# Initialize by random individuals.
# Each element in the vector represents whether to select the i-th goods or not
individuals = [
BinaryIndividual([1,1,1,0,0,0,0,0,0,0,0,1],0,0),
BinaryIndividual([1,0,0,0,1,0,0,0,0,0,0,1],0,0),
BinaryIndividual([0,0,0,0,0,1,1,0,0,1,0,0],0,0),
BinaryIndividual([0,0,1,0,0,0,0,0,1,0,0,1],0,0),
BinaryIndividual([0,1,0,0,1,0,0,0,0,0,0,1],0,0),
]
# Define selector
sel = LeadingSelector(
ratio = 0.5,
constraints=[lambda x: total_size_lt250(x, box_weights)]
)
# Define fitness function
fit = WeightedSumFitness(weights = box_importance)
# Define selector
xo = SinglePointCrossOver()
# Create environment
env = Environment(
individuals,
selector=sel,
crossover=xo,
fitness_func=fit,
MAX_GENERATION=50,
CAPACITY=100,
MAX_ITERATION=100,
log_level='info'
)
# Run genetic algorithm
env.evolute()
# Print population and generation after the algorithm stopped
print(env.species.population(), env.species.generations())
# Print best 3 solutions to the problem
print('The best 3 solutions are: ')
for sol in env.getSolution(3) :
print(sol)
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 Distributions
Built Distribution
Hashes for hello_genetic_algorithm-1.0.3-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dc5f612d151450b31affcab6676db05faec81f611512573474ccd542169c8c85 |
|
MD5 | b1b1922750cea5eae33589f1007f8efd |
|
BLAKE2b-256 | f2a113a99b12a280f6adec955b54ac493e7ccd876d76b55045e9b41e0e58bda0 |