Warning: ob_start(): non-static method wpGoogleAnalytics::get_links() should not be called statically in /home/architecteam/smallthoughts.com.br/wp-content/plugins/wp-google-analytics/wp-google-analytics.php on line 259
Smallthoughts

Minhas ferramentas de desenvolvimento ágil favoritas

Após alguns anos nesta indústria, e se você, como eu, é fã de técnicas ágeis de desenvolvimento de software e viciado em testes (testes, testes, testes!!!), acaba colecionando uma série de ferramentas, bibliotecas e idiomas para facilitar o seu trabalho. Reuni aqui aquelas que uso com frequência e aquelas que lembro ter usado por alguma razão em particular, que estão no meu cinto de utilidades:

  1. JUnit: Comecei com o óbvio, o pai de todos. A não ser que você tenha se escondido num bunker anti-nuclear pelos últimos anos, você já ouviu falar, ou já usou testes unitários. Se você for mesmo sortudo, pode até mesmo ter praticado Test Driven Development. Aliás, uma boa referência no assunto é Test Driven Development: By Example.
  2. Refatoramento: Ok, ok, já vou parar com as obviedades, mas não dá para falar em desenvolvimento ágil sem uma boa IDE que permita refatoramento. Tanto o IDE Eclipse quanto o NetBeans, meus favoritos, fornecem excelente suporte. Acho que é pouco difundido e que está caindo no esquecimento o fato de que não só os refatoramentos fornecidos pela sua IDE são os que existem, e que o livro que popularizou estas técnicas foi o Refactoring: Improving the Design of Existing Code. Nele existem uns tantos outros que não são implementados por nenhuma IDE, muitas vezes por não permitir a automação da tarefa. Vale a pena uma olhada atenta.
  3. Maven: O gerenciamento de builds pode ser um assunto complexo e fadado a erros se não for bem administrado, e no final das contas a entrega para o cliente do produto é um momento crucial, o ápice de meses de desenvolvimento com suas melhores ferramentas e técnicas, e você quer dar a impressão certa. Para mim, o maven é a ferramenta de gerenciamento de builds da minha escolha, me livra de uma série de problemas dos quais não quero saber detalhes, e me fornece uma série de relatórios sobre a saúde do projeto, como relatório de cobertura de testes, aderência a convenção de formatação do código, Javadoc, etc..., todos reunidos num belíssimo site do projeto. Ótimo para impressionar seu gerente.
  4. EasyMock: Idealmente o teste unitário tem que ter um tempo de execução muito curto, uns poucos milissegundos. Se você começa a envolver bancos de dados, serviços da plataforma JEE, I/O em geral, o ciclo de realimentação programa-refatora-testa passa a ser muito lento, e o programador pára de testar como resultado natural. Os testes unitários devem permitir que sejam executados dezenas de vezes por dia.  É aí que entra o EasyMock, que permite que vc substitua partes do seu sistema por objetos falsos, com a mesma interface do objeto real, e verificar que o sistema está fazendo as chamadas esperadas. Mágico!
  5. DBUnit: E como popular as tabelas que serão usadas no teste com sua massa de teste? Esta é uma tarefa para o DBUnit, que permite inserir e remover dados em tabelas durante seu ciclo de testes.
  6. HTTPUnit: o HTTPUnit foi primeiramente pensado para permitir o teste unitário de aplicações web. Com ele você pode acessar uma url, preencher campos em formulários, enviar, verificar a resposta, enfim, emular um usuário humano. Recentemente andei dando uma outra utilidade para ele, acesssando serviços Rest e verificando os dados da resposta. Muito bom.
  7. Liquibase: Sou fã deste projeto. Ao brincar com Ruby on Rails, fiquei realmente maravilhado com o esquema de gerenciamento de alterações do banco de dados. Ele o faz através de pequenos scripts que fazem parte do próprio projeto, mantendo controle inclusive da versão instalada e executando somente o necessário a cada nova atualização. Ao procurar no mundo Java algo semelhante, me deparei com esta biblioteca e tenho utilizado-a em minhas aplicações com sucesso. Você constrói arquivos XML com as alterações em banco, identificados com o autor e a versão, e a biblioteca toma conta de atualizar o banco de dados aplicando somente a diferença entre versões. Ou então pode-se também apenas, no final de uma iteração, gerar um arquivo com o script a ser executado, em ambiente que exigem maior controle por parte de um DBA. Recomendo.
  8. Mercurial: Sou usuário de longa data de CVS e Subversion. Mas sistemas de controle de versão distribuídos estão aí, e dão toda uma nova gama de possibilidades, além de serem extremamente velozes. O Mercurial é utilizado internamente pelo projeto NetBeans, um projeto de grande porte, e muitas das suas operações, como commits, updates, roolbacks, diffs, são praticamente instantâneos. E nada como levar consigo todo o repositório, e fazer commits no site do cliente.
  9. P6Spy: Ferramente simples demais, útil demais, estou preocupado em não sofrer atualizações desde 2003. Permite que você monitore a comunicação entre o seu código e o servidor de banco de dados, plugado direto no seu servidor, no teste unitários, em qualquer lugar onde couber um driver JDBC. Excelente para tunning e momentos de total desespero.
  10. OpenEJB: Confesso que passei um bom tempo longe da plataforma JEE por traumas com a especificação EJB, preferindo sempre opções que me permitissem agilidade e testes. Nesta época usava bastante o projeto Apache Cactus, mas convenhamos, não é a mesma coisa. O OpenEJB é o contêiner EJB usado pelo servidor Apache Gerônimo, mas pode ser usado em qualquer aplicação JSE, de forma standalone ou junto com o Tomcat, ou ainda nos seus teste unitários, permitindo o teste de mensagens assíncronas JMS, EJBs Stateless, Stateful, Singleton, Time Service, enfim, tudo o que vc espera de um servidor real. Ele ainda toma decisões muito espertinhas para realmente facilitar seu uso em testes unitários, como a criação automática de DataSources, utilizando o banco HSQLDB em memória. Apesar da existência na especificação EJB 3.1 do contêiner embarcado, próprio para uso em aplicações standalone e em teste unitários, a especificação diz que os provedores somente precisam fornecer o perfil EJB Lite, o que, se você precisa como eu testar o restante que não se encontra no perfil, é insuficiente.
  11. HSQLDB: E nada melhor para seus testes unitários com banco de dados, do que um banco de dados que permite criar tabelas apenas em memória. É isso, simples assim.
  12. SeleniumHQ: Quem já tentou automatizar testes de interfaces com o usuário, sabe que não é uma tarefa fácil. A interface com o usuário é um alvo móvel, difícil de acertar. Eu realmente admiro aqueles que se propõe esta nobre tarefa.  Desenvolver interfaces não é lá a minha praia, mas já brinquei com o Selenium, e fiquei muito impressionado. Tem as mesmas capacidades de ferramentas caras de teste, como a gravação da sua iteração com o sistema, e a capacidade de rodar o mesmo conjunto de testes numa rede de máquinas com diversas configurações de sistemas operacionais e browsers. Com certeza, para a sua próxima killer web app, vale o esforço.
  13. Cruise Control: Para saber rapidamente se o código enviado para o repositório continua funcionando, e evitar o pesadelo da fase de integração, nada melhor do que uma ferramenta de integração contínua. Já experimentei o Hudson e o Continuum, mas ainda continuo com o velho e bom Cruise Control. Apesar de ser mais difícil de configurar do que seus irmãos mais novos, permite uma flexibilidade maior na sua configuração, além de ter uma grande estabilidade. Mantenho duas tarefas agendadas: uma build após cada commit de código no repositório, e a construção do site do projeto diariamente.
  14. JMeter: E por último, e não menos importante... Não deixe seus testes funcionais para mais tarde por que, senão, pode ser tarde demais. Principalemente testes de desempenho. O JMeter permite que você simule o comportamento de centenas de usuários atacando furiosamente sua aplicação, e encontrar onde aqueles leaks e gargalos estão escondidos.

