Naslov
Primjena genetskog algoritma u problemima transporta
(Application of genetic algorithm to solve transportation problems)

Autori
Zulić, Amer

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, magistarski rad

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
30.06

Godina
1998

Stranica
75

Mentor
Kalpić, Damir

Ključne riječi
genetski algoritam; transport; problem trgovačkog putnika
(genetic algorithm; transport; travelling salesman problem)

Sažetak
U uvodu se navodi da su za potrebe rješavanja određenih problema matematičkog programiranja preuzete iz biološkog procesa evolucije neke karakteristike selekcije, nasljeđivanja i mutacije. Tretirani problemi najčešće imaju mnogo mogućih rješenja pa se otvara mogućnost optimiranja, tj. izbora onakvog rješenja koje je po nekom kriteriju najbolje. Za neke od problema poznato je da su teški i to je upravo područje primjene genetskog algoritma kao heurističkog postupka. U drugom poglavlju opisuje se detaljno genetski algoritam. Definiraju se pojmovi populacije, kromosoma i gena. Opisani su pojedini koraci algoritma, uz variranje postupaka selekcije i oblikovanja populacije. Opisano je križanje, razlozi za uvođenje mutacije i mjera konvergencije. Dana su i određena, trenutačno poznata, teorijska razmatranja. U trećem poglavlju obrađena je programska oprema zasnovana na genetskom algoritmu. Po načelima objektno-orijentiranog programiranja opisane su klase, funkcije, tijek programa i parametri o kojima ovisi ponašanje algoritma. Četvro poglavlje je kratka usporedba s ostalim algoritmima optimiranja. Peto se poglavlje bavi odabranim primjerom primjene genetskog algoritma. Radi se o rješavanju problema trgovačkog putnika. Postupak je ilustriran numeričkim primjerom i prikazom rezultata programa. Navode se moguće primjene u upravljanju strojevima kao slučaju problema trgovačkog putnika. Spominje se pomoć u komponiranju kao reprezentant drugačijeg tipa problema. Šesto poglavlje opisuje realni problem transporta te primjenjuje genetski algoritam kao optimizacijski postupak unutar funkcija informacijskog sustava hipotetskog poduzeća sa središnjim skladištem, prodavaonicama i vlastitim voznim parkom. U postupku se aproksimira realnost uvođenjem konačne nosivosti kamiona, volumena i težine robe, rokova isporuke, potrošnje goriva. Izrađen je relacijski model podataka kojim su obuhvaćeni entiteti i atributi relevantni za hipotetsko poduzeće. Genetski algoritam ugrađen je u postupak traženja lokalnog optimuma za izbor kretanja pojedinog kamiona. Zatim se razmjenjuju narudžbenice među kamionima sa ciljem približavanja globalnom optimumu. Cijeli postupak i obrada dokumenata obuhvaćeni su izrađenom programksom opremom. Može se očekivati da bi u slučaju rješavanja realnog problema značajan dio izrađene programske opreme bio izravno primjenjiv. Na kraju se spekulira s mogućnosti izrade ekspertnog sustava koji bi dinamički odabirao parametre optimiranja genetskim algoritmom. U zaključku se navodi da genetski algoritmi daju dobro rješenje u prihvatljivom vremenu prilikom rješavanja teških problema. Uspješnost genetskog algoritma raste ako se osigura dinamičko mijenjanje parametara tako da se postigne kompromis između brzine konvergencije i uklanjanja opasnosti od završetka u lokalnom optimumu. Na kraju je dan osvrt na obrađeni problem transporta.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA