AI avec Python - Algorithmes génétiques

Ce chapitre traite en détail des algorithmes génétiques de l'IA.

Que sont les algorithmes génétiques?

Les algorithmes génétiques (AG) sont des algorithmes basés sur la recherche basés sur les concepts de sélection naturelle et de génétique. Les GA sont un sous-ensemble d'une branche beaucoup plus vaste du calcul connue sous le nom de calcul évolutif.

Les AG ont été développés par John Holland et ses étudiants et collègues de l'Université du Michigan, notamment David E. Goldberg. Il a depuis été essayé sur divers problèmes d'optimisation avec un grand succès.

Dans les AG, nous avons un pool de solutions possibles au problème donné. Ces solutions subissent ensuite une recombinaison et une mutation (comme dans la génétique naturelle), produisent de nouveaux enfants et le processus se répète sur plusieurs générations. Chaque individu (ou solution candidate) se voit attribuer une valeur de fitness (en fonction de sa valeur de fonction objective) et les individus plus en forme ont une plus grande chance de s'accoupler et de céderfitterpersonnes. Ceci est conforme à la théorie darwinienne deSurvival of the Fittest.

Ainsi, il garde evolving de meilleurs individus ou solutions au fil des générations, jusqu'à ce qu'il atteigne un critère d'arrêt.

Les algorithmes génétiques sont de nature suffisamment aléatoire, mais ils fonctionnent bien mieux que la recherche locale aléatoire (où nous essayons simplement des solutions aléatoires, en gardant une trace des meilleures à ce jour), car ils exploitent également les informations historiques.

Comment utiliser GA pour les problèmes d'optimisation?

L'optimisation est une action visant à rendre la conception, la situation, les ressources et le système aussi efficaces que possible. Le diagramme suivant montre le processus d'optimisation -

Étapes du mécanisme GA pour le processus d'optimisation

Ce qui suit est une séquence d'étapes du mécanisme GA lorsqu'il est utilisé pour l'optimisation des problèmes.

Étape 1 - Générez la population initiale de manière aléatoire.
Étape 2 - Sélectionnez la solution initiale avec les meilleures valeurs de fitness.
Étape 3 - Recombinez les solutions sélectionnées à l'aide d'opérateurs de mutation et de croisement.
Étape 4 - Insérez une progéniture dans la population.
Étape 5 - Maintenant, si la condition d'arrêt est remplie, renvoyez la solution avec sa meilleure valeur de fitness. Sinon, passez à l'étape 2.

Installation des packages nécessaires

Pour résoudre le problème en utilisant des algorithmes génétiques en Python, nous allons utiliser un package puissant pour GA appelé DEAP. Il s'agit d'une bibliothèque de nouveaux cadres de calcul évolutifs pour le prototypage rapide et le test d'idées. Nous pouvons installer ce package à l'aide de la commande suivante sur l'invite de commande -

pip install deap

Si vous utilisez anaconda environnement, puis la commande suivante peut être utilisée pour installer deap -

conda install -c conda-forge deap

Implémentation de solutions à l'aide d'algorithmes génétiques

Cette section vous explique la mise en œuvre de solutions utilisant des algorithmes génétiques.

Générer des modèles de bits

L'exemple suivant vous montre comment générer une chaîne de bits qui contiendrait 15 uns, en fonction de la One Max problème.

Importez les packages nécessaires comme indiqué -

import random
from deap import base, creator, tools

Définissez la fonction d'évaluation. C'est la première étape pour créer un algorithme génétique.

def eval_func(individual):
   target_sum = 15
   return len(individual) - abs(sum(individual) - target_sum),

Maintenant, créez la boîte à outils avec les bons paramètres -

def create_toolbox(num_bits):
   creator.create("FitnessMax", base.Fitness, weights=(1.0,))
   creator.create("Individual", list, fitness=creator.FitnessMax)

Initialiser la boîte à outils

toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual,
   toolbox.attr_bool, num_bits)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

Enregistrer l'opérateur d'évaluation -

toolbox.register("evaluate", eval_func)

Maintenant, enregistrez l'opérateur de croisement -

toolbox.register("mate", tools.cxTwoPoint)

Enregistrer un opérateur de mutation -

toolbox.register("mutate", tools.mutFlipBit, indpb = 0.05)

Définir l'opérateur pour l'élevage -

toolbox.register("select", tools.selTournament, tournsize = 3)
return toolbox
if __name__ == "__main__":
   num_bits = 45
   toolbox = create_toolbox(num_bits)
   random.seed(7)
   population = toolbox.population(n = 500)
   probab_crossing, probab_mutating = 0.5, 0.2
   num_generations = 10
   print('\nEvolution process starts')

Évaluer l'ensemble de la population -

fitnesses = list(map(toolbox.evaluate, population))
for ind, fit in zip(population, fitnesses):
   ind.fitness.values = fit
print('\nEvaluated', len(population), 'individuals')

Créer et itérer à travers les générations -

for g in range(num_generations):
   print("\n- Generation", g)

Sélection des individus de la prochaine génération -

offspring = toolbox.select(population, len(population))

Maintenant, clonez les individus sélectionnés -

offspring = list(map(toolbox.clone, offspring))

Appliquer le croisement et la mutation sur la progéniture -

for child1, child2 in zip(offspring[::2], offspring[1::2]):
   if random.random() < probab_crossing:
   toolbox.mate(child1, child2)

