Naslov
Rjesavanje problema N kraljica uz pomoć genetskog algoritma
(N Queen Solving with Genetic Algorithms)

Autori
Huić, Rene

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
11.07

Godina
2008

Stranica
39

Mentor
Jakobović, Domagoj

Ključne riječi
umjetna inteligencija; genetski algoritam; genetski operatori;
(artificial intelligence; genetic algorithm; genetic operators;)

Sažetak
Problem n-kraljica je klasican kombinatoricki problem u podrucju umjetne inteligencije. Pošto problem ima jednostavnu, regularnu strukturu, i inherentne je kompleksnosti, korišten je za stvaranje mjernih programa za algoritme pretraživanja umjetne inteligencije. Problem 4-kraljica je najjednostavniji primjer problema n-kraljica, za koji postoji rješenje. Potrebno je postaviti cetiri kraljica na šahovsku plocu velicine 4x4, tako da se nijedan par kraljica ne može medusobno napasti. To znaci da nijedan par kraljica se ne može nalaziti u istom redu ili stupcu ili na istoj dijagonali. U generalnom problemu se treba postaviti N kraljica na šahovsku plocu velicine NxN, tako da si nijedan par kraljica ne može napadati. Za rješavanje ovog NP problema je potreban algoritam, koji je efikasan u pretrazi i optimizacijskim okolinama, isto tako mora biti sposoban zadovoljiti ogranicenja problema. Ne postoji niti jedan algoritam polinomne složenosti da riješi NP-težak problem, ali postoje neke nedeterministicke metode koje omogucuju rješavanje NP problema u polinomijalnom vremenu. Jedna od takvih metoda je genetski algoritam, no mora se upamtiti da je genetski algoritam samo aproksimativan, tj. ne garantira pronalaženje rješenja zadanog problema. Svrha ovog rada je prouciti ucinkovitost razlicitih operatora genetskog algoritma i skupova parametara na problemu N kraljica. Konkretno, implementirana su dva razlicita prikaza rješenja (preko permutiranog niza i bit matrice), zatim tri razlicita operatora križanja (PMX, OX, Custom) i dva razlicita operatora mutacije (obican, uvjetan) za prikaz rješenja permutiranim nizom, po jedan operator križanja i mutacije za bit matricu, te po dva operatora za elitizam i jedan za selekciju, koja su primijenjena na oba prikaza rješenja.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA