The end!

Já algum que estava para colocar aqui este post.
A partir deste momento declaro encerrado este blog até algum motivo especial o faça. A apresentação teve lugar no passado dia 14 e terminei com a classificação de 16 valores. Ficou fora das minhas expectativas, porque contava ter pelo menos 18 para conseguir atingir média de 13. Sendo assim, devo ter ficado muito perco dos 12,5, mas não o suficiente para permitir o arredondamento para mais uma unidade.
A apresentação propriamente não correu pelo melhor, visto que ficou muito longa e passou do tempo predefinido, que consistia em 20 minutos. Entrei a todo o gás na apresentação e não consegui concluír toda a apresentação dentro do tempo pré-estabelecido, de modo que quando fui advertido que tinha excedido o tempo, fui obrigado a expôr tudo o resto de seguida.
Durante a discussão, não fui capaz de responder às questões colocadas, de modo que tudo se reflecte na classificação final obtida.
Acabou a minha vida de estudante universitário, vou iniciar uma nova fase na minha vida...

Data de apresentação e discussão

Quem estiver interessado a estar presente na apresentação do meu projecto de fim de curso de Informática - Ramo Tecnológico, na Universidade do Algarve, esta vai ter lugar no próximo dia 14 de Dezembro, 4ª Feira, às 10h00 da manhã na sala 2.21 do Complexo Pedagógico do Campus de Gambelas. O tema do meu projecto intitula-se "Processamento distribuído do algoritmo Genético compacto através de Web Services" e foi orientado pelo prof. Fernando Lobo. Para além do orientador, irão integrar o júri de discussão os prof. Patrício Serendero, como director de curso e o prof. José Valente de Oliveira, na qualidade de arguente.

Já terminou !

Na realidade ainda não! Mas estive toda a semana de volta do relatório porque era obrigatório de acordo com o regulamento de estágios e projectos proceder à entrega de toda e qualquer documentação necessário para a discussão do projecto até ao dia de ontem. O relatório foi uma chatice, como sempre, mas tinha de ser! Ao todo fiquei quase duas semanas de volta do dito cujo, escrevendo, escrevendo, até me fartar! Mas não podia-me fartar, por que tinha de ser! Após muitas horas de desgaste, litros de café, e noites mal dormidas, lá consegui pôr a versão definitiva nas mãos do meu orientador, sob a forma de três cópias para cada um dos membros do júri que vão assistir à apresentação oral do projecto, a combinar em princípio para um dia entre 12 e 15 de Dezembro, sendo este o último dia possível, porque é a data final para a notar ser lançada nos serviços académicos.
Após cerca de cinco meses de esforço contínuo em volta deste tema, mesmo assim muita coisa ficou por concretizar, como a ideia original de distribuir o algoritmo através da Internet através de um cliente que fosse atractivo tipo um applet de java, que era o mais provável, ou um screensaver como a ideia original do seti@home. Isto devido à altura tardia em que iniciei o projecto, depois ter andado durante um ano inteiro com seis disciplinas mais chatas, que se não as tivesse à perna, teria investido muito mais tempo naquilo que realmente interessava. O relatório foi todo escrito usando LaTeX, uma linguagem de processamento gráfico para a elaboração de documentos para publicações científicas. Foi fixe aprender LaTeX, mas depois de o ter experimentado, confesso que não morri de amores por ele, apesar de ser verdade que cumpre aquilo que promete. Algumas coisas chateam, como por exemplo páginas apenas com uma linha, fazer quadros com pseudo-código é impossível porque não faço ideia como modificar o tipo de letra predifinido para código, entre muitas outras coisas que só muito mais tempo de "mexeriquice" com o LaTex me iria dar.
Fazer um applet ou um screensaver teria sido uma coisa gira, mas assim não sucedeu. Em vez de usar a Internet, lá tive que me desenrascar com as threads de Java para ter um efeito semelhante ao de ter multiplos computadores ligados a colaborar no algoritmo!
Mas o que foi foi, e já não se pode fazer nada para o alterar. Deixo aqui uma versão do relatório para quem estiver interessado em consultá-la.
Agora as boas notícias, abri uma conta no Sourceforge, o conhecido sistema de apoio a projectos OpenSource, e agora sou mais um! Vou colocar lá o código todo, e se tiver tempo no futuro, prometo continuar aquilo que eu não consegui concretizar nos cinco meses findos. O endereço da nova casa do WebServCGA é

webservcga.sf.net

.
Provisoriamete, também, mas não deve ficar lá muito tempo vou disponbilizar na minha área pessoal da universidade a mesma informação.

Últimos resultados

Aqui vão os últimos resultados disponíveis do meu projecto. Os gráficos foram elaborados com o GnuPlot e estão aproximadamente na mesma escala que os gráficos do artigo sobre a paralelização. Os meus resultados parecem confirmar em tudo os gráficos do artigo. A silhueta do traçado é em quase tudo semelhante, mesmo com um número menor de execuções (+-10 no meu projecto, 30 no artigo).
Aqui vão os gráficos dos resultados, conjuntamente com os gráficos do artigo original, para uma comparação directa:

NÚMEROS DE CÁLCULOS DE FITNESS POR THREAD

Resultados do projecto

Resultados do artigo

COMUNICAÇÕES POR THREAD

Resultados do projecto

Resultados do artigo

Eles aí estão, quentinhos...

Acabei de pôr à prova o meu programa, e para isso durante todo este fim-de-semana usei o computador Gazela no laboratório de projectos da Universidade, mais o computador Girafa. O Gazela, uma vez que tem um processador rápido (AMD Athlon 1800+) com 768 MB de RAM era o candidato óbvio para correr o cliente, devido a ficar encarregue de fazer "todo o trabalho" de desenvolvimentos dos indivíduos, a sua avaliação e competição. O servidor, ao contrário do que é usual, era somente passivo nesta questão, uma vez que o seu trabalho era simplesmente receber as diferenças do último vector população e actualizá-lo, verificando se entretanto não teria convergido. Com apenas 192 MB de RAM, também não era preciso muito, apesar do servidor de JSP Tomcat ser um bocado pesado, já que, sendo uma aplicação concebida em JAVA, que é um devorador de recursos em qualquer máquina.
Mas o que importa é que, depois de uma série de contratempos e de ter tentado pôr o meu trabalho a usar a Internet "a sério", com o servidor no meu servidor/gateway Linux caseiro a fazer de servidor, e uma máquina qualquer na Universidade a fazer de cliente, podia ter uma aproximação mais próxima da realidade, se é que alguma vez o meu trabalho venha a ser usado na Internet, tenho esperanças de que sim :).
Enfim, vamos mas ao que interessa, aqui estão os gráficos das experiências que fiz durante o fim de semana. Segui quase à risca as mesmas condições do artigo Referência fundamental para o projecto : Lobo F. G., Lima C. F. & Mártires H. (2004). An Architecture for Massive Parallelization of the Compact Genetic Algorithm. (PDF) na página 8, e experimentei combinações de valores de m (máximo de execuções da função de fitness entre cada comunicação com o servidor) no intervalo {8,80,800,8000,80000} com números de threads (equivalente a processadores) no intervalo {1,2,4,8,16,32,64}. O artigo tem gráficos que vão até 1028, mas como a partir de 64, os gastos de RAM dispendida para a criação de threads são enormes, decidi deixá-los para outra ocasião. Os resultados apresentados resultam da média calculada da execução de 6 experiências para todas as combinações possíveis aos pares entre os valores dos dois intervalos. Excepto para m=8, em que a execução do cliente é extremamente demorada para poder obter um número de experiências em tempo útil. Para ter uma ideia do que tou a falar, a execução do cliente com m=8 mesmo com 64 threads precisou de 7550 segundos (um pouco mais de 2 horas) para se poder completar. Para este caso, apenas procedi (por enquanto) apenas a uma 1 execução para cada valor de threads possíveis no intervalo indicado.
Aqui estão os gráficos, elaborados com a ajuda do Excel, precedido do respectivo gráfico do artigo supracitado, cujos resultados pretende reproduzir:

NÚMEROS DE CÁLCULOS DE FITNESS POR THREAD

COMUNICAÇÕES POR THREAD

Não pretendo ficar por aqui, pretendo pelo menos completar a metade direita do gráfico que ficou de fora assinalada pelo quadrado colorido, se tiver a gana, mas também o hardware para poder fazer isso. Fiquem a aguardar as notícias dos próximos capítulos :)
P.S.:Estes não são os gráficos definitivos que pretendo colocar no relatório.

Agora já bate tudo certo (ou quase...)

Depois de, na semana passada, os resultados experimentais do cGA que eu implementei não parecerem estar muito famosos, eis que agora, não sei bem como, tudo está conforme (aproximadamente) o que seria de esperar. Também é verdade que agora os resultados que apresento como gráficos no Excel foram feitos usando a média aritmética dos valores obtidos em 30 execuções do algoritmo, usando uma vez mais, como teste, a aplicação de usar uma função de trap's múltiplos concatenados.
O único senão é no total de cálculo da função de fitness, os resultados excedem ligeiramente os resultados apresentados no artigo citado. Mas, mesmo assim, de resto, todos os resultados são bastante satisfatórios. Os melhores são os que registam o número de building blocks no fim do algoritmo, o troço do gráfico segue quase a par os dos gráficos do artigo. Para além disso, de salientar que desta vez experimentar também com populações de 100 e 200, para ver como o algoritmo progride para pequenas alterações nesta gama de valores. E de facto, nota-se, quer tanto para s=4 e s=8 (s é a pressão de selecção), uma pequena subida quando se passa de popsize=8 para popsize=100 (popsize é o tamanho da população). O que não seria possível de verificar se não tivesse experimentado com esses valores.
Não consigo perceber a razão para os resultados agora estarem com esta qualidade, a única alteração que fiz no código foi na parte para seleccionar o melhor indivíduo, e estava relacionado com uma variável (que guarda o melhor fitness até o momento dentro de um loop que percorre todos os indivíduos gerados dentro de um array) em vez de ser inicializada com zero com estava dantes, passou a ser feita com menos infinito (ou melhor, o valor de Double.NEGATIVE_INFINITY ), e para além disso, estive a documentar o código todo com javadoc's e não me parece que fossem os comentários que fizessem com que o compilador percebesse também melhor o código :)
Aqui ficam os resultados obtidos:

Implementação não muito famosa

Estive a experimentar a implementar a função de multiplos traps concatenados para diferentes valores da pressão de selecção. Os resultados ficaram aquém dos que se encontram no artigo do cGA. Os gráficos abaixo foram gerados com o auxílio do GNUPlot. Ambos os gráficos indicam o número de vezes que o fitness foi calculado até atingir a convergência, em função de vários valores para o tamanho da população (experimentei 8,500,1000,1500,2000,2500 e 3000 como vinha no artigo). Em ambos os casos o número de vezes ultrapassa largamente aquele que se encontra no artigo. Estava também para mostrar os resultados para s=2, mas a minha implementação do cGA nem sequer termina dentro de tempo útil, não foi possível determinar um gráfico.

TOTAL DE CÁLCULOS DE FITNESS

S=4



S=8



Elaborei também gráficos para a quantidade de "building blocks" completos que aparecem na solução final. E os resultados também estão muito longe de satisfazer.

NÚMERO DE "BUILDING BLOCKS" CORRECTOS OBTIDOS

s=4



s=8