Algoritmo Genético Binário

Trabalho de Otimização Combinatória, faculdade de Ciência da Computação, Universidade Estadual do Oeste do Paraná - UNIOESTE, campus de Cascavel.

Desenvolvido por: Gabriel Mazzuco

Indice

• Descrição do Projeto
  • O que é um algoritmo genético?
  • Como funciona um algoritmo genético?
  • Especificação do problema proposto
    • Especificações do problema para a implementação
• Como foi implementado
  • Individuo.py
  • Funcoes_extras.py
  • Funcoes_AG.py
• Pré-requisitos
  • Requisitos para o projeto
  • Requisitos mínimos de hardware
• Como usar
• Referências

Descrição do Projeto

O que é um algoritmo genético?

Algoritmos genéticos são uma técnica de otimização que utiliza conceitos da teoria da evolução de Darwin para encontrar soluções para problemas complexos. Eles são baseados em uma população de indivíduos que representam possíveis soluções para o problema em questão. Cada indivíduo é representado por um cromossomo, que é uma sequência de genes. Os genes são os parâmetros que definem a solução proposta pelo indivíduo.

Como funciona um algoritmo genético?

O funcionamento de um algoritmo genético pode ser resumido em cinco etapas:

1. Inicialização: Uma população inicial de indivíduos é gerada aleatoriamente.
2. Avaliação: Cada indivíduo é avaliado de acordo com sua aptidão para resolver o problema em questão.
3. Seleção: Indivíduos mais aptos são selecionados para reprodução.
4. Recombinação: Os indivíduos selecionados são combinados para gerar novos indivíduos.
5. Mutação: Os novos indivíduos sofrem mutações aleatórias para introduzir diversidade na população.

Essas etapas são repetidas por um número fixo de gerações ou até que uma solução satisfatória seja encontrada.

Especificação do problema

O problema proposto consiste em encontrar a melhor solução, ou seja, o conjunto de indivíduos que alcançam a convergência para o valor ótimo da função de aptidão, conforme as gerações foram passando.

Especificações do problema para a implementação

Codificação	Seleção	Cruzamento	Mutação	Elitismo
Binária	Ranking	2 Pontos aleatórios	Inversão binária	1 indivíduo por geração

Função de otimização é dada por:

$$ Z = x^2 + y^2 + (3x + 4y - 26)^2 $$

Os valores de x e y possuem restrições que devem ser seguidas:

$x \in [0, 10]$ | $y \in [0, 20]$

• Codificação binária: Cada indivíduo é representado por um cromossomo binário. Cada gene do cromossomo pode assumir o valor 0 ou 1, nos cromossomos X, temos 4 bits para parte inteira e 10 bits para parte fracionária, e nos cromossomos Y, temos 5 bits para parte inteira e 9 bits para parte fracionária. No final das contas, geramos um número real quando passamos para a função de otimização

  • Exemplo:
    • X = [1, 0, 1, 1,| 0, 1, 1, 0, 1, 0, 1, 1, 0, 1]
    • Y = [0, 1, 1, 0, 1,| 1, 0, 1, 1, 0, 1, 1, 0, 1, 0]

• Seleção por ranking: A seleção dos indivíduos é direta e aleatória, selecionando n indivíduos da população onde todos possuem a mesma chance

• Cruzamento de 2 pontos aleatórios: Dois pontos aleatórios são escolhidos nos cromossomos dos pais, e os segmentos entre esses pontos são trocados para gerar os cromossomos dos filhos.

• Mutação por inversão binária: Um gene aleatório do cromossomo do indivíduo sofre uma inversão de valor.

• Elitismo: Um indivíduo da população é selecionado para ser mantido na próxima geração, garantindo que a melhor solução encontrada até o momento não seja perdida.

Como foi implementado

A implementação do código foi feita em python, para a execução do programa, na pasta raiz deve ter os arquivos individuo.py; funcoes_extras.py e o mais importante, o funcoes_AG.py.

Individuo.py

div align="center">

O arquivo individuo.py é responsável por criar a classe Individuo, que é responsável por criar um indivíduo com as características necessárias para a execução do algoritmo genético. Dentro dele serão armazenados os valores de x e y, o fitness do indivíduo e o seu cromossomo binário

class Individuo:
    def __init__(self, x, y, fitness, num_x, num_y):
        self.x = x              # Cromossomo X
        self.num_x = num_x      # Numero do cromossomo X
        self.y = y              # Cromossomo Y
        self.num_y = num_y      # Numero do cromossomo Y
        self.fitness = fitness  # Fitness do individuo

Funcoes_extras.py

funcoes_extras.py

O arquivo funcoes_extras.py é responsável por criar funções que são utilizadas para a execução do algoritmo genético mas que não são diretamente ligadas a ele. Dentro dele definimos o input dos parametro iniciais, como o cromossomo é montado. Também é feito de forma genérica a conversão de binário para decimal e vice-versa que é algo necessário para a execução do algoritmo genético binário.

