Minimum spanning tree construction using meta-heuristics
Meta-heuristics kullanarak minimum ayar tasarımı inşaatı
- Tez No: 484399
- Danışmanlar: DOÇ. DR. BAHRİYE AKAY
- 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: İngilizce
- Üniversite: Erciyes Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 61
Özet
Minimum Yayılan Ağaçlar (MST) minimum toplam kesit maliyetli ağacı oluşturan bir bağlı, ağırlıklı, güdümsüz grafiğin alt kümesidir. Elektrik, iletişim, ağ tasarımı, yol tasarımı, görüntü işleme ve kümelemedeki birçok sorun MST olarak tanımlanabilir. Prim Algoritması her tepe noktasını içeren bir MST bulan ve MST'deki kesitlerin toplam ağırlığını en aza indirgeyen açgözlü bir algoritmadır. Sürüzekası teknikleri optimizasyon sorunlarını çözmek için etkili metotlardır ve birleşimsel sorunları çözmek için etkin bir şekilde kullanılmıştır. Bu çalışmada, Karınca Koloni Algoritması (ACO) ve Ateşböceği Algoritması (FA) olmak üzere iki Sürü Zekası Algoritması MST maliyetleri bakımından incelenmiştir. Kontrol katsayılarının algoritmaların performansı üzerindeki etkisi incelenmiş ve FA, ACO ve Prim Algoritmaları birbiriyle karşılaştırılmıştır. Sonuçlara göre, ACO Algoritması en az maliyetli MST'yi inşa etmek için iyi bir üstsezgisel algoritmaydı ve Prim Algoritmasına bir alternative olarak, özellikle de yoğun grafiklerden seyrek altçizgeler üretmek için kullanılabilir.
Özet (Çeviri)
Minimum spanning trees (MST) is a subset of a connected weighted undirected graph which forms a tree with minimum total edge cost. Many problems in electrical, communication, network design, road design, image processing, clustering can be defined as a MST. Prim's algorithm is a greedy algorithm which finds a MST that includes every vertex and minimizes the total weight of the edges in the MST. Swarm intelligence techniques are powerful methods to solve optimization problems and have been used efficiently to solve combinatorial problems. In this study, two Swarm intelligence algorithms: Ant colony optimization (ACO) and Firefly algorithm (FA) were investigated in terms of MST costs. The effect of control parameters on the performance of the algorithms was examined and FA, ACO and Prim's algorithms were compared to each other. According to the results, ACO algorithm was a good meta-heuristic algorithm to construct a minimum-cost MST and can be used as an alternative to Prim's algorithm especially to produce sparse sub graphs from dense graphs.
Benzer Tezler
- Ağ optimizasyonu modelleri: Python ile uygulamalar
Network optimization models: Applications with python
BAGUL OVLYAKULYYEVA
Yüksek Lisans
Türkçe
2023
İstatistikOndokuz Mayıs Üniversitesiİstatistik Ana Bilim Dalı
DOÇ. DR. TALAT ŞENEL
- Proje değerlendirmede şebeke analizi ve bir bilgisayar uygulaması
Network analysis in project evaluation and a computer program
ZİYA ŞAHBAZOĞLU
- Mst-based cluster analysis: A New algorithm for determining inconsistent edges
Mst tabanlı küme analizi: Tutarsız kenarları belirlemek için yeni bir algoritma
FADİ ŞAAR
Doktora
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAnkara Yıldırım Beyazıt ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. AHMET ERCAN TOPCU
- Öğrenci işleri otomasyonu
Design and implementation of a student service application an personal computers
HAKAN KAZAZ
Yüksek Lisans
Türkçe
1993
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. FÜSUN TUNALI
- Uydu verileri ile İstanbul Boğazı ve Haliç'de su kirliliğinin makro düzeyde belirlenmesi
Intrepretation at macro level as pollution of water resources of remotely sensed data of Bosphorus and golden horn estuary by an unsupervised and supervised classification method
H.GONCA COŞKUN