Genetik algoritma ile maksimum bağımsız küme probleminin çözümü
Solution to the maximum independent set problem with genetic algorithm
Yazar: MEHMET GENCER
Danışman: DOÇ. DR. MURAT ERŞEN BERBERLER
Dokuz Eylül Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Bilimleri Ana Bilim Dalı
Derece: Yüksek Lisans, 2017
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Genetik algoritmalar = Genetic algorithms

Özet:
NP-Zor karmaşıklık sınıfına ait çizge problemlerinden biri olan Maksimum Bağımsız Küme (MIS) ile günlük hayatta sıklıkla görüntü işleme, harita işaretleme, moleküler biyoloji, zaman çizelgesi planlama(scheduling), vs. gibi alanlarda sıklıkla karşılaşılır. Bu çalışmada MIS problemine birden fazla uygun çözümün aynı anda oluşturulup kontrol edilebildiği meta sezgisel yöntemlerden birisi olan genetik algoritmalar yardımıyla kısa sürelerde optimuma yakın kalitede çözümler aranmıştır. Literatürdeki çalışmaların büyük bölümünden farklı olarak genetik algoritmanın başlangıç popülasyonu, rastgele belirlenmeyip çeşitli sezgisel yaklaşımlarla oluşturulmuştur. Farklı sezgisel yaklaşımlar ve bu yaklaşımların optimum değer bulamadığı ters örnekler incelenmiş, sezgisel yaklaşımların çözüme ulaşma olasılığı kaydırma operatörü yardımıyla farklı çözümler üretilerek arttırılmıştır. Burada kaydırma operatörü ile kastedilen yapı tepe derecelerine göre sıralı vektör üzerinde farklı çözümleri elde edebilmek için permütasyon uzayının küçük bir alt kümesinin seçilmesidir. Ayrıca çözüm uzayını etkin bir şekilde tarayabilmek amacıyla problemin boyutuna bağlı olarak büyüklüğü değişen başlangıç popülasyonu kullanılmıştır. Algoritma C dilinde kodlanmış olup farklı ayrıt yoğunluklarına sahip rastgele oluşturulmuş problemler üzerinde hesaplama denemeleri yapılmıştır. Çalışma zamanı ve amaç fonksiyonunun değerleri açısından algoritmanın verimli olduğu gözlenmiştir. Oluşturulan problemler klasik genetik algoritma ile de çözülerek, başarım oranları ve çözüm zamanları incelenmiş, sezgisel yaklaşımın etkisini gözlemlemek amacıyla bir biri ile karşılaştırılmıştır.

Abstract:
NP-hard graph problems that belong to complexity class which is one of Maximum independent set (MIS) in daily life, often with image processing, map marking, Molecular Biology, planning timeline(scheduling), etc in areas such as often is encountered. In this study, with the help of genetic algorithms which is a meta-heuristic solution approach in which more than one suitable solution of artificial intelligence techniques can be created and controlled at the same time, the solutions to the Maximum Independent Set were searched in a short period of time. Unlike most of the studies in the literature, the initial population of the genetic algorithm has not been determined at random and has been created with various heuristic approaches. Different heuristic approaches and their inverse examples in which these approaches are unable to find the optimum value have been examined, a heuristic approach designed in this process to increase the possibility of reaching to the best solution by the shifting operator, creating different solutions is ensured. Here on the scroll meant by sequential vector building operator in order to obtain different solutions according to the degree peak, is to select a small subset of the permutation space. In order to scan the solution space effectively depending on size of the problem varying size of the initial population was used. The algorithm is coded in the C language and the computational experiments on randomly produced problems in terms of runtime and objective function values have been performed and it was observed that the algorithm is efficient. Problems were solved with classical genetic algorithm, performance ratios and solution times were examined and compared with heuristic one to observe the effect of the heuristic approach.