Algoritmo Genético

Olá, hoje vou falar sobre o Algoritmo Genético (AG), uma técnica utilizada na Ciência da Computação para achar soluções aproximadas em problemas de otimização e busca.

Existem problemas tão complexos com os quais os seres humanos se deparam que não é possível ver uma solução. Problemas que um ser humano levaria muito tempo para resolver, talvez muitos anos, talvez uma vida toda, felizmente nossa inteligência nos levou a construção de uma ferramenta poderosa para nos auxiliar: O computador! Uma ferramenta magnifica criada por poucos, disponível a muitos, que nos ajuda a solucionar alguns problemas como esse.

Através da programação dos computadores somos capazes de moldar um algoritmo que resolve um determinado problema, seja ele simples ou complexo. Um algoritmo que ajuda a solucionar vários, problemas complexos, é o algoritmo genético.

Baseado na biologia evolutiva, o algoritmo genético busca apresentar possíveis soluções ao problema, não necessariamente resolvendo o problema, mas apresentando soluções muito próximas da resolução.Uma de suas principais características é justamente ele não apresentar somente uma solução mas sim várias possíveis soluções.

Um algoritmo genético é uma heurística de busca inspirada na teoria da evolução natural de Charles Darwin. Este algoritmo reflete o processo de seleção natural, onde os indivíduos mais aptos são selecionados para reprodução, a fim de produzir descendentes da próxima geração.

A estrutura básica de um AG

Se você já pesquisou um pouco sobre AG já deve ter visto um esquema parecido com esse:

Pois bem, essa é a estrutura básica de um AG. Ela contém as processos essenciais e o fluxo de funcionamento. Aparentemente é uma receita de bolo fácil de ser seguida, mas a coisa começa se complicar quando você percebe que um modelo genérico, fácil de ser desenvolvido, não apresenta um bom desempenho para resolução de todos os problemas. Um modelo genérico serve apenas para aprendizado, para que você possa entender como são os processos e o que eles fazem. A partir de que você entenda como ele funciona você poderá molda-lo otimizando ele para o seu problema.

A Seleção Natural

O processo de seleção natural começa com a seleção de indivíduos mais aptos de uma população. Eles produzem descendentes que herdam as características dos pais e serão adicionados à próxima geração. Se os pais tiverem um bom preparo físico, os filhos serão melhores que os pais e terão uma chance melhor de sobreviver. Este processo continua evoluindo e no final será encontrada uma geração com os indivíduos mais aptos.

Essa noção pode ser aplicada para um problema de pesquisa. Consideramos um conjunto de soluções para um problema e selecionamos o melhor conjunto delas.

Um algoritmo genético é composto geralmente por 5 fases.

1. População inicial
2. Função de avaliação
3. Seleção dos pais 
4. Crossover (cruzamento)
5. Mutação

A População

Um algoritmo genético trabalha com um conjunto de possíveis soluções para um problema, que se espelha em uma população de indivíduos tentando sobreviver a uma determinada situação ou ambiente. Como uma população é formada por indivíduos temos de entender o que é um indivíduo.

No AG um indivíduo é a unidade básica da população e representa uma possível solução para um problema. Esse indivíduo na sua representação mais básica é apenas um cromossomo, mas dependendo das necessidades pode portar mais informações como: nome, geração, características adicionais ou alguma outra informação relevante. A seguir um exemplo de população simples e termos comuns no AG.

O que nós vemos na ultima imagem é uma população com quatro indivíduos(A1, A2, A3, A4), cada indivíduo contém um cromossomo que é a codificação de uma possível resolução do problema. Cada cromossomo por sua vez é formado por um conjunto organizado de genes, durante a dinâmica do AG os genes se recombinam para formar novas soluções. Um gene armazena um, ou mais alelos, que pode ser um numero binário, como na imagem acima, ou um caractere que se defina: número, letra, binário.

Cálculo das aptidões 

