IA con Python - Algoritmos genéticos

Este capítulo analiza en detalle los algoritmos genéticos de la IA.

¿Qué son los algoritmos genéticos?

Los algoritmos genéticos (GA) son algoritmos basados en búsquedas que se basan en los conceptos de selección natural y genética. Los GA son un subconjunto de una rama mucho más grande de la computación conocida como Computación Evolutiva.

Los GA fueron desarrollados por John Holland y sus estudiantes y colegas de la Universidad de Michigan, sobre todo David E. Goldberg. Desde entonces, se ha probado en varios problemas de optimización con un alto grado de éxito.

En los GA, tenemos un conjunto de posibles soluciones al problema dado. Estas soluciones luego se someten a recombinación y mutación (como en la genética natural), producen nuevos hijos y el proceso se repite durante varias generaciones. A cada individuo (o solución candidata) se le asigna un valor de aptitud (basado en su valor de función objetivo) y los individuos más en forma tienen una mayor probabilidad de aparearse y ceder.fitterindividuos. Esto está en consonancia con la teoría darwiniana deSurvival of the Fittest.

Por lo tanto, mantiene evolving mejores individuos o soluciones a lo largo de generaciones, hasta que alcanza un criterio de parada.

Los algoritmos genéticos son de naturaleza suficientemente aleatoria, pero funcionan mucho mejor que la búsqueda local aleatoria (en la que solo probamos soluciones aleatorias, realizando un seguimiento de las mejores hasta ahora), ya que también explotan información histórica.

¿Cómo utilizar GA para problemas de optimización?

La optimización es una acción para hacer que el diseño, la situación, el recurso y el sistema sean lo más efectivos posible. El siguiente diagrama de bloques muestra el proceso de optimización:

Etapas del mecanismo GA para el proceso de optimización

La siguiente es una secuencia de pasos del mecanismo GA cuando se usa para optimizar problemas.

Paso 1: Genere la población inicial al azar.
Paso 2: seleccione la solución inicial con los mejores valores de aptitud.
Paso 3: vuelva a combinar las soluciones seleccionadas utilizando operadores de mutación y cruce.
Paso 4: inserta una descendencia en la población.
Paso 5: ahora, si se cumple la condición de parada, devuelva la solución con su mejor valor de aptitud. De lo contrario, vaya al paso 2.

Instalación de paquetes necesarios

Para resolver el problema mediante el uso de algoritmos genéticos en Python, vamos a utilizar un paquete poderoso para GA llamado DEAP. Es una biblioteca de un marco informático evolutivo novedoso para la creación rápida de prototipos y la prueba de ideas. Podemos instalar este paquete con la ayuda del siguiente comando en el símbolo del sistema:

pip install deap

Si esta usando anaconda entorno, luego se puede usar el siguiente comando para instalar deap:

conda install -c conda-forge deap

Implementación de soluciones utilizando algoritmos genéticos

Esta sección le explica la implementación de soluciones usando algoritmos genéticos.

Generando patrones de bits

El siguiente ejemplo le muestra cómo generar una cadena de bits que contendría 15 unidades, según el One Max problema.

Importe los paquetes necesarios como se muestra:

import random
from deap import base, creator, tools

Defina la función de evaluación. Es el primer paso para crear un algoritmo genético.

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

Ahora, cree la caja de herramientas con los parámetros correctos:

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

Inicializar la caja de herramientas

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)

Registre el operador de evaluación -

toolbox.register("evaluate", eval_func)

Ahora, registre el operador de cruce -

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

Registrar un operador de mutación -

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

Definir el operador para la cría -

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')

Evaluar a toda la población -

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

Crea e itera a través de generaciones -

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

Selección de las personas de la próxima generación:

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

Ahora, clone los individuos seleccionados -

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

Aplicar crossover y mutación en la descendencia -

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

Eliminar el valor de aptitud del niño

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

Ahora, aplique la mutación -

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

Evaluar a las personas con una aptitud no válida.

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')

Ahora, reemplace la población con el individuo de la próxima generación:

population[:] = offspring

Imprima las estadísticas de las generaciones actuales -

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")

Imprima el resultado final -

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

Problema de regresión de símbolos

Es uno de los problemas más conocidos de la programación genética. Todos los problemas de regresión simbólica utilizan una distribución de datos arbitraria y tratan de ajustar los datos más precisos con una fórmula simbólica. Por lo general, se utiliza una medida como el RMSE (error cuadrático medio) para medir la aptitud de un individuo. Es un problema clásico de regresor y aquí estamos usando la ecuación5x³-6x²+8x=1. Necesitamos seguir todos los pasos como se indica en el ejemplo anterior, pero la parte principal sería crear los conjuntos primitivos porque son los bloques de construcción de los individuos para que pueda comenzar la evaluación. Aquí usaremos el conjunto clásico de primitivas.

El siguiente código de Python explica esto en detalle:

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)

Tenga en cuenta que todos los pasos básicos son los mismos que se utilizan al generar patrones de bits. Este programa nos dará la salida como min, max, std (desviación estándar) después de 10 generaciones.

↰ Previous page Next page ↱