Key words: parallel genetic algorithm, synchronization, selection probability, number of iterations, throughput
Kratki sadržaj:
Jedan od osnovnih zadataka poboljšanja djelotvornosti genetskih algoritama je skraćenje vremena izvođenja, jer je poznato da su genetski algoritmi vremenski zahtjevne optimizacijske metode. Paralelizacijom genetskog algoritma može se značajno skratiti trajanje optimiranja na višeprocesorskom računalu. Postojeći paralelni modeli genetskih algoritama pokazali su se nepogodnima za izvođenje na višeprocesorskim računalima s operacijskim sustavom koji podržava višedretvenost. Najprimjereniji je tradicionalni model globalnih paralelnih genetskih algoritama (GPGA). Međutim, tradicionalni GPGA obavlja paralelno samo evaluaciju, dok se svi genetski operatori obavljaju sekvencijski. Povrh toga, značajan udio u potrošnji procesorskog vremena zauzima komunikacija između gospodara i slugu.
U predloženom modelu GPGA otklonjeni su spomenuti nedostaci preraspodjelom posla između gospodara i slugu. U tradicionalnom modelu GPGA sluge samo evaluiraju jedinke, dok gospodar obavlja cijelu evolucijski proces. U novom modelu GPGA gospodar samo inicijalizira populaciju, dok sluge obavljaju cijeli evolucijski proces i evaluaciju. Osim toga, koristeći višedretvenost i zajednički radni spremnik izbjegnuti su složeni komunikacijski mehanizmi. Uporabljena je 3-turnirska eliminacijska selekcija bez duplikata jer ona omogućuje izvođenje selekcije i reprodukcije u istom koraku, a cijeli postupak se može na jednostavan način izvoditi paralelno koristeći višedretvenost. Za razliku od selekcije s duplikatima, selekcija bez duplikata ima inherentno ugrađeni elitizam i sprječava generiranje novih duplikata.
Ostvarene su dvije verzije novog modela GPGA: sinkrona i asinkrona. U sinkronom GPGA dretve ne trebaju čekati da se oslobodi već zauzeta jedinka, nego jednostavno odabiru neku drugu sve dok ta slučajno odabrana jedinka ne bude slobodna. Genetski algoritam s turnirskom selekcijom slučajno odabire jedinke koje će sudjelovati u selekciji i reprodukciji. Koristeći to dobro svojstvo genetskog algoritma s turnirskom selekcijom izbjegava se čekanje dretve na oslobođenje zauzetog zajedničkog podatka.
U asinkronom GPGA više dretvi može istodobno pristupati istim zajedničkim podacima. Kada se to dogodi samo će jedna dretva obavljati korisno posao, dok će ostale dretve obavljati tu iteraciju uzalud. Izračunata je vjerojatnost da dretva obavlja posao uzalud na višeprocesorskom sustavu s proizvoljnim brojem dretvi. Naime, ako je poznata ta vjerojatnost, moguće je odrediti broj dodatnih iteracija koje asinkroni GPGA treba obaviti da bi imao ista svojstva kao i sekvencijski GA.
Novi model GPGA je ispitan na 38-dimenzijskom aproksimacijskom problemu. Eksperimentalno je određen optimalni skup parametara te propusnost, odnosno ubrzanje za asinkroni i sinkroni GPGA.
Summary:
It is a well known fact that genetic algorithms require a lot of computation power. Reducing the computational time is thus one of the basic tasks when improving efficiency of the genetic algorithms. With parallelization we can get a significant decrease in computation time on a multiprocessor system. Existing parallel models of genetic algorithms have proved not to be suitable for executing on multiprocessor computers with operating systems which support multithreading. The most appropriate model is the traditional global parallel genetic algorithm (GPGA). However, the traditional GPGA performs only evolution in parallel, while all genetic operators execute sequentially. Moreover, communication between the master and the slaves takes considerable amount of CPU time.
The disadvantages mentioned above are eliminated in the proposed model of GPGA by rearranging the jobs between the master and the slaves. In the traditional model of GPGA slaves only evaluate individuals, while the master performs the whole evolution process. In the new model of GPGA the master only initializes the population, while slaves perform the whole evaluation process including evaluation. Beside that, the complex communication mechanisms are avoided by using multithreading and shared memory. The 3-tournament elimination selection without duplicates is used, because it allows to perform selection and reproduction in the same iteration and the whole process can be easily parallelised by using multithreading. Selection without duplicates has elitism inherently implemented and it disallows generating new duplicates.
Two versions of the parallel model are realized: synchronous and asynchronous GPGA. In the synchronous GPGA the threads will randomly select another individual if the chosen one is already taken by some other thread. Genetic algorithm with tournament selection randomly chooses individuals for selection and reproduction. So, using that inherent characteristic of the genetic algorithm with tournament selection, the waiting will be avoided in most cases.
In the asynchronous GPGA several threads can change shared data at the same time. The probability that a thread will work in vain, while several threads change the same individual, is calculated. If we want to achieve the same results as sequential GA, the asynchronous GPGA must perform some additional iterations. The number of additional iterations can be predicted and calculated as it was shown in this work.
The new model of GPGA is tested on a 38-dimension approximation problem. The optimal parameter set and speedup for asynchronous and synchronous GPGA was experimentally determined.