Longe de ser uma lista definitiva e completa, é a minha lista. E é claro, uma última ferramenta importante é uma pitada de bom senso, afinal de contas, nada de tentar chegar em 100% de cobertura de testes. Pode soar como ideal, mas é sem dúvida, ingênuo. E sempre lembrando as imortais palavras de Dijkstra:

Testing shows the presence, not the absence of bugs.

Bookmark and Share
3 comments so far, add yours

Blog elevado a cidadão de primeira categoria

Gostaria de avisar a todos que seguem este blog que acabo de elevá-lo a cidadão de primeira categoria! Para quem está acostumado com os domínios www.architecteam.com.br/people/fabio/blog, e com o www.architecteam.net/people/fabio/blog, agora pode seguir este mesmo blog em www.smallthoughts.com.br. Quero que o blog cresça de importância, e isso não podia acontecer enquanto fosse tão mal tratado. Manterei os outros endereços funcionando por tempo indefinido, mas se o seu interesse é acompanhar somente o blog, sugiro que atualize seu cliente leitor de feeds para o novo domínio. Sem pressa.

Bookmark and Share
2 comments so far, add yours

Traduzindo o livro Pharo by Examples para o Português!

Eu liderarei nos próximos meses o esforço de tradução do livro Pharo by Examples para o português, minha pequena contribuição para tornar esta linguagem e ambiente que tanto gosto mais conhecidos pelos estudantes e desenvolvedores falantes da língua portuguesa, que talvez tenham como obstáculo maior a língua e não a linguagem.

Acredito que tanto o ambiente quanto a linguagem são completamente diferentes de tudo que temos no ambiente corporativo, e apesar de muitas das idéias colocadas neste ambiente terem mais de 30 anos, sempre é um ambiente revigorante de se manter em contato.

Como todo código é aberto e em Smalltalk, tudo é acessível e passível de ser mudado. Tudo é objetos. Grandes pesquisadores em linguagens, compiladores e engenharia de software testam suas idéias primeiro neste ambiente e em seus variantes, como foi com testes unitários, programação orientada a aspectos, closures e outras. Sua comunidade é, com certeza, empolgante e tem o que falar.

Criei uma nova página que manterei atualizada com o resultado parcial do trabalho de tradução. Todos que quiserem contribuir, sintam-se convidados. Serão todos bem vindos.

Bookmark and Share
Leave the first comment

Balanço Cultural Janeiro

Esse mês deve ser um mês atípico, talvez pela sensação de "férias" (apesar de não ter tido férias de verdade...). Estou quase me sentindo culpado pelo placar:

  • 13 filmes
  • 1 viagem
  • 1 livro

Começando pelos filmes, em algo como uma ordem cronológica... Assisti Norbit, e dei algumas boas risadas... Achei que ia ser uma grande porcaria, mas foi uma boa porcaria. Divertido. A história de um pobre orfão que descobre o amor da sua vida no orfanato, mas logo o perde e por um azar do destino uma mulher gigante e horrorosa cola na dele, e o faz acreditar que uma vida de humilhações e submissão é o que merece. Mas logo seu grande amor volta a cidade, mais linda do que nunca, mas com alguns problemas que o cavaleiro andante terá que ajudar a resolver. Muitas piadas sobre sua mulher gigante e seus irmãos valentões, politicamente incorreto contra pessoas gordas e negros. Pegue um grande balde de pipoca e assista sem compromisso.

El Orphanato é mais uma rica peça com a participação de não mais, não menos do que Guillermo del Toro. Um suspense de ficar colado na poltrona, segurando a mão da sua esposa/namorada/whatever. Sem apelar para o gore ou monstrinhos, consegue surpreender e agradar mesmo aqueles que estão cansados do gênero terror. Tem um gostinho de El laberinto del fauno, onde o mundo real e o imaginário se confundem perdidos na imaginação infantil. Esse eu recomendo fortemente, deve fazer parte da cultura geral de todo apreciador de cinema que se preze!

007 Cassino Royale. Meu pai tem uma coleção bem completa de todos os 007s antigos, e os meus preferidos são os com nosso amigo Sean Connery. Depois de assistir os mais recentes com Pierce Brosnan, sinceramente, fiquei cansado da overdose de sequencias de ação totalmente improváveis e irreais, onde James Bond era praticamente um super-herói cujo super poder era a sorte infinita. O foco também deixava de ser a história, para dar ênfase a parafernália eletrônica que, juro, me empolgava nos filmes antigos, mas começou a irritar pelo excesso. Acho que os diretores capturaram este descontentamento dos fãs, e criaram um ótimo filme de ação, mais crú, onde Bond se machuca, cai, leva porrada, é enganado, e só se sai bem graças as suas habilidades, e não aos seus gadgets de alta tecnologia. Thumbs up! Pipoca na veia!

Final Fantasy VII: Advent Children. Eu sou um apreciador da saga de video game Final Fantasy, sempre um RPG de excelente qualidade e gráficos incríveis. Joguei no computador o Final Fantasy VII sem no entanto finalizar o jogo. Trabalho, sempre o trabalho. Quando vi este título na locadora, o saudosismo invadiu, e quis assistir este longa baseado no jogo. Na verdade, a história se passa mais ou menos como uma continuação dos eventos do jogo, no mesmo ambiente e com os mesmos personagens. Apesar da excelência gráfica (ok, devemos dar sempre as devidas proporções de acordo com a época de produção, não espere um Avatar...) a história é chata, não empolga, não mantêm um bom ritmo, diálogos enfadonhos... enfim, boring. Uma decepção. Se você é um saudosista e gosta de computação gráfica e não tiver nada melhor o que fazer, vá e assista, caso contrário, passe longe.

Slumdog Millionare. Ou em português, Quem quer ser um milionário? Um indiano pobre começa a acertar as perguntas de um programa igual ao nosso Jogo do Milhão, e é preso por suspeita de trapaça. E então começa a contar sua saga, e como sabe a resposta de todas as perguntas, e o motivo de estar participando: a busca pelo amor da sua vida. O filme tem uma fotografia muito bonita, sua história é muito bonita, mas de tanto ouvir falar dele, esperava mais. Mas não deixe de assistir, sem dúvida é um filme que faz a diferença.

Kalifornia. Mais um filme onde Brad Pitt tenta mostrar que não serve somente para papéis de galã. E consegue. Um filme intrigante, onde um casal começa sua viagem para a Califórnia, atrás de material para um livro sobre serial killers. E acabam descobrindo que seus caronas são, eles mesmos, assassinos frios. Um suspense perturbador, mais um que nos faz questionar a natureza humana. Recomendado para os amigos.

The Last King of Scotland, filme que deu o oscar de melhor ator para Forest Whitaker, sobre o presidente ditador de Uganda Idi Amin Dada. Acredito que o filme seja pseudo-histórico, com as devidas liberdades poéticas, mas de qualquer forma também é um excelente filme, mostrando também a sempre perturbadora realidade vivida pelo continente africano. Muito bom.

Up, Altas Aventuras! E quem disse que desenho animado é só para crianças? Já a algum tempo os grandes estúdios sabem que a verdadeira fórmula de sucesso de uma animação é envolver tanto o público infantil quanto o adulto. Eu tenho minhas dúvidas se isto foi bem balanceado em Up, achei que o roteiro é muito mais apreciado por um adulto do que por uma criança. Claro que existem as cenas bobas e engraçadas feitas para a criançada rir, mas numa quantidade bem menor do que, por exemplo, Ice Age ou The Incredibles. Com certeza muito gostoso de assistir, com cenas que até dão um certo nó nesta passa seca que você chama de coração. Vale a pena.

Trois couleurs: Rouge. EU ASSISTI TODA A TRILOGIA DAS CORES. Este é o último. Podem atirar pedras aqueles que se acham cults, mas precisa ter coragem para assistir todos os três. Ok, belíssimos, sempre mostrando o lado humano, de paixão, egoísmo, amor, perda, e bla bla bla..., mas como uma boa salada de alface e tofú, é saudável mas insípido. Só não dormi porque sou daqueles que querem ver até onde o filme vai, mesmo os piores. Se quiser impressionar os amigos, vá em frente e assista! Ou ainda preciso desenvolver um gosto mais apurado por este tipo de filme, ou todos os cinéfilos se reúnem em suas rodinhas e mentem descaradamente. Tentei achar um elemento de ligação entre os três filmes, e achei: aquela velhinha corcunda ao fundo, que fica tentando colocar garrafas no recipiente de reciclagem. É quase uma brincadeira de "Onde está Wally" vê-la, então, não acredite em ninguém que diga ter visto a trilogia sem comentar da tal velhinha. Não diga que eu não avisei.

Todo sobre mi madre. E bem vindo ao mundo de Almodóvar! E falando em cinema autoral, tá aí um cara que todo filme é um convite para um passeio em sua cabeça. Eu tenho medo dele. Já vi filmes com gays, travestis, padres que violentam garotinhos, freiras que engravidam de travestis e pegam AIDS... Que mundinho deturpado. Mas não dá pra negar que o cara sabe contar uma história, e mostrar a humanidade de seus personagens, muitas vezes em situações extremas. Este filme não é diferente. Mas conheço muita gente que não teria estômago para assistí-lo, entã vá com cautela. É tapa na cara no maior estilo Almodóvar.

Gran Torino. O que eu posso falar sobre Clint Eastwood? Acho que o mundo perdeu um ator discutível, mas ganhou um diretor/produtor/roteirista de primeira. Suas histórias são simples, atacando temas polêmicos como a eutanasia em Million Dolar Baby, a visão mais humana do derrotado em Letters from Iwo Jima, e este, sobre os enganos causados pelo preconceito racial. Não sei porquê, tinha uma impressão errada do roteiro, achei que Clint seria o bad guy, mas não tem como não se afeiçoar ao velhinho mais badassmotherfucker que o cinema já viu. Recomendo!

O mais novo filme Star Trek me deu a sensação, me corrijam os trekkers de plantão, de ser um filme bem digno do nome. Eu tenho a série em minha mais alta conta, apesar de não ir ao cinema vestindo orelhas pontudas... Gostei do ritmo, gostei da ação, e de todas as referências a série de TV. Sem falar da emoção de ver meus heróis, adolescentes, e o começo de tudo. Filme pipoca + diversão com certeza!

Paris, je t'aime. O que eu posso dizer... Cinema francês deve ser pra poucos, e eu me excluo do grupo. Neste filme, um grupo de diretores famosos contam histórias de amor em Paris. Ótimo filme para agências de viagem ou se você planeja ir para a capital mais bonita do mundo, mas não se você quiser diversão. Cinéfilos sadomasoquistas, este é pra vocês.

E chega de filme, acho que exagerei este mês, preciso ler mais e perder menos tempo na frente da tela... Tudo bem que, para compensar, fiz minha primeira grande viagem de moto, passando por Jaguariúna, Pedreira, Amparo e finalmente, Serra Negra. Esta viagem gerou boas fotos, e me mostrou que estava pronto para viagens mais longas. Na verdade, só vimos de passagem tanto Jaguariúna quanto Amparo, paramos mesmo em Pedreira e Serra Negra. Pedreira tem todo tipo de artesanato feito de... pedras (vidro, porcelana, pedra sabão, ferro), além de artesanato em madeira e ítens de decoração. Apesar de não gostar de feiras de artesanato, realmente o material era muito bonito e barato, e apesar do pouco espaço, acabei trazendo um candelabro de lá, de ferro em formato de tulipa. Está na mesinha da sala. Serra Negra é uma cidade com vocação turística, que me disseram ser uma cidade romântica. Não sei se pelo pouco tempo ou pelo desconhecimento, senti falta de ver mais beleza natural, que era a minha expectativa. Mesmo assim, seguimos por uma estradinha secundária de asfalto e depois terra, e chegamos numa propriedade particular que, infelizmente, cobrava para que os visitantes tivessem acesso a Cachoeira dos Sonhos... Ela valeu a viagem.

E finalmente, para finalizar a programação cultural, li Pragmatic Thinking and Learning: Refactor Your Wetware (Pragmatic Programmers). Ultimamente tenho estado atraído pelo tema de auto-compreensão e como acessar novas formas criativas de pensamento. Sou um cara de exatas, fui treinado para ter pensamentos lógicos, analíticos e não cometer erros (ou pelo menos me esforçar...). Mas nesta altura do campeonato, algumas das minhas atividades têm perdido a cor e o sabor, como se a vida fosse um grande lanche de fast-food sem graça. Este livro sugere que para alcançarmos novos níveis de produtividade, nós, exatóides, precisamos desenvolver a nossa criatividade e permitir que nossos modos de pensar e aprender envolvam tanto a forma de pensar analítica e lógica, quanto a holística e criativa. Para muitos pode parecer um bla bla bla de livro de auto-ajuda, mas resolvi vencer meu ceticismo e comecei a praticar desenho como hobby. Comecei a ler um livro que fazia parte da referência bibliográfica: The New Drawing On The Right Side Of The Brain, e vamos ver onde vou chegar. Afinal de contas, especialização é para máquina e formigas.

E até o próximo mês...

Bookmark and Share
Leave the first comment

Balanço Cultural de Dezembro

Vou tentar começar um hábito saudável que vi em alguns blogs, de realizar um balanço cultural do mês. Este mês foi bem fraco, o placar é:

  • 2 livros
  • 5 filmes

Comecei lendo o Modular Java: Creating Flexible Applications with Osgi and Spring (Pragmatic Programmers), um livro sobre modularização de aplicações usando o framework OSGi. Achei o livro muito bom, tem muitas dicas práticas, ensina as vantagens do modelo e não é um livro feito para a propaganda de algum grande player da área, como o Spring DM ou o framework Equinox. Mostra todas as opções e como migrar de uma implementação para outra. Comecei a trabalhar em um dos meus projetos no sentido de testar estas idéias, já que sou muito traumatizado com o peso de soluções usando servidores JEE e a muito tempo trabalho somente com técnicas e frameworks que me permitam mais agilidade e testabilidade.

Li também, aliás, muito rapidamente já que a leitura é muito fácil, o livro The Passionate Programmer: Creating a Remarkable Career in Software Development (Pragmatic Life), que faz parte da coleção Pragmatic Bookshelf, a qual tem como livro mais famoso o excelente The Pragmatic Programmer: From Journeyman to Master. Este livro é quase um livro de auto-ajuda para programadores, pessoas com um viés técnico que perderam a fé em sua profissão. Eu particularmente não gosto de livros de auto-ajuda, normalmente a única pessoa a quem eles ajudam são seus próprios autores, mas este em particular chamou minha atenção logo de cara. Talvez por ser um período de reflexão coletiva, ou por eu particularmente estar no meu momento de reflexão, este livro traz algumas obviedades que são boas de se ouvir da boca de outros, e algumas outras coisas não tão óbvias. Faz o leitor refletir sobre sua carreira, suas decisões quanto a ela, e quais os caminhos a seguir caso se deseje uma carreira fantástica fazendo o que gosta, e não somente trazer o arroz com feijão para a mesa todos os dias. Recomendo!

Partindo para os filmes, alguns bons e outros nem tanto. Finalmente, e depois de todo mundo, assisti Transformers: Revenge of the Fallen. Muito bom! Para aqueles saudosistas que como eu, cresceram assistindo aos desenhos, um presentão, pancadaria robótica de excelente qualidade, excelentes efeitos, tudo de bom. A história é meio fraquinha, bem batida mesmo, mas e daí? É pipoca e diversão na certa pra quem gosta do estilo. Tem inclusive uma cena com um conjunto de robôs pequenos se unindo para criar um robô maior e mais complexo, que tem tudo a ver com as matérias que tenho visto no mestrado, em inteligência de enxame e robótica coletiva. Dêem uma olhada neste vídeo e nos demais associados e vão ver o que estou falando.

Assisti este mês também o filme Solaris, uma ficção científica protagonizada por, pasme, George Clooney. Sinceramente, meus sentimentos para com este filme ficaram meio confusos. O roteiro é bom, mas dá a impressão que poderia ser melhor explorado. Tem um quê de Gattaca, um filme que gosto muito, no sentido de que é um filme de ficção sem um grande orçamento para efeitos especiais, e então se concentra na história. E tem bastante de Sphere, outro filme que gosto bastante, em relação ao roteiro. Mas George Clooney não convenceu numa ficção, é melhor que continue como médico em E.R. ou em outros tantos filmes de ação que fez. Ponha no final da sua lista.

Assisti também Yes Man, e só confirmou minhas impressões anteriores, prefiro Jim Carrey fazendo comédias onde não tenha que fazer caretas. Filminho bom, mas fraquinho, prefiro Bruce Almighty ou Me, Myself & Irene dos cômicos de Jim, ou a obra de arte  Eternal Sunshine of the Spotless Mind, que é do Jim, mas explora sua veia dramática. Se estiver na locadora e não tiver nada melhor, pode pegar que rende umas risadas.

Fui com alguns sobrinhos assistir o Avatar, sem grandes expectativas, achando até mesmo que seria um filme/desenho meio infantil. Que engano. Efeitos visuais incríveis, roteiro empolgante, soberbo! Aliás, os efeitos visuais merecem comentários a parte... Conseguiram fazer com que toda uma fauna e flora fosse coesa, com elementos anatômicos semelhantes entre as criaturas superiores (afinal de contas, todo cordado tem o corpo simétrico, tem mesmo número de olhos, pulmões, membros superioes e inferiores, etc...) e as espressões dos personagens, caramba, sempre ficava a dúvida se era computação gráfica ou atores maquiados. Ainda preciso pesquisar qual a técnica usada. Se ainda não viu, corra! Mas tente ver numa destas salas 3D, infelizmente não fui numa destas, mas imagino que a experiência deve ser muito mais rica.

E finalmente, The Boy in the Striped Pyjamas, muito bom, pode assistir sem medo, mas esperava algo... sei lá, a mais. Mais um drama envolvendo a segunda guerra mundial, só que agora envolvendo crianças, que que torna ainda mais triste, e tal. Senti que tentaram arrancar algumas lágrimas, mas não funcionou comigo. Quer um drama envolvendo crianças na segunda guerra, que seja surpreendente tanto no roteiro quanto no visual? Assista El laberinto del fauno, mais um filme excelente do diretor Guillermo del Toro.

Tentei assistir também Disaster Movie, mas não consegui, parei nos primeiros 15 min. de filme. Fiquei com medo que alguém visse que eu estava assistindo aquilo. Fique longe desse título, nem se for o que sobrou na locadora, deve matar alguns neurônios no processo. Que filme ruim! Do tipo pastelão, sem sentido e sem graça.

