Algoritmos Genéticos
17 de outubro de 2021O Objetivo do algoritmo genéticos é recombinar soluções possíveis de problemas, filtrando estas soluções sempre pelo grau de acerto. Criando descendentes mais adaptados.
Um exemplo de uso, seria encontrar conjuntos de solução que melhor se adapte. Exemplo, alocação de professor em horario de aula.
Fornecendo gerações mais adaptadas a resolução de problemas, até que na Enézima geração encontrar a melhor solução possível.
Os critérios de Parada
O Critério de parada, é utilizado para determinar o fim das interações genéticas.
- Tempo de Execução
- Número de Gerações
- Melhor solução a resposta alcançada.
Seleção de individuos
Nos algoritmos genéticos, usamos os individuos criados na seleção anterior, avaliando os resultados obtidos.
Utilizando para proxima geração apenas os individuos que apresentaram as melhores soluções.
Propriedades de uma geração
São propriedades da geração:
- Taxa de reprodução
- Probabilidade de mutação
- Controle populacional
- Critérios de parada
- Restrições de ambiente
Cromossomo
O Cromossomo, é a represantação da geração, quanto as informações e funcionalidades presentes no individuo, quanto a resolução do problema proposto.
Codificação
É a transformação da informação em valores posicionais para representar informações presentes no algoritmo genético.
Podemos representar a codificação do cromossomo, através da expressão do peso (Valor) .
Como exemplo iremos atribuir os seguintes itens:
- Caracteristica 1 – V1=2
- Característica 2 – V2=4
- Característica 3 – V3=8
- Característica 4 – V4=16
Em uma matriz binária, poderiamos representar nosso gene, através de um sistema binário.
| Car1 | CAR2 | CAR3 | CAR4 |
| 1 | 0 | 0 | 1 |
Na representação acima, podemos ver que a caracteristica 1 e 4 estão presentes no gene.
População Inicial
É a população que possui caracteristicas généticas que serão cruzadas entre sí, gerando diversidade genética.
Mutação
É o relacionamento entre individuos de genética diferente, criando prole diversa, com características misturadas dos individuos PAIS.
Valor Fitness ou adaptabilidade
É o valor de adaptação do genoma, que irá expressar o grau de adaptação ao ambiente que queremos otimizar.
O individuo com menor valor será o mais apto.
Seleção e Reprodução
Taxa de Reprodução é o percentual da população que gerará descendentes. Pode ir de 100% até 0%.
Seleção, é o crivo que determinará se um individuo esta apto a propagar seu gene para a próxima geração.
Avaliação de elegibilidade reprodutiva
Probabilidade ou peso genético
Pega-se o valor fitness do cromossomo, dividindo pelo total do fitness dos cromossomos.
Peso de cromossomo
O Peso do cromossomo, é a soma de todos os genes ativos de um individuo.
Exemplo:
| Car1 | CAR2 | CAR3 | CAR4 |
| 1 | 0 | 0 | 1 |
No exemplo acima, podemos calcular o peso, sendo 1×2+0x4+0x8+1×16= 18.
Podemos determinar um limitador, que será o peso de corte, onde não incluiremos individuos, com valores genéticos acima de um valor. Para evitar chegarmos a valores genéticos totais.
Corte de cromossomo
É o ponto de cruzamento dos cromossomos, no momento da passagem de gene para seus descendentes.
O local de corte é proximo ao ponto central, porem é aleatório.
Otimização
É o processo de tentar encontrar a melhor solução dentre as possíveis para resolução de um problema.
Elementos do Algoritmo genético
- Alelo – Valor que pode representar um gene.
- Gene – Representa uma parte ou característica que forma o cromossomo
- Cromossomo – Representa uma solução genética, formado por genes
- Individuo – Um possivel solução, contendo um conjunto de dados cromossomicos.
- `População – Um conjunto de individuos, que serão cruzados