Hibridizacija genetskega algoritma za reševanje problema vozliščnega pokritjaRANDL, KLEMEN (Avtor) Brodnik, Andrej (Mentor) vozliščno pokritjegenetski algoritemhibridizacijalokalna optimizacijaV tej diplomski nalogi je obravnavan problem najmanjšega vozliščnega pokritja, ki je eden izmed zahtevnejših optimizacijskih problemov iz teorije grafov, spada namreč v kategorijo NP-težkih problemov. Verjetnost, da je mogoče optimalno rešitev zanj najti v polinomskem času, je zelo majhna, obstaja pa več načinov za iskanje približka optimalne rešitve. Tukaj je predstavljen način reševanja tega problema z genetskim algoritmom, ki se izkaže za precej učinkovitega, saj je z njegovo uporabo mogoče najti zelo dober približek optimalne rešitve v sprejemljivem času. Z uvedbo hibridizacije v genetski algoritem se kakovost rešitve v določenih primerih močno izboljša, vendar se poveča tudi čas izvajanja algoritma, odvisno od tega, kako pogosto in na katerih delih algoritma se hibridizacija izvede. Izkaže se, da najboljšo rešitev algoritem najde, če je hibridizacija enakomerno razporejena, vendar za to porabi tudi največ časa. V primeru hibridizacije samo na sredini ali samo na koncu izvajanja algoritma je najdena rešitev za malenkost slabša, vendar algoritem do nje pride v veliko krajšem času. V primerih, ko je čas izvajanja algoritma pomemben, je takšna hibridizacija torej bolj smiselna od enakomerno porazdeljene. S povečevanjem odstotka hibridizacije se kakovost rešitve sicer izboljšuje, ampak se hitro povečuje tudi porabljeni čas. Podobno se zgodi tudi v primeru povečevanja števila generacij (ustavitveni pogoj algoritma), vendar se izkaže, da je v primerih, ko je potrebna boljša rešitev, bolj smiselno povečati odstotek hibridizacije kot pa število generacij, saj algoritem tako najde boljšo rešitev v krajšem času.20172017-03-23 14:25:02Diplomsko delo/naloga91168VisID: 18230sl