Genetik algoritma ile maksimum bağımsız küme probleminin çözümü
Solution to the maximum independent set problem with genetic algorithm
- Tez No: 491149
- Danışmanlar: DOÇ. DR. MURAT ERŞEN BERBERLER
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: Türkçe
- Üniversite: Dokuz Eylül Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 93
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Binary mean-variance mapping optimization algorithm
İkili ortalama-varyans eşleme optimizasyonu algoritması
ALI HAKEM JABOR ALSAEEDI
Yüksek Lisans
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYıldız Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
Assist. Prof. Dr. OĞUZ ALTUN
- Multi-objective subcontractor selection model based on performance measurement framework in international construction projects
Uluslararası inşaat projelerinde performans ölçüm çerçevesine dayalı çok amaçlı alt yüklenici seçim modeli
BEFRİN NEVAL BİNGÖL
Doktora
İngilizce
2017
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÜL POLAT TATAR
- Kapasitör uyarmalı asenkron generatörün optimal kapasitesinin hibrit genetik algoritma ile belirlenmesi
Determination of the optimal capacitance for the capacitor excited induction generator using the hybrid genetic algorithm
FEVZİ ARSLAN
Yüksek Lisans
Türkçe
2010
Elektrik ve Elektronik MühendisliğiDüzce ÜniversitesiElektrik Eğitimi Ana Bilim Dalı
DOÇ. DR. NEDİM TUTKUN
- Uçak itkisinin fadec sistemi için performans modellerinin oluşturulması ve optimizasyonu
Thrust performance modelling and optimization for aircraft fadec system
ECE YURDUSEVİMLİ METİN
Doktora
Türkçe
2021
Havacılık MühendisliğiEskişehir Teknik ÜniversitesiHavacılık Elektrik ve Elektroniği Ana Bilim Dalı
PROF. DR. ÖNDER TURAN
- Kriging interpolasyonu kullanan vekil modeller ile gemi kıç formunun viskoz direnç yönünden optimizasyonu
Aft form optimization of ships for minimum viscous resistance by using kriging metamodeling technique
HAYRİYE PEHLİVAN SOLAK
Doktora
Türkçe
2020
Gemi Mühendisliğiİstanbul Teknik ÜniversitesiGemi İnşaatı ve Gemi Makineleri Mühendisliği Ana Bilim Dalı
PROF. DR. ÖMER GÖREN