ALGORITMOS GENÉTICOS

A primeira postagem do blog é um tema que exige uma abordagem detalhada, pois é necessário para entender alguns estudos que serão publicados posteriormente: Algoritmos genéticos. Algoritmos genéticos representam uma técnica de otimização, de busca com padrão aleatório (como os algoritmos de otimização sem força brusca funcionam) a fim de que seja apresentada uma solução ótima para um problema, não sendo essa necessariamente a melhor solução, porém um bom resultado obtido em um espaço de tempo menor do que uma busca por todo o espaço amostral do problema analisado (aqui se fala de bases de dados realmente grandes, as quais seriam difíceis de percorrer totalmente em curto espaço de tempo). Esse algoritmo se baseia no processo evolutivo, observado por Darwin.

1) Apresentação

Exemplo de esquema de fluxograma de um algoritmo genético

A imagem acima apresenta o esquema de etapas da execução de um algoritmo genético. Uma populacão inicial é gerada aleatoriamente e posteriormente entra no processo de reproducão. A seleção determina os indivíduos que serão escolhidos para as etapas posteriores, baseados em caráter aleatório e o valor de aptidão da função utilizada para tal objetivo. Os cromossomos passam pelo cruzamento, misturando genes para gerar descendentes. Posteriormente acontece o processo de mutacão, gerando novas características (ou não, pois também é de caráter probabilístico e depende da taxa de mutação) para a populacão. Novamente a populacão é avaliada. O processo é feito até que sejam criadas todas as gerações especificadas. Algoritmos genéticos podem ser do tipo contínuo ou binário. O tipo abordado nessa publicação será o binário, justificado pela sua praticidade, mas os conceitos são estritamente os mesmos para a versão contínua.

2) Etapas de um algoritmo genético

2.1) Geração de indivíduos

A primeira população é gerada de maneira totalmente aleatória. Um indivíduo é um cromossomo, representado por genes, que, em se tratando de algoritmos genéticos binários, são zeros ou uns.

Estrutura de um indivíduo

2.2) Seleção

A seleção é responsável por escolher os pais, que gerarão descendentes para cada geração. O método de escolha mais comum é a função roleta. Ele consiste na seleção de um indivíduo de acordo com uma probabilidade associada ao cromossomo, sendo esta representada pela função de aptidão. A partir do cálculo da aptidão do indivíduos, uma função de distribuição acumulada é modelada, e seus valores serão armazenados em um vetor organizado de maneira decrescente. São selecionados dois pais de acordo com um índice R, aleatório. As probabilidades dos indivíduos devem ser normalizadas para que se localizem entre 0 e 1.

Distribuição de probabilidade para seleção pela roleta

Processo de seleção dentro de vetor em estrutura de programação

2.3) Cruzamento

Essa etapa, também conhecida como ”Crossover”(o uso do termo sem tradução aparece em alguns trabalhos na área), é responsável pela combinação dos genes dos pais, a fim de

gerar descendentes. De maneira geral, os pacotes gratuitos disponíveis em algumas linguagens possuem os métodos de um ponto ou de dois pontos, para a definição de posição de gene até o qual filho herdará parte de um ancestral, e a partir desse ponto definido, a parte do outro ancestral. Dois pontos aumentam o número de possibilidades de combinação de genes. Por exemplo: Herdar genes do início e fim do vetor de genes de um pai, e a parte intermediária entre esses pontos de outro pai. Costuma-se trabalhar com altas taxas de crossover, pois é mais desejável ter descendentes.

Crossover de ponto único

Crossover de dois pontos

2.4) Mutação

A mutação é uma etapa cuja ação gera uma mudança aleatória de gene associado aos cromossomos da população. Essa alteração gera a necessidade de nova avaliação da capacidade dos indivíduos, para verificar se houve melhor adaptação. Por meio deste operador, novas características dos indivíduos podem ser exploradas, podendo gerar um aprimoramento da solução. Este operador garante uma varredura mais ampla do espaço de estados e evita, por conseguinte, que o algoritmo se precipite e convirja muito cedo para mínimos locais.

Mutação

2.5 ) Elitismo

Esta etapa não é observada em todos os algoritmos genéticos, pois é um aprimoramento da técnica. O Elitismo salva e copia uma pequena porção dos melhores indivíduos, preservando-os para uma próxima geração sem alteração. Para compreender essa etapa de maneira sucinta, seja a restrita a análise para as duas primeiras gerações. Uma primeira geração será totalmente aleatória e a segunda será resultado dessa primeira geração após as etapas de seleção, cruzamento e mutação. Portanto, apenas descendentes passam de um geração para a seguinte. No entanto, pode haver casos para os quais ospais possuem um valor de aptidão interessante e características às vezes mais adaptáveis do que as de seus descendentes. Para tal caso, o projetista consegue evitar a perda de informações presentes nesses indivíduos de alta avaliação, que em alguns casos podem ser perdidas durante os processos de seleção e cruzamento. A destruição de melhores indivíduos pode acontecer por parte da mutação ou crossover. A fim de que seja evitada tal ocorrência, uma parte selecionada dos melhores genes (definidos por uma taxa) pode ser copiada para gerações posteriores. Esse processo melhora a precisão da solução final.

Efeitos do elitismo dentro da evolução

Efeitos do elitismo na convergência de um AG

2.6) Alguns parâmetros comuns de um algoritmo genético:

Algoritmos inteligentes têm soluções aleatórias baseadas em parâmetros probabilísticos.A seguir são apresentados os parâmetros de controle, anteriormente citados e relacionados a probabilidades, os mais comuns em algoritmos genéticos:

• R: Número aleatório gerado no código de seleção responsável pela escolha do indivíduo de acordo com valor gerado entre 0 e 1, que será relacionado com a função de distribuição acumulada

• Pc: Probabilidade de crossover

• Pm: Probabilidade de mutação

• Er: Taxa de elitismo