Title Poboljšavanje djelotvornosti paralelnih genetskih algoritama Author Marin Golub Mentor Leo Budin (mentor)Committee member Slobodan Ribarić (član povjerenstva)Committee member Leo Budin (član povjerenstva)Committee member Darko Fischer (član povjerenstva)Committee member Vedran Mornar (član povjerenstva)Committee member Bojana Dalbelo-Bašić (član povjerenstva)Granter University of Zagreb Defense date and country 2001-01-17, Croatia Scientific / art field, TECHNICAL SCIENCES Universal decimal classificationUDC ) 004 - Computer science and technology. Computing. Data processing Abstract Jedan od osnovnih zadataka poboljanja djelotvornosti genetskih algoritama je skraćenje vremena izvođenja, jer je poznato da su genetski algoritmi vremenski zahtjevne optimizacijske metode. Paralelizacijom genetskog algoritma moe se značajno skratiti trajanje optimiranja na vieprocesorskom računalu. Postojeći paralelni modeli genetskih algoritama pokazali su se nepogodnima za izvođenje na vieprocesorskim računalima s operacijskim sustavom koji podrava viedretvenost. 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 potronji procesorskog vremena zauzima komunikacija između gospodara i slugu. U predloenom 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 viedretvenost i zajednički radni spremnik izbjegnuti su sloeni 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 moe na jednostavan način izvoditi paralelno koristeći viedretvenost. 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 vie dretvi moe 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 vieprocesorskom 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.
Abstract (english) 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.
Keywords
Paralelni genetski algoritam
sinkronizacija
vjerojatnost selekcije
broj iteracija
propusnost
Keywords (english)
Parallel genetic algorithm
synchronization
selection probability
number of iterations
throughput
Language croatian URN:NBN urn:nbn:hr:168:961925 Study programme Title: Computer Science Type of resource Text File origin Born digital Access conditions Closed access Terms of use Created on 2019-04-15 07:31:19
