Nalazite se na CroRIS probnoj okolini. Ovdje evidentirani podaci neće biti pohranjeni u Informacijskom sustavu znanosti RH. Ako je ovo greška, CroRIS produkcijskoj okolini moguće je pristupi putem poveznice www.croris.hr
izvor podataka: crosbi !

Rjesavanje problema N kraljica uz pomoć genetskog algoritma (CROSBI ID 353959)

Ocjenski rad | sveučilišni preddiplomski završni rad

Huić, Rene Rjesavanje problema N kraljica uz pomoć genetskog algoritma / Jakobović, Domagoj (mentor); Zagreb, Fakultet elektrotehnike i računarstva, . 2008

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

Povezanost rada

Računarstvo

Poveznice