Definições e Características Gerais


1. Codificação

        As partes que relacionam um AG com um problema dado são a codificação e a função de evolução.

        Se um problema pode ser representado por um conjunto de parâmetros (genes), estes podem ser unidos para formar uma cadeia de valores (cromossomo), este processo se chama codificação. Em genética este conjunto representado por um cromossomo em particular é referenciado como genótipo, contendo a informação necessária para construir um organismo, conhecido como fenótipo. Estes mesmos termos se aplicam em AG, por exemplo, para se desenhar um aponte, um conjunto de parâmetros especificando o desenho é o genótipo, e a construção final é o fenótipo. A adaptação de cada indivíduo depende de seu fenótipo, no qual se pode inferir seu genótipo.

        Por exemplo, para um problema de maximizar uma função de três variáveis, F(X, Y, Z), se poderia representar cada variável por um número binário de 10 bits, obtendo-se um cromossomo de 30 bits de longitude e 3 genes.

        Existem vários aspectos relacionados com a codificação de um problema a serem tomados em conta no momento de sua realização:

se deve utilizar um alfabeto o menor possível para representar os parâmetros; normalmente se utiliza um dígito binário;

as variáveis que representam os parâmetros do problema devem ser discretizadas para poder representar as cadeias de bits;

a maior parte dos problemas tratados com AG's são não lineares e muitas vezes existem relações "ocultas" entre as variáveis que formam a solução;

o tratamento dos genótipos inválidos deve ser tomado em conta para o desenho da codificação.


2. Função de Avaliação

        Dado um cromossomo, a função de avaliação consiste em associar um valor numérico de "adaptação", no qual se supõe que é proporcional a sua "utilidade" ou "habilidade" do indivíduo representado. Em muitos casos, o desenvolvimento de uma função de avaliação pode estar baseada no rendimento e representar somente uma avaliação parcial do problema. Adicionalmente deve ser rápida, já que vai ser aplicada para cada indivíduo de cada população e das sucessivas gerações; devido a este fato, grande parte do tempo gasto por um algoritmo genético se aplica a função de avaliação.


3. Convergência Prematura

        Um problema dos AG's devido a uma mal formulação do modelo é aquele no qual os genes de um poucos indivíduos relativamente bem adaptados, contudo não ótimos, podem rapidamente dominar a população causando que converja a um máximo local. Uma vez que isto ocorre, a habilidade do modelo de buscar melhores soluções é eliminada completamente, e os algoritmo genético se converte em uma busca lenta largada ao azar. Para evitar este problema, é necessário controlar o número de oportunidades reprodutivas de cada indivíduo.


4. Finalização Lenta

        Este é um problema contrário ao anterior, ao longo de muitas gerações, a população haverá convergido, mas não haverá localizado o máximo global. A adaptação será alta e haverá pouca diferença entre o maior e o menor indivíduo. Por conseguinte será muito baixa a tendência da função de adaptação a levar um algoritmo ao máximo As mesmas técnicas na convergência prematura são utilizadas neste caso.


5. Reprodução

        Durante esta fase de um AG, se selecionam indivíduos da população sendo recombinados para formar descendentes que formarão a seguinte geração. Os pares são selecionados ao azar, usando um método que favorece os indivíduos melhor adaptados. Logo que escolhidos os pares, seus cromossomos se mesclam e combinam usando crossover e mutação. As formas básicas destes operadores são:

       Crossover: toma dos indivíduos e corta seus cromossomos em uma partição selecionada ao azar, para produzir os segmentos anteriores e os posteriores, os posteriores realizam um intercâmbio para obter dois novos cromossomos.

        Mutação: um processo importante nos AG's é a mutação, a pesar de que está usualmente concebida como um operador cujo papel é secundário. No caso binário a mutação consiste em substituir com certa probabilidade ( taxa de mutação) o valor de um bit. Existem basicamente duas maneiras de implementá-la. A primeira troca o bit que no teste de probabilidade permite (é decidir, se o i-ésimo bit vale 1 e passa o teste de probabilidade, o novo valor conterá zero na i-ésima posição). Na Segunda, se gera ao azar um novo bit para substituir o bit que passou no teste de probabilidade. Por tanto, 50% das vezes o novo bit não trocará de valor e portanto a taxa de mutação será a metade da primeira técnica.


6. Convergência

        Se um AG foi devidamente implementado, a população evoluirá ao longo de sucessivas gerações de que a adaptação do melhor indivíduo, convergirá para um ótimo global. A convergência é uma progressão uniforme. Um gene será convertido quando em 95% da população tem o mesmo valor. A população converge quando todos os genes de cada indivíduo convergirem.


Características Gerais

        Os Algorítmos Genéticos (AGs) são algorítmos de otimização global empregando uma estratégia de busca paralela e estruturada, mas aleatória, voltada em direção da busca de pontos de "alta aptidão", ou seja, pontos nos quais a função a ser minimizada (ou maximizada) tem valores relativamente baixos (ou altos). Os AGs exploram informações históricas para encontrar novos pontos de busca onde são esperados melhores desempenhos. Isto é feito através de processos iterativos, onde cada iteração é chamada de geração.

        O ponto de partida para a utilização de AGs, como ferramenta para solução de problemas, é a representação destes problemas de maneira que os AGs possam trabalhar adequadamente sobre eles. Tradicionalmente, os indivíduos são representados genotípicamente por vetores binários, onde cada elemento de um vetor denota a presença (1) ou ausência (0) de uma determinada característica: o seu genótipo. Os elementos podem ser combinados formando as características reais do indivíduo, ou o seu fenótipo.

        O princípio básico do funcionamento do AGs é que um critério de seleção vai fazer com que, depois de muitas gerações, o conjunto inicial de indivíduos gere indivíduos masi aptos.

        Um método de seleção muito utilizado é o Método da Roleta, onde indivíduos de uma geração são escolhidos para fazer parte da próxima geração, através de um sorteio de roleta. Os indivíduos são representados na roleta proporcionalmente ao seu índice de aptidão. Finalmente, a roleta é girada um determinado número de vezes, dependendo do tamanho da população, e são escolhidos como indivíduos que participarão da próxima geração, aqueles sorteados na roleta.

        Um conjunto de operações é necessário para que, dada uma população, se consiga gerar populações sucessivas que (espera-se) melhorem sua aptidão com o tempo. Estes operadores são: cruzamento (crossover) e mutação. Eles são utilizados para assegurar que a nova geração seja totalmente nova, mas possui, de alguma forma, características de seus pais. Para prevenir que os melhores indivíduos não desapareçam da população pela manipulação dos operadores genéticos, eles podem ser automaticamente colocados na próxima geração, através da reprodução elitista.

        Esse ciclo é repetido um determinado número de vezes. Abaixo é mostrado um exemplo de Algoritmo Genético. Durante esse processo, os melhores indivíduos, assim como alguns dados estatísticos, podem ser coletados e armazenados para avaliação.

 Procedimento AG
{
    t = 0;
    inicia_população (P, t);
    avaliação (P, t);
    repita até (t = d)
    {
        t = t + 1;
        seleção_dos_pais (P, t);
        recombinação (P, t);
        mutação (P, t);
        avaliação (P, t);
        sobrevivem (P, t);
    }
}

Onde:

t - tempo atual;

d - tempo determinado para finalizar o algoritmo;

P - população.
 

voltar