Tepe Örtüsü Problemi için Yeni Bir Hibrid Genetik Algoritma

Abstract

The minimum vertex cover problem belongs to the class of NP-compl ete graph theoretical problems. This paper presents a hybrid genetic algorithm to solve minimum ver tex cover problem. In this paper, it has been shown that when local optimization technique is added t o genetic algorithm to form hybrid genetic algorithm, it gives more quality solution than simple genet ic algorithm. Also, anew mutation operator has been developed especially for minimum vertex cover problem, whichc onverges faster to the global optimal solution. The new hybrid gentic algorith m has been compared with the previous works. The experimental results have shown that the propose d algorithm can yield quality solutions in reasonable times.

Özet

Minimum tepe örtüsü problemi, NP-Tam sınıfına ait teorik bir graf problemidir. Bu makale minimum tepe örtüsü problemini çözmek için yeni bir hibrid algoritma sunar. Bu makalede genetik algoritmaya yerel optimizasyon tekniğini eklenince basit genetik algoritmadan daha kaliteli sonuçlar elde edildiği gösterilmiştir. Ayrıca özellikle minimum tepe örtüsü problemi içinn, genel en iyi sonuca daha hızlı yakınsayan yeni bir mutasyon operatörü geliştirilmiştir. Yeni hibrid algoritma önceki çalışmalarla karşılaştırılmıştır. Hesaplama sonuçları algoritmanın makul sürelerde kaliteli sonuçlar verebileceğini göstermektedir