Zadatak za četvrtu lab. vježbu

Za četvrtu vježbu na izboru je implementacija genetskog algoritma ili simuliranog kaljenja.

1. Genetski algoritam

Načiniti programsku implementaciju genetskog algoritma koja će tražiti optimum zadanog optimizacijskog problema. Potrebno je omogućiti da se bez prevođenja programa mogu definirati:

q broj članova populacije,

q vjerojatnost mutacije (i križanja, ako algoritam upotrebljava tu vjerojatnost),

q broj iteracija postupka.

Kao uvjet zaustavljanja mora se omogućiti izvođenje za zadani broj iteracija dok su ostali uvjeti proizvoljni. Poželjno je pratiti vrijednost najboljeg člana populacije i ispisivati ga na ekran tokom postupka.

Preporučena inačica GA obuhvaća 3-turnirski odabir, jednostavnu mutaciju, jednoliko križanje, binarni prikaz rješenja, a dana je sljedećim pseudokodom:

stvori populaciju;

evaluiraj populaciju; // svaka jedinka ima pridruženu dobrotu

ponavljaj

odaberi slucajno 3 jedinke;

eliminiraj najlosiju;

nova_jedinka=krizanje(preostale dvije);

eliminirana=nova_jedinka;

obavi mutaciju na novoj jedinki uz vjerojatnost p_m;

evaluiraj novu jedinku;

dok(nije zadovoljen uvjet zaustavljanja)

Genetski algoritam primijeniti na pronalaženje koeficijenata aproksimacijske funkcije. Problem je definiran kako slijedi: zadan je skup točaka koji odgovara vrijednostima neke veličine u određenim diskretnim vremenskim trenucima, npr. niz {(0,0), (1,3.2), (2,4.7), …} određuje vrijednosti u trenucima t=0, t=1, itd. Za tako zadani vremenski niz potrebno je odrediti funkciju koja ga najbolje aproksimira. Aproksimacijska funkcija se gradi po uzoru na Fourierovu transformaciju kao:

Genetski algoritam treba odrediti vrijednosti koeficijenata a_i tako da se postigne što bolja aproksimacija. Jedan kromosom je niz svih koeficijenata uporabljenih u aproksimacijskoj funkciji. Ako je vremenski niz zadan kao:

T = {(x₁, y₁), (x₂, y₂), …, (x_P, y_P)}

tada se ocjena dobrote pojedinog rješenja (jednog mogućeg skupa koeficijenata) dobiva kao suma kvadrata odstupanja aproksimacijske funkcije od stvarne vrijednosti u zadanim vremenskim točkama:

Za konkretnu implementaciju aproksimacijska funkcija neka ima 5 sinusnih članova:

Granice varijabli neka su:

a preciznost svakog koeficijenta neka bude 3 decimale.

Zadani vremenski niz koji treba aproksimirati može se učitati u obliku matrice. Primjer je dan u nastavku:

1 1

2 3

3 6

4 5

5 10

6 10

7 8

8 6

9 5

10 1

2. Simulirano kaljenje

Načiniti programsku implementaciju simuliranog kaljenja koja će rješavati problem trgovačkog putnika. Algoritam postupka dan je na predavanjima. Postupak treba uključivati barem dva načina dobivanja susjednog rješenja, od kojih se jedan može odabrati prilikom pokretanja ili prevođenja programa (osim dva predložena na predavanjima, možete i sami probati definirati neke načine).

Test problem možete naći na adresi http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/kroA200.tsp.gz. Najbolje dobiveno rješenje dosada je 29368 (duljina puta). Druge zanimljive TSP probleme i rješenja možete naći na adresama http://www.math.princeton.edu/tsp/index.html i http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ .