Sažetak

U ovom radu je opisana primena genetskih algoritama (GA) za rešavanje nekoliko problema kombinatorne optimizacije: prost lokacijski problem, problem dizajniranja mreže neograničenog kapaciteta i problem izbora indeksa. Dati NP-kompletni problemi ne samo što nalaze veliku primenu u praktičnim oblastima kao što su proizvodnja, transport, planiranje zaliha i trgovina, već i u specifičnim oblastima vezanim za računare, odnosno, programiranje kao što su telekomunikacije, lokalne računarske mreže, globalne računarske mreže, Internet i baze podataka.

Sekvencijalna GA implementacija sadrži fleksibilno realizovane razne varijante genetskih operatora selekcije, ukrštanja i mutacije. Osim njih dato je i nekoliko funkcija prilagođenosti, razni kriterijumi završetka rada GA i različite politike zamene generacija. Sve zajedničke GA promenljive su grupisane u strukturu, pa je laka dopuna funkcijama koje zavise od prirode samog problema, što obezbeđuje relativno jednostavno rešavanje novih problema.

Opisana aplikacija je zatim paralelizovana i implementirana na mreži računara. Za paralelizaciju je korišćen MPI standard (Message Passing Interface), koji postaje prihvaćeni standard za veliki broj višeprocesorskih arhitektura. Za razvoj, testiranje i izvršavanje programa je korišćena mreža PC kompatibilnih radnih stanica. Implementiran je distribuirani model paralelnog GA, gde svaki proces izvršava lokalni genetski algoritam na svojoj sopstvenoj potpopulaciji, uz povremenu razmenu najboljih jedinki, između susednih procesa.

Za dalje poboljšanje performansi sekvencijalne i paralelne implementacije razvijena je posebna tehnika, nazvana keširanje GA. Ona ne utiče na rezultate koje dobijamo, već samo smanjuje vreme izvršavanja. Keširanje GA je opšta tehnika, primenljiva na širokom spektru problema, a relativno dobre rezultate daje baš u primeni na NP-kompletne probleme.

Rezultati izvršavanja na datim problemima pokazuju da je sekvencijalna GA implementacija postigla rezultate koji su u svim slučajevima uporedivi sa heuristikama i ostalim metodama poznatim u literaturi, a u nekim slučajevima i bolji. Paralelizacija i implementacija korišćenjem MPI standarda je dalje poboljšala performanse GA, i učinila programski kod lako prenosivim na razne tipove paralelnih računara.

Ključne reči: genetski algoritmi, paralelni algoritmi, NP-kompletni problemi, prost lokacijski problem, problem dizajna mreže neograničenog kapaciteta, problem selekcije indeksa, keširanje GA.

Povratak na glavnu stranu

Poslednja promena: 08.03. 2000.