Exploração de paralelismo massivo em algoritmos evolucionários

Abstract

Esta dissertação está centrada na paralelização massiva da biblioteca Java Evolutionary Cornputation Library), JECoLi, que se foca no desenvolvimento de meta-heurísticas de otimização(e.g. Algoritmos Evolucionários (AEs)) na linguagem Java. Os AEs são um paradigma da Computação Evolucionária (CE) utilizados para resolver problemas complexos através de um método iterativo que evolui um conjunto de soluções (população) tendo em conta os princípios da teoria de evolução por seleção natural apresentada por Charles Darwin. Estes algoritmos estão divididos em duas categorias, AEs não estruturados e AEs estruturados. Os AEs não estruturados são caracterizados por uma população centralizada onde existe apenas um conjunto de soluções ao qual é aplicado o processo evolutivo. Por outro lado, os AEs estruturados contêm várias populações onde os processos evolutivos são conduzidos de forma independente, embora existindo troca de informação. Os algoritmos de ambas as categorias podem ser paralelizados de diferentes maneiras. Nesta dissertação, foram implementadas quatro versões paralelas da plataforma JECoLi de forma o menos invasiva possível, tendo em conta modelos paralelos já formulados: um modelo de paralelismo global; um modelo de ilhas em ambiente de memória partilhada; um modelo de ilhas em ambiente de memória distribuída; e um modelo híbrido. Estas implementações paralelas foram executadas no cluster Services and Advanced Research Cornputing with HTC/HPC clusters (SeARCH) utilizando o máximo de recursos computacionais possíveis de modo a realizar uma posterior análise dos resultados obtidos. Foram utilizados dois casos de estudo reais para validar as implementações paralelas, um problema de otimização de um bioprocesso de fermentação fed-batch e outro de otimização dos pesos de um protocolo de encaminhamento (OSP F). Cada uma das implementações paralelas foi testada nos dois casos de estudo, aplicando o máximo de paralelismo possível tendo em conta as limitações de cada caso de estudo, dos modelos paralelos e dos recursos disponíveis. Com estes testes concluí-se uma boa escalabilidade destes algoritmos, onde se destacam as implementações relativas ao modelo de ilhas em memória distribuída e ao modelo híbrido. Contudo, algumas configurações que originam maiores ganhos foram descartadas pois não produzem valores de aptidão aceitáveis.

This dissertation is centered in the massive parallelization of the Java Evolutionary Computation Library, JECoLi, which focuses on the development of meta-heuristics optimizations (e.g. Evolutionary Algorithms (EAs)) in the Java programming language. The EAs are a paradigm of Evolutionary Computation (EC) used to solve complex problems through an iterative method that evolves a set of solutions (population) taking into account the principles of the theory of evolution by natural selection by Charles Darwin. These algorithms are divided into two categories, unstructured EAs and structured EAs. The unstructured AEs are characterized by a centralized population where there is only one set of solutions for which the iterative method is applied. On the other hand, structured AEs contain several independent populations where evolutionary processes are applied, although there exchange information. The algorithms of both categories can be parallelized in different ways. ln this dissertation, it was implemented four parallel versions of the platform JECoLi in a less invasive way, taking into account parallel models already formulated: a global parallelism model; a island model in shared memory environment; a island mo del in distributed memory environment; and a hybrid model. These parallel implementations were executed in the cluster SeARCH using the maximum computing resources in order to perform a further analysis of the results obtained. Two case studies were used to validate the parallel implementations, a bioprocess optirnization problem of fed-batch fermentation and other weights optimization problem of a routing protocol (OSPF). Each of the parallel implementations were tested in the two case studies, applying the maximum parallelism taking into account the limitations of each case studies, parallel models and available resources. With these tests can be concluded a good scalability of these algorithms, which highlights the implementations on the island model in distributed memory and hybrid model. However, some settings that give greater gains were discarded because they produce no acceptable fitness values.