Poboljšavanje djelotvornosti paralelnih genetskih algoritama : doktorska disertacija - Golub, Marin (M. Golub ; Fakultet elektrotehnike i računarstva, 2001)
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. Ključne riječi: paralelni genetski algoritam, sinkronizacija, vjerojatnost selekcije, broj iteracija, propusnost