Rjesavanje problema N kraljica uz pomoć genetskog algoritma (CROSBI ID 353959)
Ocjenski rad | sveučilišni preddiplomski završni rad
Podaci o odgovornosti
Huić, Rene
Jakobović, Domagoj
hrvatski
Rjesavanje problema N kraljica uz pomoć genetskog algoritma
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.
umjetna inteligencija; genetski algoritam; genetski operatori;
nije evidentirano
engleski
N Queen Solving with Genetic Algorithms
nije evidentirano
artificial intelligence; genetic algorithm; genetic operators;
nije evidentirano
Podaci o izdanju
39
11.07.2008.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Fakultet elektrotehnike i računarstva
Zagreb