Algoritmos Genéticos - Introdução

Algoritmo Genético (GA) é uma técnica de otimização baseada em pesquisa baseada nos princípios de Genetics and Natural Selection. É freqüentemente usado para encontrar soluções ótimas ou quase ótimas para problemas difíceis que, de outra forma, levariam uma vida inteira para serem resolvidos. É frequentemente usado para resolver problemas de otimização, em pesquisa e em aprendizado de máquina.

Introdução à Otimização

Otimização é o processo de making something better. Em qualquer processo, temos um conjunto de entradas e um conjunto de saídas, conforme mostrado na figura a seguir.

Otimização refere-se a encontrar os valores das entradas de forma que obtenhamos os “melhores” valores de saída. A definição de “melhor” varia de problema para problema, mas em termos matemáticos, refere-se a maximizar ou minimizar uma ou mais funções objetivo, variando os parâmetros de entrada.

O conjunto de todas as soluções ou valores possíveis que as entradas podem assumir constitui o espaço de pesquisa. Neste espaço de busca, encontra-se um ponto ou um conjunto de pontos que dá a solução ótima. O objetivo da otimização é encontrar aquele ponto ou conjunto de pontos no espaço de busca.

O que são algoritmos genéticos?

A natureza sempre foi uma grande fonte de inspiração para toda a humanidade. Algoritmos Genéticos (AGs) são algoritmos baseados em busca baseados nos conceitos de seleção natural e genética. GAs são um subconjunto de um ramo muito maior da computação conhecido comoEvolutionary Computation.

Os GAs foram desenvolvidos por John Holland e seus alunos e colegas da Universidade de Michigan, principalmente David E. Goldberg, e desde então foram testados em vários problemas de otimização com alto grau de sucesso.

Em GAs, temos um pool or a population of possible solutionspara o problema fornecido. Essas soluções então passam por recombinação e mutação (como na genética natural), produzindo novos filhos, e o processo se repete por várias gerações. Cada indivíduo (ou solução candidata) recebe um valor de aptidão (com base em seu valor de função objetivo) e os indivíduos mais aptos têm uma chance maior de acasalar e produzir indivíduos mais "aptos". Isso está de acordo com a teoria darwiniana de “sobrevivência do mais apto”.

Desta forma, continuamos “evoluindo” melhores indivíduos ou soluções ao longo das gerações, até chegarmos a um critério de parada.

Os algoritmos genéticos são suficientemente aleatórios por natureza, mas têm um desempenho muito melhor do que a pesquisa local aleatória (na qual apenas tentamos várias soluções aleatórias, rastreando as melhores até agora), pois também exploram informações históricas.

Vantagens dos GAs

Os AGs têm várias vantagens que os tornaram imensamente populares. Isso inclui -

  • Não requer nenhuma informação derivada (que pode não estar disponível para muitos problemas do mundo real).

  • É mais rápido e eficiente em comparação com os métodos tradicionais.

  • Possui recursos paralelos muito bons.

  • Otimiza funções contínuas e discretas e também problemas multi-objetivos.

  • Fornece uma lista de soluções “boas” e não apenas uma solução única.

  • Sempre obtém uma resposta para o problema, que fica melhor com o tempo.

  • Útil quando o espaço de pesquisa é muito grande e há um grande número de parâmetros envolvidos.

Limitações de GAs

Como qualquer técnica, os AGs também sofrem de algumas limitações. Isso inclui -

  • Os AGs não são adequados para todos os problemas, especialmente problemas que são simples e para os quais informações derivadas estão disponíveis.

  • O valor de aptidão é calculado repetidamente, o que pode ser caro do ponto de vista computacional para alguns problemas.

  • Por ser estocástico, não há garantias sobre a otimalidade ou a qualidade da solução.

  • Se não for implementado corretamente, o GA pode não convergir para a solução ideal.

GA - Motivação

Algoritmos genéticos têm a capacidade de fornecer uma solução “boa o suficiente” “rápida o suficiente”. Isso torna os algoritmos genéticos atraentes para uso na solução de problemas de otimização. Os motivos pelos quais os AGs são necessários são os seguintes -

Resolvendo problemas difíceis

Na ciência da computação, há um grande conjunto de problemas, que são NP-Hard. O que isso significa essencialmente é que, mesmo os sistemas de computação mais poderosos levam muito tempo (até anos!) Para resolver esse problema. Em tal cenário, GAs provam ser uma ferramenta eficiente para fornecerusable near-optimal solutions em um curto espaço de tempo.

Falha de métodos baseados em gradiente

Os métodos tradicionais baseados em cálculo funcionam começando em um ponto aleatório e movendo-se na direção do gradiente, até chegarmos ao topo da colina. Essa técnica é eficiente e funciona muito bem para funções objetivo de pico único, como a função de custo na regressão linear. Mas, na maioria das situações do mundo real, temos um problema muito complexo chamado de paisagens, que são feitas de muitos picos e muitos vales, o que faz com que tais métodos falhem, pois sofrem de uma tendência inerente de ficarem presos no ótimo local conforme mostrado na figura a seguir.

Obtendo uma boa solução rapidamente

Alguns problemas difíceis, como o Problema do Vendedor Viajante (TSP), têm aplicações do mundo real, como localização de caminho e projeto VLSI. Agora imagine que você está usando seu sistema de navegação GPS e leva alguns minutos (ou mesmo algumas horas) para calcular o caminho “ótimo” da origem ao destino. Atrasos em tais aplicativos do mundo real não são aceitáveis ​​e, portanto, uma solução "boa o suficiente", que é entregue "rápido" é o que é necessário.