Derece kısıtlı minimum yayılan ağaç problemi için genetik algoritmalar
A genetic algorithm for the degree contrained minimum spannig tree problem
- Tez No: 196399
- Danışmanlar: DOÇ. DR. FULYA ALTIPARMAK
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2005
- Dil: Türkçe
- Üniversite: Gazi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 73
Özet
Derece kısıtlı minimum ağaç (DKMYA) problemi, düğümlere girecek hatsayılarının kısıtlandırıldığı bir graf için minimum yayılan ağacın bulunmasıdır.DKMYA problemi, haberleşme, ulaştırma ve enerji şebekelerinin tasarımıaşamasında ortaya çıkmaktadır. DKMYA probleminin çözümü için geliştirilenyöntemler, eniyi çözümü bulan yöntemler ve yaklaşık çözümü bulan yöntemler(sezgisel) olmak üzere iki grupta toplanmaktadır. Ancak, bu problem NP-zorproblemler sınıfına girdiği için eniyi çözümü bulan yöntemler ile çözüm zamanıproblem boyutuna bağlı olarak üstel artış göstermektedir. Bu nedenle, pratiktekarşılaşılan problemlerin çözümünde yaklaşık çözümü bulan sezgiselyöntemlerden yararlanılmaktadır. Bu tezde, DKMYA problemini çözmek içinGenetik Algoritmalara dayalı bir sezgisel algoritma geliştirilmiştir. Geliştirilenalgoritmanın performansına etki eden faktörlerin (başlangıç yığını, çaprazlamave mutasyon operatörü, yığın genişliği, çaprazlama ve mutasyon oranları) eniyikombinasyonunu belirlemek amacı ile bir deney tasarımı yapılmıştır.Algoritmanın performansı literatürdeki test problemleri üzerindedeğerlendirilmiş ve bu konudaki diğer çalışmalarla karşılaştırılmıştır.Bilim Kodu : 605-02-02Anahtar Kelimeler : Minimum yayılan ağaç, derece kısıtlı minimum yayılanağaç, genetik algoritmalar, sezgisel optimizasyonSayfa Adedi : 61Tez Yöneticisi : Doç.Dr. Fulya Altıparmak
Özet (Çeviri)
Degree Constrained Minimum Spanning Tree (DCMST) on a graph is theproblem of generating a minimum spanning tree with constraints on thenumber of arcs that can be incident to vertices of the graph. DCMST problem isused to design of communication, transportation and energy networks. Methodsto solve DCMST problem are classified in two groups as exact algorithms andheuristics. Since DCMST problems fall into NP-hard class, solution time of allexact algorithms increases exponentially with problem size. For this reason,heuristics are used to solve real application problems. In this thesis, newalgorithm based on Genetic Algorithms have been developed to solve DCMSTproblem. An experimental design had been carried out to determine the bestcombination of factors such as selection mechanism, crossover and mutationoperators, population size, crossover and mutation rates which were effective onthe performance of developed algorithm. Additionally, the effectiveness of thealgorithm was investigated on test problems in literature, and developedalgorithm was compared with different heuristics which were developed forDCMST problem.Science Code : 605-02-02Key Words : Minimum spanning tree, degree constrained minimum spanningtree, genetic algorithms, heuristic optimizationPage Number : 61Adviser : Assoc. Prof. Fulya Altıparmak
Benzer Tezler
- Improvement of the cyclic flexural capacity of RC columns with FRP reinforcement
Lifli polimer donatılar kullanılarak betonarme kolonların çevrimsel yükler altında eğilme kapasitelerinin artırılması
ENGİN CÜNEYT SEYHAN
Doktora
İngilizce
2016
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. ALPER İLKİ
- Lignoselülozik biyokütleden ön arıtımla kombine biyoetanol ve metan üretim proseslerinin geliştirilmesi
Development of Bioethanol and Methane Production Processes Combined with Pretreatment from Lignocellulosic Biomass
ELÇİN KÖKDEMİR ÜNŞAR
Doktora
Türkçe
2019
Çevre MühendisliğiAkdeniz ÜniversitesiÇevre Mühendisliği Ana Bilim Dalı
PROF. DR. NURİYE ALTINAY PERENDECİ
- A cryogenic cmos low dropout regulator design for space applications
Uzay uygulamaları için kriyojenik cmos alçak gerilim düşümlü regülatör tasarımı
HALİL İBRAHİM KAYIHAN
Yüksek Lisans
İngilizce
2019
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MUSTAFA BERKE YELTEN
- Classification of chest X-rays by divergence-based convolutional neural network
Diverjans temelli evrişimsel ağ ile akciğer röntgen görüntülerinin sınıflandırılması
MUHAMMED NUR TALHA KILIÇ
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. TAMER ÖLMEZ
- Airline scheduling to minimize operational costs and variability
Operasyonel maliyetleri ve değişkenliği enazlayan havayolu çizelgeleme
DENİZ ŞİMŞEK
Yüksek Lisans
İngilizce
2021
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. MEHMET SELİM AKTÜRK