Até o próximo mês!

Bookmark and Share
2 comments so far, add yours

Relembrando Aqueles que fazem falta

Não consigo deixar de admirar pessoas como Edsger Dijkstra, pessoas que como ele fizeram a diferença na área em que trabalho e estudo. Estas pessoas servem de inspiração e devem sempre ser lembradas. Dijkstra uma vez escreveu em suas Notes on Structured Programming:

These notes have the status of "Letters written to myself": I wrote them down because, without doing so, I found myself repeating the same arguments over and over again. When reading what I had written, I was not always too satisfied.

Este pequeno trecho já demonstra toda sua preocupação com a perfeição e com sua busca pela melhora contínua como pesquisador.

Quem dera eu ter tantas coisas boas a escrever para mim mesmo como este gigante.

Bookmark and Share
Leave the first comment

Erlang em Pílulas – Compilando um Programa

Saber entrar e sair do shell do Erlang é o primeiro passo, mas não é muito útil. A diversão começa quando passamos a construir nossos próprios programas.

Eu tenho usado o Emacs para escrever meus programas em Erlang, ele tem um ambiente que colore os elementos e ajuda a fechar parênteses e completar expressões.

Linguagens funcionais são recursivas por natureza, então nada de Hello World, nada melhor do que começar com uma função recursiva como exemplo. Que tal o fatorial:

-module(lib).
-export([fac/1]).

fac(0) ->
    1;
fac(N) ->
    N * fac(N-1).

O código acima pode ser escrito num arquivo e compilado, e demonstra algumas coisas básicas da linguagem. Primeiro, todo comando deve terminar com um ponto ".". Na linha 1 e 2 estão algumas diretivas obrigatórias de todo código fonte, module e export. Toda diretiva de compilação começa com o sinal de "-". A diretiva module declara o nome do módulo deste arquivo. Em Erlang, cada arquivo é um módulo, ou seja, um conjunto coeso de funções. Normalmente se o módulo se chama "lib" como o exemplo, então o arquivo precisa se chamar "lib.erl", porque com esta convenção o compilador consegue encontrá-lo automaticamente. Em Erlang, uma lista de elementos é representada usando colchetes "[]" com cada elemento separado por vírgulas. Alguns exemplos de listas:


[3,78,2,7,3].
["hello", "world"].
[hello, world].

A primeira lista contêm 5 números inteiros, a segunda 2 cadeias de caracteres, e a terceira 2 átomos. Então como podemos perceber a segunda diretiva de compilação export recebe como argumento uma lista, onde cada elemento é o nome de uma função que o módulo exporta para uso externo e o número de argumentos. Em Erlang, funções com mesmo nome mas número diferente de argumentos são funções completamente diferentes. Toda função em Erlang precisa retornar algum valor.

Uma função em Erlang sempre tem o formato Assinatura -> CódigoParaExecução. A primeira parte determina o nome e os argumentos da função, enquanto a segunda contêm o que será executado. Em Erlang a execução de uma função sempre envolve comparação de padrões, e uma função pode declarar vários padrões separados por ";". Cada padrão é testado contra os argumentos, em sequência, até que algum se aplique ou caso contrário, é lançado um erro.

No caso do fatorial, o primeiro padrão é "fac(0) -> 1". Ao se chamar esta função com o primeiro argumento igual a zero, será retornado zero. O segundo padrão é "fac(N) -> N * fac(N - 1)". Ou seja, para qualquer valor de parâmetro diferente de zero, o segundo padrão é invocado, e faz uma chamada recursiva para a mesma função, até que o parâmetro seja igual a zero, e então é executado o código do primeiro padrão, e a recursão pára.

Ok, hora de compilar e executar esse código. Salve um arquivo com o nome "lib.erl" com o conteúdo acima e no mesmo diretório execute:

fbdo@Marvin:~/Projetos/Erlang$ erl
Erlang (BEAM) emulator version 5.5.5 [async-threads:0] [kernel-poll:false]

Eshell V5.5.5 (abort with ^G)
1> c(lib).
{ok,lib}
2> lib:fac(10).
3628800
3>

Como pode ser visto, invoquei o shell usando o comando "erl", compilei o código usando "c(lib)", recebi a mensagem de que a compilação teve sucesso "{ok,lib}" e então invoquei a função que acabei de compilar usando a convenção modulo:função "lib:fac(10)". E agora, para impressionar os amigos, que tal calcular o fatorial de 1000?


