20.500.12556/RUL-171656 Evolucija populacij rešitev nekaterih težkih problemov na grafih Evolution of solution populations of some hard graph problems V delu eksperimentalno preverimo, ali populacija genetskih algoritmov z uporabo šibke selekcije konvergira v populacijo, ki je sestavljena izključno iz modelov. Pri tem se osredotočimo na problem minimalnega pokritja, minimalne dominantne množice in 3-barvanja. S tem nadgradimo delo Livnata in soavtorjev, ki so to lastnost dokazali za problem izpolnjivosti, in Širclja, ki je problem izpolnjivosti eksperimentalno obravnaval. V delu predstavimo izbiro vrednosti za izvedbo preizkusov za posamezen problem. Preizkuse smo nato izvedli z različnimi vrednostmi parametra šibke selekcije in velikosti populacije. Za reprodukcijo smo uporabili produktno reprodukcijo in rekombinacijo. Obe vrsti reprodukcije smo obravnavali tudi z dodatkom mutacije. Pri minimalnem pokritju in minimalni dominantni množici smo dokazali, da ob zadostno veliki vrednosti zmnožka velikosti populacije in parametra šibke selekcije dosežemo konvergenco v populacijo modelov, ki pa kvalitativno niso tako dobri kot optimalne rešitve. Pri problemu 3-barvanja smo konvergenco v modelno populacijo dosegli le v omejenem številu primerov. In this work, we experimentally verify if a population of genetic algorithms employing weak selection converges to a population composed exclusively of models. We investigate the minimum vertex cover problem, the minimum dominating set problem, and the 3-coloring problem. In doing so, we extend the work of Livnat et al., who established this property for the satisfiability problem, and Šircelj, who examined the satisfiability problem through experimental analysis. We detail the selection of parameter values used for the experimental evaluation of each problem. The experiments were conducted using varying values of the weak selection parameter and population size. We used two types of reproduction; product reproduction and recombination. We also used both methods in combination with mutation. For the minimum vertex cover and minimum dominating set problems, we demonstrate that, given a sufficiently large product of population size and the weak selection parameter, the population converges to a population of models. However, these models are qualitatively inferior to the optimal solutions. In the case of the 3-coloring problem, convergence to a model population was observed only in a limited number of instances. genetski algoritmi evolucija NP-težki problemi grafovski problemi konvergenca modelna populacija genetic algorithms evolution NP-hard problems graph problems convergence model population true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2025-08-29 12:25:01 2025-08-29 12:25:06 2025-09-13 03:49:26 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37790 247770115 Savnik_Jure_-_Evolucija_populacij_resitev_nekaterih_tezkih_problemov_na_grafih.pdf Savnik_Jure_-_Evolucija_populacij_resitev_nekaterih_tezkih_problemov_na_grafih.pdf 1 3F836C880154F44449547A0CC767E990 4ed9d7f62580b9abc30a88ba0a6516e0cb440358147a95ea43fbda39c8a7c90d 4d1f31a1-84c2-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=215037 Fakulteta za računalništvo in informatiko 0 0 0