-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathskripta.txt
22 lines (13 loc) · 4.55 KB
/
skripta.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Dobar dan, tema našeg projekta bila je da uvidimo kako incijalizacijske funkcije utječu na proces genetskog algoritma.
Uvod
Koristili smo 3 različite inicijalizacijske heuristics od kojih svaka ima 4 dodatne konfiguracije. Svaka konfiguracija opisuje koliki će postotak populacije u jediniki biti nasumično odnosno heuristički generiran.
Tijekom izvršavaja koristio se jedan te isti genetski algoritam. Bitno je imati konzistentne postavke u GA da bi kasnije mogli usporediti kako različite inicijalizacije utječu na rezultate. Što mislimo, s kojom heuristikom ili s kojim omjerom nasumičnosti i heuristics ćemo dobiti najbolje rezultate? Ili s čim ćemo rezultate dobiti brže? Da li inicijalizacija uopće utječe na rezultate? Odgovor slijedi u sljedećim slajdovima.
Podaci kojim smo raspolagali su iz TSPLIB knjižnice, 15 instanci (ne gradova) koje reprezentiraju 2D točku u nekom prostoru. Instance sadrže svoje ime i uz njih broj koji govori broj lokacija unutar instance.
Jedna zanimljivost - pokušali smo koristiti već izračunate udaljenosti, znači napravili smo program koji je izračunao udaljenosti i spremio ih u npy datoteku tako da ne moramo za svake dvije točku ponovno izračunati distance, no ispada da nam je to samo produžilo time_of_execution izvršavanja. Razlog je tome što pristupanje memoriji traje duže nego računanje pomoću procesora svaki put iznova, tu tvrdnju smo potkrijepili jednim znanstvenim radom koji se zove "Accelerating 2-opt and 3-opt Local Search Using GPU in the Travelling Salesman Problem".
Kako smo mi implementirali naš genetski algoritam:
kao prvo, uzmemo prvu (i bolju) polovicu populacije i spremimo ju u polje nazvano elitists koje koristi elitizam. Razlog zašto to radimo je da ne zapnemo u lokalnom optimumu, jer ako bi uzimali elitiste (najbolje jedinke) nakon generiranja djece, bilo bi moguće da neki put koji bi bio gori od sve djece, a koji bi u par izmjena postao optimum, bio odbačen. Tada možda nikada ne bismo došli do optimuma ili bi samo duže trajalo.
Nakon toga generiramo djecu pomoću roditelja, tj na roditelje primjenjujemo križanje i novo križane jedinke dodajemo na end populacija uz roditelje. ograničili smo broj djece zato što smo eksperimentiranje uvidjeli da nakon određenog broja djece nema poboljšanja u rezultatima, a algoritam samo traje duže. Broj djece ovisi o broju lokacija instance - više lokacija, više djece. Prvi roditelj se bira uz šansu od 90%, drugi nasumično, sve dok se ne postigne dovoljan broj djece. Svako generirano dijete ima 10% šanse mutirati, tj. biti podlegnuto 2-opt optimizaciji. Dosjetili smo se da je dovoljno samo djecu optimizirati zato što nakon što dijete bude generirano, na dijetetu se više ne događaju promijene kao što su križanje pa ne bi ni imali smisla raditi 2-opt optimizaciju na već optimiziranim jedinkama.
U sljedećem koraku dio populacije prekopiramo iz polja elitists, a dio iz roulette wheel selectiona. Nakon toga sortiramo populaciju i tako sve u krug. Na kraju svake iteracije pogledamo fitness najbolje jedinke i usporedimo s svevremenskim najboljim fitnessom. Ako se fitness najbolje jedinke ne promijeni nakon puno iteracija, zaustavljamo algoritam zato što pretpostavljamo da nema boljeg rješenja ili da bolje rješenje nije dovoljno bolje od trenutnog da bi trošili time_of_execution na dostizanje istog.
S desne strane je blalblabla
time_of_execution izvršavanja u našem radu je 40 do 80 puta duže nego u radu kojeg smo obrađivali stoga smo morali izrazito veliku pozornost obratiti na skraćivanje times_of_execution izvršavanja. Pokušali smo sa preračunatim udaljenostima, ograničavanje broja djece i iteracija, i zadnje, paraleliziranje eksperimenata raspodjelom zadataka na zasebne jezgre procesora. I dalje nam nije jasno kako je u originalnom radu time_of_execution toliko kratko. Kod proučavanja što troši najviše times_of_execution, shvatili smo da je najveći krivac 2-opt operator. Ovdje je priložena slika koja prikazuje stanja programa u brojevima od 1 do 7 po osi y i time_of_execution u sekundama po osi x. Graf prikazuje jedan poziv 2-opta u instanci Pr144 i traje oko 10 sekundi. Najviše times_of_execution je provedeno u stanjima 3 do 5, a to su stanja u kojima program uspoređuje različite udaljenosti. Zamjene rubova se događaju u stanjima 6 i 7 i jasno je vidljivo da se češće događaju na početku nego pri kraju 2-opta, što je logično zato što nakon svake zamijene algoritam ide isponova od prvog čvora uspoređivati, u slučaju da su se pojavile mogućnosti za optimizacijom koje prije nisu bile vidljive.
Fitness