Algoritmos Genéticos

Introdução

 

 

Um algoritmo de otimização é um procedimento ou conjunto de regras matemáticas que busca encontrar a melhor solução possível para um problema específico. Existem diferentes exemplos de algoritmos de otimização, dentre eles está o tema do nosso artigo, Algoritmos Genéticos.

 

 

 Basicamente Algoritmos Genéticos são uma classe de algoritmos de otimização inspirados na seleção natural e na genética. Desenvolvidos por John Holland na década de 1960, esses algoritmos têm sido aplicados com sucesso em diversos domínios, desde engenharia e ciência da computação a biologia e finanças.

 

 

A ideia fundamental por trás desses algoritmos é explorar sistemática e eficientemente o espaço de soluções possíveis para encontrar aquela que otimiza a função objetivo. Existem várias abordagens para desenvolver algoritmos de otimização, e a escolha da técnica adequada muitas vezes depende da natureza específica do problema em questão.

 

 

 

---

 

 

A Teoria da Seleção Natural

 

 

A seleção natural é um conceito fundamental na teoria da evolução proposta por Charles Darwin. Segundo esta teoria, os indivíduos mais adaptados ao seu ambiente têm maiores chances de sobreviver e passar suas características para as próximas gerações. Com o tempo, isso resulta na evolução das espécies, onde características vantajosas tornam-se mais prevalentes.

 

 

Simplificando, aquele ser vivo que está mais adaptado a sobreviver continua passando suas características para seus filhos, aquele que está menos adaptado morre e suas características são perdidas.

 

 

 

 

A seleção natural possui princípios, são eles variação, hereditariedade e seleção diferencial e os algoritmos genéticos utilizam da teoria desses princípios.

 

 

Vamos explicar esses tópicos e relacioná-los com os algoritmos.

 

 

• • Variação: indivíduos de uma população apresentam variação em suas características, devido à diversidade genética.

• • Hereditariedade: as características que conferem alguma vantagem para a sobrevivência e reprodução têm maior probabilidade de serem transmitidas para a próxima geração.

• • Seleção diferencial: ambientes seletivos favorecem certas características, resultando em maior sucesso reprodutivo para os indivíduos que as possuem.

 

 

A ideia fundamental dos algoritmos genéticos é emular esse processo de seleção natural para encontrar soluções otimizadas para um problema específico. Podemos relacionar esses pilares da seleção natural com alguns princípios básicos dos algoritmos genéticos.

 

 

 

---

 

 

Princípios básicos dos algoritmos genéticos

 

 

Os algoritmos genéticos operam com uma população de soluções candidatas, onde cada solução é representada como um “indivíduo” com um conjunto de características ou genes.

 

 

O processo de encontrar o melhor indivíduo dentro dessa população envolve as seguintes etapas:

 

 

População inicial

 

 

Uma população inicial de soluções candidatas é criada. Cada solução representa um indivíduo na população.

 

 

Avaliação de aptidão

 

 

Cada solução na população é avaliada quanto à sua “aptidão” ou “qualidade”, com base na função objetivo que se deseja otimizar. A aptidão é uma medida de quão bem a solução resolve o problema proposto.

 

 

Seleção

 

 

Indivíduos mais aptos têm uma maior probabilidade de serem selecionados para reprodução. Os melhores indivíduos que atenderem ao problema proposto serão selecionados.

 

 

Recombinação (Crossover)

 

 

Pares de soluções selecionadas são combinados para criar novas soluções, chamadas descendentes. 

 

 

Mutação

 

 

Algumas das novas soluções podem sofrer mutações, introduzindo pequenas alterações aleatórias em suas características. Isso simula a variabilidade genética que ocorre naturalmente.

 

 

Substituição

 

 

As novas soluções (descendentes) e as soluções originais são combinadas para formar a próxima geração de soluções.

 

 

Esse ciclo de seleção, recombinação e mutação é repetido por várias gerações até que uma solução satisfatória ou otimizada seja encontrada.

 

 

 

 

 

 

Aplicações práticas

 

 

 

 

 

 

---

 

 

Vamos à prática!

 

 

