Evolution, from Man to Evolutionary Algorithms
O texto abaixo foi apresentado pelo grupo Ariel Malves, Rodrigo Marques e Fabio Oliveira como trabalho final no curso de Algoritmos Evolutivos, sigla IA770, ministrado no Departamento de Engenharia da Computação e Automação Industrial da Universidade Estadual de Campinas (Unicamp).
Resumo: Os Algoritmos Evolutivos(AEs) têm se mostrado muito eficientes em diversos problemas extremamente difíceis de serem atacados por métodos mais clássicos, e por serem naturalmente paralelizáveis e necessitarem de muitos recursos computacionais, diversas técnicas estão sendo utilizadas para melhorar seu desempenho, elevando ainda mais a utilidade prática desta ferramenta. No entanto, muitas vezes a paralelização do algoritmo leva a alterações estruturais que mudam o seu comportamento comparado a um AE seqüencial, ou então aumentam mais ainda o leque já vasto de parâmetros para ajuste do mesmo. Pretendemos mostrar uma taxonomia dos AEs paralelos e distribuídos, suas principais diferenças, parâmetros e ganhos com relação aos seqüenciais, e construir um arcabouço para comparação do desempenho de um algoritmo representativo contra um semelhante porém seqüencial, demonstrando com um exemplo prático suas características.
Introdução
Os Algoritmos Evolutivos(AEs) mantêm uma população de possíveis soluções que competem entre si seguindo a metáfora da Teoria Evolutiva Moderna. Os operadores envolvidos em AEs para problemas não triviais precisam de muitos recursos computacionais, e por isso a busca por melhores técnicas para a melhora de seu desempenho, como o uso de computação paralela e distribuída.
Em geral, os operadores dos AEs como a recombinação e a mutação, e mesmo a avaliação do fitness , se concentram em um ou em alguns poucos indivíduos da população, tornando os AEs muito propícios a paralelização. Mesmo o operador seleção, que em geral avalia todos os indivíduos simultaneamente, e por isso mesmo seria um gargalo a paralelização, pode ser alterado para se adaptar melhor a este paradigma, ou então podemos nos ater a somente ao subconjunto das suas variantes que se utilizam da informação de poucos indivíduos, como por exemplo o operador torneio.
Normalmente, quando se aplica técnicas de paralelização, busca-se tão e somente diminuição do tempo necessário para a execução do algoritmo. No entanto, no caso de AEs, há evidências [ 1 ][ 2 ] não somente da redução do tempo necessário, mas também da maior manutenção da diversidade, da melhora na capacidade de busca de múltiplas soluções em problemas multi-modais, e na maior qualidade do resultado.
A melhora da qualidade do resultado merece uma discussão mais detalhada. Ao se executar um algoritmo usando N threads de execução ou então ao se executar em N nós (máquinas) diferentes em uma rede no caso de sua distribuição, pode-se esperar uma redução no tempo de execução proporcional a N. No entanto, esta expectativa idealizada é muitas vezes ingênua, já que tanto uma técnica quanto a outra dependem de instrumentos de comunicação e sincronização que no caso seqüencial não são necessários, e sobrecarregam a execução do algoritmo. Mas no caso dos AEs, ao se executar o mesmo algoritmo de forma seqüencial e de forma paralela até que encontrem uma solução de mesma qualidade, muitos experimentos têm mostrado uma melhora super linear do tempo de execução [ 3 ][ 4 ].
Taxonomia
De acordo com o trabalho de Erick Cantú-Paz [ 5 ], há três tipos principais de AEs paralelos:
- População única, mestre/escravo: A população é única como nos AEs seqüenciais, mas a avaliação do fitness é distribuída em múltiplos processadores. Como os operadores consideram a população inteira, também são conhecidos como AEs paralelos globais.
- População única, modelo celular: Muito utilizado em computadores massivamente paralelos, consiste de uma população estruturada distribuída. A seleção e a recombinação são restritas a uma pequena vizinhança, mas como há a sobreposição de vizinhanças, há iterações entre todos os indivíduos. Busca ter idealmente um único indivíduo por processo.
- Múltiplas populações, modelo ilha: Consiste em sub-populações que trocam indivíduos ocasionalmente. Esta troca de indivíduos é chamada migração. É o tipo mais popular por permitir o uso de hardware comum e acessível, porém não é completamente compreendido, e introduz mudanças fundamentais na operação dos AEs.
É claro que neste espectro, existem muitas abordagens híbridas, como por exemplo com arquiteturas combinando múltiplas populações com mestre/escravo. Estas abordagens híbridas são também chamadas de AEs paralelos hierárquicos.
Modelo Mestre/Escravo
O modelo mestre/escravo sugere que a cada geração o processo mestre contendo a população delegue a tarefa de cálculo do fitness para cada um dos processos escravos (ver figura 1) para então devolver esta informação para o mestre. Cabe então ao mestre, assim que todos os escravos retornarem suas informações, as tarefas de seleção dos pais para a próxima geração e criação de novos indivíduos utilizando operadores de recombinação e mutação. É uma técnica simples, que pode ser aplicada em problemas onde a avaliação do fitness no problema atacado seja computacionalmente onerosa.
Figura 1. Modelo Mestre/Escravo
Como a população é única e os operadores consideram a população total para atuar, esta é a técnica de paralelismo que mais se assemelha a abordagem clássica de um AE seqüencial e uma aplicação pouco cuidadosa dessa abordagem pode levar a uma imprecisa interpretação dos ganhos em desempenho ou precisão.
Entre o processo mestre e os escravos podemos ter uma comunicação síncrona, onde o mestre interrompe sua execução e aguarda que os escravos retornem a ele todos os resultados, mesmo que existam diferenças de desempenho entre os nós. Obviamente, este tipo de implementação resulta em tempo ocioso de máquina, aproveitando inadequadamente o hardware disponível.
Sempre temos duas comunicações entre mestre-escravo para cada nó adicional, primeiramente no envio da fração da população para avaliação e depois no retorno do fitness avaliado.
Este tempo de comunicação gasto proporcional ao número de escravos pode, dependendo da infra-estrutura utilizada, ser inclusive maior que o ganho efetivo de desempenho conseguido pelo paralelismo. Podemos então ver que quanto maior o número de escravos nesta topologia, melhor a distribuição da tarefa de avaliação de fitness e portanto menor tempo computacional gasto na mesma. Por outro lado, a mesma condição implica em um maior tempo gasto na comunicação entre mestre e escravos.
Este é um compromisso que depende do tempo necessário para avaliar um indivíduo, da quantidade de escravos utilizada e de constantes que dependem do hardware utilizado, mas sugere que existe um número ótimo de escravos que minimize este tempo de execução [ 6 ].
Uma implementação assíncrona pode ser considerada, embora perca um pouco da analogia e das características que assemelham o algoritmo a um AE seqüencial, introduzindo outros fatores que podem ser benéficos de acordo com a classe do problema minimizando os gastos com o tempo de comunicação.
Numa implementação assíncrona o mestre não esperaria pela resposta dos escravos, e trabalharia com as informações que estivessem disponíveis no momento. Cada escravo ainda teria uma fração de população a avaliar mas devolveria os valores de fitness assim que o processamento estivesse concluído. Neste caso a avaliação em um processador mais lento atuaria em gerações espaçadas de acordo com a velocidade do mestre.
Outros operadores como a recombinação e a mutação também são sugeridos como passíveis de execução paralela por terem as mesmas características de independência entre indivíduos, mas por serem operadores normalmente pouco custosos a perda com o aumento das comunicações entre mestre-escravo faz com que esta abordagem seja pouco promissora na maioria dos casos.
Modelo Celular
Um AE celular ou de paralelismo massivo é uma proposta que difere significativamente de um AE tradicional. Neste modelo temos uma população distribuída em uma rede, um indivíduo por nó, como por exemplo num espaço bidimensional, formando uma grade que limita as interações entre os indivíduos, permitindo apenas a interação entre elementos vizinhos (ver figura 2). Como vimos no caso mestre-escravo, existe um custo alto na comunicação entre nós, e esta abordagem só se mostra vantajosa com o uso de hardware específico, como computadores ou processadores massivamente paralelos.
Figura 2. Modelo Celular
Os operadores genéticos de seleção e recombinação ocorrem apenas entre indivíduos próximos. Por esta característica, e por representar cada indivíduo na forma de um processo independente interagindo com o meio, oferece uma metáfora mais próxima da real para pesquisadores interessados no estudo de vida artificial.
A forma de implementação varia de acordo com a aplicação de interesse, podendo ter regiões de vizinhança sobrepostas, estruturas multidimensionais, ou mesmo migrações distantes ou disseminação dos melhores indivíduos de forma que não se limitem apenas a sua vizinhança.
Podemos pensar no AE celular como sendo uma adaptação de um AE tradicional que tenha em paralelo componentes do algoritmo como seleção dos indivíduos para recombinação, a própria recombinação, mutação, e a avaliação de fitness . Neste caso o modelo muito se assemelha aos outros modelos propostos tendo um foco maior na topologia e na distância relativa entre os indivíduos.
Portando uma mudança fundamental no AE é remoção da seleção global dos pais para recombinação, limitando-os a vizinhança. O comportamento é alterado significantemente com novos resultados e novos parâmetros como o tamanho da população e as fronteiras de vizinhança, que assumem papel importante nesta abordagem, controlando inclusive a pressão seletiva do algoritmo.
A parametrização ainda contaria com a topologia da rede, os métodos de seleção, recombinação, mutação, tamanho da população e sua distribuição entre múltiplos processadores e número de novos indivíduos gerados a cada iteração, considerando seu espaço de atuação.
Modelo Ilha
A característica fundamental deste modelo é o uso de algumas poucas populações relativamente grandes e do operador de migração. Cada sub-população é processada por um nó e atua como se fosse uma população totalmente independente, mas de acordo com uma política de migração, recebe e envia indivíduos de/para outros nós, distribuindo as informações sobre as soluções candidatas até o momento (ver figura 3).
Figura 3. Modelo Ilha
Experimentos considerando a razão de migração mostraram que para populações isoladas (sem migração), a qualidade do resultado final era pior do que o de uma única população. Para taxas de migração altas, a qualidade era igual a de uma única população.
O excesso de comunicação, da mesma forma como no caso mestre/escravo, degrada o tempo de execução do algoritmo. Existem também indícios de que existe para cada problema e tamanho da população, uma quantidade ideal de nós.
Olhando pela ótica da metáfora natural, pode-se dizer que o modelo ilha reproduz o comportamento e a comunicação entre ecossistemas separados por barreiras naturais, e o resultado se assemelha a teoria do equilíbrio pontual ( punctuated equilibria ) da biologia evolutiva [ 2 ], onde os diversos ecossistemas e seus organismos vivem em equilíbrio a maior parte do tempo, e a alteração do ambiente produz um rápido movimento evolucionário. O modelo ilha adiciona um novo operador de migração aos demais operadores clássicos, e este operador, ao trazer novos indivíduos a uma população estável, gera um impulso evolucionário semelhante. O aumento da capacidade de exploração deste modelo, a evolução de sub-populações isoladas e este mecanismo de perturbação por migração são as chaves para explicar referências apontando melhoras de desempenho super lineares [ 3 ].
A popularidade desse modelo advém da sua simplicidade, facilidade de implementação e possibilidade de aplicação em hardware acessível, como em uma rede de estações de trabalho comuns.
Este modelo ainda oferece muita área para estudo, com muitas questões ainda não respondidas, como por exemplo qual a melhor forma da topologia de rede, ou então qual a melhor taxa e o intervalo de migração.
Migração
Na maioria dos esquemas de migração, ela é síncrona, ocorrendo em intervalo constante. Nesta forma de implementação, todos os nós pulsam numa mesma geração, parando no ponto de sincronização onde ocorre a troca de indivíduos. Pode também ser assíncrono, e neste caso cada nó mantêm uma fila de indivíduos recebidos, numa metáfora de caixa postal, nunca tendo que aguardar o envio/recebimento de indivíduos para continuar com o processamento, perdendo-se com isso o conceito de geração da população como um todo. Alguns esquemas aplicam a migração somente quando a sub-população está próxima de convergir, restaurando a diversidade.
Aliás, uma questão recorrente é de quando deve ocorrer a migração. Ocorrendo muito cedo, os migrantes podem ter building blocks pequenos demais para influenciar a população. Ocorrendo tardiamente, cada nó pode perder diversidade e estagnar num ótimo local, também consumindo preciosos recursos computacionais.
Há referências de um esquema diferente desenvolvido [ 5 ], onde processadores escravos evoluíam suas sub-populações e enviavam seus melhores indivíduos para o mestre, e este então aplicava a seleção com viés para os melhores, e enviava os selecionados para os escravos. Mostrou aumento de desempenho super-linear.
Topologia de rede
A topologia da rede do modelo ilha determina o quão rápido ou quão devagar uma boa solução é disseminada para as demais populações. Também determina o custo de comunicação da rede.
Normalmente são usadas topologias estáticas, que são usadas do começo ao fim do algoritmo, mas já foram feitos experimentos com topologias dinâmicas, onde a migração é realizada entre populações de acordo com algum critério, como diversidade da população, ou então a distância genotípica entre populações, ou até mesmo de forma aleatória.
Híbridos
E, como não poderia deixar de ser, como com os demais parâmetros dos AEs seqüenciais, existe muito espaço para a criatividade em termos de topologias e hibridizações.
Na figura 4, podemos ver um modelo híbrido ilha/celular, onde computadores massivamente paralelos desenvolvem suas sub-populações de forma quase independente, trocando informações de seus indivíduos de tempos em tempos como no modelo ilha.
Figura 4. Modelo Híbrido Ilha + Celular
Já na figura 5 podemos ver um modelo híbrido ilha/mestre-escravo, onde cada nó do modelo ilha delega a tarefa do cálculo da função de avaliação para uma outra coleção de computadores.
Figura 5. Modelo Híbrido Ilha + Mestre/Escravo
E finalmente, na figura 6 uma possível configuração ilha/ilha, onde em cada nó do modelo ilha existe um outro modelo ilha, com uma rede mais densa e de maior velocidade.
Figura 6. Modelo Ilha + Ilha
Cada modelo e suas variantes sempre devem ser criados e parametrizados de acordo com o problema atacado, como já é hábito no modelo seqüencial.
Problema de Teste
Para confirmar os dados teóricos até agora expostos, realizamos alguns experimentos. E para tanto buscamos na literatura um problema conhecido usado para realizar a comparação entre as diversas implementações.
Usamos o problema subset sum como detalhado em [ 9 ]. O problema subset sum é NP-Completo, e tem diversas formas, entre elas as mais conhecidas são: dado um conjunto de números 
de n inteiros e uma constante M, encontrar um subconjunto 
tal que a soma dos elementos em V é igual a M. Esta versão é basicamente um problema de decisão. Já um problema de otimização seria o de encontrar V tal que a soma dos elementos em V se aproxime de M, sem nunca ultrapassá-lo. A segunda forma será a usada por nós em nossos experimentos.
Nossas instâncias do problema foram criadas com 100000 elementos que foram aleatoriamente escolhidos com distribuição uniforme no intervalo ![[0.10 ^ 6]](http://www.smallthoughts.com.br/wp-content/plugins/latex/cache/tex_555ba822a33f748438cb5d3100a603ee.gif)
. Como pode ser notado, nossa variante é maior do que descrito em [ 9 ], e isto foi feito propositalmente pois as instâncias na forma descritas não se mostraram desafiadoras tanto para o algoritmo seqüencial quanto para o distribuído, obrigando-nos a aumentar seu tamanho e usar o procedimento de criação descrito como inspiração.
Para podermos comparar a nossa implementação quanto a eficiência contra metodologias clássicas, implementamos também um algoritmo para cálculo exato e outro para cálculo aproximado dado um percentual de erro aceitável, como descrito em [ 10 ]. Como o algoritmo para cálculo exato precisa de tempo e memória exponenciais em relação ao tamanho do problema, e lembrando que no caso do subset sum estamos falando de 
possíveis subconjuntos, o algoritmo exato só é viável para instâncias muito pequenas. Em estações de trabalho típicas de hoje, fomos capazes de resolver instâncias com até 40 elementos, para instâncias maiores não houve memória suficiente. Já o algoritmo aproximado precisa de tempo e memória polinomiais, e resolveu uma instância com 10000 elementos em 68 minutos em uma estação de trabalho típica. Para uma instância de 100000 elementos, dois dias de execução não foram suficientes para se encontrar uma boa solução com o algoritmo aproximado.
Detalhes de implementação
De todos os modelos apresentados, escolhemos o modelo ilha para ser implementado, por ser bem diferente do AE seqüencial, e ao mesmo permitir a implementação em hardware facilmente acessível.
A representação escolhida foi de uma cadeia binária C com 100000 bits. Cada n-ésimo bit ativo indicava o uso do elemento n do conjunto original. Seja 
e 
, a função objetivo utilizada foi:
onde 
quando 
é factível, i.e., quando 
, e 
nos outros casos. Dessa maneira, o valor obtido como fitness é a própria soma do sub-conjunto representado por C, ou então o valor objetivo e uma penalidade de um décimo de 
para soluções infactíveis.
Para que obtivéssemos um maior controle do processo de seleção, usamos o operador de torneio para escolha dos indivíduos que iriam compor a lista de pais para criação de uma nova geração.
Importante também salientar que, no processo de seleção, os filhos substituem os pais em uma configuração 
. Através de testes preliminares, fora constado que o tempo de convergência estava sendo excessivamente prejudicado pela perda de boas soluções, fato que nos motivou a implementar o operador de elitismo, que mantinha na população a melhor solução encontrada.
Na recombinação utilizamos o operador de crossover de pois pontos e a mutação pontual. A importância do operador de crossover em um AE distribuído não pode ser ignorado, especialmente quando se usa um operador de migração para disseminar a informação genotípica dos elementos através das ilhas.
Nesse experimento utilizamos o operador de migração para transportar os n melhores indivíduos de uma ilha para outra. A ilha receptora elimina seus n piores indivíduos para receber os migrantes. Nos testes, o valor que mostrou melhores resultados foi de n = 2.
A topologia implementada foi a anel com passagem de token . Cada ilha possui outra como destino de suas migrações, mas a todo momento apenas uma ilha pode realizar o processo de migração, exatamente aquela que possuir o token . O token é enviado a ilha alvo junto com os indivíduos migrantes. Essa topologia apresentou-se interessante pois conseguimos ajustar a periodicidade da migração para que ocorresse quando as ilhas já estivessem perto de, ou já estivessem entrado em um estado de equilíbrio, quando atingiam um máximo local.
O software desenvolvido para os testes foi dividido em dois componentes: o AE propriamente dito, realizando o processo de seleção, recombinação, mutação, migração, etc..., e um controlador, um componente que servia para registrar os nós (instâncias dos AEs), configurá-los remotamente, iniciá-los, finalizá-los e coletar dados estatísticos. Este segundo componente proporcionou uma grande versatilidade, possibilitando inúmeras execuções a fim de se testar diferentes parâmetros.
Vale ressaltar também que foram implementados outros operadores e topologias que não foram utilizados na execução final. Um dos operadores criados implementava um algoritmo greedy (guloso) que basicamente colocava os organismos em ótimos locais de maneira bem rápida. Tal operador pode ser muito interessante para resolver instâncias do problema subset sum cujo conjunto possua uma boa quantidade de números de pequena ordem, mas ineficaz para outros tipos de instâncias.
Como topologias adicionais, foram implementadas a dinâmica, onde cada ilha migrava organismos para outra escolhida de forma aleatória, podendo todas as ilhas efetuar o processo de migração de forma simultânea, e o anel sem passagem de token , que é a mesma que a topologia utilizada em nossos experimentos, porém possibilitando migrações simultâneas. Tanto uma como outra forma se mostraram densas demais, fazendo surgir um comportamento de população única.
Ambiente de testes
Foram utilizados 17 computadores, cada qual com CPUs de dois núcleos a 2,2 GHz e 2Gb de memória RAM.
Em cada computador executamos uma instância do AE (ilha). O fato dos computadores possuírem um núcleo adicional auxiliou o transporte dos indivíduos migrantes e do envio de estatísticas para o controlador, visto que essas operações foram concebidas de forma assíncrona, e em threads de execução separadas.
A rede local tinha a velocidade de 100 Mbits/s e cada computador estava ligado a um switch também de 100Mbits/s.
Análise
Para averiguar os ganhos obtidos com as técnicas de paralelização e distribuição descritas, comparamos os tempos de execução para a obtenção de resultados de mesma qualidade confrontando a versão paralela contra sua versão seqüencial com parametrização similar. Obtemos os resultados mostrados na tabela 1.
| Execução |
Seqüencial |
Modelo Ilha |
| 1 |
4m50s |
2m03s |
| 2 |
12m41s |
2m04s |
| 3 |
25m16s |
1m15s |
| 4 |
8m42s |
1m12s |
| 5 |
5m37s |
0m42s |
| 6 |
6m36s |
0m29s |
| 7 |
32m54s |
0m25s |
| 8 |
33m18s |
0m32s |
| 9 |
38m17s |
1m25s |
| 10 |
18m14s |
0m59s |
| 11 |
5m25s |
1m11s |
| 12 |
15m47s |
1m11s |
| 13 |
24m22s |
2m28s |
Nas execuções seqüenciais, a mais rápida execução obteve uma solução em 4m50s, e a mais lenta levou 38m17s. O tempo médio para obtenção de uma solução foi de 17m51s.
Para as execuções em paralelo temos um ganho considerável, onde a mais rápida execução concluiu em 25s e a mais lenta em 2m28s, com tempo médio de execução de 1m10s.
A análise dos resultados visivelmente satisfatórios leva ainda a um Speedup alcançado de 15.28 (praticamente linear), que é definido como sendo o tempo médio das execuções seqüenciais dividido pelo tempo médio das execuções paralelas, neste caso específico utilizando 17 nós.
Conclusões
Foi visto durante o experimento que múltiplas populações isoladas ajudam a manter a diversidade.
O operador de migração, ao disseminar a informação dos indivíduos de melhor fitness gera perturbações na ilha receptora, fazendo com que esta realize um salto para um novo ótimo local.
Foi observado que as sob-populações colaboram entre si para a fuga de máximos locais.
Foi constatado um aumento significativo no número de parâmetros do AE, o que dificulta ainda mais o acerto para um problema específico. O novo parâmetro de periodicidade de migração se mostrou fundamental para alcançar o resultado favorável.
Referências
[ 1 ] E. Alba and J. M. Troya, “An analysis of synchronous and asynchronous parallel distributed genetic algorithms with structured and panmictic islands,” in Parallel and Distributed Processing, ser. Lectures Notes in Computer Science. Berlin: Springer, oct 1999, pp. 248–256.
[ 2 ] T. Baeck, D. B. Foegel, and Z. Michalewicz, Eds., Evolutionary Computation: Advanced Algorithms and Operators, 1st ed. Dirac House, Temple Back, Bristol BS1 6BE, United Kingdom: Institute of Physics Publishing, November 2000, vol. 2, ch. 15, 16, 26, pp. 101–124; 125–133; 253–263.
[ 3 ] S. R., “Parallel genetic algorithms,” in Proceedings of the Fifth International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann, 1993, pp. 334–341.
[ 4 ] “Speedup,” 2009. [Online]. Available: http://en.wikipedia.org/wiki/Speedup
[ 5 ] E. Cant ́ -Paz, “A survey of parallel genetic algorithms,” Calculateurs Paralleles, vol. 10, 1998.
[ 6 ] ——, “Designing efficient master-slave parallel genetic algorithms,” Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Tech. Rep. 97004, May 1997.
[7] ——, “Efficient and accurate parallel genetic algorithms.”
[8] X. Li and M. Kirley, “The effects of varying population density in a fine-grained parallel genetic algorithm.”
[ 9 ] M. Jelasity, “A wave analysis of the subset sum problem,” in Proceedings of the Seventh International Conference on Genetic Algorithms, T. Baeck, Ed. San Francisco, CA: Morgan Kaufmann, 1997, pp. 89–96.
[ 10 ] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. Cambridge, Massachusetts 02142: MIT Press, 2001, pp. 1043–1049.
One comment so far, add another ▶