tamanho_populacao = int(input("Digite o tamanho da populacao: "))
geracoes = int(input("Digite o numero de geracoes: "))
probabilidade_mutacao = float(input("Digite a probabilidade de mutacao: "))
probabilidade_cruzamento = float(input("Digite a probabilidade de cruzamento: "))

cromossomo_gene_inteiro_x = 4
cromossomo_gene_inteiro_y = 5
cromossomo_gene_real = 10

# Converte a cadeia binária em sua representação decimal, dividindo-a em parte inteira e parte fracionária.
def converte_bin_num(num, cromossomo_gene_inteiro):

# Converte um número decimal em sua representação binária, dividindo-o em parte inteira e parte fracionária.
def converte_num_bin(num, cromossomo_gene_inteiro, cromossomo_gene_real)

Funcoes_AG.py

funcoes_AG.py

O arquivo funcoes_AG.py é responsável por criar as funções que são utilizadas de fato no algoritmo genético. Dentro dele definimos as funções de otimização, seleção, cruzamento, mutação e elitismo. Além disto, é gerado os indivíduos que serão adicionados a população

def funcao_de_otimização(x, y):
    z = (math.pow(x, 2)) + (math.pow(y, 2)) + (math.pow((3*x) + (4*y) - 26, 2))
    return z

def gera_individuo(cromossomo_gene_inteiro_x, cromossomo_gene_inteiro_y, cromossomo_gene_real):

    # Gera um cromossomo X -> Cadeia binaria de bits de tamanho cromossomo_gene_inteiro_x
    cromossomo_x = random.choices([0, 1], k=cromossomo_gene_inteiro_x + cromossomo_gene_real)

    # Gera um cromossomo Y -> Cadeia binaria de bits de tamanho cromossomo_gene_inteiro_y
    cromossomo_y = random.choices([0, 1], k=cromossomo_gene_inteiro_y + cromossomo_gene_real)

# Função aonde é determinado o melhor individuo da população
def eletista(populacao):

# A seleção é por ranking, ou seja a probabilidade de seleção é direta e aleatória
# seleciona-se n indivíduos onde todos têm a mesma chance de serem selecionados
def seleciona_pais_ranking(populacao):

# Função de cruzamento de 2 pontos aleatórios, aonde é feito a troca de genes entre os pais
# separando o cromossomo em 3 partes e trocando a parte do meio
def crossover(pai1, pai2, probabilidade_cruzamento, tam_cromossomo_x, tam_cromossomo_y):
    # Cria os filhos
    filho1_x = parte1_x_pai1 + parte2_x_pai2 + parte3_x_pai1
    filho1_y = parte1_y_pai1 + parte2_y_pai2 + parte3_y_pai1
    
    filho2_x = parte1_x_pai2 + parte2_x_pai1 + parte3_x_pai2
    filho2_y = parte1_y_pai2 + parte2_y_pai1 + parte3_y_pai2

# Passa por todos os genes do filho e faz a mutacao de acordo com a probabilidade
# se for menor que a probabilidade de mutacao, ele muda o gene trocando de 0 para 1 e vice-versa
def mutacao(filho1_x, filho1_y, filho2_x, filho2_y, probabilidade_mutacao):

Pré-requisitos

Requisitos para o projeto

Para executar o projeto, você precisará ter instalado em sua máquina as seguintes ferramentas:

• Python, versão 3.8 ou superior

  • 'sudo apt-get install python3.8'

• Rich, versão 10.6.0 ou superior

  • 'pip install rich'

• Matplotlib, versão 3.4.3 ou superior

  • 'pip install matplotlib'

Requisitos mínimos de hardware

• Sistema operacional: Windows 10 ou superior com WSL, Linux
• Processador: Intel Core dual-core ou superior
• Memória RAM: 4 GB ou superior
• Espaço em disco: 1 GB ou superior

Como usar

1. Clone o repositório
   • 'git clone
2. Acesse a pasta do projeto
   • 'cd algoritmo-genetico'
3. Execute o arquivo principal
   • 'python3 main.py' ou abra o arquivo algoritmo-genetico.ipynb no Jupyter Notebook
4. Determine os parâmetros iniciais do algoritmo genético
   • 'Digite o número de gerações: '
   • 'Digite o tamanho da população: '
   • 'Digite a taxa de mutação: '
   • 'Digite o número de indivíduos selecionados para reprodução: '
5. Aguarde a execução do algoritmo genético
6. Visualize os resultados obtidos
   • Será exibido 3 gráficos:
     • Gráfico de dispersão com a população final
     • Gráfico ideal para a função de otimização
     • Gráfico do fitness médio da população por geração

Referências

• Algoritmo Genético: Princípios e Aplicações
• Algoritmo genético
• OpenAI. (2024). GPT-3.5: Modelo de Linguagem Pré-Treinado
• OpenAI e GitHub. (2024). GitHub Copilot: Ferramenta de Autocompletar de Código