Naslov
Poboljšavanje djelotvornosti paralelnih genetskih algoritama
(Improving the Efficiency of Parallel Genetic Algorithms)

Autori
Golub, Marin

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
17.01

Godina
2001

Stranica
149

Mentor
Budin, Leo

Ključne riječi
paralelni genetski algoritam; sinkronizacija; vjerojatnost selekcije; broj iteracija; propusnost
(parallel genetic algorithm; synchronization; selection probability; number of iterations; throughput)

Sažetak
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.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA