Naslov
Distribuirani evolucijski algoritmi za problem usmjeravanja vozila
(Distributed Evolutionary Algorithms for Vehicle Routing Problem)

Autori
Puljić, Krunoslav

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
Prirodoslovno-matematički fakultet - Matematički odsjek

Mjesto
Zagreb

Datum
26.11

Godina
2009

Stranica
223

Mentor
Manger, Robert

Ključne riječi
distribuirani evolucijski algoritmi ; problem usmjeravanja vozila
(distributed evolutionary algorithm ; vehicle routing problem)

Sažetak
U radu je predloženo nekoliko novih distribuiranih evolucijskih algoritama za rješavanje problema usmjeravanja vozila. Predloženi algoritmi se razlikuju od dosadašnjih jer su distribuirani, asinkorni, ne-hibridni, te heterogeni na razini operatora i na razini evaluacije. Svi predloženi algoritmi detaljno su eksperimentalno evaluirani, te je proučen utjecaj raznih operatora i parametara ne učinak predloženih distribuiranih evolucijskih algoritama. Rezultati su pokazali da predloženi distribuirani evolucijski algoritmi primjenjeni na problem usmjeravanja vozila daju bolje rezultate od odgovarajućih serijskih evolucijskih algoritama. Posebno se to odnosi na predloženi heterogeni distribuirani evolucijski algoritam na razini operatora, koji je detaljnije obrađen i evaluairan, te je pokazao nadlinearno slabo sekvencijalno ubrzanje, što nije tako česta pojava. Također, iako rezultati predloženog hetereogenog distribuiranog evolucijskog algoritma zaostaju za rezultatima ostalih metaheuristika (kao što je npr. Tabu pretraživanje), te za rezultatima raznih hibridnih serijskih evolucijskih algoritama, postignuto prosječno odstupanje koje iznosi manje od 2% za razne primjerke problema, te je postignuto u svega 30-tak sekundi, predstavlja sasvim zadovoljavajuće rezulate. U ovom radu analizirano je i djelovanje različitih politika migracije na učinak distribuiranih evolucijskih algoritama. Definiranje politike migracije uključuje definiranje različitih parametara i metoda migracije, te je predložena originalna politika migracije koja se pokazala prilično uspješnom. Navedena politika je asinkrona, česta, te reagira čim se pojavi novo najbolje rješenje. Za razliku od uobičajeno potrebne relativno dugačke izoliranosti podpopulacija tijekom čak 1.000.000 generacija, a prilikom rješavanja raznih problema, za problem usmjeravanja vozila predložena je i pokazala se jako dobrom vrlo česta migracija (otprilike svakih 50 generacija). U predloženim evolucijskim algoritmima isprobano je i nekoliko novih operatora križenja, poznatih iz rješevanja problema trgovačakog putnika, a koja se još nisu primjenjivala na problem usmjeravanja vozila. Zanimljivo je da su se čak tri nova križanja (križanje naizmjeničnim bridovima - AEX, heurističko pohlepno križanje - HGreX i heurističko vjerojatnosno križanje - HProX) pokazala znatno boljima od do sada najčešće korištenog redoslijednog križanja (OX). Prvo poglavlje opisuje problem usmjeravanja vozila, njegove varijante i matematičke modele problema. Na kraju poglavlja pokazana je NP-težina problema. Drugo poglavlje posvećeno je poznatim biblitekama sa konkretnim primjercima problema, a koje služe za evaluaciju algoritama za rješavanje problema usmjeravanja vozila. Treće poglavlje detaljno opisuje evolucijske algoritme i operatore koji se često u njima koriste. U četvrtom poglavlju razmatraju se paralelni evolucijski algoritmi, s naglaskom na distribuirane algoritme. Posebno je opisan operator migracije, te su predloženi novi distribuirani evolucijski algoritmi za problem usmjeravanja vozila. U petom poglavlju su navedeni rezultati eksperimenata sa predloženim distribuiranim evolucijskim algoritmima, te je eksperimentalno utvrđeno slabo sekvencijalno ubrzanje.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA