Parallel Genetic Algorithms in the Cloud
Abstract
Genetic Algorithms (GAs) are a metaheuristic search technique belonging to the
class of Evolutionary Algorithms (EAs). They have been proven to be effective
in addressing several problems in many fields but also suffer from scalability
issues that may not let them find a valid application for real world problems.
Thus, the aim of providing highly scalable GA-based solutions, together with
the reduced costs of parallel architectures, motivate the research on Parallel
Genetic Algorithms (PGAs).
Cloud computing may be a valid option for parallelisation, since there
is no need of owning the physical hardware, which can be purchased from
cloud providers, for the desired time, quantity and quality. There are different
employable cloud technologies and approaches for this purpose, but they all
introduce communication overhead. Thus, one might wonder if, and possibly
when, specific approaches, environments and models show better performance
than sequential versions in terms of execution time and resource usage.
This thesis investigates if and when GAs can scale in the cloud using
specific approaches. Firstly, Hadoop MapReduce is exploited designing and
developing an open source framework, i.e., elephant56, that reduces the effort in
developing and speed up GAs using three parallel models. The performance of
the framework is then evaluated through an empirical study. Secondly, software
containers and message queues are employed to develop, deploy and execute
PGAs in the cloud and the devised system is evaluated with an empirical
study on a commercial cloud provider. Finally, cloud technologies are also
explored for the parallelisation of other EAs, designing and developing cCube, a
collaborative microservices architecture for machine learning problems. [edited by Author] I Genetic Algorithms (GAs) sono una metaeuristica di ricerca appartenenti
alla classe degli Evolutionary Algorithms (EAs). Si sono dimostrati efficaci nel
risolvere tanti problemi in svariati campi. Tuttavia, le difficoltà nello scalare
spesso evitano che i GAs possano trovare una collocazione efficace per la
risoluzione di problemi del mondo reale. Quindi, l’obiettivo di fornire soluzioni
basate altamente scalabili, assieme alla riduzione dei costi di architetture
parallele, motivano la ricerca sui Parallel Genetic Algorithms (PGAs).
Il cloud computing potrebbe essere una valida opzione per la parallelizzazione, dato che non c’è necessità di possedere hardware fisico che può, invece,
essere acquistato dai cloud provider, per il tempo desiderato, quantità e qualità. Esistono differenti tecnologie e approcci cloud impiegabili a tal proposito
ma, tutti, introducono overhead di computazione. Quindi, ci si può chiedere
se, e possibilmente quando, approcci specifici, ambienti e modelli mostrino
migliori performance rispetto alle versioni sequenziali, in termini di tempo di
esecuzione e uso di risorse.
Questa tesi indaga se, e quando, i GAs possono scalare nel cloud utilizzando approcci specifici. Prima di tutto, Hadoop MapReduce è sfruttato per
modellare e sviluppare un framework open source, i.e., elephant56, che riduce
l’effort nello sviluppo e velocizza i GAs usando tre diversi modelli paralleli. Le
performance del framework sono poi valutate attraverso uno studio empirico.
Successivamente, i software container e le message queue sono impiegati per
sviluppare, distribuire e eseguire PGAs e il sistema ideato valutato, attraverso
uno studio empirico, su un cloud provider commerciale. Infine, le tecnologie
cloud sono esplorate per la parallelizzazione di altri EAs, ideando e sviluppando cCube, un’architettura a microservizi collaborativa per risolvere problemi
di machine learning. [a cura dell'Autore]
URI
http://hdl.handle.net/10556/2577http://dx.doi.org/10.14273/unisa-976
http://dx.doi.org/10.14273/unisa-976