Algoritmos Genéticos: o que são, o que comem e como se reproduzem?
Quando o melhor dos mundos de Charles Darwin e Alan Turing se unem, só pode surgir coisa boa.
Fundamentada por Charles Darwin em 1859, a Teoria da Evolução deixou para trás a tese de que a vida precisou de intervenção divina para existir. Segundo o cientista, os indivíduos mais aptos ao ambiente têm mais chances de sobreviver e reproduzir-se. Tendo a grande contribuição de Darwin como pano de fundo, temos os algoritmos genéticos.
No contexto orgânico, cada ser vivo tem o seu habitat, que diferencia as qualidades necessárias para sobrevivência e reprodução. No contexto artificial, a situação é análoga. Os algoritmos genéticos foram desenvolvidos para a resolução de problemas de um grupo específico: os problemas de otimização.
Habitat dos Algoritmos Genéticos: Problemas de Otimização
Otimização é um termo derivado de “Ótimo”. Na matemática, um “valor ótimo” é aquele que fornece a melhor solução para determinado problema. Dessa forma, a melhor solução é aquela que maximiza o desempenho ou minimiza o custo de determinado sistema.
Por exemplo, uma empresa de logística busca minimizar a distância percorrida pelos seus motoristas. Em outro contexto, investidores do mercado de ações querem tomar decisões que maximizem seus lucros. Ainda que esses problemas sejam aparentemente distintos, ambos podem fazer parte do escopo da otimização.
Ao modelarmos o problema, criamos uma função objetivo. Ela é a chave para calcularmos objetivamente o quão adaptado está cada indivíduo. Abaixo, temos um exemplo de função objetivo:
O algoritmo nasce da ideia de encontrarmos os indivíduos mais adaptados àquele ambiente, que forneçam valores ótimos para a função objetivo. Para criarmos uma população de indivíduos candidatos, precisamos encontrar quais características eles devem possuir. Esse é o primeiro passo para aplicar o algoritmo genético: como as variáveis deverão comportar em nossos indivíduos?
Variáveis de entrada: parâmetros do problema
Nesse momento, é necessário que haja um levantamento de variáveis, seus respectivos intervalos e qual o nível de precisão necessário para cada uma delas. Algoritmos genéticos podem ser considerados algoritmos de busca, portanto a definição desses intervalos diminui o espaço de soluções candidatas e ajuda na convergência.
Por exemplo, vamos dizer que temos 3 variáveis de entrada para determinado problema. Para cada uma delas precisaremos de seus valores mínimo e máximo e quantidade de bits para representação.
Variável x1: de -100 a 100, com 8 bits;
Variável x2: de 50 a 730, com 10 bits;
Variável x3: de 0 a 7 com 3 bits.
Ao transformarmos as variáveis de decimais para binárias através de uma interpolação, será possível desenvolver uma cadeia, análoga aos genes biológicos. A transformação para binário será necessária para operações que faremos mais adiante.
Variável x1: de 00000000 a 11111111;
Variável x2: de 0000000000 a 1111111111;
Variável x3: de 000 a 111.
Unindo todos os genes na biologia obtemos um cromossomo, que caracteriza cada indivíduo. Para algoritmos genéticos, o mesmo acontece ao concatenarmos as cadeias binárias. Abaixo, construímos um exemplo de indivíduo artificial:
População Inicial: a primeira comunidade
Agora que possuímos as características básicas de cada variável, é possível criarmos uma população de indivíduos artificiais. Cada indivíduo representará uma solução candidata ao nosso problema de otimização. A quantidade de indivíduos é definida pelo usuário a depender da complexidade do problema e da quantidade de recursos computacionais disponíveis. Em geral, a concepção da população inicial é dada de forma completamente aleatória.
Após a criação da população inicial, começamos um processo iterativo. O processo visa simular a evolução natural, através dos processos de seleção, cruzamento, mutação e elitismo, os quais iremos detalhar em seguida.
Seleção: indivíduos artificiais indo para a fase adulta
Após termos gerado a população inicial, reconvertemos seus valores em decimais e calculamos a função objetivo para cada indivíduo. Dessa forma, descobrimos objetivamente quem são os candidatos mais aptos a nos fornecer valores próximos ao ótimo. Assim como na natureza, onde aqueles que sobrevivem na infância e chegam à fase adulta têm a oportunidade de se reproduzir, nossos indivíduos mais aptos terão maiores probabilidades de serem selecionados e passar seus genes adiante. Existem diversos métodos de seleção de indivíduos para a reprodução. Em nosso código disponibilizamos os métodos da roleta e do torneio.
Seleção pela Roleta
Após termos calculado o quão adaptado está um indivíduo pela função objetivo, é possível definir probabilidades de seleção. Quanto mais adaptado está o indivíduo, maior sua probabilidade de ser selecionado. Para a garantia da diversidade e buscando que indivíduos menos adaptados também sejam selecionados, é comum que alguma manobra seja utilizada para “achatar” a função. Abaixo, trazemos a abordagem tradicional da roleta e a versão achatada com a aplicação de um logaritmo.
Após termos o calculo das probabilidades, giramos a roleta e fazemos sorteios com números aleatórios entre 0 a 100. A depender do número gerado, selecionamos um indivíduo. Por exemplo, se utilizarmos a abordagem tradicional da roleta e sortearmos o valor de 18, o segundo indivíduo, de f(x)=87, será escolhido. O valor sorteado (18) cai no intervalo referente à ele, onde a probabilidade acumulada está entre 10,07 e 19,69.
A quantidade de sorteios realizada é igual à quantidade de indivíduos da população inicial.
Seleção por Torneio
A seleção por torneio é bastante simples: um par de indivíduos é escolhido aleatoriamente. Em seguida, estes são comparados e aquele que possui o melhor valor de f(x) é selecionado.
A quantidade de torneios realizado é a mesma quantidade de indivíduos da população, fazendo com que essa mantenha seu tamanho.
Cruzamento: ah, o amor S2
Após a seleção no processo anterior, procedemos com o acasalamento. No cruzamento iremos promover a troca de material genético entre os indivíduos. Novamente, existem diversas formas de promover a reprodução. Aqui, iremos explanar apenas um tipo de cruzamento.
Cruzamento em um ponto
Primeiramente, o usuário define uma probabilidade de cruzamento. Afinal de contas, assim como na natureza, tentar reproduzir não significa ter êxito na tarefa.
Em seguida, são sorteados aleatoriamente pares da população, um ponto de corte e também uma probabilidade. Se a probabilidade sorteada for maior que a probabilidade de cruzamento definida pelo usuário, o cruzamento é concretizado. Caso contrário, não.
Se o cruzamento acontecer, eliminamos os pais da população e substituímos pelos filhos. Se o cruzamento não for concretizado, mantemos os pais na população.
Mutação: diversidade é a palavra chave em algoritmos genéticos
Assim como na natureza, o cruzamento artificial não faz apenas a troca de genes. Além da criação de novos indivíduos, mutações são geradas na população com o intuito de aumentar a diversidade e fomentar a criação de entidades inéditas.
Dessa maneira, o usuário determina uma taxa de mutação e, para alguns indivíduos, bits aleatórios mudam seu valor de 0 para 1 e vice-versa:
Elitismo: os bons sobrevivem
Todos os esforços da seleção, do cruzamento e da mutação irão por água abaixo caso o elitismo não seja executado. O elitismo garante que os indivíduos mais adaptados prossigam para a próxima geração.
Em nossa implementação, a performance de cada indivíduo é armazenada no início da geração. Após a realização das etapas de seleção, cruzamento e mutação, a performance é recalculada e os indivíduos são ordenados por ela. Em seguida, os n melhores indivíduos sobrevivem e passam para a próxima geração. Os n piores são descartados. E o ciclo recomeça…
…mas até quando?
Critérios de Parada
Existem algumas maneiras para encerrar as iterações e o ciclo de “vida” de nossa comunidade artificial. É importante que o problema em que o algoritmo esteja sendo aplicado seja analisado, pois talvez ele dê dicas valiosas quanto aos níveis de precisão, tempo computacional disponível, etc. Em geral, existem quatro critérios de parada:
- Parar quando atingir uma quantidade máxima de gerações;
- Parar quando o melhor indivíduo não for superado por n gerações;
- Parar quando não houver melhoria de performance superior a determinado valor;
- Parar quando atingir uma quantidade máxima de cálculos da função f(x).
Em nosso código, implementamos o critério 1.
Falando em implementação, cadê o código?
Está bem aqui, na continuação desse artigo. Lá, apresentamos o código e o botamos à prova com funções projetadas especialmente para testar algoritmos genéticos. Vamos nessa?