3> lib:fac(1000).
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044\\
208486969404800479988610197196058631666872994808558901323829669944590997424504087073759\\
918823627727188732519779505950995276120874975462497043601418278094646496291056393887437\\
886487337119181045825783647849977012476632889835955735432513185323958463075557409114262\\
417474349347553428646576611667797396668820291207379143853719588249808126867838374559731\\
746136085379534524221586593201928090878297308431392844403281231558611036976801357304216\\
168747609675871348312025478589320767169132448426236131412508780208000261683151027341827\\
977704784635868170164365024153691398281264810213092761244896359928705114964975419909342\\
221566832572080821333186116811553615836546984046708975602900950537616475847728421889679\\
646244945160765353408198901385442487984959953319101723355556602139450399736280750137837\\
615307127761926849034352625200015888535147331611702103968175921510907788019393178114194\\
545257223865541461062892187960223838971476088506276862967146674697562911234082439208160\\
153780889893964518263243671616762179168909779911903754031274622289988005195444414282012\\
187361745992642956581746628302955570299024324153181617210465832036786906117260158783520\\
751516284225540265170483304226143974286933061690897968482590125458327168226458066526769\\
958652682272807075781391858178889652208164348344825993266043367660176999612831860788386\\
150279465955131156552036093988180612138558600301435694527224206344631797460594682573103\\
790084024432438465657245014402821885252470935190620929023136493273497565513958720559654\\
228749774011413346962715422845862377387538230483865688976461927383814900140767310446640\\
259899490222221765904339901886018566526485061799702356193897017860040811889729918311021\\
171229845901641921068884387121855646124960798722908519296819372388642614839657382291123\\
125024186649353143970137428531926649875337218940694281434118520158014123344828015051399\\
694290153483077644569099073152433278288269864602789864321139083506217095002597389863554\\
277196742822248757586765752344220207573630569498825087968928162753848863396909959826280\\
956121450994871701244516461260379029309120889086942028510640182154399457156805941872748\\
998094254742173582401063677404595741785160829230135358081840096996372524230560855903700\\
624271243416909004153690105933983835777939410970027753472000000000000000000000000000000\\
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\\
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\\
000000000000000000000000000000000000000000000
4>

Uau, isso foi rápido. E o mais impressionante: este número gigante que no meu terminal ocupa 30 linhas e que foi calculado por uma função recursiva não estourou a pilha de execução, nem o tamanho da variável. Para pessoas que, como eu, têm mais experiência com C/C++ ou Java, é quase mágico o que acaba de acontecer. Mas as magias tem nome, e se chamam otimização da recursão em cauda e conversão implícita de tipos.

Em Erlang só existem dois tipos numéricos, o inteiro e o número de ponto flutuante. E eles nunca estouram porque não têm tamanhos fixos, e sim crescem enquanto houver memória disponível.

Para linguagens funcionais, a recursão é parte essencial, já que não existem operadores de laços. Então quase todas otimizam o quanto podem as chamadas recursivas, e no caso do fatorial a otimização é trivial, já que não existem operações a serem realizadas após a chamada recursiva, o que é chamado de recursão em cauda. O que a máquina virtual Erlang faz, ao invés de empilhar a chamada recursiva, é sempre substituir o endereço de retorno da função pelo endereço da função chamada, mantendo a pilha com tamanho constante. Nada de "StackOverflowException". É como se substituíssemos a função recursiva por uma interativa equivalente:


função fatorial(x: inteiro): inteiro
var i, aux: inteiro
inicio
aux <- 1;
para i de 1 até x faça
aux <- aux * i
fim_para
fatorial <- aux
fim

E por hoje chega de diversão com funções recursivas.

Bookmark and Share
Leave the first comment

E o reconhecimento de voz/imagem se tornam commodities...

Ao abrir minha Communications ACM deste mês, vi um artigo na sessão BLOG@CACM que me chamou a atenção. O artigo de Tessa Lau Hello Computer comentava sobre sua satisfação com seu novo GPS, um Garmin Nüvi 850. Não por simplesmente ser um excelente GPS, mas sim por ter uma interface ativada por voz.

Isso me fez lembrar de um pequeno projeto em que me envolvi com alguns amigos, a algum tempo, por nós chamado de projeto MONOH (MOmmy, NO Hands!). Resumindo, o objetivo do projeto era criar um plugin para a IDE Netbeans que fornecesse a capacidade da ativação por voz de alguns comandos normalmente acessíveis via teclas de atalho. Cá entre nós, e que ninguém nos ouça, confesso que a razão principal de investir neste projeto era, na época, a de poder ganhar o NetBeans Innovators Grants Contest, o que conseguimos com relativo sucesso. Eu acredito que um fator determinante para nossa vitória foi exatamente o fator coolness da proposta, afinal de contas todo mundo acha muito legal parar de usar o mouse e o teclado e começar a falar com a máquina. De uma forma geral, o que queremos mesmo é parar de ter que nos relacionar com todas as inúmeras máquinas que nos cercam no dia-a-dia usando a linguagem delas, para poder usar a nossa. Acabar de uma vez por todas com este problema de impedância.

O que me deixa mais chateado é ter que confessar também que todo o mérito pelo reconhecimento de voz do nosso projeto não é de ninguém da equipe, e sim do projeto Sphinx4. Este projeto, apoiado pela Carnegie Mellon University entre outros, é um reconhecedor de voz escrito em Java, estado-da-arte, livre e open source. Nosso mérito foi o de estudar a API NetBeans, estudar a API do Sphinx4, e colar os dois. É assombroso a qualidade do que se tem hoje em dia na forma de software livre e open source. Ou seja, para fazer hoje um aplicativo que reconhece a voz, não é mais necessário um doutorado. Com tempo e paciência qualquer um pode impressionar seus amigos.

Outro exemplo de como o relacionamento homem-máquina tem melhorado, mas é quase bobagem mencionar, são essas máquinas fotográficas que temos hoje que somente batem a foto quando as pessoas focalizadas sorriem. Elas são quase banais, estão a venda em qualquer loja por preços acessíveis a qualquer mortal. Será que somente eu me assombro em como um simplório chip que cabe numa máquina fotográfica é capaz de fazer o reconhecimento de face, e determinar se alguém está sorrindo?!?!

