N1_IA

Prévia do material em texto

Erick Steffano Modolin dos Santos 
 
Universidade Anhembi Morumbi 
Outubro 2021 
 
 
 
 
 
 
 
 
 
 
Algoritmos Genéticos 
 
Inteligência Artificial e Aprendizado de Máquina 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 2 
 
1. INTRODUÇÃO 
 
Os algoritmos genéticos são uma família de modelos computacionais inspirados 
e baseados na proposta evolutiva de Darwin (seleção natural). 
A moderna teoria da evolução combina a genética e as ideias de Darwin e Alfred 
Russel Wallace sobre a seleção natural, criando o princípio básico de Genética 
Populacional: a variabilidade entre indivíduos em uma população de organismos 
que se reproduzem sexualmente é produzida pela mutação e pela recombinação 
genética. 
Este princípio foi desenvolvido durante vários anos, por biólogos e matemáticos 
de importantes centros de pesquisa. Durante os anos 50 e 60, muitos biólogos 
começaram a desenvolver simulações computacionais de sistemas genéticos. 
Entretanto, foi John Holland quem começou, seriamente, a desenvolver as 
primeiras pesquisas no tema. Holland foi gradualmente refinando suas idéias e 
em 1975 publicou o seu livro Adaptation in Natural and Artificial Systems, hoje 
considerado a Bíblia de Algoritmos Genéticos. 
Atualmente algoritmos genéticos são particularmente utilizados e aplicados em 
problemas complexos de otimização, como por exemplo: 
1. Problemas com diversos parâmetros ou características que precisam ser 
combinadas em busca da melhor solução; 
2. Problemas com muitas restrições ou condições que não podem ser 
representadas matematicamente; 
3. Problemas com grandes espaços de busca. 
Este tipo de algoritmo é eficiente para a resolução de problemas de otimização 
e pode ser aplicado em diversas áreas, do setor industrial ao setor da saúde. 
Alguns exemplos de aplicações desenvolvidas são: 
• Fluxo de Caixa Inteligente; 
• Classificação de Clientes (Data Mining); 
• Alocação de Espaço Físico; 
• Planejamento e Otimização de Embarque de Minérios. 
Devido ao funcionamento deste algoritmo ser baseado em uma teoria evolutiva 
natural, temos as seguintes analogias entre Algoritmos Genéticos e o sistema 
natural: 
 
 3 
Natureza Algoritmos Genéticos 
Cromossoma Palavra binária, vetor, etc 
Gene Característica do 
problema 
Alelo Valor da característica 
Loco Posição na palavra, vetor 
Genótipo Estrutura 
Fenótipo Estrutura submetida ao 
problema 
Indivíduo Solução 
Geração Ciclo 
 
 
2. FUNCIONAMENTO DO ALGORITMO 
 
O primeiro estágio trata da criação da população de soluções candidatas ao 
problema. Com esse conjunto inicial, passa-se a uma fase de avaliação, em que 
a função avaliadora (fitness function) verifica a adequação de cada membro 
gerado ao problema proposto. 
Os valores obtidos pela função avaliadora são classificados pelo algoritmo, 
sendo selecionadas as soluções com melhor desempenho para a fase seguinte, 
que é a reprodução. 
Nessa última fase, as soluções com melhor valor de fitness compõem um novo 
conjunto de soluções candidatas, e estes são submetidos a uma reprodução 
entre pares, onde são misturadas partes das soluções dos cromossomos pais, 
gerando dois novos cromossomos. 
Ainda na fase de reprodução, os cromossomos recém gerados, são submetidos 
a uma fase de mutação de seus genes, sendo mutados seguindo uma 
probabilidade previamente definida. 
Após estes cromossomos serem submetidos a mutação, estes são submetidos 
novamente a função fitness, que avaliará a aptidão de cada cromossomo 
gerado, selecionando as soluções mais aptas para compor esta nova geração. 
Caso o critério para a parada do algoritmo seja atingido, seja pela quantidade 
de gerações definidas ou por atingir a meta satisfatória, estas soluções serão 
apresentadas. Caso contrário o algoritmo submetera os cromossomos aos passos 
citados acima novamente em um loop, até que seja atingido o critério de 
parada do algoritmo. 
 
2.1 DETALHES DE FUNCIONAMENTO 
 
