Aprendizagem de máquina, Inteligência artificial, Robótica

O que é algoritmo genético?

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.

 

Liked it? Take a second to support Electrical e-Library on Patreon!

About Pedro Ney Stroski

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *