Algoritmo Genético – Introdução

 

Um algoritmo genético (AG) é uma técnica de busca utilizada na ciência da computação para achar soluções aproximadas em problemas de otimização e busca, fundamentado principalmente pelo americano John Henry Holland. Algoritmos genéticos são uma classe particular de algoritmos evolutivos que usam técnicas inspiradas pela biologia evolutiva como hereditariedade, mutação, seleção natural e recombinação (ou crossing over).

Por Magno Lima

O objetivo deste artigo é apresentar de forma apenas abrangente o uso do AG, sendo recomenda a leitura de outros artigos para maior detalhamento.

Uma boa Inteligência Artificial

O uso de Algoritmo Genérico é melhor do que a IA convencional, pois é mais robusto. Ao contrário dos sistemas de IA mais antigos, eles não se quebram facilmente mesmo que as entradas mudem ligeiramente ou haja presença de ruído razoável. Além disso, ao pesquisar um grande espaço de estados, espaço de estado multimodal ou superfície n-dimensional, um algoritmo genético pode oferecer benefícios significativos em busca de técnicas de otimização mais típicas.

 

Outra abordagem

Para uma solução simplória, o uso de um algoritmo empírico (convencional) poderia ser criado com base num conjunto de regras, por exemplo “se determinada condição for alcançada, aja desta forma”. Com regras suficientes poderíamos reproduzir uma inteligência natural, entretanto a quantidade trabalho seria incalculável e a solução final não seria melhor do que a do seu criador. Seria frustrante desprender tanto tempo sabendo que não se chegará a uma solução elegante e que atenda perfeitamente o propósito esperado.

Daí surgiu o Algoritmo Genético, inspirado na biologia evolutiva cuja ideia é fazer o algoritmo “evoluir” a fim de encontrar a melhor solução para um determinado problema. O algoritmo genético é assim um algoritmo de busca heurística adaptativa. O pai do AG original foi John Holland nos anos de 1970.

Os algoritmos genéticos são especialmente importantes para resolução de problemas do tipo NP-Complete ou NP-C/NPC (nondeterministic polynomial time / tempo polinomial não determinável), problemas deste tipo são aqueles cuja solução rápida para eles não são conhecidas, ou seja, o tempo requerido para resolve-los utilizando qualquer algoritmo conhecido aumenta muito rapidamente conforme o tamanho do problema cresça. Como consequência, estes tipos de problemas NP-C é um dos principais problemas não resolvidos na ciência da computação atualmente.

O passos de funcionamento de Algoritmo Genético pode, ser desmembrados da seguinte forma:

  1. Creation – Criamos uma população de membros aleatórios, pertinentes ao tipo do problema que se deseja resolver;
  2. Fitness – Qualificamos cada membro da população baseado em algum objetivo. A esta qualificação chamamos de “fitness”, ela é a certamente a mais importante pois dela sairá a melhor solução ou melhor espécime daquela população com condição de solucionar/executar o problema;
  3. Selection – Seleciona-se os melhores membros da população para criar descendentes para a nova população, com base no melhor indicador apontado em fitness e eliminamos os restantes (sobrevivem os de maior fitness);
  4. Cross-over – Com os melhores indivíduos executamos o cross-over, ou breed (procriação) para gerar novos membros;
  5. Mutation – Executamos uma “mutação” em alguns membros para tentar desenvolver/encontrar candidatos ainda melhores;
  6. Repetition – Repetimos o segundo passo. A cada iteração através destes passos é o que chamada de “geração”.

A repetição de uma quantidade de vezes deste processo irá resultar nos melhores membros possíveis da população.

As pré-condições para geração da primeira população e o modelo lógico a ser utilizado no cálculo de fitness são extremamente particulares, não há como haver um método de AG universal que inclua todas as soluções possíveis, é obrigatória uma mente pensante por trás a fim de compreender o objetivo que se espera e por consequência tanto os indivíduos iniciais quanto a qualidade definida para seleção e fitness estão diretamente conectadas ao algoritmo inicial que foi desenvolvido. Quanto melhor o código pensado, melhor o resultado.

Um mesmo AG não pode ser utilizado para uma funcionalidade distinta, considere um algoritmo AG como uma espécie de código especializado numa tarefa e esta espécie não se mistura com outras, embora trechos comuns possam ser compartilhados. Um AG orientado para pesquisa de texto não é o mesmo que irá resolver um sistema de roteamento de vias em uma cidade ou ensinar um robô a andar em um ambiente.

Reforçando o conceito: apesar da capacidade de “aprender”, o AG é um código especializado. Em uso com uma rede neural artificial, onde os parâmetros de reconhecimento de padrões possam ser desenvolvidos, uma solução de múltiplos algoritmos tipo AG poderiam ser utilizados, ainda assim mesmo com uma rede neural, é em tese impossível que uma inteligência artificial possa concorrer a fim de obter solução para qualquer demanda que se fizer necessária. A limitação intrínseca dos algoritmos orientados para o aprendizado de máquinas é da própria capacidade atual do homem e das ferramentas que este tem a sua disposição.

No próximo artigo iremos ver como podemos fazer uma simples aplicação que utilize um algoritmo genérico, na prática, além de discorrer em exemplos de utilização e aplicação.

 

 

Deixe uma resposta

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