Para exemplificar o uso de tal modelo de algoritmo, utilizarei um problema de 
otimização combinatória que consiste em preencher uma mochila com diversos 
objetos de diferentes pesos e valores, onde a finalidade é que ocupe esta 
mochila com o maior valor possível, sem ultrapassar seu peso limite. 
 4 
Foram criadas várias listas do tamanho da população, onde cada uma tem 
tamanho igual ao número de itens da mochila, os valores individuais destas 
listas podem ser 0 ou 1, representando a presença ou ausência de cada item 
naquela possível solução. Também foi criado uma lista de listas contendo os 
pesos dos itens e seus respectivos valores. 
Após ter definido os pesos e valores de todos os itens, foi extraído a quantia 
total de itens que temos, o peso máximo que a mochila pode carregar, o 
tamanho da população por geração, e o número de gerações desejadas. Com os 
dados definidos, o algoritmo se inicia realizando os seguintes passos: 
1. Gera uma população aleatória de acordo com o número de indivíduos 
desejado; 
2. Utiliza uma função Fitness para avaliar os cromossomos de acordo com o 
valor total contido em sua mochila, e descarta indivíduos cujo peso total 
de seus itens excedam o limite; 
3. Com base no valor contido na mochila de cada indivíduo considerado 
apto, é executado uma função roleta, com a finalidade de sortear quais 
cromossomos serão cruzados entre si, sem haver elitismo, os 
cromossomos sempre são misturados para próxima geração. O operador 
de cruzamento escolhido foi de “um-ponto”, sendo o corte sempre 
realizado no meio do cromossomo, ou no caso de número ímpar de genes, 
com truncamento do número pelo valor imediatamente inferior (função 
chão). Os indivíduos gerados pelos pais são a nova geração; 
4. Após a reprodução, alguns dos filhos gerados sofrem mutação. A taxa 
padrão definida foi de 8%, ou seja, cada filho tem uma chance de 8% de 
ter algum de seus genes alterado, se isso ocorrer, o gene a ser mutado é 
selecionado de forma aleatória, se seu valor for 1 muda para 0 e vice-
versa; 
5. Volta para o item 2, até que cumpra o critério de parada, onde neste 
caso é o número de gerações definido anteriormente, e então finaliza a 
execução apresentando os resultados. 
 
 
 5 
3. CÓDIGO 
 
Genetica.py 
 
from random import getrandbits, randint, random, choice 
 
def individual(n_de_itens): 
 """Cria um membro da populacao""" 
 return [ getrandbits(1) for x in range(n_de_itens) ] 
 
def population(n_de_individuos, n_de_itens): 
 """"Cria a populacao""" 
 return [ individual(n_de_itens) for x in range(n_de_individuos) ] 
 
def fitness(individuo, peso_maximo, pesos_e_valores): 
 """Faz avaliacao do individuo""" 
 peso_total, valor_total = 0, 0 
 for indice, valor in enumerate(individuo): 
 peso_total += (individuo[indice] * pesos_e_valores[indice][0]) 
 valor_total += (individuo[indice] * pesos_e_valores[indice][1]) 
 
 if (peso_maximo - peso_total) < 0: 
 return -1 #retorna -1 no caso de peso excedido 
 return valor_total #se for um individuo valido retorna seu valor, sendo maior melhor 
 
def media_fitness(populacao, peso_maximo, pesos_e_valores): #só leva em 
consideracao os elementos que respeitem o peso maximo da mochila 
 """Encontra a avalicao media da populacao""" 
 summed = sum(fitness(x, peso_maximo, pesos_e_valores) for x in populacao if 
fitness(x, peso_maximo, pesos_e_valores) >= 0) 
 return summed / (len(populacao) * 1.0) 
 
def selecao_roleta(pais): 
 """Seleciona um pai e uma mae baseado nas regras da roleta""" 
 def sortear(fitness_total, indice_a_ignorar=-1): #2 parametro garante que não vai 
