Application of genetic algorithms in artificial intelligence

Cilj rada je opisati princip rada genetskih algoritama te njihovu primjenu na konkretnom primjeru problema. U radu su opisana dva genetska algoritma: algoritam usamljenog mutanta te algoritam čvrstog stanja. U algoritmima su se koristili različiti genetski operatori selekcije, mutacije i križanja kromosoma (koji predstavljaju rješenje problema)u populaciji. Osim genetskih algoritama, korišten je i algoritam sirove snage te je uspoređeno vrijeme izvođenja oba algoritma. Problem rješen u ovom radu je problem ruksaka, kombinatorni problem smještanja određenog broja predmeta u “ruksak” fiksnog kapaciteta. Ima čestu primjenu u kombinatorici i računarstvu te je logičan izbor problema za rješavanje algoritmima koji tek odnedavno počinju dobijati na popularnosti. Nakon implementacije problema programskim jezikom C#, testiranja su pokazala da genetski algoritmi daju “dovoljno dobro” rješenje u vrlo prihvatljivom vremenu te su odličan odabir algoritama za one probleme kojima je važnija brzina izvođenja, a ne odabir baš onog najboljeg mogućeg rješenja.The aim of the thesis is to describe the principle of genetic algorithms and their application in a concrete example of a problem. Two genetic algorithms are described: lonely mutant algorithm and steady state algorithm.In the algorithms, different examples of genetic operators (selection, mutation and crossover) were used to operate over chrommosomes (representation of solution of the problem) in population. In addition to genetic algorithms, a brute force algorithm was used, and the time of running both algorithms was compared. Problem solved in this thesis was knapsack problem, combinatorial problem of placing a certain number of items in a “knapsack” of fixed capacity. It has frequent use in combinatorics an computer science and it is logical choice of problem to solve with algorithms that have recently began to gain popularity. After implementation of problem with C# programming language, tests have shown that genetic algorithms provide a “good enough” solution in very acceptable time and are excellent choice of algorithms for problems where the speed is more important than finding exactly the best solution