GeneticAlgorithm

class auxjad.GeneticAlgorithm(*, target: list, genes: list, initial_individual: Optional[list] = None, population_size: int = 100, select_n_parents: int = 10, keep_n_parents: int = 0, mutation_chance: float = 0.2, mutation_index: float = 0.1, evaluation_index: float = 0.2)

An implementation of a genetic algorithm. Takes a target list and a list of genes to prod`uce generations of individuals at each __call__(). Fittest individual of the current generation can be accessed directly using the property fittest_individual.

Basic usage:

The genetic algorithm should be initialised with two list’s of objects. The elements of these list can be of any type. The first one is the target list used to evaluate the individuals in the population. The second is the genes list which should contain all possible elements that can make up an individual. All elements of target must also be present in genes. For this example, population_size will be set to a very small value of 4, though in practice it’s better to use substantially larger numbers (default value is 100). select_n_parents also needs to be decreased, as it must always be smaller than population_size.

>>> ga = auxjad.GeneticAlgorithm(
...     target=['A', 'B', 'C', 'D', 'E'],
...     genes=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'],
...     population_size=4,
...     select_n_parents=2,
... )

Calling the GA generator will generate a population of individuals, each of wich will also be awarded a score according to an evaluation function. population and scores are always ordered from the fittest to the least fit.

>>> ga()
>>> ga.population
[['A', 'J', 'J', 'B', 'H'],
 ['D', 'A', 'E', 'A', 'F'],
 ['F', 'F', 'A', 'F', 'F'],
 ['F', 'F', 'E', 'J', 'C'],
 ]
>>> ga.scores
[0.209603072,
 0.0912,
 0.05638400000000001,
 0.016396800000000003,
 ]

Each subsequent call will generate a new generation of individuals which will become increasingly fit.

fittest_individual and fittest_individual_score:

The fittest individual of the whole population can be directly accessed using the property fittest_individual:

>>> ga = auxjad.GeneticAlgorithm(
...     target=['A', 'B', 'C', 'D', 'E'],
...     genes=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'],
...     population_size=4,
...     select_n_parents=2,
... )
>>> ga()
>>> ga.fittest_individual
['A', 'J', 'J', 'B', 'H']

Its score is also directly accessible using fittest_individual_score:

>>> ga.fittest_individual_score
0.209603072

Evolution:

As expected, each generation will become increasingly fitter in relation to the target. The example below shows the fittest individual of each of 10 generations, with a population_size to 50:

>>> ga = auxjad.GeneticAlgorithm(
...     target=['A', 'B', 'C', 'D', 'E'],
...     genes=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'],
...     population_size=50,
... )
>>> for _ in range(10):
...     ga()
...     print(ga.fittest_individual, ga.fittest_individual_score)
['A', 'J', 'B', 'E', 'E'] 0.480000512
['A', 'H', 'C', 'D', 'J'] 0.6000768
['A', 'C', 'D', 'D', 'E'] 0.6799999999999999
['A', 'C', 'D', 'D', 'E'] 0.6799999999999999
['A', 'C', 'D', 'D', 'E'] 0.6799999999999999
['A', 'C', 'C', 'D', 'E'] 0.8400000000000001
['A', 'C', 'C', 'D', 'E'] 0.8400000000000001
['A', 'C', 'C', 'D', 'E'] 0.8400000000000001
['A', 'C', 'C', 'D', 'E'] 0.8400000000000001
['A', 'C', 'C', 'D', 'E'] 0.8400000000000001

Evaluation function and evaluation_index:

The evaluation function gives out a score between 0.0 to 1.0 to each individual in the population. For each given individual, this function compares each element of its elements with the element in the target at the same index. As to accomodate arbitrary objects being used as genes (as opposed to numbers only), this comparison uses the distance between the current individual and target genes using the genes property. Consider the following example, where the available genes are ['A', 'B', 'C', 'D', 'E', 'F'] and the target is ['B', 'A', 'A', 'C']. Suppose an individual has the genes ['D', 'D', 'A', 'B'].

To evaluate this individual, first the algorithm finds the indices of both the target’s genes (in this case, [1, 0, 0, 2]) and also of the individual to be evaluated (in this case, [3, 3, 0, 1]). It then scores each element of this individual against the target using:

difference = abs(target_gene_index - individual_gene_index)
element_score = evaluation_index ** difference

Thus, when the difference is 0, the score of this element is 1.0. The higher the difference, the smaller the value; this decay can be controlled using the property evaluation_index, whose default value is 0.2. Thus when the difference is 1 or -1, the score is 0.2 ** 1 = 0.2, when the difference is 2 or -2, the score is 0.2 ** 2 = 0.04, and so on. The total score of an individual will be given by the normalised sum of the evaluation of each of its genes.

select_n_parents and keep_n_parents:

When creating a new generation of individuals, the algorithm will select the fittest individuals to be parents for the next generation. The number of parents is given by select_n_parents, whose default value is 10. These parents generate offspring by being recombined through a crossover process, in which the first half of a random parent and a second half of another random parent are combined into a new individual. Parents are not kept in the next generation by default and are solely used in this crossover process. To ‘clone’ parents into the next generation, set the property keep_n_parents to a value larger than 0 (its default value).

mutation_chance and mutation_index:

After the crossover process, an individual can go through random mutations. The chance of this occuring on a given individual is given by mutation_chance, whose value should range between 0.0 and 1.0 (default is 0.2). If an individual is selected to undergo a random mutation, then each of its genes will have a chance of being mutated, which in turn is given by the property mutation_index (default value is 0.1).

initial_individual:

Instead of starting with a random population of individuals, it’s possible to set a custom initial individual as a starting point. This can be used to ‘morph’ fittest individual from this initial one to a fit one according to the target.

>>> ga = auxjad.GeneticAlgorithm(
...     target=['A', 'B', 'C', 'D', 'E'],
...     genes=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'],
...     initial_individual=['F', 'G', 'H', 'I', 'J'],
... )
>>> for _ in range(10):
...     ga()
...     ga.fittest_individual
['F', 'G', 'H', 'I', 'J']
['F', 'B', 'H', 'I', 'J']
['F', 'B', 'H', 'I', 'E']
['F', 'B', 'H', 'I', 'E']
['A', 'B', 'H', 'I', 'E']
['A', 'B', 'E', 'I', 'E']
['A', 'B', 'E', 'D', 'E']
['A', 'B', 'E', 'D', 'E']
['A', 'B', 'E', 'D', 'E']
['A', 'B', 'D', 'D', 'E']

reset():

Use the reset() method to reset the genetic algorithm at any point:

>>> ga = auxjad.GeneticAlgorithm(
...     target=['A', 'B', 'C', 'D', 'E'],
...     genes=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'],
... )
>>> ga.fittest_individual
None
>>> ga.generation_number
None
>>> for _ in range(10):
...     ga()
>>> ga.fittest_individual
['C', 'B', 'C', 'D', 'E']
>>> ga.generation_number
9
>>> ga.reset()
>>> ga.fittest_individual
None
>>> ga.generation_number
None

Methods

__call__()	Calls the genetic algorithm process for one iteration.
__init__(*, target, genes[, …])	Initialises self.
__iter__()	Returns an iterator, allowing instances to be used as iterators.
__len__()	Returns the number of genes in each individual.
__next__()	Calls the genetic algorithm process for one iteration.
__repr__()	Returns interpreter representation of target.
reset()	Resets that genetic algorithm.

Attributes

evaluation_index	The index used in the evaluation function.
fittest_individual	Read-only property, returns the fittest individual of the current population.
fittest_individual_score	Read-only property, returns the score of the fittest individual of the current population.
generation_number	Read-only property, returns the number of the current generation (initial generation is 0).
genes	List of possible genes that make up all individuals.
initial_individual	Optional initial individual (instead of random initial population).
keep_n_parents	Number of the best-fit individuals that survive into the next generation.
mutation_chance	The chance of any given individual experiencing mutation.
mutation_index	Given an individual selected to undergo mutation, this index gives the percentage of genes of that individual which will be mutated.
population	Read-only property, returns a list with all the population of the current generation.
population_size	Number of individuals in any given generation.
scores	Read-only property, returns the list of individual scores of the current population.
select_n_parents	Number of the best-fit individuals that are selected to be the parents for the next generation.
target	Target individual used for evaluation.

__call__() → None

Calls the genetic algorithm process for one iteration. Creates a new generation of length population_size via reproduction and mutation processes and scores each individual using the evaluation function. Sorts the population according to their scores.

__init__(*, target: list, genes: list, initial_individual: Optional[list] = None, population_size: int = 100, select_n_parents: int = 10, keep_n_parents: int = 0, mutation_chance: float = 0.2, mutation_index: float = 0.1, evaluation_index: float = 0.2) → None

Initialises self.

__iter__() → None

Returns an iterator, allowing instances to be used as iterators.

__len__() → int

Returns the number of genes in each individual.

__next__() → None

Calls the genetic algorithm process for one iteration. Creates a new generation of length population_size via reproduction and mutation processes and scores each individual using the evaluation function. Sorts the population according to their scores.

__repr__() → str

Returns interpreter representation of target.

property evaluation_index: float

The index used in the evaluation function. This index will be raised by the difference between indices of the target value and the current value. Consider the following example, where the available genes are ['A', 'B', 'C', 'D', 'E', 'F'] and the target is ['B', 'A', 'A', 'C']. Suppose an individual has the genes ['D', 'D', 'A', 'B'].

To evaluate this individual, first the algorithm finds the indices of both the target’s genes (in this case, [1, 0, 0, 2]) and also of the individual to be evaluated (in this case, [3, 3, 0, 1]). It then scores each element of this individual against the target using:

difference = abs(target_gene_index - individual_gene_index)
element_score = evaluation_index ** difference

Thus, when the difference is 0, the score of this element is 1.0. The higher the difference, the smaller the value; this decay can be controlled using this very property, whose default value is 0.2. Thus when the difference is 1 or -1, the score is 0.2 ** 1 = 0.2, when the difference is 2 or -2, the score is 0.2 ** 2 = 0.04, and so on. The total score of an individual will be given by the normalised sum of the evaluation of each of its genes.

property fittest_individual: Optional[list]

Read-only property, returns the fittest individual of the current population.

property fittest_individual_score: Union[list, float]

Read-only property, returns the score of the fittest individual of the current population.

property generation_number: Optional[int]

Read-only property, returns the number of the current generation (initial generation is 0).

property genes: list

List of possible genes that make up all individuals.

property initial_individual: Optional[list]

Optional initial individual (instead of random initial population).

property keep_n_parents: int

Number of the best-fit individuals that survive into the next generation. Default is 0.

property mutation_chance: float

The chance of any given individual experiencing mutation.

property mutation_index: float

Given an individual selected to undergo mutation, this index gives the percentage of genes of that individual which will be mutated.

property population: Optional[list]

Read-only property, returns a list with all the population of the current generation.

property population_size: int

Number of individuals in any given generation.

reset() → None

Resets that genetic algorithm.

property scores: list

Read-only property, returns the list of individual scores of the current population. Scores are normalised.

property select_n_parents: int

Number of the best-fit individuals that are selected to be the parents for the next generation.

property target: list

Target individual used for evaluation.