Supprimer la valeur de fitness de l'enfant

del child1.fitness.values
del child2.fitness.values

Maintenant, appliquez la mutation -

for mutant in offspring:
   if random.random() < probab_mutating:
   toolbox.mutate(mutant)
   del mutant.fitness.values

Évaluer les personnes dont l'aptitude physique est invalide -

invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
   ind.fitness.values = fit
print('Evaluated', len(invalid_ind), 'individuals')

Maintenant, remplacez la population par l'individu de la prochaine génération -

population[:] = offspring

Imprimer les statistiques des générations actuelles -

fits = [ind.fitness.values[0] for ind in population]
length = len(population)
mean = sum(fits) / length
sum2 = sum(x*x for x in fits)
std = abs(sum2 / length - mean**2)**0.5
print('Min =', min(fits), ', Max =', max(fits))
print('Average =', round(mean, 2), ', Standard deviation =',
round(std, 2))
print("\n- Evolution ends")

Imprimer la sortie finale -

best_ind = tools.selBest(population, 1)[0]
   print('\nBest individual:\n', best_ind)
   print('\nNumber of ones:', sum(best_ind))
Following would be the output:
Evolution process starts
Evaluated 500 individuals
- Generation 0
Evaluated 295 individuals
Min = 32.0 , Max = 45.0
Average = 40.29 , Standard deviation = 2.61
- Generation 1
Evaluated 292 individuals
Min = 34.0 , Max = 45.0
Average = 42.35 , Standard deviation = 1.91
- Generation 2
Evaluated 277 individuals
Min = 37.0 , Max = 45.0
Average = 43.39 , Standard deviation = 1.46
… … … …
- Generation 9
Evaluated 299 individuals
Min = 40.0 , Max = 45.0
Average = 44.12 , Standard deviation = 1.11
- Evolution ends
Best individual:
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 
 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0,
 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1]
Number of ones: 15

Problème de régression de symboles

C'est l'un des problèmes les plus connus de la programmation génétique. Tous les problèmes de régression symbolique utilisent une distribution de données arbitraire et tentent d'ajuster les données les plus précises avec une formule symbolique. Habituellement, une mesure comme le RMSE (Root Mean Square Error) est utilisée pour mesurer la forme physique d'un individu. C'est un problème de régresseur classique et ici nous utilisons l'équation5x³-6x²+8x=1. Nous devons suivre toutes les étapes comme suit dans l'exemple ci-dessus, mais la partie principale serait de créer les ensembles primitifs car ce sont les blocs de construction pour les individus afin que l'évaluation puisse commencer. Ici, nous utiliserons l'ensemble classique de primitives.

Le code Python suivant explique cela en détail -

import operator
import math
import random
import numpy as np
from deap import algorithms, base, creator, tools, gp
def division_operator(numerator, denominator):
   if denominator == 0:
      return 1
   return numerator / denominator
def eval_func(individual, points):
   func = toolbox.compile(expr=individual)
   return math.fsum(mse) / len(points),
def create_toolbox():
   pset = gp.PrimitiveSet("MAIN", 1)
   pset.addPrimitive(operator.add, 2)
   pset.addPrimitive(operator.sub, 2)
   pset.addPrimitive(operator.mul, 2)
   pset.addPrimitive(division_operator, 2)
   pset.addPrimitive(operator.neg, 1)
   pset.addPrimitive(math.cos, 1)
   pset.addPrimitive(math.sin, 1)
   pset.addEphemeralConstant("rand101", lambda: random.randint(-1,1))
   pset.renameArguments(ARG0 = 'x')
   creator.create("FitnessMin", base.Fitness, weights = (-1.0,))
   creator.create("Individual",gp.PrimitiveTree,fitness=creator.FitnessMin)
   toolbox = base.Toolbox()
   toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)
   toolbox.expr)
   toolbox.register("population",tools.initRepeat,list, toolbox.individual)
   toolbox.register("compile", gp.compile, pset = pset)
   toolbox.register("evaluate", eval_func, points = [x/10. for x in range(-10,10)])
   toolbox.register("select", tools.selTournament, tournsize = 3)
   toolbox.register("mate", gp.cxOnePoint)
   toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)
   toolbox.register("mutate", gp.mutUniform, expr = toolbox.expr_mut, pset = pset)
   toolbox.decorate("mate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17))
   toolbox.decorate("mutate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17))
   return toolbox
if __name__ == "__main__":
   random.seed(7)
   toolbox = create_toolbox()
   population = toolbox.population(n = 450)
   hall_of_fame = tools.HallOfFame(1)
   stats_fit = tools.Statistics(lambda x: x.fitness.values)
   stats_size = tools.Statistics(len)
   mstats = tools.MultiStatistics(fitness=stats_fit, size = stats_size)
   mstats.register("avg", np.mean)
   mstats.register("std", np.std)
   mstats.register("min", np.min)
   mstats.register("max", np.max)
   probab_crossover = 0.4
   probab_mutate = 0.2
   number_gen = 10
   population, log = algorithms.eaSimple(population, toolbox,
      probab_crossover, probab_mutate, number_gen,
      stats = mstats, halloffame = hall_of_fame, verbose = True)

Notez que toutes les étapes de base sont les mêmes que celles utilisées lors de la génération de modèles de bits. Ce programme nous donnera la sortie sous forme de min, max, std (écart type) après 10 générations.

↰ Previous page Next page ↱