E por último, um vídeo no YouTube também fez minha cabeça explodir. O mundo foi assolado pela febre do Wii, mas isso poderá ser nada comparado ao Project Natal. O Project Natal, que tem seu nome em homenagem a, pasmem, nossa cidade de Natal no Rio Grande do Norte graças ao brasileiro que comanda o projeto, leva a iteratividade a um outro patamar: não há controles! Somente você, balançando suas mãos e pernas na frente do console, tendo seus movimentos reproduzidos na tela. Droga, serei obrigado a comprar um XBox 360 (além de um PS3 quando sair o God of War III).

Tudo isso me faz ver que estamos no momento histórico onde aquelas inúmeras pesquisas que a décadas não passavam de estudo acadêmico estão chegando às prateleiras, estão aí nas ruas, não assombram mais ninguém. Provavelmente nossos filhos vão achar engraçado nossas histórias de como era usar uma bugiganga com 102 teclas e uma outra com 2 teclas que movíamos na mesa pra lá e pra cá para fazer nossos computadores nos entenderem. Finalmente estamos no ponto histórico onde estudos do guarda chuva de inteligência artificial, por muitos considerados distantes e áridos, viraram commodities, na mão de todo mundo, sem que ninguém nem precise saber o quão sofisticado aquilo na verdade é para poder usar, e poder usufruir.

Não espere mais, comece a falar com seu computador hoje! Ele um dia poderá entender.

Bookmark and Share
Leave the first comment

Erlang em Pílulas - Entrando e saindo do shell

Como muitas vezes é dito por Andrew Hunt, autor do livro The Pragmatic Programmer: From Journeyman to Master (recomendo!) é muito bom para todo programador aprender pelo menos duas novas linguagens por ano. Já a algum tempo tenho flertado com Erlang, e uma das razões é todo o alvoroço na comunidade de desenvolvedores a volta de linguagens funcionais, e outra pelos meus interesses em desenvolvimento de código paralelo e concorrente.

E é justamente nestes pontos em que Erlang mostra a que veio, e é por este motivo todo o alvoroço. Erlang foi desenvolvido nos laboratórios da Ericsson para o desenvolvimento de centrais telefonicas, num ambiente com requisitos de tempo real mais leves e alta disponibilidade. O fato de ser uma linguagem funcional faz ter uma característica muito comum em muitas linguagens funcionais: a ausência de efeitos colaterais em suas funções, não existindo, com isso, a necessidade da existência de mecanismos de sincronização para áreas de memória compartilhada. Existem primitivas na linguagem que permitem o desenvolvimento de software paralelo e concorrente de forma muito mais simples do que no mundo procedural das principais linguagens como Java, Python ou C/C++, usando passagem de mensagens, implementando o modelo de atores (Actor Model). Quem já teve que implementar um programa concorrente usando múltiplas threads sabe que não é uma das tarefas mais triviais. Mas isso tudo é muito bem explicado em qualquer sítio na internet sobre Erlang, o que eu gostaria mesmo é de demonstrar um pouco de como é desenvolver programas usando esta linguagem.

Primeiro, instale uma versão de Erlang na sua plataforma preferida. Eu uso linux/Ubuntu, então meus exemplos vão ter a cara desta plataforma. Ao executar o comando erl na linha de comando, você verá algo como isto:


Erlang (BEAM) emulator version 5.5.5

[/source]

[async-threads:0] [kernel-poll:false]

Eshell V5.5.5 (abort with ^G)
1>

Agora digite o seguinte:


1> 2 + 5.
7
2>

Primeira coisa a perceber é que o shell do Erlang numera as linhas conforme você dá entrada. Todo comando em Erlang deve terminar com ponto "." e um enter. Todo comando devolve alguma coisa, e ao digitar 2 + 5 ele corretamente devolveu 7.

Para terminar com o shell do Erlang, basta um Control-C. Você verá a seguinte saída:


BREAK: (a)bort (c)ontinue (p)roc info (i)nfo (l)oaded
(v)ersion (k)ill (D)b-tables (d)istribution

Digite "a" para deixar o shell.

Outra forma de deixar o sistema, é digitando "halt()":


1> halt().
fbdo@Marvin:~$

Na próxima pílula de Erlang, vou falar um pouco sobre como compilar um programa nesta linguagem.

Bookmark and Share
3 comments so far, add yours

Usos de Computação Paralela e Distribuída em Computação Evolutiva

Evolution, from Man to Evolutionary Algorithms

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:

  1. 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.
  2. 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.
  3. 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

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

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).

distribuido

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

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

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

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 W = \{w_1,w_2,...,w_n\} de n inteiros e uma constante M, encontrar um subconjunto V \subseteq W 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]. 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 2^n 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 C = (\vec{x} = (x_1,x_2,...,x_{100000})) e P(\vec{x}) = \sum_{i=1}^{100000}x_i w_i, a função objetivo utilizada foi:

f(\vec{x}) = a \cdot P(\vec{x}) + (1 - a) \cdot \lfloor (M - 0,1 \cdot P(\vec{x})) \rfloor

onde a=1 quando \vec{x} é factível, i.e., quando M - P(\vec{x}) \geq 0, e a=0 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 P(\vec{x}) 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 (\mu,\lambda). 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.

Bookmark and Share
One comment so far, add another