crta
Hrvatska znanstvena Sekcija img
bibliografija
3 gif
 Home
 About the project
 FAQ
 Contact
4 gif
Browsing
Basic search
Advanced search
Statistical data
Other bibliographies
Similar projects
 Catalogues and databases

Bibliographic record number: 408178

Disertation

Author: Huić, Rene
Title: Rjesavanje problema N kraljica uz pomoć genetskog algoritma
( N Queen Solving with Genetic Algorithms )
Type: baccalaureus graduate thesis
Faculty: Fakultet elektrotehnike i računarstva
University: Sveučilište u Zagrebu
Location: Zagreb
Date: 11.07.
Year: 2008
Page: 39
Mentor: Jakobović, Domagoj
Keywords: umjetna inteligencija; genetski algoritam; genetski operatori;
( artificial intelligence; genetic algorithm; genetic operators; )
Abstract:
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.
Project / theme: 036-0362980-1921
Original language: hrv
Research fields:
Computer science
Full paper text: 408178.Zavrsni_rad_-_Rene_Huic.pdf (tekst priložen 8. Lip. 2009. u 17:23 sati)
URL: http://www.zemris.fer.hr/~yeti/studenti/
Contrib. to CROSBI by: yeti@fer.hr (yeti@fer.hr), 8. Lip. 2009. u 17:23 sati



Print version   za tiskati


upomoc
foot_4