Vamos agora aplicar os conceitos fundamentais dos Algoritmos Genéticos (AGs) na prática, usando um exemplo simples implementado em Python. Abaixo, destacamos a implementação dos princípios básicos de algoritmos genéticos explicados anteriormente.

 

 

Inicialização da população

 

 

 Gera aleatoriamente uma população inicial, onde cada indivíduo é uma sequência de bits representada por uma lista de números 0 ou 1. Este código implementa um algoritmo genético para otimizar uma população de sequências binárias, onde cada sequência representa um indivíduo. O objetivo é evoluir essa população ao longo de várias gerações para que todos os bits de cada indivíduo se tornem 1.

def initialize_population(population_size, individual_size):    

      return [[random.randint(0, 1) for _ in range(individual_size)] for _ in range(population_size)]

Função de aptidão

 

 

Esta função calcula a aptidão de um indivíduo, que é simplesmente a soma dos bits 1 na sequência. Isso representa como um indivíduo é “bom” em termos de resolver o problema.

 

 

def fitness_function(individual):
    return sum(individual)

 

 

 

 

Crosssover

 

 

Realiza a operação de crossover. Escolhe aleatoriamente um ponto de crossover e combina os genes dos pais para criar um descendente.

 

 

def crossover(parent1, parent2):
    crossover_point = random.randint(0, len(parent1) - 1)
    child = parent1[:crossover_point] + parent2[crossover_point:]
    return child

 

 

 

 

Mutação

 

 

Introduz mutação em um indivíduo. Cada bit na sequência tem uma chance de ser invertido (XOR) com base na taxa de mutação.

 

 

def mutate(individual, mutation_rate):
    return [bit ^ (random.random() < mutation_rate) for bit in individual]

 

 

 

 

Algoritmo genético

 

 

Esta é a função principal que executa o algoritmo genético.

 

 

1. 1. Inicialização: Gera a população inicial.

1. 1. Loop das Gerações: Itera sobre as gerações.

1. 1. Avaliação da Aptidão: Calcula a aptidão de cada indivíduo.

1. 1. Seleção dos Pais: Seleciona os melhores indivíduos como pais.

1. 1. Crossover e Mutação: Gera uma nova geração combinando genes dos pais e introduzindo mutações.

1. 1. Substituição: Atualiza a população com a nova geração.

1. 1. Convergência: Verifica se a convergência foi alcançada.

1. 1. Impressão: Exibe informações sobre a melhor aptidão na geração atual.

 

 

def genetic_algorithm(population_size, generations, mutation_rate, individual_size):
    population = initialize_population(population_size, individual_size)
    for generation in range(generations):
        fitness_scores = [(individual, fitness_function(individual)) for individual in population]
        population = [individual for individual, _ in sorted(fitness_scores, key=lambda x: x[1],                  reverse=True)]
        parents = population[:int(0.2 * population_size)]
        children = []
        while len(children) < population_size - len(parents):
            parent1, parent2 = random.choice(parents), random.choice(parents)
            child = mutate(crossover(parent1, parent2), mutation_rate)
            children.append(child)
        population = parents + children
        best_individual, best_fitness = max(fitness_scores, key=lambda x: x[1])
        print(f"Geracao {generation}: Melhor aptidão = {best_fitness}, Melhor indivíduo =             {best_individual}")
        if best_fitness == individual_size:
            print("Convergência alcançada! Todos os bits são 1.")
            break
    return max(fitness_scores, key=lambda x: x[1])[0]

 

 

 

 

 

Saída do código

 

 