Ocorre que cada um dos indivíduos da população deve passar por uma avaliação para determinar o seu fitness (nota de aptidão ou nota de avaliação). Dessa forma são calculadas as aptidão de todos os indivíduos. A probabilidade de um indivíduo ser selecionado para reprodução baseia-se nessa sua nota fitness. Geralmente se usa um escala que vai de 0 a 1 para expressar essa qualidade do fitness, isso é compatível com a lógica fuzzy. Então podemos organizar nossa população do melhor indivíduo para o pior (ou ao inverso) tendo uma escala numérica para expressar isso, quanto mais próximo de 1 mais apto é o indivíduo.

A função de avaliação é justamente o que determina o fitness do indivíduo, em muitos casos, é a única ligação do problema real com o AG. Ela apenas avalia a qualidade daquele indivíduo frente ao problema a ser resolvido. Eu vejo a função de avaliação com sendo um ambiente virtual onde testamos os individuos, e obtemos como retorno o quanto bom é cada indivíduo.

Uma função de avaliação geralmente é escrita, nas diversas linguagens de programação, recebendo um indivíduo como parâmetro e retornado um valor numérico que expressa a sua qualidade, isso é a parte genérica! A parte central da função, onde é feita a avaliação, é uma virtualização do problema a ser resolvido, um conjunto de cálculos, equações e regras que devem refletir os objetivos a serem alcançados na resolução do problema.

Seleção de Pais

Assim como acontece com espécies biológicas os indivíduos mais aptos tem mais chances de gerar filhos, no entanto individuos menos aptos também podem gerar filhos, mas eles tem menos chances. No AG os individuos com melhor classificação (por exemplo a nota fitness próximo de 1) são os mais aptos, portanto eles tem mais chances de serem escolhidos para gerar seus filhos, mas não se deve desprezar os individuos com classificação ruim (por exemplo a nota fitness próximo de 0), pois eles podem conter características genéticas que em combinação com outras características de outro indivíduo podem gerar a melhor solução para o problema.

Pode ocorrer um sério problema chamado Convergência Genética, caso o AG seja limitado a selecionar apenas os melhores pais para se reproduzirem. Este problema consiste em que os filhos gerados iram se parecer cada vez mais com os pais, dessa forma a evolução é barrada totalmente! E isso destrói por completo o objetivo do AG que é evoluir as soluções fazendo uma diversidade de combinações até atingir seu objetivo. Mesmo dando chances justas a todos os individuos a convergência genética pode ocorrer, mas a probabilidade é consideravelmente menor.

Existem alguns métodos para a seleção dos pais, um bem comum é o método da roleta viciada, onde é definida uma roleta "virtual" e cada indivíduo terá parte correspondente nela de acordo com sua avaliação, se rodarmos essa roleta, quando ela parar um determinado indivíduo será selecionado, vale ressaltar que essa mecânica da roleta deve ocorrer de forma aleatória!

Crossover

Crossover é a fase mais significativa em um algoritmo genético. Para cada par de pais a serem acasalados, um ponto de corte é escolhido aleatoriamente dentro dos genes.

Por exemplo, considere o ponto de corte como 3, conforme mostrado abaixo.

Os descendentes são criados trocando os genes dos pais entre si até que o ponto de cruzamento seja alcançado.

Os novos filhos são adicionados à população.

Mutação

Em alguns novos filhos formados, alguns de seus genes podem ser submetidos a uma mutação com baixa probabilidade aleatória. Isto implica que alguns dos bits na cadeia de bits podem ser invertidos.

 

  

A mutação ocorre para manter a diversidade dentro da população e prevenir a convergência genética.

Finalização

O algoritmo finaliza se a população tiver convergido (não produz descendentes que sejam significativamente diferentes da geração anterior), ou se algo das regras para finalizações for alcançada, como por exemplo, se a solução for encontrada ou se o numero de gerações for atingido. Então, diz-se que o algoritmo genético forneceu um conjunto de soluções para o nosso problema, que são justamente os individuos da ultima geração.

(Digitando...)