selecionar o mesmo elemento 
 """Monta roleta para realizar o sorteio""" 
 roleta, acumulado, valor_sorteado = [], 0, random() 
 
 if indice_a_ignorar!=-1: #Desconta do total, o valor que sera retirado da roleta 
 fitness_total -= valores[0][indice_a_ignorar]for indice, i in enumerate(valores[0]): 
 if indice_a_ignorar==indice: #ignora o valor ja utilizado na roleta 
 continue 
 acumulado += i 
 roleta.append(acumulado/fitness_total) 
 if roleta[-1] >= valor_sorteado: 
 return indice 
 
 6 
 valores = list(zip(*pais)) #cria 2 listas com os valores fitness e os cromossomos 
 fitness_total = sum(valores[0]) 
 
 indice_pai = sortear(fitness_total) 
 indice_mae = sortear(fitness_total, indice_pai) 
 
 pai = valores[1][indice_pai] 
 mae = valores[1][indice_mae] 
 
 return pai, mae 
 
def evolve(populacao, peso_maximo, pesos_e_valores, n_de_cromossomos, 
mutate=0.08): 
 """Tabula cada individuo e o seu fitness""" 
 pais = [ [fitness(x, peso_maximo, pesos_e_valores), x] for x in populacao if fitness(x, 
peso_maximo, pesos_e_valores) >= 0] 
 pais.sort(reverse=True) 
 
 # REPRODUCAO 
 filhos = [] 
 while len(filhos) < n_de_cromossomos: 
 homem, mulher = selecao_roleta(pais) 
 meio = len(homem) // 2 
 filho = homem[:meio] + mulher[meio:] 
 filhos.append(filho) 
 
 # MUTACAO 
 for individuo in filhos: 
 if mutate > random(): 
 pos_to_mutate = randint(0, len(individuo)-1) 
 if individuo[pos_to_mutate] == 1: 
 individuo[pos_to_mutate] = 0 
 else: 
 individuo[pos_to_mutate] = 1 
 
 return filhos 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 7 
MochilaAG.py 
 
from Genetica import * 
 #[peso,valor] 
pesos_e_valores = [[5, 50], [8, 100], [8, 30], [2, 75], \ 
 [2, 10], [60, 180], [9, 300], [12, 50], \ 
 [100, 400], [8, 300]] 
peso_maximo = 140 
n_de_cromossomos = 100 
geracoes = 150 
n_de_itens = len(pesos_e_valores) #Analogo aos pesos e valores 
 
#EXECUCAO DOS PROCEDIMENTOS 
populacao = population(n_de_cromossomos, n_de_itens) 
historico_de_fitness = [media_fitness(populacao, peso_maximo, pesos_e_valores)] 
for i in range(geracoes): 
 populacao = evolve(populacao, peso_maximo, pesos_e_valores, n_de_cromossomos) 
 historico_de_fitness.append(media_fitness(populacao, peso_maximo, 
pesos_e_valores)) 
 
#PRINTS DO TERMINAL 
for indice,dados in enumerate(historico_de_fitness): 
 print ("Geracao: ", indice," | Media de valor na mochila: ", dados) 
 
print("\nPeso máximo:",peso_maximo,"g\n\nItens disponíveis:") 
for indice,i in enumerate(pesos_e_valores): 
 print("Item ",indice+1,": ",i[0],"g | R$",i[1]) 
 
print("\nExemplos de boas solucoes: ") 
for i in range(5): 
 print(populacao[i]) 
 
#GERADOR DE GRAFICO 
from matplotlib import pyplot as plt 
plt.plot(range(len(historico_de_fitness)), historico_de_fitness) 
plt.grid(True, zorder=0) 
plt.title("Problema da mochila") 
plt.xlabel("Geracao") 
plt.ylabel("Valor medio da mochila") 
plt.show() 
 
 
 
 
 
 
 
 
 
 8 
4. REFERENCIAS 
 
< ALGORITMOS GENÉTICOS: PRINCÍPIOS E APLICAÇÕES -
http://www.inf.ufsc.br/~mauro.roisenberg/ine5377/Cursos-ICA/CE-intro_apost.pdf > 
 
< APLICAÇÕES DE ALGORITMOS GENÉTICOS - 
http://www.fsma.edu.br/si/edicao3/aplicacoes_de_alg_geneticos.pdf > 
 
< Algoritmos Genéticos - https://sites.icmc.usp.br/andre/research/genetic/ > 
 
< Introdução ao Algoritmo Genético - 
https://www.youtube.com/watch?v=xtHMSJLnKsE, 
https://www.youtube.com/watch?v=96mlWTAvjik > 
https://www.youtube.com/watch?v=xtHMSJLnKsE