IA com Python - Algoritmos Genéticos

Este capítulo discute algoritmos genéticos de IA em detalhes.

O que são algoritmos genéticos?

Algoritmos Genéticos (AGs) são algoritmos de busca baseados nos conceitos de seleção natural e genética. Os AGs são um subconjunto de um ramo muito maior da computação conhecido como Computação Evolutiva.

Os AGs foram desenvolvidos por John Holland e seus alunos e colegas da Universidade de Michigan, principalmente David E. Goldberg. Desde então, ele foi testado em vários problemas de otimização com alto grau de sucesso.

Em GAs, temos um conjunto de soluções possíveis para o problema fornecido. Essas soluções então passam por recombinação e mutação (como na genética natural), produzem novos filhos e o processo se repete por várias gerações. Cada indivíduo (ou solução candidata) recebe um valor de aptidão (com base em seu valor de função objetivo) e os indivíduos mais aptos recebem uma chance maior de acasalar e produzirfitterindivíduos. Isso está de acordo com a Teoria Darwiniana deSurvival of the Fittest.

Assim, mantém evolving melhores indivíduos ou soluções ao longo das gerações, até atingir um critério de parada.

Os algoritmos genéticos são suficientemente aleatórios por natureza, mas têm um desempenho muito melhor do que a pesquisa local aleatória (onde apenas tentamos soluções aleatórias, rastreando as melhores até agora), pois também exploram informações históricas.

Como usar o GA para problemas de otimização?

A otimização é uma ação de tornar o design, a situação, o recurso e o sistema tão eficazes quanto possível. O diagrama de blocos a seguir mostra o processo de otimização -

Estágios do mecanismo GA para o processo de otimização

A seguir está uma sequência de etapas do mecanismo de GA quando usado para otimização de problemas.

Etapa 1 - Gerar a população inicial aleatoriamente.
Etapa 2 - Selecione a solução inicial com os melhores valores de aptidão.
Etapa 3 - recombinar as soluções selecionadas usando operadores de mutação e crossover.
Etapa 4 - Insira uma prole na população.
Etapa 5 - Agora, se a condição de parada for atendida, retorne a solução com seu melhor valor de aptidão. Caso contrário, vá para a etapa 2.

Instalando os pacotes necessários

Para resolver o problema usando Algoritmos Genéticos em Python, vamos usar um pacote poderoso para GA chamado DEAP. É uma biblioteca de nova estrutura de computação evolutiva para prototipagem rápida e teste de ideias. Podemos instalar este pacote com a ajuda do seguinte comando no prompt de comando -

pip install deap

Se você estiver usando anaconda ambiente, o seguinte comando pode ser usado para instalar o deap -

conda install -c conda-forge deap

Implementando Soluções Usando Algoritmos Genéticos

Esta seção explica a implementação de soluções usando Algoritmos Genéticos.

Gerando padrões de bits

O exemplo a seguir mostra como gerar uma string de bits que conteria 15 unidades, com base no One Max problema.

Importe os pacotes necessários conforme mostrado -

import random
from deap import base, creator, tools

Defina a função de avaliação. É o primeiro passo para criar um algoritmo genético.

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

Agora, crie a caixa de ferramentas com os parâmetros certos -

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

Inicialize a caixa de ferramentas

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 o operador de avaliação -

toolbox.register("evaluate", eval_func)

Agora, registre o operador de crossover -

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

Registre um operador de mutação -

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

Defina o operador para reprodução -

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

Avalie toda a população -

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

Crie e repita através das gerações -

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

Selecionando os indivíduos da próxima geração -

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

Agora, clone os indivíduos selecionados -

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

Aplicar crossover e mutação na prole -

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

Exclua o valor de aptidão da criança

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

Agora, aplique a mutação -

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

Avalie os indivíduos com aptidão invá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')

Agora, substitua a população por indivíduos da próxima geração -

population[:] = offspring

Imprima as estatísticas para as gerações atuais -

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 o 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 regressão de símbolo

É um dos problemas mais conhecidos da programação genética. Todos os problemas de regressão simbólica usam uma distribuição de dados arbitrária e tentam ajustar os dados mais precisos com uma fórmula simbólica. Normalmente, uma medida como o RMSE (Root Mean Square Error) é usada para medir a aptidão de um indivíduo. É um problema clássico de regressor e aqui estamos usando a equação5x³-6x²+8x=1. Precisamos seguir todas as etapas conforme seguidas no exemplo acima, mas a parte principal seria criar os conjuntos primitivos porque eles são os blocos de construção para os indivíduos para que a avaliação possa começar. Aqui estaremos usando o conjunto clássico de primitivas.

O código Python a seguir explica isso em detalhes -

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)

Observe que todas as etapas básicas são iguais às usadas durante a geração de padrões de bits. Este programa nos dará a saída como min, max, std (desvio padrão) após 10 números de gerações.

↰ Previous page Next page ↱