Rede Neural Artificial - Algoritmo Genético

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

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

Em AGs, temos um conjunto ou população de soluções possíveis para o problema em questão. 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”.

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

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

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, bem como 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 o gás atraente 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. No entanto, na maioria das situações do mundo real, temos um problema muito complexo chamado de paisagens, feito de muitos picos e muitos vales, que faz com que tais métodos falhem, pois sofrem de uma tendência inerente de ficarem presos nos ótimos locais, conforme mostrado na figura a seguir.

Obtendo uma boa solução rapidamente

Alguns problemas difíceis, como o Travelling Salesman Problem (TSP), têm aplicações do mundo real, como localização de caminhos 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.

Como usar o GA para problemas de otimização?

Já sabemos que otimização é uma ação de tornar algo como design, situação, recurso e sistema o mais eficaz possível. O processo de otimização é mostrado no diagrama a seguir.

Estágios do mecanismo de GA para o processo de otimização

A seguir estão os estágios do mecanismo de GA quando usados ​​para otimização de problemas.

  • Gere a população inicial aleatoriamente.

  • Selecione a solução inicial com os melhores valores de fitness.

  • Recombine as soluções selecionadas usando operadores de mutação e crossover.

  • Insira a prole na população.

  • Agora, se a condição de parada for atendida, retorne a solução com seu melhor valor de adequação. Caso contrário, vá para a etapa 2.