O assunto deste post é uma introdução de mais uma área da inteligência artificial: O algoritmo genético. É um método de otimização baseado na evolução biológica, buscando a melhor solução para um problema.
Definições
Tem uma função objetiva, que é a solução e um grupo de candidatos, cujo nome é população, para ver quais se aproximam mais da solução. Cada solução tem um grupo de bits, chamado cromossomo. E cada bit é um gene.
O crossover consiste em pegar os genes das soluções que passaram no primeiro teste e criar uma nova geração. A próxima geração tem seus genes modificados pela mutação. Os operadores genéticos fazem a mutação e o crossover nos cromossomos.
Todo algoritmo genético tem 4 parâmetros:
- Tamanho da população: Muito baixa população cai o desempenho, enquanto uma população muito alta exige maior poder computacional;
- Taxa de cruzamento: Valor muito baixo torna o algoritmo lento, mas um valor muito alto pode eliminar cromossomos adaptados;
- Taxa de mutação: Determina o grau de mutações nos cromossomos.
- Intervalo de geração: Determina o tamanho da parte da população que será substituída pela próxima geração.
Procedimento
Este é o fluxograma básico do algoritmo genético.
Primeiro os candidatos são gerados aleatoriamente e codificados em um grupo de bits, depois faz-se o cálculo da aptidão. Os cromossomos mais próximos da solução são selecionados e embaralhados criando pares de parceiros para realizar o crossover. Existem três formas de crossover, de um-ponto, onde é escolhido um ponto de cruzamento.
Tem o crossover de múltiplos pontos.
Ou pode-se cortar e emendar, este método pode mudar o tamanho do conjunto de bits.
O operador genético de mutação troca os bits de um cromossomo aleatoriamente, a mutação é útil para encontrar a melhor solução possível.
A nova geração é avaliada pela função de adaptação, o ciclo continua até a resolução do problema ser encontrada.
Algumas aplicações
Estes algoritmos podem ser usados em robôs que se auto programam e se adaptam a mudanças de situações e padrões. Aplicações fora da robótica envolvem:
- Resolução de problemas de otimização como o problema do caixeiro viajante;
- Gerenciamento de redes sem fio para descobrir as melhores rotas para conexões;
- Síntese de circuitos eletrônicos;
- Simulação de modelos biológicos.
