Busca baseada em populações e Computação Evolutiva
Este texto é parte da disciplina de Fundamentos de Inteligência Artificial do Programa de Pós-Graduação em Computação da Universidade Federal de Pelotas e não foi feito para fazer muito sentido fora deste contexto.
Algoritmos de busca heurística como Subida de Encosta e Têmpera Simulada, possuem como característica ter um único estado como o “estado atual” em qualquer momento, aquele que serve de âncora para o processo de busca. Uma alternativa a esta abordagem é manter múltiplos estados correntes simultâneamente, ou uma “população” de estados.
Há duas motivações principais por trás da proposta de métodos baseados em populações. Primeiro, pode-se aproveitar o paralelismo dos computadores atuais ou múltiplos computadores. Porém, nada impede de rodarmos, em cada núcleo do computador, uma Têmpera Simulada independente uma da outra — certamente estamos aproveitando o paralelismo sem criar nada novo. O que leva à segunda motivação: talvez amostrar a topografia da função da avaliação em múltiplos pontos simultâneamente nos dê alguma informação sobre onde bons estados podem estar.
Central a esta segunda motivação está a necessidade de limitar o uso de recursos computacionais. A avaliação da função é tipicamente a parte mais custosa de qualquer processo de otimização: aqui são meras funções matemáticas, mas na prática pode envolver coisas como a construção de um carro para teste em pista, algo que definitivamente não iremos querer fazer com muita frequência. Portanto, uma boa função de otimização deve reduzir o número de avaliações da função, ao mesmo tempo que amostra o suficiente para obter informações sobre estados que valem a pena ser avaliados na sequência. Uma busca por subida de encosta com reinício aleatório pode ser eficiente no uso de recursos em qualquer uma das buscas, mas os reinícios nada aproveitam das buscas anteriores.
Uma suposição subjacente a ideia de amostrar a função de avaliação é a de que a topografia desta função é suave o suficiente, isto é, não apresenta mudanças bruscas para pequenas variações nos parâmetros. A figura abaixo ilustra a situação. Na esquerda, supondo suavidade na curva podemos inferir razoavelmente o valor da curva entre os dois pontos amostrados — e, portanto, pode não ser interessante alocar novas amostras naquela região. Na direita, porém, a função é altamente irregular e não é possível inferir algo útil a partir apenas dos dois pontos com mesma separação anterior. Deve-se notar porém que a suavidade de uma função pode depender do intervalo adotado para os parâmetros ou da região sendo amostrada.
Um algoritmo baseado em populações é o Busca em Feixe (Beam Search). Como todo algoritmo baseado em populações, ele inicia com N estados iniciais. Todos são avaliados e os N/2 piores são descartados. Cada estado restante gera um novo estado amostrado em suas vizinhanças, retornando a N estados. Repete-se o processo até algum critério de parada (e.g. número de rodadas).
Considerando que cada estado tem que ser avaliado, o efeito que este algoritmo tem é o de realocar computação para áreas promissoras da função. Por exemplo, considere o caso inicial abaixo, onde N=10, e temos um problema de maximização da função.
Os 5 piores estados estão localizados no vale da direita e são descartados. Dos 5 restantes, geramos 5 novos estados na vizinhaça. Aqui, cada estado tem dois vizinhos: para gerar um, soma-se a constante 0,1 e, para o outro, subtrai-se a constante 0,1. Geramos qualquer um dos dois com igual probabilidade. Um resultado possível é representado abaixo.
Observe como os novos estados estão localizados em áreas “melhores” do que aqueles onde os que foram removidos estavam. A computação que seria utilizada para avaliar vizinhos daqueles piores estados foi redirecionada para outras áreas da função. A suposição, novamente, é que sendo a função suave o suficiente no entorno de bons valores da função haverá outros bons valores também, então esforços devem se concentrar nestas regiões promissoras.
Abaixo a animação completa da busca. Observe como, ao final, ela essencialmente se torna uma busca por subida de encosta, ainda que ineficiente devido a múltiplos estados estarem explorando essencialmente o mesmo local. Esta ineficiência é aparente devido a simplicidade da função — em uma função mais complexa, como aquela mostrada algumas figuras acima, os estados explorariam uma região próxima, mas não necessariamente convergiriam para um mesmo ótimo.
Ainda que pareça que a busca teve razoável sucesso, é possível observar que o ótimo global está, na realidade, na extrema direita do gráfico. Apesar de haver estados iniciais próximos deste ótimo global, que chegariam nele com uma simples subida de encosta, estes foram descartados logo no primeiro passo do algoritmo devido a presença de estados já próximos a ótimos locais. Este é um caso de um algoritmo excessivamente exploitativo: no momento que encontra regiões melhores, a computação é direcionada para estas regiões. Pode-se aumentar a exploração tendo mais estados, mas ultimamente este é um problema inevitável.
Computação Evolutiva
A chamada Computação Evolutiva, ou Algoritmos Evolutivos, ou outros tantos nomes, é uma grande área de algoritmos de otimização baseados em população. Pode ser visto como uma variação sofisticada da Busca em Feixe e são inspirados na Evolução Natural.
A Evolução Natural é o processo pelo qual seres vivos se adaptam ao seu ambiente, inicialmente postulado por Charles Darwin. Ela se baseia em três componentes essenciais: seleção, hereditabilidade e variação. A seleção é o processo pelo qual indivíduos menos adaptados são (probabilisticamente) eliminados da população: uma ave incapaz de voar ou correr provavelmente não sobreviverá muito tempo em meio a predadores. A hereditabilidade é a capacidade dos animais se reproduzirem e transmitirem suas características para a prole: aves que voam dão origem a outras aves que voam. E variação é hereditabilidade imperfeita, onde apesar dos filhos se parecerem com seus genitores, eles não são idênticos.
Estes três componentes permitem a adaptação ao ambiente. Indivíduos que sobrevivem (seleção) se reproduzem e dão a origem a novos indivíduos semelhantes, mas com pequenas variações. Entre estas variações, as que são menos adaptadas tendem a não sobreviver, enquanto as mais adaptadas tendem a se reproduzir e gerar novos indivíduos que herdam esta variação. Ao longo do tempo, o ambiente seleciona os indivíduos com as variações mais adaptadas, descartando aquelas menos adaptadas.
É possível mapear esta explicação para a Busca em Feixe. Os indivíduos são os estados. Ao descartarmos os N/2 piores, estamos aplicando o critério de seleção (neste caso, o ambiente é a função de avaliação). Dos que sobraram, geramos novos estados/indivíduos que são próximos (hereditariedade) mas diferentes (variação) e repetimos.
A Computação Evolutiva leva adiante a analogia e incorpora outros fatores aos algoritmos de busca. Dois se destacam: (i) a seleção é probabilísitca, o que implica que mesmo o pior indivíduo pode sobreviver e o melhor ser descartado e (ii) pode-se aplicar reprodução sexuada, ao contrário da Busca em Feixe onde cada novo indivíduo é originado de apenas um estado.
Talvez os mais conhecidos algoritmos da Computação Evolutiva sejam os Algoritmos Genéticos. Neste momento, é interessante ler diretamente o primeiro capítulo do livro da Melanie Mitchell.
Assim como Têmpera Simulada, os algoritmos genéticos possuem parâmetros que permitem controlar a troca entre exploração e exploitação. Ao contrário da Têmpera, porém, há múltiplos parâmetros para isso que se afetam mutuamente. A probabilidade de mutação é o parâmetro mais evidente para isso — baixa mutação significa indivíduos mais próximo dos genitores. Mas pode-se controlar também a força da seleção, mantendo com maior ou menor probabilidade os indivíduos ruins. O tipo de crossover e a aplicação ou não de elitismo (quando força-se os melhores indivíduos a sobreviver) também afetam a troca e alteram as características do algoritmo. O ajuste destes múltiplos parâmetros é com frequência o maior desafio no uso destes algoritmos.
Os algoritmos genéticos, bem como outras variações que compõem a Computação Evolutiva, são muito utilizados para solucionar problemas de otimização. A tendência mais atual envolve não codificar os parâmetros do problema na forma binária, mas utilizar sua forma natural (e.g. números inteiros ou reais) e adaptar os operadores de mutação e crossover para esta forma, mas em grande parte o processo básico permanece o mesmo. Não deve-se pensar nestes algoritmos, porém, como otimizadores universais e mesmo sua real utilidade comparada a técnicas mais simples é debatível. Ainda assim, são sem dúvida ferramentas úteis para se ter disponível.
Abaixo alguns vídeos de coisas interessantes onde Computação Evolutiva foi aplicada para encontras soluções. Observem como em alguns casos as soluções são bastante diferentes de algo que pessoas construiriam. Estes algoritmos otimizam agressivamente a função de avaliação, sem levar em conta coisas como simetria ou senso comum. O que não está na função não é considerado, fazendo com que a construção da função de avaliação seja a parte mais importante destas tarefas. Com a função errada, resolvemos o problema errado. Isso é bastante evidente no último vídeo.
Aqui é possível brincar com um algoritmo genético para evoluir carros.
