Getting Started with Python Genetic Algorithms
――I will write about the genetic algorithm as a study of the basic and simple parts. ――In order to deepen your understanding, we will actually write the code of the genetic algorithm in Python and move it in the form of solving some problems.
What is a genetic algorithm?
Genetic algorithm in English. The first appearance was proposed in 1975 by Professor John H. Holland of the University of Michigan.
-[Genetic Algorithm --Wikipedia](https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0) -[John H. Holland-Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%B8%E3%83%A7%E3%83%B3%E3%83%BBH%E3% 83% BB% E3% 83% 9B% E3% 83% A9% E3% 83% B3% E3% 83% 89)
To some extent, generate a large number of elements that are treated as "genes" and "chromosomes" with individual attributes for each individual, and generate the next generation until good results are obtained for the target problem while involving random elements It is an algorithm that repeats.
Like Darwin's theory of evolution (as if an individual who was able to adapt to survive well survives), fortunately, the elements that fit well to the problem are left to the next generation, or the elements that fit well are problematic. It will be the answer of.
There is no answer before executing the algorithm, and it is a calculation that searches for a matched answer while involving random elements, and it may be a little similar to reinforcement learning of unsupervised learning (the code itself is also a little similar). There are some parts that will be implemented, and there are various things in the reinforcement learning area).
What kind of calculation is it
In the following, one element will be referred to as a chromosome (Chromosome).
First, it randomly generates chromosomes. This number is arbitrary. The larger the number, the more calculations for one generation, while the more various conditions are generated in one generation, and the more variations there are.
The evaluation function then evaluates each element to determine what to do with the next generation. This merit function returns a value of how well it fits the problem. In machine learning, it's like an error function.
The content of the evaluation function is arbitrarily determined according to the problem. Biologically, for example, it is an index such as "how strong it is against the cold" or "how good the eyes are". For example, "How high is the score for a specific problem in a real problem?"
For the next generation, based on each element of the current generation, as an example, the following calculation will determine how to propagate the features to later generations (various adjustments and selections will be made in this area as well). I can do it).
** crossover **
Crossover leaves two chromosomes in the next generation in a way that inherits the characteristics of the two chromosomes in half. The calculation is such that half of the characteristics are inherited from the parents and two children are treated as the next generation.
** mutation **
Mutations leave chromosomes with completely unusual properties in some or most of the next generation.
It is used to prevent the remaining of similar chromosomes due to crossing, etc., and to reduce cases such as local solutions (such as biased and optimal answers not being given).
** Roulette wheel selection **
There is a method called roulette selection as a selection method when selecting two chromosomes at the time of transition to the next generation such as crossing.
This is a random selection in which the higher the performance of the evaluation function, the higher the probability of selection.
Depending on the performance of the evaluation function, the weight of the probability in random extraction is determined, and so on.
** tournament selection **
For tournament selection, a certain number is randomly extracted from the entire chromosome (for example, 100 is randomly extracted from 2000 chromosomes in total), and then the required number of high evaluation functions are selected (for example, by crossing). If necessary, 2) will be extracted.
** When to stop the calculation **
If the target value of the evaluation function is known, the number of generations may be set enormously until the value is obtained. For example, in the case of route search, if a condition such as "a route that can reach the goal within minutes" is OK, the calculation is completed when that condition is met.
Alternatively, if the target value is not known, the calculation is stopped when a certain number of generations are reached, and the attribute value of the chromosome with the maximum evaluation function value is used. This is a way to stop the calculation, such as "calculate for 200 generations and use the one with the best grade" because you do not know the clear answer or allowable value in advance.
What are the characteristics / when is it suitable?
As mentioned above, the genetic algorithm strongly involves random elements in many calculations. Therefore, the amount of calculation until the problem is solved changes every time it is executed.
In addition, there are cases where the solution is solved immediately, and there are cases where the answer cannot be reached for a long time. Basically, if there is an algorithm that is suitable for the problem, there are many cases where the amount of calculation is much smaller if you use it.
Even if you arrive at a solution that looks good, there may be cases where it is not the optimal solution.
On the other hand, it can be used for various purposes even in loose cases where the optimum algorithm cannot be thought of and you want to search for the answer exploratively.
As an example of a use case that is suitable based on these,
--A case where it is OK if an answer of about 80 points is required instead of 100 points (optimal solution) --Case where short calculation time is not required --Case where you can't think of a more optimal algorithm
And so on.
Implementation in Python
Let's try to solve some problems using a genetic algorithm.
What to use
- Python 3.8.5 --Pylance (for type check)
- Like other similar articles I wrote in the past, I will write using the built-in module without using a library etc. for studying.
Points to remember
As a suitable use case, I mentioned "a case where you can't think of a more optimal algorithm", but the problems mentioned in this article are intentionally simple problems for studying, or there are many more optimal solutions. We will respond to.
Keep in mind that using the best algorithm can take a long time to complete a quick calculation.
Import of required modules
First of all, we will import the built-in ones to be used.
from __future__ import annotations
from typing import TypeVar, List, Dict
from random import choices, random, randrange, shuffle
from heapq import nlargest
from abc import ABC, abstractmethod
from copy import deepcopy
from datetime import datetime
--Annotations are used because the type annotations that will be adopted in future Python versions will be available. --In order to use type annotation, we are importing what we need from the typing package. --choices is a function that randomly selects any number of iterable ones specified in the argument. It is used to select the next generation of individuals. You can also set the magnitude of the probability for each individual with the weight argument. --random is a function that gets random numbers in the range 0.0 to 1.0. --randrange is a function that randomly gets a value from the range of values that can be obtained when specified by range (such as randomly getting any of 0 to 9). --shuffle is a function that shuffles iterable elements. --nlargest is a function that fetches n large ones in order within the specified iterable element. It is used to extract the top individuals in tournament selection. --This time, in order to solve two problems, we are importing the one in the abc (abstract base class) package to use the abstract class. --Deepcopy, as the name implies, is a function that deep copies elements. We use deep copy when making next-generation individuals.
Definition of an abstract class of an individual
As mentioned above, this article will deal with two problems, so we will add an individual abstract class to inherit for each problem.
By adding @abstractmethod and a decorator, you can make the inherited class angry with an error unless you overwrite the method with the decorator.
class Chromosome(ABC):
"""
An abstract class that deals with chromosomes (one element of a genetic algorithm).
"""
@abstractmethod
def get_fitness(self) -> float:
"""
For the merit function Y to obtain the excellence of the chromosome for the problem of interest
Abstract method.
Returns
-------
fitness : float
Value of chromosomal excellence for the problem of interest. The higher the problem
It becomes a suitable chromosome.
It is also used to determine the end of a genetic algorithm.
"""
...
@classmethod
@abstractmethod
def make_random_instance(cls) -> Chromosome:
"""
Create an instance with random characteristics (attribute values)
Abstract method.
Returns
-------
instance : Chromosome
The generated instance.
"""
...
@abstractmethod
def mutate(self) -> None:
"""
An abstract method of processing that (suddenly) mutates chromosomes.
Random different value settings such as instance attributes are executed.
"""
...
@abstractmethod
def exec_crossover(self, other: Chromosome) -> List[Chromosome]:
"""
Crossover is executed with reference to another individual specified in the argument.
Parameters
----------
other : Chromosome
Another individual used in crossing.
Returns
-------
result_chromosomes : list of Chromosome
Two individuals (chromosomes) generated after crossing.
"""
...
def __lt__(self, other: Chromosome) -> bool:
"""
A function for comparing the value of the evaluation function, which is used for comparison between individuals.
Parameters
----------
other : Chromosome
Other individuals to be compared.
Returns
-------
result_bool : bool
Boolean value of whether or not the lesser condition is satisfied.
"""
return self.get_fitness() < other.get_fitness()
The evaluation function (get_fitness), mutation (mutate), and crossover (exec_crossover) interfaces required for the genetic algorithm are provided. Only the Ellipsis instance (...) is described and the others are omitted (overwrite with the inheritance destination).
Also, since it is necessary to generate the first generation before the algorithm starts, we have prepared a method called make_random_instance as a class method.
Since it is necessary to extract the value above the evaluation function value, the method of __lt__ is defined for comparison so that the evaluation function value is used for small comparison.
Definition of classes of genetic algorithms
We will define a class for the genetic algorithm.
C = TypeVar('C', bound=Chromosome)
class GeneticAlgorithm:
SelectionType = int
SELECTION_TYPE_ROULETTE_WHEEL: SelectionType = 1
SELECTION_TYPE_TOURNAMENT: SelectionType = 2
def __init__(
self, initial_population: List[C],
threshold: float,
max_generations: int, mutation_probability: float,
crossover_probability: float,
selection_type: SelectionType) -> None:
"""
A class that deals with genetic algorithms.
Parameters
----------
initial_population : list of Chromosome
First generation population (chromosomal group).
threshold : float
Threshold value used to judge problem solving. Individuals that exceed this value
The calculation ends when it occurs.
max_generations : int
Maximum number of generations to run in the algorithm.
mutation_probability : float
Mutation probability (0.0～1.0）。
crossover_probability : float
Crossover probability (0.0～1.0）。
selection_type : int
Selection method. Specify one of the following constant values.
- SELECTION_TYPE_ROULETTE_WHEEL
- SELECTION_TYPE_TOURNAMENT
"""
self._population: List[Chromosome] = initial_population
self._threshold: float = threshold
self._max_generations: int = max_generations
self._mutation_probability: float = mutation_probability
self._crossover_probability: float = crossover_probability
self._selection_type: int = selection_type
The place C = TypeVar ('C', bound = Chromosome) defines the type as generic (C of Chromosome).
When using it, if it is a subclass of Chromosome etc., it will be caught in the type check of Pylance (determined as subclass ≠ Chromosome class), so I am using it.
The bound argument is an argument that gives a constraint such as "OK if it is a Chromosome or a subclass of Chromosome".
Regarding the constructor, "first population" required by the algorithm, "threshold value of the evaluation function used to judge the stop of the algorithm", "upper limit of the number of generations", "mutation probability", "crossover probability", "selection method such as roulette selection" Is specified.
Other selection method constants are defined (for example, SELECTION_TYPE_ROULETTE_WHEEL: SelectionType = 1).
Implementation of roulette selection
We will add roulette selection processing to the GeneticAlgorithm class.
def _exec_roulette_wheel_selection(self) -> List[Chromosome]:
"""
Select two individuals (chromosomes) to be used for roulette selection and crossing.
get.
Returns
-------
selected_chromosomes : list of Chromosome
A list containing the two selected individuals (chromosomes). The selection process is an evaluation function
It is randomly extracted with the weight set by (fitness method).
Notes
-----
It cannot be used for problems where the value of the result of the evaluation function is negative.
"""
weights: List[float] = [
chromosome.get_fitness() for chromosome in self._population]
selected_chromosomes: List[Chromosome] = choices(
self._population, weights=weights, k=2)
return selected_chromosomes
In roulette selection, individuals are randomly selected, but the weight is set so that the one with the higher value obtained by the evaluation function has priority.
Regarding this weight, imagine the following roulette, assuming that there are five individuals A to E.
The value of the evaluation function of each individual is the area on the roulette. Individuals with a small area (individuals with a low evaluation by the evaluation function) can also be selected, but the probability is low.
Implementation of tournament selection
Similarly, we will add tournament selections to the GeneticAlgorithm class. Whether roulette selection or tournament selection is used depends on the selection_type specification in the constructor.
def _exec_tournament_selection(self) -> List[Chromosome]:
"""
Two individuals for tournament selection and crossing
Obtain (chromosome).
Returns
-------
selected_chromosomes : list of Chromosome
A list containing the two selected individuals (chromosomes). tournament
The top two individuals are extracted from the number of cases specified by the argument for
Set.
"""
participants_num: int = len(self._population) // 2
participants: List[Chromosome] = choices(self._population, k=participants_num)
selected_chromosomes: List[Chromosome] = nlargest(n=2, iterable=participants)
return selected_chromosomes
In tournament selection, we first extract the population used in the tournament. This time, half of the population is selected by hard coding.
Also, since the return value is 2 individuals, the top 2 individuals are extracted with the nlargest function. Since it is necessary to compare the elements in the list inside this function, it is necessary to set the method of __lt__ in the Chromosome class.
Implementation of transition processing to the next generation
Now we will add processing to the GeneticAlgorithm class to move from the current generation to the next generation.
As for what to do
-[1]. Extract two individuals according to the selection method (roulette selection, etc.) (named parents). -[2]. Change the two individuals extracted according to the crossover probability and mutation probability specified in the constructor (with random numbers and probabilities, if crossover etc. does not occur, set the parent individual as it is to the next generation ). -[3]. Add the two prepared individuals to the list of next-generation individuals. -[4]. Repeat [1]-[3] until the list of next-generation individuals is the same as the list of current-generation individuals.
It will be the process.
def _to_next_generation(self) -> None:
"""
Generated next-generation individuals (chromosomes) and generated attribute values for populations
Replace with the next generation population.
"""
new_population: List[Chromosome] = []
#The comparison of the number of cases is not equal, considering the case where the number of cases of the original population is odd.
#Judgment is made based on lesser conditions.
while len(new_population) < len(self._population):
parents: List[Chromosome] = self._get_parents_by_selection_type()
next_generation_chromosomes: List[Chromosome] = \
self._get_next_generation_chromosomes(parents=parents)
new_population.extend(next_generation_chromosomes)
#Due to the convenience of increasing the next-generation list by two, the number of cases is larger than the original list
#If there are many, remove them from the list and match the number of items in the list with the original list.
if len(new_population) > len(self._population):
del new_population[0]
self._population = new_population
def _get_next_generation_chromosomes(
self, parents: List[Chromosome]) -> List[Chromosome]:
"""
Treat as the next generation from the calculated list of two parental individuals
Get a list of two populations.
Cross or mutate with a certain probability, and if the probability is not satisfied, the value of the argument will be
It will be set as the next generation as it is.
Parameters
----------
parents : list of Chromosome
List of two individuals of the calculated parent
Returns
-------
next_generation_chromosomes : list of Chromosome
A list containing two individuals set as the next generation.
"""
random_val: float = random()
next_generation_chromosomes: List[Chromosome] = parents
if random_val < self._crossover_probability:
next_generation_chromosomes = parents[0].exec_crossover(
other=parents[1])
random_val = random()
if random_val < self._mutation_probability:
for chromosome in next_generation_chromosomes:
chromosome.mutate()
return next_generation_chromosomes
def _get_parents_by_selection_type(self) -> List[Chromosome]:
"""
Obtain a list of two parental individuals (chromosomes) according to the selection method.
Returns
-------
parents : list of Chromosome
A list of two individuals (chromosomes) of the acquired parent.
Raises
------
ValueError
When an unsupported selection method is specified.
"""
if self._selection_type == self.SELECTION_TYPE_ROULETTE_WHEEL:
parents: List[Chromosome] = self._exec_roulette_wheel_selection()
elif self._selection_type == self.SELECTION_TYPE_TOURNAMENT:
parents = self._exec_tournament_selection()
else:
raise ValueError(
'An unsupported selection method is specified: %s'
% self._selection_type)
return parents
Implementation of processing to run the algorithm
I will write a process that repeats the transition to the next generation until the value of the evaluation function exceeds the threshold value (≈ an individual that reaches the target value is born) or exceeds the upper limit of the number of generations.
In terms of machine learning, it's like a code for learning. It's like the epoch that generations call machine learning. The best individual for each generation is output as information by the print function.
However, the best individual corresponds to "the best individual of all generations". Please note that it is not a per-epoch value like machine learning.
def run_algorithm(self) -> Chromosome:
"""
An instance of an individual (chromosome) that executes a genetic algorithm and results in execution
To get.
Returns
-------
betst_chromosome : Chromosome
An individual of the algorithm execution result. Individuals that exceed the threshold value with the evaluation function
Or, if the threshold is not exceeded, the specified number of generations has been reached.
The individual with the highest evaluation function value at that time is set.
"""
best_chromosome: Chromosome = \
deepcopy(self._get_best_chromosome_from_population())
for generation_idx in range(self._max_generations):
print(
datetime.now(),
f'Number of generations: {generation_idx}'
f'Best individual information: {best_chromosome}'
)
if best_chromosome.get_fitness() >= self._threshold:
return best_chromosome
self._to_next_generation()
currrent_generation_best_chromosome: Chromosome = \
self._get_best_chromosome_from_population()
current_gen_best_fitness: float = \
currrent_generation_best_chromosome.get_fitness()
if best_chromosome.get_fitness() < current_gen_best_fitness:
best_chromosome = deepcopy(currrent_generation_best_chromosome)
return best_chromosome
def _get_best_chromosome_from_population(self) -> Chromosome:
"""
From the list of populations, select the individual (chromosome) with the highest evaluation function value.
get.
Returns
-------
best_chromosome : Chromosome
The individual with the highest evaluation function value in the list.
"""
best_chromosome: Chromosome = self._population[0]
for chromosome in self._population:
if best_chromosome.get_fitness() < chromosome.get_fitness():
best_chromosome = chromosome
return best_chromosome
Add a simple formula problem to check the operation and try it.
Let's create a simple problem and run the algorithm to confirm the implementation of the genetic algorithm.
We use the problem of finding x and y so that the values in the following expressions are maximized.
6x - x^2 + 4y - y^2
The answer is 13 when x = 3 and y = 2, which is the maximum.
For the purpose of checking the operation, as mentioned above, it is not necessary to use the genetic algorithm (rather, it is not preferable in terms of calculation time).
Inherit the Chromosome class, which is an abstract class prepared in advance.
class SimpleEquationProblem(Chromosome):
def __init__(self, x: int, y: int) -> None:
"""
The following simple formula for checking the operation of the genetic algorithm
6x - x^2 + 4 * y - y^2
A class that deals with the problem of finding the x and y values that maximize the value of.
(The correct answer is x= 3, y = 2）
Parameters
----------
x : int
Initial value of x.
y : int
Initial value of y.
"""
self.x = x
self.y = y
We will add evaluation functions. The higher the numerical value, the better the return value of the evaluation function is judged by the genetic algorithm, but since the problem this time is simply to find the larger values x and y, $ 6 x --x ^ 2 + 4y --y ^ Use the calculated value of 2 $.
def get_fitness(self) -> float:
"""
6x with current x and y values- x^2 + 4 * y - y^Of the calculation result of equation 2
A method used as an evaluation function to get a value.
Returns
-------
fitness : int
The value of the calculation result of the formula.
"""
x: int = self.x
y: int = self.y
return 6 * x - x ** 2 + 4 * y - y ** 2
The make_random_instance class method used during the first population generation should set x and y to random values between 0 and 99.
@classmethod
def make_random_instance(cls) -> SimpleEquationProblem:
"""
Of the SimpleEquationProblem class with a random initial value
Create an instance.
Returns
-------
problem : SimpleEquationProblem
The generated instance. x and y are random in the range 0-99
The value is set.
"""
x: int = randrange(100)
y: int = randrange(100)
problem = SimpleEquationProblem(x=x, y=y)
return problem
For the mutation, we calculated whether to add or subtract the value of x or y by 1.
def mutate(self) -> None:
"""
Mutate an individual (suddenly) (depending on the random number, the value of x or y
1 increase / decrease).
"""
value: int = choices([1, -1], k=1)[0]
if random() > 0.5:
self.x += value
return
self.y += value
I will write the crossover in the same way. The crossover inherits the characteristics of the two individuals in half, and returns two next-generation individuals.
def exec_crossover(
self, other: SimpleEquationProblem
) -> List[SimpleEquationProblem]:
"""
Crossover is executed with reference to another individual specified in the argument.
Parameters
----------
other : SimpleEquationProblem
Another individual used in crossing.
Returns
-------
result_chromosomes : list of SimpleEquationProblem
A list containing the two individuals generated after the crossover. Become a parent
It is an individual that inherits half the values of x and y from each individual.
"""
child_1: SimpleEquationProblem = deepcopy(self)
child_2: SimpleEquationProblem = deepcopy(other)
child_1.y = other.y
child_2.x = self.x
result_chromosomes: List[SimpleEquationProblem] = [
child_1, child_2,
]
return result_chromosomes
Since we want to output the best individual information for each generation during algorithm execution, write the processing for that in the __str__ method.
def __str__(self) -> str:
"""
Return the character string of individual information.
Returns
-------
info : str
A character string of individual information.
"""
x: int = self.x
y: int = self.y
fitness: float = self.get_fitness()
info: str = f'x = {x}, y = {y}, fitness = {fitness}'
return info
Let's move the problem of SimpleEquationProblem class
I will actually move it.
if __name__ == '__main__':
simple_equation_initial_population: List[SimpleEquationProblem] = \
[SimpleEquationProblem.make_random_instance() for _ in range(30)]
ga: GeneticAlgorithm = GeneticAlgorithm(
initial_population=simple_equation_initial_population,
threshold=13,
max_generations=100,
mutation_probability=0.2,
crossover_probability=0.3,
selection_type=GeneticAlgorithm.SELECTION_TYPE_TOURNAMENT)
_ = ga.run_algorithm()
We have selected 30 individuals, 100 maximum generations, 20% mutation probability, 30% crossover probability, and tournament selection method. Since each number is fixed, there is no particular reason to select it (select by atmosphere).
However, if the value of the evaluation function can be negative as shown below, roulette selection cannot be selected (for reasons such as weight), so tournament selection is specified.
** Roulette selection ** ... This method is the selection method used when Holland first proposed it, and it is the most famous selection method, but it is assumed that the fitness does not take a negative number. [Genetic Algorithm-Wikipedia](https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0 #% E3% 83% AB% E3% 83% BC% E3% 83% AC% E3% 83% 83 % E3% 83% 88% E9% 81% B8% E6% 8A% 9E)
Also, this time I know that the answer for the maximum value is 13, so I specified 13 as the threshold.
When executed, the output is as follows. As explained in the algorithm explanation section at the beginning, the genetic algorithm is highly random, so it may end immediately or it may require a large number of generations, and the result will change each time it is executed.
2020-10-31 19:24:39.948226 Number of generations:0 Best individual information: x = 14, y = 6, fitness = -124
2020-10-31 19:24:39.960250 Number of generations:1 Best individual information: x = 14, y = 5, fitness = -117
2020-10-31 19:24:39.961220 Number of generations:2 Best individual information: x = 13, y = 5, fitness = -96
2020-10-31 19:24:39.962218 Number of generations:3 Best individual information: x = 13, y = 4, fitness = -91
2020-10-31 19:24:39.975251 Number of generations:4 Best individual information: x = 12, y = 4, fitness = -72
2020-10-31 19:24:39.982250 Number of generations:5 Best individual information: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.982250 Number of generations:6 Best individual information: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.996219 Number of generations:7 Best individual information: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.997251 Number of generations:8 Best individual information: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.998224 Number of generations:9 Best individual information: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.999254 Number of generations:10 Best individual information: x = 11, y = 2, fitness = -51
2020-10-31 19:24:40.000221 Number of generations:11 Best individual information: x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.001250 Number of generations:12 Best individual information: x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.001250 Number of generations:13 Best individual information: x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.002251 Number of generations:14 Best individual information: x = 8, y = 2, fitness = -12
2020-10-31 19:24:40.003250 Number of generations:15 Best individual information: x = 8, y = 2, fitness = -12
2020-10-31 19:24:40.004217 Number of generations:16 Best individual information: x = 6, y = 2, fitness = 4
2020-10-31 19:24:40.005251 Number of generations:17 Best individual information: x = 6, y = 2, fitness = 4
2020-10-31 19:24:40.006252 number of generations:18 Best individual information: x = 5, y = 3, fitness = 8
2020-10-31 19:24:40.006252 number of generations:19 Best individual information: x = 5, y = 2, fitness = 9
2020-10-31 19:24:40.007219 Number of generations:20 Best individual information: x = 4, y = 2, fitness = 12
2020-10-31 19:24:40.008219 Number of generations:21 Best individual information: x = 3, y = 2, fitness = 13
This time, the answer of x = 3 and y = 2 is required for the 22nd generation, and it can be confirmed that the value of the evaluation function is 13 (this area is similar to learning deep learning). ..
Try to solve the problem of SEND + MORE = MONEY's verbal arithmetic
I confirmed that it works with a simple problem, so I will try to solve another problem with a slightly more complicated one.
We will deal with the SEND + MORE = MONEY problem, which is one of the so-called verbal arithmetic.
What is the SEND + MORE = MONEY problem?
It is a problem that makes the following calculation possible. Words such as SEND and MONEY have no particular meaning.
You can apply a number from 0 to 9 to each letter. For example, assign 3 to S, 5 to E, and so on (some patterns do not include 0 as an option, but in this article we will proceed by including 0 as an option).
However, you cannot assign the same number to another letter (you cannot set S to 8 and E to 8 as well).
A SEND value consisting of a 4-digit S value, a 3-digit E value, a 2-digit N, and a 1-digit D, and a 4-digit M, a 3-digit O, a 2-digit R, and a 1-digit D. A combination in which the sum of the MORE values consisting of E exactly matches the value of MONEY consisting of 5 digits M, 4 digits O, 3 digits N, 2 digits E, and 1 digit Y. The problem is to ask.
If the letters are the same, the numbers to be assigned will be the same. In other words, if you assign 8 to M of MORE, you have to set M of MONEY to 8.
SEND + MORE = Add class for MONEY problem
As with the SimpleEquationProblem class, we will add classes that inherit from the Chromosome class. The flow is almost the same as SimpleEquationProblem.
LetterDict = Dict[str, int]
class SendMoreMoneyProblem(Chromosome):
LETTERS: List[str] = ['S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y']
def __init__(self, letters_dict: LetterDict) -> None:
"""
SEND + MORE =MONEY's verbal arithmetic problem with a genetic algorithm
A class to solve.
Parameters
----------
letters_dict : LetterDict
Each of the eight characters (keys) used in the problem and the assigned numerical value (value)
A dictionary that stores the initial values of.
"""
self.letters_dict: LetterDict = letters_dict
This time, we will use a dictionary with the target character for the key and the number assigned to the value, so we defined a type alias named LetterDict.
We will add methods for the evaluation function to the SendMoreMoneyProblem class. The evaluation function is created by adding the number of digits to each character such as SEND, MORE, and MONEY, and the difference between the MONEY value and the total value of SEND + MORE is calculated.
def get_fitness(self) -> float:
"""
SEND with the number assigned to each current character+With MORE numbers
A method for the evaluation function based on the difference between the numerical values of MONEY.
Notes
-----
Because the value of the evaluation function of the genetic algorithm is highly evaluated,
The value is adjusted so that the larger the error, the lower the value.
Will be returned.
Returns
-------
fitness : int
SEND +Evaluation value based on the difference between the MORE value and the MONEY value.
The smaller the difference, the larger the value is set.
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
return 1 / (difference + 1)
def _get_send_val(self) -> int:
"""
Get the value of SEND by the numerical value of each character currently allocated.
Returns
-------
send_val : int
The value of SEND that is the numerical value of each character currently allocated.
"""
s: int = self.letters_dict['S']
e: int = self.letters_dict['E']
n: int = self.letters_dict['N']
d: int = self.letters_dict['D']
send_val: int = s * 1000 + e * 100 + n * 10 + d
return send_val
def _get_more_val(self) -> int:
"""
Gets the MORE value of each character that is currently allocated.
Parameters
----------
more_val : int
The value of MORE by the numerical value of each character currently allocated
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
r: int = self.letters_dict['R']
e: int = self.letters_dict['E']
more_val: int = m * 1000 + o * 100 + r * 10 + e
return more_val
def _get_money_val(self):
"""
Gets the value of MONEY based on the numerical value of each character currently assigned.
Returns
-------
money_val : int
The value of MONEY based on the numerical value of each character currently assigned.
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
n: int = self.letters_dict['N']
e: int = self.letters_dict['E']
y: int = self.letters_dict['Y']
money_val = m * 10000 + o * 1000 + n * 100 + e * 10 + y
return money_val
In the genetic algorithm, the larger the value, the better, but the smaller the difference, the better. Therefore, the return value is set to 1 / (difference + 1) so that the larger the difference, the smaller the value.
The + 1 part is a value to prevent division by zero from occurring. Since the minimum difference is 0, we can see that the maximum value of the merit function is 1/1, which is 1 (so the threshold when executing the algorithm is 1).
We will define the class method for instantiation. This is not difficult, just assigning each letter so that it does not cover the numbers 0-9.
@classmethod
def make_random_instance(cls) -> SendMoreMoneyProblem:
"""
Of the SendMoreMoneyProblem class with a random initial value
Create an instance.
Returns
-------
problem : SendMoreMoneyProblem
The generated instance. Each character has a range of 0-9
Values are set so that the numbers do not overlap.
"""
num_list: List[int] = list(range(10))
shuffle(num_list)
num_list = num_list[:len(cls.LETTERS)]
letters_dict: LetterDict = {
char: num for (char, num) in zip(cls.LETTERS, num_list)}
problem: SendMoreMoneyProblem = SendMoreMoneyProblem(
letters_dict=letters_dict)
return problem
I will write the processing of mutation. The mutation is also simple enough to change to another number so as not to cover one randomly selected letter.
def mutate(self) -> None:
"""
Mutate an individual (suddenly) (randomly assigned a specific letter value)
Replace with a number that does not exist).
"""
target_char: str = choices(self.LETTERS, k=1)[0]
not_assigned_num: int = self._get_not_assigned_num()
self.letters_dict[target_char] = not_assigned_num
def _get_not_assigned_num(self) -> int:
"""
Gets the number that is not assigned to each character.
Returns
-------
not_assigned_num : int
A number that is not assigned to each letter. While there are 8 letters,
Since there are 10 numbers from 0 to 9, there are 2 unallocated numbers,
One of them is set.
"""
values: list = list(self.letters_dict.values())
not_assigned_num: int = -1
for num in range(10):
if num in values:
continue
not_assigned_num = num
break
return not_assigned_num
Next, I will write the processing of crossing. I was wondering what to do with the crossover process, but I made the following contents.
-[1]. Copy the parent individual. -[2]. In each of the two child individuals, half each (4 characters each of SEND and MORY) can inherit the numerical values of different parents (however, due to duplication of numerical values, the allocation of letters and numerical values is the same. do not do). -[3]. If you cannot take over (when parents often use duplicate numbers), allocate the unallocated numbers.
def exec_crossover(
self,
other: SendMoreMoneyProblem) -> List[SendMoreMoneyProblem]:
"""
Crossover is executed with reference to another individual specified in the argument.
Parameters
----------
other : SendMoreMoneyProblem
Another individual used in crossing.
Returns
-------
result_chromosomes : list of SendMoreMoneyProblem
A list containing the two individuals generated after the crossover.
"""
child_1: SendMoreMoneyProblem = deepcopy(self)
child_2: SendMoreMoneyProblem = deepcopy(other)
for char in ('S', 'E', 'N', 'D'):
child_2.letters_dict[char] = self.\
_get_not_assigned_num_from_parent(
child=child_2,
parent=self,
)
for char in ('M', 'O', 'R', 'Y'):
child_1.letters_dict[char] = \
self._get_not_assigned_num_from_parent(
child=child_1,
parent=other,
)
result_chromosomes = [child_1, child_2]
return result_chromosomes
def _get_not_assigned_num_from_parent(
self, child: SendMoreMoneyProblem,
parent: SendMoreMoneyProblem) -> int:
"""
Among the numbers set for the parent, the numbers that have not yet been set for the child
get.
Notes
-----
Cases where selectable values cannot be found depending on the combination of parent and child numbers
In that case, the unallocated number among the values from 0 to 9 is
Set.
Parameters
----------
child : SendMoreMoneyProblem
Individual child.
parent : SendMoreMoneyProblem
Parental individual.
Returns
-------
not_assigned_num : int
Calculated, unallocated number.
"""
not_assigned_num: int = -1
for parent_num in parent.letters_dict.values():
child_nums: list = list(child.letters_dict.values())
if parent_num in child_nums:
continue
not_assigned_num = parent_num
if not_assigned_num == -1:
not_assigned_num = self._get_not_assigned_num()
return not_assigned_num
Finally, for the output of information for each generation, the individual information should be returned by the __str__ method.
def __str__(self) -> str:
"""
Return the character string of individual information.
Returns
-------
info : str
A character string of individual information.
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
info: str = (
f"\nS = {self.letters_dict['S']}"
f" E = {self.letters_dict['E']}"
f" N = {self.letters_dict['N']}"
f" D = {self.letters_dict['D']}"
f"\nM = {self.letters_dict['M']}"
f" O = {self.letters_dict['O']}"
f" R = {self.letters_dict['R']}"
f" Y = {self.letters_dict['Y']}"
f'\nSEND = {send_val}'
f' MORE = {more_val}'
f' MONEY = {money_val}'
f' difference : {difference}'
'\n--------------------------------'
)
return info
When passed through the print function etc., it will be output in the following format.
2020-10-31 20:51:15.345000 generations:5 Best individual information:
S = 4 E = 6 N = 1 D = 9
M = 0 O = 5 R = 3 Y = 2
SEND = 4619 MORE = 536 MONEY = 5162 difference : 7
Let's move the problem of SendMoreMoneyProblem class
Let's run a genetic algorithm to solve a problem in the SendMoreMoneyProblem class.
if __name__ == '__main__':
send_more_money_initial_population: List[SendMoreMoneyProblem] = \
[SendMoreMoneyProblem.make_random_instance() for _ in range(1000)]
ga = GeneticAlgorithm(
initial_population=send_more_money_initial_population,
threshold=1.0,
max_generations=1000,
mutation_probability=0.7,
crossover_probability=0.2,
selection_type=GeneticAlgorithm.SELECTION_TYPE_ROULETTE_WHEEL)
_ = ga.run_algorithm()
This time, the problem is more complicated than SimpleEquationProblem, so we have increased the number of individuals to 1000 (the calculation time will be longer accordingly).
The threshold is 1.0 when the error becomes 0 as mentioned in the evaluation function section. Since there may be cases where the problem cannot be solved, the maximum number of generations has been increased to 1000.
Since the value of the evaluation function does not become negative this time, roulette selection can be used, so it is a good idea to specify roulette selection.
When I moved it, the error became 0 in the 25th generation as shown below.
2020-10-31 20:51:33.663973 Number of generations:24 Best individual information:
S = 5 E = 7 N = 3 D = 1
M = 0 O = 6 R = 4 Y = 8
SEND = 5731 MORE = 647 MONEY = 6378 difference : 0
--------------------------------
The solution was found as $ 5731 + 647 = 6378 $. Since this combination holds for another combination, the execution result may be another combination. In addition, although the answer was sought in a relatively early generation this time, there are cases where more generations are needed because it depends on random results, and conversely, the answer can be found immediately in the third generation.
Whole code
from __future__ import annotations
from typing import TypeVar, List, Dict
from random import choices, random, randrange, shuffle
from heapq import nlargest
from abc import ABC, abstractmethod
from copy import deepcopy
from datetime import datetime
class Chromosome(ABC):
"""
An abstract class that deals with chromosomes (one element of a genetic algorithm).
"""
@abstractmethod
def get_fitness(self) -> float:
"""
For the merit function Y to obtain the excellence of the chromosome for the problem of interest
Abstract method.
Returns
-------
fitness : float
Value of chromosomal excellence for the problem of interest. The higher the problem
It becomes a suitable chromosome.
It is also used to determine the end of a genetic algorithm.
"""
...
@classmethod
@abstractmethod
def make_random_instance(cls) -> Chromosome:
"""
Create an instance with random characteristics (attribute values)
Abstract method.
Returns
-------
instance : Chromosome
The generated instance.
"""
...
@abstractmethod
def mutate(self) -> None:
"""
An abstract method of processing that (suddenly) mutates chromosomes.
Random different value settings such as instance attributes are executed.
"""
...
@abstractmethod
def exec_crossover(self, other: Chromosome) -> List[Chromosome]:
"""
Crossover is executed with reference to another individual specified in the argument.
Parameters
----------
other : Chromosome
Another individual used in crossing.
Returns
-------
result_chromosomes : list of Chromosome
Two individuals (chromosomes) generated after crossing.
"""
...
def __lt__(self, other: Chromosome) -> bool:
"""
A function for comparing the value of the evaluation function, which is used for comparison between individuals.
Parameters
----------
other : Chromosome
Other individuals to be compared.
Returns
-------
result_bool : bool
Boolean value of whether or not the lesser condition is satisfied.
"""
return self.get_fitness() < other.get_fitness()
C = TypeVar('C', bound=Chromosome)
class GeneticAlgorithm:
SelectionType = int
SELECTION_TYPE_ROULETTE_WHEEL: SelectionType = 1
SELECTION_TYPE_TOURNAMENT: SelectionType = 2
def __init__(
self, initial_population: List[C],
threshold: float,
max_generations: int, mutation_probability: float,
crossover_probability: float,
selection_type: SelectionType) -> None:
"""
A class that deals with genetic algorithms.
Parameters
----------
initial_population : list of Chromosome
First generation population (chromosomal group).
threshold : float
Threshold value used to judge problem solving. Individuals that exceed this value
The calculation ends when it occurs.
max_generations : int
Maximum number of generations to run in the algorithm.
mutation_probability : float
Mutation probability (0.0～1.0）。
crossover_probability : float
Crossover probability (0.0～1.0）。
selection_type : int
Selection method. Specify one of the following constant values.
- SELECTION_TYPE_ROULETTE_WHEEL
- SELECTION_TYPE_TOURNAMENT
"""
self._population: List[Chromosome] = initial_population
self._threshold: float = threshold
self._max_generations: int = max_generations
self._mutation_probability: float = mutation_probability
self._crossover_probability: float = crossover_probability
self._selection_type: int = selection_type
def _exec_roulette_wheel_selection(self) -> List[Chromosome]:
"""
Select two individuals (chromosomes) to be used for roulette selection and crossing.
get.
Returns
-------
selected_chromosomes : list of Chromosome
A list containing the two selected individuals (chromosomes). The selection process is an evaluation function
It is randomly extracted with the weight set by (fitness method).
Notes
-----
It cannot be used for problems where the value of the result of the evaluation function is negative.
"""
weights: List[float] = [
chromosome.get_fitness() for chromosome in self._population]
selected_chromosomes: List[Chromosome] = choices(
self._population, weights=weights, k=2)
return selected_chromosomes
def _exec_tournament_selection(self) -> List[Chromosome]:
"""
Two individuals for tournament selection and crossing
Obtain (chromosome).
Returns
-------
selected_chromosomes : list of Chromosome
A list containing the two selected individuals (chromosomes). tournament
The top two individuals are extracted from the number of cases specified by the argument for
Set.
"""
participants_num: int = len(self._population) // 2
participants: List[Chromosome] = choices(self._population, k=participants_num)
selected_chromosomes: List[Chromosome] = nlargest(n=2, iterable=participants)
return selected_chromosomes
def _to_next_generation(self) -> None:
"""
Generated next-generation individuals (chromosomes) and generated attribute values for populations
Replace with the next generation population.
"""
new_population: List[Chromosome] = []
#The comparison of the number of cases is not equal, considering the case where the number of cases of the original population is odd.
#Judgment is made based on lesser conditions.
while len(new_population) < len(self._population):
parents: List[Chromosome] = self._get_parents_by_selection_type()
next_generation_chromosomes: List[Chromosome] = \
self._get_next_generation_chromosomes(parents=parents)
new_population.extend(next_generation_chromosomes)
#Due to the convenience of increasing the next-generation list by two, the number of cases is larger than the original list
#If there are many, remove them from the list and match the number of items in the list with the original list.
if len(new_population) > len(self._population):
del new_population[0]
self._population = new_population
def _get_next_generation_chromosomes(
self, parents: List[Chromosome]) -> List[Chromosome]:
"""
Treat as the next generation from the calculated list of two parental individuals
Get a list of two populations.
Cross or mutate with a certain probability, and if the probability is not satisfied, the value of the argument will be
It will be set as the next generation as it is.
Parameters
----------
parents : list of Chromosome
List of two individuals of the calculated parent
Returns
-------
next_generation_chromosomes : list of Chromosome
A list containing two individuals set as the next generation.
"""
random_val: float = random()
next_generation_chromosomes: List[Chromosome] = parents
if random_val < self._crossover_probability:
next_generation_chromosomes = parents[0].exec_crossover(
other=parents[1])
random_val = random()
if random_val < self._mutation_probability:
for chromosome in next_generation_chromosomes:
chromosome.mutate()
return next_generation_chromosomes
def _get_parents_by_selection_type(self) -> List[Chromosome]:
"""
Obtain a list of two parental individuals (chromosomes) according to the selection method.
Returns
-------
parents : list of Chromosome
A list of two individuals (chromosomes) of the acquired parent.
Raises
------
ValueError
When an unsupported selection method is specified.
"""
if self._selection_type == self.SELECTION_TYPE_ROULETTE_WHEEL:
parents: List[Chromosome] = self._exec_roulette_wheel_selection()
elif self._selection_type == self.SELECTION_TYPE_TOURNAMENT:
parents = self._exec_tournament_selection()
else:
raise ValueError(
'An unsupported selection method is specified: %s'
% self._selection_type)
return parents
def run_algorithm(self) -> Chromosome:
"""
An instance of an individual (chromosome) that executes a genetic algorithm and results in execution
To get.
Returns
-------
betst_chromosome : Chromosome
An individual of the algorithm execution result. Individuals that exceed the threshold value with the evaluation function
Or, if the threshold is not exceeded, the specified number of generations has been reached.
The individual with the highest evaluation function value at that time is set.
"""
best_chromosome: Chromosome = \
deepcopy(self._get_best_chromosome_from_population())
for generation_idx in range(self._max_generations):
print(
datetime.now(),
f'Number of generations: {generation_idx}'
f'Best individual information: {best_chromosome}'
)
if best_chromosome.get_fitness() >= self._threshold:
return best_chromosome
self._to_next_generation()
currrent_generation_best_chromosome: Chromosome = \
self._get_best_chromosome_from_population()
current_gen_best_fitness: float = \
currrent_generation_best_chromosome.get_fitness()
if best_chromosome.get_fitness() < current_gen_best_fitness:
best_chromosome = deepcopy(currrent_generation_best_chromosome)
return best_chromosome
def _get_best_chromosome_from_population(self) -> Chromosome:
"""
From the list of populations, select the individual (chromosome) with the highest evaluation function value.
get.
Returns
-------
best_chromosome : Chromosome
The individual with the highest evaluation function value in the list.
"""
best_chromosome: Chromosome = self._population[0]
for chromosome in self._population:
if best_chromosome.get_fitness() < chromosome.get_fitness():
best_chromosome = chromosome
return best_chromosome
class SimpleEquationProblem(Chromosome):
def __init__(self, x: int, y: int) -> None:
"""
The following simple formula for checking the operation of the genetic algorithm
6x - x^2 + 4 * y - y^2
A class that deals with the problem of finding the x and y values that maximize the value of.
(The correct answer is x= 3, y = 2）
Parameters
----------
x : int
Initial value of x.
y : int
Initial value of y.
"""
self.x = x
self.y = y
def get_fitness(self) -> float:
"""
6x with current x and y values- x^2 + 4 * y - y^Of the calculation result of equation 2
A method used as an evaluation function to get a value.
Returns
-------
fitness : int
The value of the calculation result of the formula.
"""
x: int = self.x
y: int = self.y
return 6 * x - x ** 2 + 4 * y - y ** 2
@classmethod
def make_random_instance(cls) -> SimpleEquationProblem:
"""
Of the SimpleEquationProblem class with a random initial value
Create an instance.
Returns
-------
problem : SimpleEquationProblem
The generated instance. x and y are random in the range 0-99
The value is set.
"""
x: int = randrange(100)
y: int = randrange(100)
problem = SimpleEquationProblem(x=x, y=y)
return problem
def mutate(self) -> None:
"""
Mutate an individual (suddenly) (depending on the random number, the value of x or y
1 increase / decrease).
"""
value: int = choices([1, -1], k=1)[0]
if random() > 0.5:
self.x += value
return
self.y += value
def exec_crossover(
self, other: SimpleEquationProblem
) -> List[SimpleEquationProblem]:
"""
Crossover is executed with reference to another individual specified in the argument.
Parameters
----------
other : SimpleEquationProblem
Another individual used in crossing.
Returns
-------
result_chromosomes : list of SimpleEquationProblem
A list containing the two individuals generated after the crossover. Become a parent
It is an individual that inherits half the values of x and y from each individual.
"""
child_1: SimpleEquationProblem = deepcopy(self)
child_2: SimpleEquationProblem = deepcopy(other)
child_1.y = other.y
child_2.x = self.x
result_chromosomes: List[SimpleEquationProblem] = [
child_1, child_2,
]
return result_chromosomes
def __str__(self) -> str:
"""
Return the character string of individual information.
Returns
-------
info : str
A character string of individual information.
"""
x: int = self.x
y: int = self.y
fitness: float = self.get_fitness()
info: str = f'x = {x}, y = {y}, fitness = {fitness}'
return info
LetterDict = Dict[str, int]
class SendMoreMoneyProblem(Chromosome):
LETTERS: List[str] = ['S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y']
def __init__(self, letters_dict: LetterDict) -> None:
"""
SEND + MORE =MONEY's verbal arithmetic problem with a genetic algorithm
A class to solve.
Parameters
----------
letters_dict : LetterDict
Each of the eight characters (keys) used in the problem and the assigned numerical value (value)
A dictionary that stores the initial values of.
"""
self.letters_dict: LetterDict = letters_dict
def get_fitness(self) -> float:
"""
SEND with the number assigned to each current character+With MORE numbers
A method for the evaluation function based on the difference between the numerical values of MONEY.
Notes
-----
Because the value of the evaluation function of the genetic algorithm is highly evaluated,
The value is adjusted so that the larger the error, the lower the value.
Will be returned.
Returns
-------
fitness : int
SEND +Evaluation value based on the difference between the MORE value and the MONEY value.
The smaller the difference, the larger the value is set.
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
return 1 / (difference + 1)
def _get_send_val(self) -> int:
"""
Get the value of SEND by the numerical value of each character currently allocated.
Returns
-------
send_val : int
The value of SEND that is the numerical value of each character currently allocated.
"""
s: int = self.letters_dict['S']
e: int = self.letters_dict['E']
n: int = self.letters_dict['N']
d: int = self.letters_dict['D']
send_val: int = s * 1000 + e * 100 + n * 10 + d
return send_val
def _get_more_val(self) -> int:
"""
Gets the MORE value of each character that is currently allocated.
Parameters
----------
more_val : int
The value of MORE by the numerical value of each character currently allocated
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
r: int = self.letters_dict['R']
e: int = self.letters_dict['E']
more_val: int = m * 1000 + o * 100 + r * 10 + e
return more_val
def _get_money_val(self):
"""
Gets the value of MONEY based on the numerical value of each character currently assigned.
Returns
-------
money_val : int
The value of MONEY based on the numerical value of each character currently assigned.
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
n: int = self.letters_dict['N']
e: int = self.letters_dict['E']
y: int = self.letters_dict['Y']
money_val = m * 10000 + o * 1000 + n * 100 + e * 10 + y
return money_val
@classmethod
def make_random_instance(cls) -> SendMoreMoneyProblem:
"""
Of the SendMoreMoneyProblem class with a random initial value
Create an instance.
Returns
-------
problem : SendMoreMoneyProblem
The generated instance. Each character has a range of 0-9
Values are set so that the numbers do not overlap.
"""
num_list: List[int] = list(range(10))
shuffle(num_list)
num_list = num_list[:len(cls.LETTERS)]
letters_dict: LetterDict = {
char: num for (char, num) in zip(cls.LETTERS, num_list)}
problem: SendMoreMoneyProblem = SendMoreMoneyProblem(
letters_dict=letters_dict)
return problem
def mutate(self) -> None:
"""
Mutate an individual (suddenly) (randomly assigned a specific letter value)
Replace with a number that does not exist).
"""
target_char: str = choices(self.LETTERS, k=1)[0]
not_assigned_num: int = self._get_not_assigned_num()
self.letters_dict[target_char] = not_assigned_num
def _get_not_assigned_num(self) -> int:
"""
Gets the number that is not assigned to each character.
Returns
-------
not_assigned_num : int
A number that is not assigned to each letter. While there are 8 letters,
Since there are 10 numbers from 0 to 9, there are 2 unallocated numbers,
One of them is set.
"""
values: list = list(self.letters_dict.values())
not_assigned_num: int = -1
for num in range(10):
if num in values:
continue
not_assigned_num = num
break
return not_assigned_num
def exec_crossover(
self,
other: SendMoreMoneyProblem) -> List[SendMoreMoneyProblem]:
"""
Crossover is executed with reference to another individual specified in the argument.
Parameters
----------
other : SendMoreMoneyProblem
Another individual used in crossing.
Returns
-------
result_chromosomes : list of SendMoreMoneyProblem
A list containing the two individuals generated after the crossover.
"""
child_1: SendMoreMoneyProblem = deepcopy(self)
child_2: SendMoreMoneyProblem = deepcopy(other)
for char in ('S', 'E', 'N', 'D'):
child_2.letters_dict[char] = self.\
_get_not_assigned_num_from_parent(
child=child_2,
parent=self,
)
for char in ('M', 'O', 'R', 'Y'):
child_1.letters_dict[char] = \
self._get_not_assigned_num_from_parent(
child=child_1,
parent=other,
)
result_chromosomes = [child_1, child_2]
return result_chromosomes
def _get_not_assigned_num_from_parent(
self, child: SendMoreMoneyProblem,
parent: SendMoreMoneyProblem) -> int:
"""
Among the numbers set for the parent, the numbers that have not yet been set for the child
get.
Notes
-----
Cases where selectable values cannot be found depending on the combination of parent and child numbers
In that case, the unallocated number among the values from 0 to 9 is
Set.
Parameters
----------
child : SendMoreMoneyProblem
Individual child.
parent : SendMoreMoneyProblem
Parental individual.
Returns
-------
not_assigned_num : int
Calculated, unallocated number.
"""
not_assigned_num: int = -1
for parent_num in parent.letters_dict.values():
child_nums: list = list(child.letters_dict.values())
if parent_num in child_nums:
continue
not_assigned_num = parent_num
if not_assigned_num == -1:
not_assigned_num = self._get_not_assigned_num()
return not_assigned_num
def __str__(self) -> str:
"""
Return the character string of individual information.
Returns
-------
info : str
A character string of individual information.
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
info: str = (
f"\nS = {self.letters_dict['S']}"
f" E = {self.letters_dict['E']}"
f" N = {self.letters_dict['N']}"
f" D = {self.letters_dict['D']}"
f"\nM = {self.letters_dict['M']}"
f" O = {self.letters_dict['O']}"
f" R = {self.letters_dict['R']}"
f" Y = {self.letters_dict['Y']}"
f'\nSEND = {send_val}'
f' MORE = {more_val}'
f' MONEY = {money_val}'
f' difference : {difference}'
'\n--------------------------------'
)
return info
if __name__ == '__main__':
simple_equation_initial_population: List[SimpleEquationProblem] = \
[SimpleEquationProblem.make_random_instance() for _ in range(30)]
ga: GeneticAlgorithm = GeneticAlgorithm(
initial_population=simple_equation_initial_population,
threshold=13,
max_generations=100,
mutation_probability=0.2,
crossover_probability=0.3,
selection_type=GeneticAlgorithm.SELECTION_TYPE_TOURNAMENT)
_ = ga.run_algorithm()
send_more_money_initial_population: List[SendMoreMoneyProblem] = \
[SendMoreMoneyProblem.make_random_instance() for _ in range(1000)]
ga = GeneticAlgorithm(
initial_population=send_more_money_initial_population,
threshold=1.0,
max_generations=1000,
mutation_probability=0.7,
crossover_probability=0.2,
selection_type=GeneticAlgorithm.SELECTION_TYPE_ROULETTE_WHEEL)
_ = ga.run_algorithm()
Reference site / reference summary
- Classic Computer Science Problems in Python -[Genetic Algorithm --Wikipedia](https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0) -[John H. Holland-Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%B8%E3%83%A7%E3%83%B3%E3%83%BBH%E3% 83% BB% E3% 83% 9B% E3% 83% A9% E3% 83% B3% E3% 83% 89) -Darwinian theory of evolution. Those who survive are not "people who can change" but "people who are lucky" -[Verbal arithmetic] SEND + MORE = MONEY I will thoroughly explain how to solve the problem!
Recommended Posts