<?xml version="1.0"?>
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:dc="http://purl.org/dc/elements/1.1/"><rdf:Description rdf:about="https://repozitorij.uni-lj.si/IzpisGradiva.php?id=171656"><dc:title>Evolucija populacij rešitev nekaterih težkih problemov na grafih</dc:title><dc:creator>Savnik,	Jure	(Avtor)
	</dc:creator><dc:creator>Fijavž,	Gašper	(Mentor)
	</dc:creator><dc:subject>genetski algoritmi</dc:subject><dc:subject>evolucija</dc:subject><dc:subject>NP-težki problemi</dc:subject><dc:subject>grafovski problemi</dc:subject><dc:subject>konvergenca</dc:subject><dc:subject>modelna populacija</dc:subject><dc:description>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.</dc:description><dc:date>2025</dc:date><dc:date>2025-08-29 12:25:01</dc:date><dc:type>Magistrsko delo/naloga</dc:type><dc:identifier>171656</dc:identifier><dc:language>sl</dc:language></rdf:Description></rdf:RDF>