Problemi optimizirani s GA
Problem Sudokua
Sudoku je u modernom obliku započeo 1783. godine kada je Leonhard Euler sastavio latinski kvadrat dimenzija 9x9.
Prateći razvoj tehnologije i Interneta, Sudoku zagonetke pojavile su se u brojnim web i mobilnim aplikacijama i danas ih rješavaju milijuni ljudi diljem svijeta.
Sudoku je vrsta zagonetke u kojoj je potrebno brojevima popuniti prazne ćelije unutar mreže držeći se zadanih pravila.
Mreže mogu biti različitih veličina, ovisno o vrsti Sudoku zagonetke, ali standardni i pri tom najzastupljeniji oblik jest 9x9 Sudoku. U tom slučaju, u polja se unose brojevi od 1 do 9.
Osnovno pravilo u klasičnoj Sudoku zagonetki jest da se pri popunjavanju polja brojevima, niti jedan broj ne smije ponavljati više od jednom u jednom retku, stupcu i odjeljku, koji je u ovom slučaju, veličine 3x3.
Na početku igre zadani su početni brojevi pomoću kojih se popunjava ostatak polja. Neke zanimljive jednakosti koje proizlaze iz ovih pravila je to da će suma znamenki u svakom retku, stupcu i odjeljku biti jednake i to:
Rješenje Sudokua genetskim algoritmom
U ovom je radu iskorišten genetski algoritam kako bi se pronašlo jedinstveno rješenje određenog sudoku problema. Kromosom predstavlja jedna permutacija brojeva 1-9 (red u sudoku).Tako se jedinka sastoji od 9 kromosoma. Genetski algoritam koristi će odabir tri najuspješnije jedinke generacije koji će onda služiti kao baza za sljedeću generaciju i tako će se ponavljati dok ne dođemo do rješenja problema (Dok jednoj jedinci ne bude fitness evaluiran kao maksimalni mogući).