Premiers pas avec les algorithmes génétiques Python
«J'écrirai sur l'algorithme génétique comme une étude des parties de base et simples. Afin d'approfondir votre compréhension, nous allons en fait écrire le code de l'algorithme génétique en Python et le déplacer sous forme de résolution de certains problèmes.
Qu'est-ce qu'un algorithme génétique?
Algorithme génétique en anglais. La première apparition a été proposée en 1975 par le professeur John H. Holland de l'Université du Michigan.
- [Algorithme génétique-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)
Dans une certaine mesure, un grand nombre d'éléments traités comme des «gènes» et des «chromosomes» avec des attributs individuels sont générés chez chaque individu, et la génération suivante est générée jusqu'à ce que de bons résultats soient obtenus pour le problème cible tout en impliquant des éléments aléatoires. C'est un algorithme qui se répète.
Comme la théorie de l'évolution de Darwin (comme si un individu qui s'adapte bien pour survivre survit), nous avons la chance de laisser les éléments qui correspondent bien au problème à la génération suivante, ou de résoudre les éléments qui correspondent bien. Je vais l'utiliser comme réponse.
Il n'y a pas de réponse avant d'exécuter l'algorithme, et c'est un calcul qui recherche une réponse correspondante tout en impliquant des éléments aléatoires, et cela peut être un peu similaire à l'apprentissage amélioré de l'apprentissage non supervisé (le code lui-même est également un peu similaire). Certaines parties seront mises en œuvre, et il y a diverses choses dans le domaine de l'apprentissage amélioré)
De quel genre de calcul s'agit-il
Ci-après, un élément sera appelé chromosome (chromosome).
Tout d'abord, générez des chromosomes au hasard. Ce nombre est arbitraire. Plus le nombre est élevé, plus il y a de calculs pour une génération, tandis que plus les conditions sont générées en une génération et plus il y a de variations.
La fonction d'évaluation évalue ensuite chaque élément pour déterminer ce qu'il faut faire avec la prochaine génération. Cette fonction d'évaluation renvoie une valeur indiquant à quel point elle s'adapte au problème. Dans l'apprentissage automatique, c'est comme une fonction d'erreur.
Le contenu de la fonction d'évaluation est décidé arbitrairement en fonction du problème. Biologiquement, à titre d'exemple, il s'agit d'un indice tel que «sa force contre le froid» ou «la qualité des yeux». Par exemple, "Quel est le score d'un problème spécifique dans un problème réel?"
Pour la prochaine génération, en fonction de chaque élément de la génération actuelle, par exemple, déterminez comment propager les fonctionnalités aux générations futures par le calcul suivant (divers ajustements et sélections ici également) Je peux le faire).
** croisement **
Crossover laisse deux chromosomes dans la génération suivante d'une manière qui hérite les caractéristiques des deux chromosomes de moitié. C'est un calcul qui hérite des caractéristiques des parents moitié par moitié et traite deux enfants comme la génération suivante.
** mutation **
La mutation laisse un chromosome avec des propriétés complètement inhabituelles dans une partie ou la plupart de la génération suivante.
Il est utilisé pour empêcher que seuls des chromosomes similaires restent en raison d'un croisement, etc., et pour réduire les cas tels que des solutions locales (telles que des réponses biaisées et optimales non données).
** sélection de roue de roulette **
Il existe une méthode appelée sélection à la roulette comme méthode de sélection lors de la sélection de deux chromosomes au moment de la transition vers la génération suivante, comme le croisement.
Il s'agit d'une sélection aléatoire dans laquelle plus la performance de la fonction d'évaluation est élevée, plus la probabilité de sélection est élevée.
En fonction des performances de la fonction d'évaluation, le poids de la probabilité au moment de l'extraction aléatoire est déterminé, et ainsi de suite.
** sélection de tournois **
Pour la sélection de tournoi, après avoir extrait au hasard un certain nombre de l'ensemble du chromosome (par exemple, extraire au hasard 100 à partir de 2000 chromosomes au total), celui avec la fonction d'évaluation la plus élevée est sélectionné pour le nombre de cas requis (par exemple, par croisement). Si nécessaire, 2) seront extraits.
** Quand arrêter le calcul **
Si la valeur cible de la fonction d'évaluation est connue, le nombre de générations peut être énormément fixé jusqu'à ce que la valeur soit obtenue. Par exemple, dans le cas de la recherche d'itinéraire, si une condition telle que «un itinéraire pouvant atteindre l'objectif en quelques minutes» est correcte, le calcul sera terminé si cette condition est remplie.
En variante, si la valeur cible n'est pas connue, le calcul est arrêté lorsqu'un certain nombre de générations est atteint, et la valeur d'attribut du chromosome avec la valeur de fonction d'évaluation maximale est utilisée. C'est une façon d'arrêter le calcul, comme "calculer pour 200 générations et utiliser celle avec les meilleurs résultats" sans connaître à l'avance la réponse claire ou la valeur autorisée.
Quelles sont les caractéristiques / quand convient-il?
Comme mentionné ci-dessus, les algorithmes génétiques impliquent fortement des éléments aléatoires dans de nombreux calculs. Par conséquent, la quantité de calcul jusqu'à ce que le problème soit résolu change à chaque fois qu'il est exécuté.
En outre, il existe des cas où la solution est résolue immédiatement et des cas où la réponse ne peut être atteinte pendant longtemps. Fondamentalement, s'il existe un algorithme adapté au problème, il existe de nombreux cas où la quantité de calcul est beaucoup plus petite si vous l'utilisez.
Même si vous arrivez à une solution qui semble bonne, il peut y avoir des cas où ce n'est pas la solution optimale.
D'autre part, il peut être utilisé à des fins diverses, même dans des cas vagues où vous ne pouvez pas penser à l'algorithme optimal et que vous souhaitez rechercher des réponses de manière exploratoire.
À titre d'exemple de cas d'utilisation adapté à ces derniers,
- Un cas où c'est OK si une réponse d'environ 80 points est requise au lieu de 100 points (solution optimale)
- Cas où un temps de calcul court n'est pas nécessaire
- Cas où vous ne pouvez pas penser à un algorithme plus optimal
Etc.
Implémentation en Python
Essayons de résoudre certains problèmes en utilisant des algorithmes génétiques.
Quoi utiliser
- Python 3.8.5 --Pylance (pour le contrôle de type)
- Comme d'autres articles similaires que j'ai écrits dans le passé, j'écrirai en utilisant le module intégré sans utiliser de bibliothèque, etc. pour étudier.
Points à retenir
Comme cas d'utilisation approprié, j'ai mentionné «un cas où je ne peux pas penser à un algorithme plus optimal», mais les problèmes mentionnés dans cet article sont des problèmes intentionnellement simples à étudier, et il existe de nombreuses autres solutions optimales. Nous y répondrons.
Gardez à l'esprit que l'utilisation du meilleur algorithme peut prendre beaucoup de temps pour effectuer un calcul rapide.
Importation des modules requis
Tout d'abord, nous importerons les éléments intégrés à utiliser.
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
- Les annotations sont utilisées car les annotations de type qui seront adoptées dans les futures versions de Python seront disponibles.
- Afin d'utiliser les annotations de type, nous importons ce dont nous avons besoin à partir du package de saisie. --choices est une fonction qui sélectionne de manière aléatoire un nombre arbitraire de fonctions itérables spécifiées dans l'argument. Il est utilisé pour sélectionner la prochaine génération d'individus. Vous pouvez également définir l'ampleur de la probabilité pour chaque individu avec l'argument de pondération. --random est une fonction qui obtient des nombres aléatoires compris entre 0,0 et 1,0. --randrange est une fonction qui obtient de manière aléatoire une valeur à partir de la plage de valeurs obtenue lorsqu'elle est spécifiée par plage (par exemple, obtenir aléatoirement n'importe lequel de 0 à 9). --shuffle est une fonction qui mélange les éléments itérables. --nlargest est une fonction qui récupère n grands dans l'ordre dans l'élément itérable spécifié. Il est utilisé lors de l'extraction des meilleurs individus dans la sélection du tournoi. --Cette fois, afin de résoudre deux problèmes, nous importons le package abc (abstract base class) pour utiliser la classe abstraite. --Deepcopy, comme son nom l'indique, est une fonction qui copie en profondeur des éléments. La copie profonde est utilisée lors de la création d'individus de nouvelle génération.
Définition d'une classe abstraite individuelle
Comme mentionné ci-dessus, cet article traitera de deux problèmes, nous allons donc ajouter une classe abstraite individuelle à hériter pour chaque problème.
En ajoutant @ abstractmethod et un décorateur, vous pouvez mettre la classe héritée en colère contre une erreur à moins que vous n'écrasiez la méthode avec le décorateur.
class Chromosome(ABC):
"""
Une classe abstraite qui traite des chromosomes (un élément d'un algorithme génétique).
"""
@abstractmethod
def get_fitness(self) -> float:
"""
Pour la fonction d'évaluation Y pour obtenir l'excellence des chromosomes pour le problème d'intérêt
Méthode abstraite.
Returns
-------
fitness : float
Valeur de l'excellence chromosomique pour le problème d'intérêt. Plus le problème est élevé
Il devient un chromosome approprié.
Il est également utilisé pour déterminer la fin d'un algorithme génétique.
"""
...
@classmethod
@abstractmethod
def make_random_instance(cls) -> Chromosome:
"""
Créer une instance avec des caractéristiques aléatoires (valeurs d'attribut)
Méthode abstraite.
Returns
-------
instance : Chromosome
L'instance générée.
"""
...
@abstractmethod
def mutate(self) -> None:
"""
Une méthode abstraite de traitement qui (soudainement) mute un chromosome.
Des paramètres de valeur différents aléatoires tels que les attributs d'instance sont exécutés.
"""
...
@abstractmethod
def exec_crossover(self, other: Chromosome) -> List[Chromosome]:
"""
Le croisement est exécuté en référence à une autre personne spécifiée dans l'argument.
Parameters
----------
other : Chromosome
Un autre individu utilisé en croisement.
Returns
-------
result_chromosomes : list of Chromosome
Deux individus (chromosomes) générés après le croisement.
"""
...
def __lt__(self, other: Chromosome) -> bool:
"""
Une fonction pour comparer la valeur de la fonction d'évaluation, qui est utilisée pour la comparaison entre les individus.
Parameters
----------
other : Chromosome
Autres individus à comparer.
Returns
-------
result_bool : bool
Valeur booléenne indiquant si la condition la plus faible est satisfaite ou non.
"""
return self.get_fitness() < other.get_fitness()
Les interfaces de fonction d'évaluation (get_fitness), de mutation (mutation) et de croisement (exec_crossover) requises pour l'algorithme génétique sont fournies. Seule l'instance Ellipsis (...) est décrite et les autres sont omises (écrasées par la destination d'héritage).
De plus, puisqu'il est nécessaire de générer la première génération avant le démarrage de l'algorithme, une méthode appelée make_random_instance est fournie en tant que méthode de classe.
Puisqu'il est nécessaire d'extraire la valeur au-dessus de la valeur de la fonction d'évaluation, une méthode de «lt» est définie pour la comparaison afin que la valeur de la fonction d'évaluation puisse être utilisée pour de petites comparaisons.
Définition des classes d'algorithmes génétiques
Nous définirons une classe pour l'algorithme génétique.
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:
"""
Une classe qui traite des algorithmes génétiques.
Parameters
----------
initial_population : list of Chromosome
Population de première génération (groupe chromosomique).
threshold : float
Un seuil utilisé pour déterminer la résolution des problèmes. Les individus qui dépassent cette valeur
Le calcul se termine lorsqu'il se produit.
max_generations : int
Nombre maximum de générations à exécuter dans l'algorithme.
mutation_probability : float
Probabilité de mutation (0.0～1.0）。
crossover_probability : float
Probabilité de croisement (0.0～1.0）。
selection_type : int
Méthode de sélection. Spécifiez l'une des valeurs constantes suivantes.
- 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
L'endroit «C = TypeVar (« C », lié = Chromosome)» définit le type comme un générique (Chromosome C).
Lors de son utilisation, s'il s'agit d'une sous-classe de Chromosome etc., il sera pris dans le contrôle de type de Pylance (déterminé comme sous-classe ≠ Chromosome class), donc je l'utilise.
L'argument lié est un argument qui donne une contrainte telle que "OK si c'est un chromosome ou une sous-classe de chromosome".
Concernant le constructeur, «première population» requise par l'algorithme, «seuil de la fonction d'évaluation utilisée pour juger l'arrêt de l'algorithme», «limite supérieure du nombre de générations», «probabilité de mutation», «probabilité de croisement», «méthode de sélection telle que la sélection à la roulette» Est spécifié.
De plus, la constante de méthode de sélection est définie (SELECTION_TYPE_ROULETTE_WHEEL: SelectionType = 1, etc.).
Mise en place de la sélection de roulette
Nous ajouterons le traitement de sélection de la roulette à la classe GeneticAlgorithm.
def _exec_roulette_wheel_selection(self) -> List[Chromosome]:
"""
Sélectionnez la roulette et sélectionnez deux individus (chromosomes) à utiliser pour le croisement, etc.
avoir.
Returns
-------
selected_chromosomes : list of Chromosome
Une liste contenant les deux individus sélectionnés (chromosomes). Le processus de sélection est une fonction d'évaluation
Il est extrait au hasard avec le poids défini par (méthode de remise en forme).
Notes
-----
Il ne peut pas être utilisé pour les problèmes où la valeur de résultat de la fonction d'évaluation est négative.
"""
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
Dans la sélection à la roulette, les individus sont sélectionnés au hasard, mais le poids est défini de sorte que celui avec la valeur la plus élevée obtenue par la fonction d'évaluation ait la priorité.
Concernant ce poids, imaginez la roulette suivante, en supposant qu'il y a cinq individus A à E.
La valeur de la fonction d'évaluation de chaque individu est la surface de la roulette. Les personnes de petite superficie (personnes avec une faible évaluation par la fonction d'évaluation) peuvent également être sélectionnées, mais la probabilité est faible.
Mise en place de la sélection de tournois
De même, nous ajouterons des sélections de tournois à la classe GeneticAlgorithm. L'utilisation de la sélection de roulette ou de sélection de tournoi dépend de la spécification selection_type dans le constructeur.
def _exec_tournament_selection(self) -> List[Chromosome]:
"""
Deux individus pour la sélection du tournoi et le croisement
Obtenez (chromosome).
Returns
-------
selected_chromosomes : list of Chromosome
Une liste contenant les deux individus sélectionnés (chromosomes). tournoi
Les deux premiers individus sont extraits du nombre de cas spécifié dans l'argument pour
Ensemble.
"""
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
Dans la sélection du tournoi, la population utilisée dans le tournoi est d'abord extraite. Cette fois, la moitié de la population est sélectionnée par codage en dur.
De plus, comme la valeur de retour est de 2 individus, les 2 premiers individus sont extraits par la fonction la plus grande. Puisqu'il est nécessaire de comparer les éléments de la liste à l'intérieur de cette fonction, il est nécessaire de définir la méthode de __lt__ dans la classe Chromosome.
Implémentation du traitement de transition vers la prochaine génération
Nous allons maintenant ajouter un traitement à la classe GeneticAlgorithm pour passer de la génération actuelle à la génération suivante.
Quant à quoi faire
- [1]. Extraire deux individus selon la méthode de sélection (sélection roulette, etc.) (parents nommés).
- [2]. Modifiez les deux individus extraits en fonction de la probabilité de croisement et de la probabilité de mutation spécifiés dans le constructeur (avec des nombres aléatoires et des probabilités, si le croisement ne se produit pas, définissez l'individu parent tel qu'il est à la génération suivante ).
- [3] Ajoutez les deux individus préparés à la liste des individus de la prochaine génération.
- [4] Répétez [1] - [3] jusqu'à ce que la liste des individus de la prochaine génération soit la même que la liste des individus de la génération actuelle.
Ce sera le processus.
def _to_next_generation(self) -> None:
"""
Généré l'individu de prochaine génération (chromosome) et généré la valeur d'attribut de la population
Remplacez par la population de la prochaine génération.
"""
new_population: List[Chromosome] = []
#La comparaison du nombre de cas n'est pas égale, compte tenu du cas où le nombre de cas de la population d'origine est un nombre impair.
#Le jugement est basé sur des conditions moindres.
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)
#En raison de la commodité d'augmenter la liste de nouvelle génération de deux, le nombre de cas est plus grand que la liste d'origine
#S'il y en a beaucoup, supprimez-les de la liste et faites correspondre le nombre d'éléments de la liste avec la liste d'origine.
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]:
"""
Traiter comme la prochaine génération à partir de la liste calculée de deux parents
Obtenez une liste de deux populations.
Croiser ou muter avec une certaine probabilité, si la probabilité n'est pas satisfaite, la valeur de l'argument sera
Il sera défini comme la prochaine génération tel qu'il est.
Parameters
----------
parents : list of Chromosome
Liste de deux individus du parent calculé
Returns
-------
next_generation_chromosomes : list of Chromosome
Une liste contenant deux individus définis comme la prochaine génération.
"""
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]:
"""
Obtenez une liste de deux individus parents (chromosomes) selon la méthode de sélection.
Returns
-------
parents : list of Chromosome
Une liste des deux individus (chromosomes) du parent acquis.
Raises
------
ValueError
Lorsqu'une méthode de sélection non prise en charge est spécifiée.
"""
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(
'Une méthode de sélection non prise en charge est spécifiée: %s'
% self._selection_type)
return parents
Implémentation du traitement pour exécuter l'algorithme
J'écrirai un processus qui répète la transition vers la génération suivante jusqu'à ce que la valeur de la fonction d'évaluation dépasse la valeur seuil (≈ un individu qui atteint la valeur cible est né) ou dépasse la limite supérieure du nombre de générations.
En termes d'apprentissage automatique, c'est comme du code pour l'apprentissage. C'est comme l'époque que les générations appellent l'apprentissage automatique. Le meilleur individu pour chaque génération est émis sous forme d'informations par la fonction d'impression.
Cependant, le meilleur individu correspond au «meilleur individu de toutes les générations». Veuillez noter qu'il ne s'agit pas d'une valeur par époque comme l'apprentissage automatique.
def run_algorithm(self) -> Chromosome:
"""
Une instance d'un individu (chromosome) qui exécute un algorithme génétique et aboutit à une exécution
Obtenir.
Returns
-------
betst_chromosome : Chromosome
Individu du résultat de l'exécution de l'algorithme. Les personnes qui dépassent le seuil dans la fonction d'évaluation
Ou si le seuil n'est pas dépassé, le nombre spécifié de générations a été atteint.
L'individu avec la valeur de fonction d'évaluation la plus élevée à ce moment est défini.
"""
best_chromosome: Chromosome = \
deepcopy(self._get_best_chromosome_from_population())
for generation_idx in range(self._max_generations):
print(
datetime.now(),
f'Nombre de générations: {generation_idx}'
f'Meilleures informations individuelles: {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:
"""
Dans la liste des populations, sélectionnez l'individu (chromosome) avec la valeur de fonction d'évaluation la plus élevée.
avoir.
Returns
-------
best_chromosome : Chromosome
L'individu avec la valeur de fonction d'évaluation la plus élevée de la liste.
"""
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
Ajoutez un problème de formule simple pour vérifier l'opération et essayez-le.
Créons un problème simple et exécutons l'algorithme pour confirmer la mise en œuvre de l'algorithme génétique.
Utilisez le problème de recherche de x et y afin que les valeurs des formules suivantes soient maximisées.
6x - x^2 + 4y - y^2
La réponse est 13 lorsque x = 3 et y = 2, qui est le maximum.
Dans le but de vérifier le fonctionnement, comme mentionné ci-dessus, il n'est pas nécessaire d'utiliser l'algorithme génétique (au contraire, il n'est pas préférable en termes de temps de calcul).
Hérite de la classe Chromosome, qui est une classe abstraite préparée à l'avance.
class SimpleEquationProblem(Chromosome):
def __init__(self, x: int, y: int) -> None:
"""
La formule simple suivante pour vérifier le fonctionnement de l'algorithme génétique
6x - x^2 + 4 * y - y^2
Une classe qui traite le problème de trouver les valeurs de x et y qui maximisent la valeur de.
(La bonne réponse est x= 3, y = 2）
Parameters
----------
x : int
La valeur initiale de x.
y : int
La valeur initiale de y.
"""
self.x = x
self.y = y
Nous ajouterons des fonctions d'évaluation. Plus la valeur numérique est élevée, meilleure est la valeur de retour de la fonction d'évaluation jugée par l'algorithme génétique, mais comme le problème cette fois-ci est simplement de trouver les valeurs plus grandes x et y, $ 6 x --x ^ 2 + 4y --y ^ Utilisez la valeur calculée de 2 $.
def get_fitness(self) -> float:
"""
6x avec les valeurs x et y actuelles- x^2 + 4 * y - y^Du résultat du calcul de l'équation 2
Une méthode utilisée comme fonction d'évaluation pour obtenir la valeur.
Returns
-------
fitness : int
La valeur du résultat du calcul de la formule.
"""
x: int = self.x
y: int = self.y
return 6 * x - x ** 2 + 4 * y - y ** 2
La méthode de classe make_random_instance utilisée lors de la première génération de population doit définir x et y sur des valeurs aléatoires comprises entre 0 et 99.
@classmethod
def make_random_instance(cls) -> SimpleEquationProblem:
"""
De la classe SimpleEquationProblem avec une valeur initiale aléatoire
Créez une instance.
Returns
-------
problem : SimpleEquationProblem
L'instance générée. x et y sont aléatoires dans la plage 0-99
La valeur est définie.
"""
x: int = randrange(100)
y: int = randrange(100)
problem = SimpleEquationProblem(x=x, y=y)
return problem
Pour la variation, nous avons calculé s'il fallait ajouter ou soustraire la valeur de x ou y par 1.
def mutate(self) -> None:
"""
Mutant (soudainement) un individu (selon le nombre aléatoire, la valeur de x ou y
1 augmentation / diminution).
"""
value: int = choices([1, -1], k=1)[0]
if random() > 0.5:
self.x += value
return
self.y += value
J'écrirai le crossover de la même manière. Crossover hérite de moitié des caractéristiques des deux individus et renvoie deux individus de la prochaine génération.
def exec_crossover(
self, other: SimpleEquationProblem
) -> List[SimpleEquationProblem]:
"""
Le croisement est exécuté en référence à une autre personne spécifiée dans l'argument.
Parameters
----------
other : SimpleEquationProblem
Un autre individu utilisé en croisement.
Returns
-------
result_chromosomes : list of SimpleEquationProblem
Une liste contenant les deux individus générés après le croisement. Devenir parent
C'est un individu qui hérite de la moitié des valeurs de x et y de chaque individu.
"""
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
Puisque nous voulons produire les meilleures informations individuelles pour chaque génération pendant l'exécution de l'algorithme, écrivez le traitement pour cela dans la méthode __str__.
def __str__(self) -> str:
"""
Renvoie la chaîne de caractères des informations individuelles.
Returns
-------
info : str
Chaîne de caractères d'informations individuelles.
"""
x: int = self.x
y: int = self.y
fitness: float = self.get_fitness()
info: str = f'x = {x}, y = {y}, fitness = {fitness}'
return info
Déplaçons le problème de la classe SimpleEquationProblem
Je vais vraiment le déplacer.
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()
Nous avons sélectionné 30 individus, 100 générations maximum, 20% de probabilité de mutation, 30% de probabilité de croisement et la méthode de sélection des tournois. Puisque chaque nombre est fixe, il n'y a aucune raison particulière de le sélectionner (sélectionner par atmosphère).
Cependant, si la valeur de la fonction d'évaluation peut être négative comme indiqué ci-dessous, la sélection de la roulette ne peut pas être sélectionnée (pour des raisons telles que le poids), donc la sélection du tournoi est spécifiée.
** Sélection de roulette ** ... Cette méthode est la méthode de sélection utilisée lorsque Holland l'a proposée pour la première fois, et c'est la méthode de sélection la plus connue, mais on suppose que l'adaptabilité ne prend pas un nombre négatif. [Algorithme génétique-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)
De plus, cette fois, je sais que la réponse pour la valeur maximale est 13, j'ai donc spécifié 13 comme seuil.
Lorsqu'elle est exécutée, la sortie est la suivante. Comme expliqué dans la section sur l'explication de l'algorithme au début, l'algorithme génétique a un fort caractère aléatoire, il peut donc se terminer immédiatement ou il peut nécessiter un grand nombre de générations, et le résultat changera chaque fois qu'il est exécuté.
2020-10-31 19:24:39.948226 Nombre de générations:0 Meilleures informations individuelles: x = 14, y = 6, fitness = -124
2020-10-31 19:24:39.960250 Nombre de générations:1 Meilleure information individuelle: x = 14, y = 5, fitness = -117
2020-10-31 19:24:39.961220 Nombre de générations:2 Meilleures informations individuelles: x = 13, y = 5, fitness = -96
2020-10-31 19:24:39.962218 Nombre de générations:3 Meilleures informations individuelles: x = 13, y = 4, fitness = -91
2020-10-31 19:24:39.975251 Nombre de générations:4 Meilleures informations individuelles: x = 12, y = 4, fitness = -72
2020-10-31 19:24:39.982250 Nombre de générations:5 Meilleures informations individuelles: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.982250 Nombre de générations:6 Meilleures informations individuelles: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.996219 Nombre de générations:7 Meilleures informations individuelles: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.997251 Nombre de générations:8 Meilleures informations individuelles: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.998224 Nombre de générations:9 Meilleures informations individuelles: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.999254 Nombre de générations:10 Meilleures informations individuelles: x = 11, y = 2, fitness = -51
2020-10-31 19:24:40.000221 Nombre de générations:11 Meilleures informations individuelles: x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.001250 nombre de générations:12 Meilleures informations individuelles: x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.001250 nombre de générations:13 Meilleures informations individuelles: x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.002251 Nombre de générations:14 Meilleures informations individuelles: x = 8, y = 2, fitness = -12
2020-10-31 19:24:40.003250 Nombre de générations:15 Meilleures informations individuelles: x = 8, y = 2, fitness = -12
2020-10-31 19:24:40.004217 Nombre de générations:16 Meilleures informations individuelles: x = 6, y = 2, fitness = 4
2020-10-31 19:24:40.005251 Nombre de générations:17 Meilleures informations individuelles: x = 6, y = 2, fitness = 4
2020-10-31 19:24:40.006252 nombre de générations:18 Meilleures informations individuelles: x = 5, y = 3, fitness = 8
2020-10-31 19:24:40.006252 nombre de générations:19 Meilleures informations individuelles: x = 5, y = 2, fitness = 9
2020-10-31 19:24:40.007219 Nombre de générations:20 Meilleures informations individuelles: x = 4, y = 2, fitness = 12
2020-10-31 19:24:40.008219 Nombre de générations:21 Meilleures informations individuelles: x = 3, y = 2, fitness = 13
Cette fois, la réponse x = 3 et y = 2 est requise pour la 22e génération, et il peut être confirmé que la valeur de la fonction d'évaluation est 13 (ce domaine est similaire à l'apprentissage en profondeur). ..
Essayez de résoudre le problème du calcul masqué de SEND + MORE = MONEY
J'ai confirmé que cela fonctionnait avec un problème simple, donc j'essaierai de résoudre un autre problème avec un problème légèrement plus compliqué.
Nous traiterons le problème SEND + MORE = MONEY, qui est l'un des soi-disant cryptorithmétiques.
Qu'est-ce que le problème SEND + MORE = MONEY?
C'est un problème qui rend possible le calcul suivant. Des mots tels que SEND et MONEY n'ont pas de signification particulière.
Vous pouvez appliquer un nombre de 0 à 9 à chaque lettre. Par exemple, attribuez 3 à S, 5 à E, etc. (certains modèles n'incluent pas 0 en option, mais dans cet article, nous allons procéder en incluant 0 en option).
Cependant, vous ne pouvez pas attribuer le même numéro à une autre lettre (vous ne pouvez pas régler S sur 8 et E affecter également 8).
Valeur S à 4 chiffres, valeur E à 3 chiffres, N à 2 chiffres, valeur D SEND à 1 chiffre, M à 4 chiffres, O à 3 chiffres, R à 2 chiffres, 1 chiffre Une combinaison dans laquelle la somme des valeurs MORE consistant en E correspond exactement à la valeur de MONEY composée de 5 chiffres M, 4 chiffres O, 3 chiffres N, 2 chiffres E et 1 chiffre Y. Le problème est de demander.
Si les caractères sont identiques, les numéros à attribuer seront les mêmes. En d'autres termes, si vous attribuez 8 à M de MORE, vous devez régler M of MONEY à 8.
ENVOYER + PLUS = Ajouter une classe pour un problème MONEY
Comme pour la classe SimpleEquationProblem, nous ajouterons des classes qui héritent de la classe Chromosome. Le flux est presque le même que 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 =Problème de calcul masqué de MONEY avec un algorithme génétique
Classe à résoudre.
Parameters
----------
letters_dict : LetterDict
Chacun des huit caractères (clés) utilisés dans le problème et la valeur numérique attribuée (valeur)
Un dictionnaire qui stocke les valeurs initiales de.
"""
self.letters_dict: LetterDict = letters_dict
Cette fois, nous utiliserons un dictionnaire qui a le caractère cible de la clé et le numéro attribué à la valeur, nous avons donc défini un alias de type nommé LetterDict.
Nous ajouterons des méthodes pour la fonction d'évaluation à la classe SendMoreMoneyProblem. La fonction d'évaluation est créée en ajoutant le nombre de chiffres à chaque caractère tel que SEND, MORE et MONEY, et la différence entre la valeur MONEY et la valeur totale de SEND + MORE est calculée.
def get_fitness(self) -> float:
"""
SEND par la valeur numérique attribuée à chaque caractère courant+Avec PLUS de numéros
Une méthode pour la fonction d'évaluation basée sur la différence entre les valeurs numériques de MONEY.
Notes
-----
Parce que la valeur de la fonction d'évaluation de l'algorithme génétique est hautement évaluée
La valeur est ajustée de sorte que plus l'erreur est grande, plus la valeur est basse.
Sera retourné.
Returns
-------
fitness : int
SEND +Valeur d'évaluation basée sur la différence entre la valeur MORE et la valeur MONEY.
Plus la différence est petite, plus la valeur est définie.
"""
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:
"""
Obtenez la valeur de SEND par la valeur numérique de chaque caractère actuellement alloué.
Returns
-------
send_val : int
La valeur de SEND par la valeur numérique de chaque caractère actuellement alloué.
"""
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:
"""
Obtenez la valeur de MORE par la valeur numérique de chaque caractère actuellement alloué.
Parameters
----------
more_val : int
La valeur de MORE par la valeur numérique de chaque caractère actuellement alloué
"""
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):
"""
Obtenez la valeur de MONEY par la valeur numérique de chaque caractère actuellement attribué.
Returns
-------
money_val : int
La valeur de MONEY basée sur la valeur numérique de chaque caractère actuellement attribué.
"""
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
Dans l'algorithme génétique, plus la valeur est élevée, meilleure est la différence, mais plus la différence est petite, mieux c'est. Par conséquent, la valeur de retour est définie sur «1 / (différence + 1)» de sorte que plus la différence est grande, plus la valeur est petite.
La partie «+ 1» est une valeur pour empêcher la division 0 de se produire. Puisque la différence minimale est de 0, nous pouvons voir que la valeur maximale de la fonction d'évaluation est «1/1», qui est 1 (donc le seuil lors de l'exécution de l'algorithme est 1).
Nous définirons la méthode de classe pour l'instanciation. Ce n'est pas difficile, il suffit d'attribuer chaque caractère pour qu'il ne couvre pas les nombres 0-9.
@classmethod
def make_random_instance(cls) -> SendMoreMoneyProblem:
"""
De la classe SendMoreMoneyProblem avec une valeur initiale aléatoire
Créez une instance.
Returns
-------
problem : SendMoreMoneyProblem
L'instance générée. Chaque caractère a une plage de 0 à 9
Les valeurs sont définies de sorte que les nombres ne se chevauchent pas.
"""
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
J'écrirai le traitement de la mutation. Le contenu de la variation est aussi simple que de le changer en un autre nombre afin de ne pas couvrir un caractère sélectionné au hasard.
def mutate(self) -> None:
"""
Couper le son d'un individu (soudainement) (attribuer au hasard une valeur de caractère spécifique)
Remplacez par un nombre inexistant).
"""
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:
"""
Obtient le numéro qui n'est pas attribué à chaque caractère.
Returns
-------
not_assigned_num : int
Un numéro qui n'est pas attribué à chaque caractère. Bien qu'il y ait 8 caractères,
Puisqu'il y a 10 nombres de 0 à 9, il y a 2 nombres non attribués,
L'un d'eux est défini.
"""
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
Ensuite, j'écrirai le traitement du croisement. Je me demandais quoi faire avec le processus de croisement, mais j'ai créé le contenu suivant.
- [1]. Copiez l'individu parent.
- [2] Dans chacun des deux individus enfants, la moitié de chacun (4 caractères chacun de SEND et MORY) peut hériter des valeurs numériques de différents parents (cependant, en raison de la duplication des valeurs numériques, l'attribution des caractères et les valeurs numériques correspondent. ne pas faire).
- [3]. Si vous ne pouvez pas prendre la relève (alors que les parents utilisent souvent des numéros en double), attribuez les numéros non attribués.
def exec_crossover(
self,
other: SendMoreMoneyProblem) -> List[SendMoreMoneyProblem]:
"""
Le croisement est exécuté en référence à un autre individu spécifié dans l'argument.
Parameters
----------
other : SendMoreMoneyProblem
Un autre individu utilisé en croisement.
Returns
-------
result_chromosomes : list of SendMoreMoneyProblem
Une liste contenant les deux individus générés après le croisement.
"""
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:
"""
Parmi les numéros définis pour le parent, les numéros qui n'ont pas encore été définis pour l'enfant
avoir.
Notes
-----
Cas où les valeurs sélectionnables ne peuvent pas être trouvées en fonction de la combinaison des valeurs parent et enfant
Dans ce cas, le nombre non alloué parmi les valeurs de 0 à 9 est
Ensemble.
Parameters
----------
child : SendMoreMoneyProblem
Enfant individuel.
parent : SendMoreMoneyProblem
Individu parental.
Returns
-------
not_assigned_num : int
Numéro calculé, non attribué.
"""
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
Enfin, pour la sortie des informations pour chaque génération, les informations individuelles doivent être retournées par la méthode __str__.
def __str__(self) -> str:
"""
Renvoie la chaîne de caractères des informations individuelles.
Returns
-------
info : str
Chaîne de caractères d'informations individuelles.
"""
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
Lorsqu'il est passé par la fonction d'impression, etc., il sera imprimé dans le format suivant.
2020-10-31 20:51:15.345000 générations:5 Meilleures informations individuelles:
S = 4 E = 6 N = 1 D = 9
M = 0 O = 5 R = 3 Y = 2
SEND = 4619 MORE = 536 MONEY = 5162 difference : 7
Essayez de déplacer des problèmes dans la classe SendMoreMoneyProblem
Exécutons un algorithme génétique pour résoudre un problème dans la classe SendMoreMoneyProblem.
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()
Cette fois, ce sera un problème plus compliqué que SimpleEquationProblem, nous avons donc augmenté le nombre d'individus à 1000 (le temps de calcul sera donc plus long en conséquence).
Le seuil est de 1,0 lorsque l'erreur devient 0 comme indiqué dans la section des fonctions d'évaluation. Puisqu'il peut y avoir des cas où le problème ne peut être résolu, le nombre maximum de générations a été porté à 1000.
Puisque la valeur de la fonction d'évaluation ne devient pas négative cette fois, la sélection de la roulette peut être utilisée, c'est donc une bonne idée de spécifier la sélection de la roulette.
Lorsque je l'ai déplacé, l'erreur est devenue 0 à la 25e génération, comme indiqué ci-dessous.
2020-10-31 20:51:33.663973 Nombre de générations:24 Meilleures informations individuelles:
S = 5 E = 7 N = 3 D = 1
M = 0 O = 6 R = 4 Y = 8
SEND = 5731 MORE = 647 MONEY = 6378 difference : 0
--------------------------------
La solution a été trouvée comme 5731 $ + 647 = 6378 $. Puisque cette combinaison vaut pour une autre combinaison, le résultat de l'exécution peut être une autre combinaison. De plus, bien que la réponse ait été recherchée dans une génération relativement précoce cette fois, il y a des cas où plus de générations sont nécessaires parce que cela dépend de résultats aléatoires, et inversement, la réponse peut être trouvée immédiatement dans la troisième génération.
Code entier
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):
"""
Une classe abstraite qui traite des chromosomes (un élément d'un algorithme génétique).
"""
@abstractmethod
def get_fitness(self) -> float:
"""
Pour la fonction d'évaluation Y pour obtenir l'excellence des chromosomes pour le problème d'intérêt
Méthode abstraite.
Returns
-------
fitness : float
Valeur de l'excellence chromosomique pour le problème d'intérêt. Plus le problème est élevé
Il devient un chromosome approprié.
Il est également utilisé pour déterminer la fin d'un algorithme génétique.
"""
...
@classmethod
@abstractmethod
def make_random_instance(cls) -> Chromosome:
"""
Créer une instance avec des caractéristiques aléatoires (valeurs d'attribut)
Méthode abstraite.
Returns
-------
instance : Chromosome
L'instance générée.
"""
...
@abstractmethod
def mutate(self) -> None:
"""
Une méthode abstraite de traitement qui (soudainement) mute un chromosome.
Des paramètres de valeur différents aléatoires tels que les attributs d'instance sont exécutés.
"""
...
@abstractmethod
def exec_crossover(self, other: Chromosome) -> List[Chromosome]:
"""
Le croisement est exécuté en référence à une autre personne spécifiée dans l'argument.
Parameters
----------
other : Chromosome
Un autre individu utilisé en croisement.
Returns
-------
result_chromosomes : list of Chromosome
Deux individus (chromosomes) générés après le croisement.
"""
...
def __lt__(self, other: Chromosome) -> bool:
"""
Une fonction pour comparer la valeur de la fonction d'évaluation, qui est utilisée pour la comparaison entre les individus.
Parameters
----------
other : Chromosome
Autres individus à comparer.
Returns
-------
result_bool : bool
Valeur booléenne indiquant si la condition la plus faible est satisfaite ou non.
"""
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:
"""
Une classe qui traite des algorithmes génétiques.
Parameters
----------
initial_population : list of Chromosome
Population de première génération (groupe chromosomique).
threshold : float
Un seuil utilisé pour déterminer la résolution des problèmes. Les individus qui dépassent cette valeur
Le calcul se termine lorsqu'il se produit.
max_generations : int
Nombre maximum de générations à exécuter dans l'algorithme.
mutation_probability : float
Probabilité de mutation (0.0～1.0）。
crossover_probability : float
Probabilité de croisement (0.0～1.0）。
selection_type : int
Méthode de sélection. Spécifiez l'une des valeurs constantes suivantes.
- 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]:
"""
Sélectionnez la roulette et sélectionnez deux individus (chromosomes) à utiliser pour le croisement, etc.
avoir.
Returns
-------
selected_chromosomes : list of Chromosome
Une liste contenant les deux individus sélectionnés (chromosomes). Le processus de sélection est une fonction d'évaluation
Il est extrait au hasard avec le poids défini par (méthode de remise en forme).
Notes
-----
Il ne peut pas être utilisé pour les problèmes où la valeur de résultat de la fonction d'évaluation est négative.
"""
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]:
"""
Deux individus pour la sélection du tournoi et le croisement
Obtenez (chromosome).
Returns
-------
selected_chromosomes : list of Chromosome
Une liste contenant les deux individus sélectionnés (chromosomes). tournoi
Les deux premiers individus sont extraits du nombre de cas spécifié dans l'argument pour
Ensemble.
"""
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:
"""
Généré l'individu de prochaine génération (chromosome) et généré la valeur d'attribut de la population
Remplacez par la population de prochaine génération.
"""
new_population: List[Chromosome] = []
#La comparaison du nombre de cas n'est pas égale, compte tenu du cas où le nombre de cas de la population d'origine est un nombre impair.
#Le jugement est basé sur des conditions moindres.
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)
#En raison de la commodité d'augmenter la liste de nouvelle génération de deux, le nombre de cas est plus grand que la liste d'origine
#S'il y en a beaucoup, supprimez-les de la liste et faites correspondre le nombre d'éléments de la liste avec la liste d'origine.
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]:
"""
Traiter comme la prochaine génération à partir de la liste calculée de deux parents
Obtenez une liste de deux populations.
Croiser ou muter avec une certaine probabilité, si la probabilité n'est pas satisfaite, la valeur de l'argument sera
Il sera défini comme la prochaine génération tel qu'il est.
Parameters
----------
parents : list of Chromosome
Liste de deux individus du parent calculé
Returns
-------
next_generation_chromosomes : list of Chromosome
Une liste contenant deux individus définis comme la prochaine génération.
"""
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]:
"""
Obtenez une liste de deux individus parents (chromosomes) selon la méthode de sélection.
Returns
-------
parents : list of Chromosome
Une liste des deux individus (chromosomes) du parent acquis.
Raises
------
ValueError
Lorsqu'une méthode de sélection non prise en charge est spécifiée.
"""
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(
'Une méthode de sélection non prise en charge est spécifiée: %s'
% self._selection_type)
return parents
def run_algorithm(self) -> Chromosome:
"""
Une instance d'un individu (chromosome) qui exécute un algorithme génétique et aboutit à une exécution
Obtenir.
Returns
-------
betst_chromosome : Chromosome
Individu du résultat de l'exécution de l'algorithme. Les personnes qui dépassent le seuil dans la fonction d'évaluation
Ou si le seuil n'est pas dépassé, le nombre spécifié de générations a été atteint.
L'individu avec la valeur de fonction d'évaluation la plus élevée à ce moment est défini.
"""
best_chromosome: Chromosome = \
deepcopy(self._get_best_chromosome_from_population())
for generation_idx in range(self._max_generations):
print(
datetime.now(),
f'Nombre de générations: {generation_idx}'
f'Meilleures informations individuelles: {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:
"""
Dans la liste des populations, sélectionnez l'individu (chromosome) avec la valeur de fonction d'évaluation la plus élevée.
avoir.
Returns
-------
best_chromosome : Chromosome
L'individu avec la valeur de fonction d'évaluation la plus élevée de la liste.
"""
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:
"""
La formule simple suivante pour vérifier le fonctionnement de l'algorithme génétique
6x - x^2 + 4 * y - y^2
Une classe qui traite le problème de trouver les valeurs de x et y qui maximisent la valeur de.
(La bonne réponse est x= 3, y = 2）
Parameters
----------
x : int
La valeur initiale de x.
y : int
La valeur initiale de y.
"""
self.x = x
self.y = y
def get_fitness(self) -> float:
"""
6x avec les valeurs x et y actuelles- x^2 + 4 * y - y^Du résultat du calcul de l'équation 2
Une méthode utilisée comme fonction d'évaluation pour obtenir la valeur.
Returns
-------
fitness : int
La valeur du résultat du calcul de la formule.
"""
x: int = self.x
y: int = self.y
return 6 * x - x ** 2 + 4 * y - y ** 2
@classmethod
def make_random_instance(cls) -> SimpleEquationProblem:
"""
De la classe SimpleEquationProblem avec une valeur initiale aléatoire
Créez une instance.
Returns
-------
problem : SimpleEquationProblem
L'instance générée. x et y sont aléatoires dans la plage 0-99
La valeur est définie.
"""
x: int = randrange(100)
y: int = randrange(100)
problem = SimpleEquationProblem(x=x, y=y)
return problem
def mutate(self) -> None:
"""
Mutant (soudainement) un individu (selon le nombre aléatoire, la valeur de x ou y
1 augmentation / diminution).
"""
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]:
"""
Le croisement est exécuté en référence à une autre personne spécifiée dans l'argument.
Parameters
----------
other : SimpleEquationProblem
Un autre individu utilisé en croisement.
Returns
-------
result_chromosomes : list of SimpleEquationProblem
Une liste contenant les deux individus générés après le croisement. Devenir parent
C'est un individu qui hérite de la moitié des valeurs de x et y de chaque individu.
"""
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:
"""
Renvoie la chaîne de caractères des informations individuelles.
Returns
-------
info : str
Chaîne de caractères d'informations individuelles.
"""
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 =Problème de calcul masqué de MONEY avec un algorithme génétique
Classe à résoudre.
Parameters
----------
letters_dict : LetterDict
Chacun des huit caractères (clés) utilisés dans le problème et la valeur numérique attribuée (valeur)
Un dictionnaire qui stocke les valeurs initiales de.
"""
self.letters_dict: LetterDict = letters_dict
def get_fitness(self) -> float:
"""
SEND par la valeur numérique attribuée à chaque caractère courant+Avec PLUS de numéros
Une méthode pour la fonction d'évaluation basée sur la différence entre les valeurs numériques de MONEY.
Notes
-----
Parce que la valeur de la fonction d'évaluation de l'algorithme génétique est hautement évaluée
La valeur est ajustée de sorte que plus l'erreur est grande, plus la valeur est basse.
Sera retourné.
Returns
-------
fitness : int
SEND +Valeur d'évaluation basée sur la différence entre la valeur MORE et la valeur MONEY.
Plus la différence est petite, plus la valeur est définie.
"""
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:
"""
Obtenez la valeur de SEND par la valeur numérique de chaque caractère actuellement alloué.
Returns
-------
send_val : int
La valeur de SEND par la valeur numérique de chaque caractère actuellement alloué.
"""
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:
"""
Obtenez la valeur de MORE par la valeur numérique de chaque caractère actuellement alloué.
Parameters
----------
more_val : int
La valeur de MORE par la valeur numérique de chaque caractère actuellement alloué
"""
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):
"""
Obtenez la valeur de MONEY par la valeur numérique de chaque caractère actuellement attribué.
Returns
-------
money_val : int
La valeur de MONEY basée sur la valeur numérique de chaque caractère actuellement attribué.
"""
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:
"""
De la classe SendMoreMoneyProblem avec une valeur initiale aléatoire
Créez une instance.
Returns
-------
problem : SendMoreMoneyProblem
L'instance générée. Chaque caractère a une plage de 0 à 9
Les valeurs sont définies de sorte que les nombres ne se chevauchent pas.
"""
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:
"""
Couper le son d'un individu (soudainement) (attribuer au hasard une valeur de caractère spécifique)
Remplacez par un nombre inexistant).
"""
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:
"""
Obtient le numéro qui n'est pas attribué à chaque caractère.
Returns
-------
not_assigned_num : int
Un numéro qui n'est pas attribué à chaque caractère. Bien qu'il y ait 8 caractères,
Puisqu'il y a 10 nombres de 0 à 9, il y a 2 nombres non alloués,
L'un d'eux est défini.
"""
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]:
"""
Le croisement est exécuté en référence à une autre personne spécifiée dans l'argument.
Parameters
----------
other : SendMoreMoneyProblem
Un autre individu utilisé en croisement.
Returns
-------
result_chromosomes : list of SendMoreMoneyProblem
Une liste contenant les deux individus générés après le croisement.
"""
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:
"""
Parmi les numéros définis pour le parent, les numéros qui n'ont pas encore été définis pour l'enfant
avoir.
Notes
-----
Cas où les valeurs sélectionnables ne peuvent pas être trouvées en fonction de la combinaison des valeurs parent et enfant
Dans ce cas, le nombre non alloué parmi les valeurs de 0 à 9 est
Ensemble.
Parameters
----------
child : SendMoreMoneyProblem
Enfant individuel.
parent : SendMoreMoneyProblem
Individu parental.
Returns
-------
not_assigned_num : int
Numéro calculé, non attribué.
"""
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:
"""
Renvoie la chaîne de caractères des informations individuelles.
Returns
-------
info : str
Chaîne de caractères d'informations individuelles.
"""
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()
Site de référence / résumé de référence
- Classic Computer Science Problems in Python
- [Algorithme génétique-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)
- Théorie de l'évolution de Darwin. Ceux qui survivent ne sont pas "des gens qui peuvent changer" mais "des gens qui ont de la chance"
- [Calcul non masqué] ENVOYER + PLUS = ARGENT Je vais vous expliquer en détail comment résoudre le problème!
Recommended Posts