Hibridizacija genetskega algoritma za reševanje problema vozliščnega pokritja

RANDL, KLEMEN (author), Brodnik, Andrej (mentor)

V 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.

• Language: Slovenian
• Keywords: vozliščno pokritje, genetski algoritem, hibridizacija, lokalna optimizacija
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2017
• PID: 20.500.12556/RUL-91168
• Publication date in RUL: 23.03.2017

Secondary language

• Language: English
• Title: Hybridisation of Genetic Algorithm for Vertex Cover Problem

Abstract

In this bachelor’s thesis, we discuss minimum vertex cover problem, which is one of the most complex problems in graph theory. It is a typical example of a NP-hard optimization problem. Finding an optimal solution in polynomial time is highly improbable, but there are many ways of finding an approximate solution to the problem. One of the options presented here is a use of a genetic algorithm, which turns out to be quite effective, since it is able to find a reasonably good solution in an acceptable amount of time. In certain cases, the quality of solution is highly improved with the introduction of hybridization to the genetic algorithm, but the running time of the algorithm increases as well. The result depends on the section of the algorithm to which the hybridization is applied to, and how frequently it is used. As it turns out, the best solution is obtained with the periodically applied hybridization. However, the running time of the algorithm is the longest in this case. If hybridization is applied only in the middle or at the end of the run, the solution found is only slightly inferior, but the running time is much shorter. This type of hybridization is suitable for the cases in which the running time is a bigger concern than the quality of solution. If the hybridization is used more frequently, the quality of solution increases, but so does the running time. The same happens when the number of generations (algorithm's termination condition) is increased. However, in the cases where the quality of solution is a priority, it is more sensible to increase the frequency of the hybridization than to increase the number of generations because that way the algorithm finds better solutions in shorter time.

• Keywords: vertex cover, genetic algorithm, hybridisation, local optimisation