Geracao 0: Melhor aptidão = 5, Melhor indivíduo = [0, 1, 0, 0, 0, 1, 1, 0, 1, 1]
Geracao 1: Melhor ap
Geracao 1: Melhor aptidão = 5, Melhor indivíduo = [0, 1, 0, 0, 0, 1, 1, 0, 1, 1]
Geracao 2: Melhor aptidão = 5, Melhor indivíduo = [0, 1, 0, 0, 0, 1, 1, 0, 1, 1]
Geracao 3: Melhor aptidão = 7, Melhor indivíduo = [1, 1, 0, 0, 0, 1, 1, 1, 1, 1]
Geracao 4: Melhor aptidão = 7, Melhor indivíduo = [1, 1, 0, 0, 0, 1, 1, 1, 1, 1]
Geracao 5: Melhor aptidão = 7, Melhor indivíduo = [1, 1, 0, 0, 0, 1, 1, 1, 1, 1]
Geracao 6: Melhor aptidão = 7, Melhor indivíduo = [1, 1, 0, 0, 0, 1, 1, 1, 1, 1]
Geracao 7: Melhor aptidão = 8, Melhor indivíduo = [1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
Geracao 8: Melhor aptidão = 8, Melhor indivíduo = [1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
Geracao 9: Melhor aptidão = 8, Melhor indivíduo = [1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
Geracao 10: Melhor aptidão = 8, Melhor indivíduo = [1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
Geracao 11: Melhor aptidão = 8, Melhor indivíduo = [1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
Geracao 12: Melhor aptidão = 9, Melhor indivíduo = [1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
Geracao 13: Melhor aptidão = 9, Melhor indivíduo = [1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
Geracao 14: Melhor aptidão = 9, Melhor indivíduo = [1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
Geracao 15: Melhor aptidão = 9, Melhor indivíduo = [1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
Geracao 16: Melhor aptidão = 9, Melhor indivíduo = [1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
Geracao 17: Melhor aptidão = 9, Melhor indivíduo = [1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
Geracao 18: Melhor aptidão = 10, Melhor indivíduo = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Convergência alcançada! Todos os individuos são 1.

Melhor solução encontrada: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Valor da função de aptidão: 10

 

 

 

 

Link para o código completo

 

 

https://colab.research.google.com/drive/1dGjc3ykcvjNoW5C8jiAcNMuVxAn81KXT?authuser=0#scrollTo=ZzIPpXmFOXlc

 

 

 

 

---

 

 

Prós e Contras dos Algoritmos Genéticos

 

 

Os algoritmos genéticos (AGs) são uma ferramenta poderosa na caixa de ferramentas de um programador, mas como qualquer ferramenta, eles têm suas vantagens e desvantagens.

 

 

 

 

Prós dos Algoritmos Genéticos

 

 

Algoritmos genéticos podem ser aplicados a uma ampla variedade de problemas, especialmente aqueles onde o espaço de solução é vasto ou mal definido. Além disso, eles são eficazes em encontrar soluções satisfatórias em ambientes complexos e em constante mudança, onde os métodos tradicionais de otimização podem falhar. Eles podem se adaptar às mudanças nas condições do problema ou do ambiente ao longo do tempo.

 

 

 

 

Contras dos Algoritmos Genéticos

 

 

Algoritmos genéticos geralmente encontram boas soluções, mas não há garantia de que a solução ótima será encontrada. Dependendo do tamanho do problema e da complexidade do espaço de busca, os AGs podem ser computacionalmente intensivos. Ajustar os parâmetros dos AGs (como taxa de mutação, tamanho da população) pode ser complicado e ter um grande impacto no desempenho do algoritmo.

 

 

 

 

Desafios na implementação

 

 

Uma das maiores dificuldades é projetar uma função de aptidão que reflita adequadamente o problema e guie eficazmente a evolução. Encontrar o equilíbrio certo entre explorar novas áreas do espaço de busca e explorar as áreas conhecidas para refinar soluções existentes. Evitar a convergência prematura e manter uma diversidade genética saudável na população ao longo das gerações.

 

 

 

 

---

 

 

Conclusão

 

 

Os algoritmos genéticos oferecem uma abordagem única e eficaz para a seleção do melhor indivíduo em um conjunto de soluções. Sua capacidade de imitar a evolução biológica e aplicar princípios de seleção natural faz deles uma ferramenta poderosa para a otimização e a solução de problemas complexos em diversos domínios. Se você está em busca da melhor escolha entre várias possibilidades, os algoritmos genéticos podem ser a chave para o sucesso. 

 

Autores

172885 Felipe Akira Nozaki 

174265 Vinicius Jardim Vasconcelos 

234451 Caio Gomes Piteli 

237468 Eduardo Longhi 

255002 Henrique Bexiga Eulálio