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.