20.500.12556/RUL-95915 Izpolnljivost logičnih funkcij in evolucija Satisfiability of logical functions and evolution V delu smo eksperimentalno ovrednotili rezultate Livnata in soavtorjev (Satisfiability and evolution, FOCS, 2014), ki so pokazali, da populacija naborov slučajne logične funkcije z uporabo šibke selekcije in produktne genetske evolucije konvergira k deležu samih modelov. Preizkuse smo izvajali na družini 28-mestnih logičnih funkcij, v genetskem postopku pa delali s populacijami velikosti 10000. Pri tem smo eksperimentalno potrdili njihove rezultate ter za nekaj dodatnih razredov logičnih funkcij, in ne za zgolj monotone funkcije, pokazali, da genetski postopek k populaciji modelov ravno tako pripelje hitreje kot v splošnem primeru. Eksperimente smo izvedli tudi z uporabo klasičnih reproduktivnih metod genetskih algoritmov, križanja in mutacij. Tudi v tem primeru smo pri slučajno generiranih logičnih funkcijah zaznali konvergenco k populaciji z velikim deležem modelov. Pri nekaterih razredih logičnih funkcij z uporabo križanja in mutacij konvergence k modelom nismo zaznali. This thesis contains experimental evaluation of results of Livnat et al. (Satisfiability and evolution, FOCS, 2014), who have shown that, given a logical function, the population of binary vectors converges to a population of function models, under the assumption of weak selection and product reproduction. Our experiments worked with population size 10000 and genotype length 28. We have experimentally confirmed their theoretical results and for a handful of special logical functions shown that the convergence speed towards the population of models matches the convergence speed of monotone logical functions. We have also run the experiments using crossover and mutations reproduction model. In this case we have for a random logical function experimentally detected convergence towards a population with high ratio of models. However, there are some classes of logical function for which we failed to achieve a similar convergence. genetski algoritem izpolnljivost izjavnih funkcij evolucija šibka selekcija genetic algorithm boolean satisfiability problem evolution weak selection true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2017-09-25 14:14:42 2017-09-25 14:14:45 2022-08-10 07:01:09 0000-00-00 00:00:00 2017 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 19911 Sircelj_Beno_-_Izpolnljivost_logicnih_funkcij_in_evolucija.pdf Sircelj_Beno_-_Izpolnljivost_logicnih_funkcij_in_evolucija.pdf 1 299736D8E135774CCE1FC8AFFF9B6C8D f64221905ecd457e7cb9ff40e5e683263426c8a2201bbcb642458502faae53f1 db626bef-a1b3-11eb-a523-00155dcfd717 20.500.12556/rul/353e07b1-1f31-444a-bd60-fb90864c0748 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=104562 Fakulteta za računalništvo in informatiko 0 0 0