Meta-heuristics for dynamic point label placement problem
Dinamik nokta etiketi yerleştirme problemi için meta-sezgisel yöntemler
- Tez No: 604295
- Danışmanlar: PROF. DR. FATİH ERDOĞAN SEVİLGEN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Dinamik optimizasyon, Genetik algoritmalar, Sezgisel algoritmalar, Dynamic optimization, Genetic algorithms, Heuristic algorithms
- Yıl: 2019
- Dil: İngilizce
- Üniversite: Gebze Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Nokta etiketi yerleştirme, haritalar ve coğrafi bilgi sistemleri gibi grafiksel araçlar ve sistemler için temel ve yaygın bir problemdir. Problem noktasal nesnelere ait etiketlerin, aralarındaki çakışmanın asgariye indirileceği, netliğin artırılacağı şekilde yerleştirilmesini gerektirir. Problemin en yararlı tipleri NP-Zor karmaşıklıktadır. Bu sebeple sezgisel eniyileme yöntemleri iyi ve verimli sonuçlar elde etmek için tercih edilmektedir. Statik nokta etiketi yerleştirme için birçok algoritma önerilmiş olsa da, noktaların hareket ettiği dinamik ortamlar için mevcut çalışmalar çok sınırlıdır. Bu tez çalışmasında statik nokta etiketi yerleştirmenin çözümüne katkıda bulunmanın yanısıra dinamik ortamlar için de sezgisel eniyileme yöntemleri geliştirmek amaçlanmıştır. Hırslı algoritma ve yerel arama aşamalarından oluşan bir dizi hızlı sezgisel algoritma statik yöntemler olarak sunulmuştur. Bu algoritmalar ile statik problemler için çözüm kalitesi ve hesaplama süresi açısından iyi sonuçlara ulaşıldığı gibi algoritmaların dinamik ortamlarda kullanılmaya uygun olduğu görülmüştür. Dinamik problemler için ayrıca, Rastgele Göç yöntemi Maskeleme ile Genetik Algoritma (GA) yöntemine adapte edilerek yeni bir dinamik algoritma geliştirilmiştir. Geliştirilen algoritmaların deneysel olarak incelenebilmesi için noktaların farklı değişim hızlarında hareket ettiği benzetim ortamları betimlenmiştir. Standart Maskeleme ile GA ve dinamik parametrelerin çözüm kalitesi ilişkisini incelemek için oluşturulan dinamik ortamda test edilmiştir. Dinamik etiket yerleştirme probleminde dinamik GA yönteminin statik GA'ya karşı avantajı gösterilmiştir. Son olarak, geliştirilen en iyi hızlı sezgisel algoritma dinamik ortamlarda test edilmiş ve performansı dinamik GA ile kıyaslanmıştır. Yavaş değişen ortamlarda dinamik GA'nın daha iyi performans gösterdiği, diğerlerinde hızlı sezgisel yöntemin daha iyi performans gösterdiği gözlemlenmiştir. Bu iki sınıftaki çözüm yöntemlerinin problemin değişme özelliği dikkate alınarak kullanılması önerilmektedir.
Özet (Çeviri)
Point label placement is a basic and common problem in graphical instruments and systems such as maps and geographical information systems. The problem requires labels belong to point objects to be placed to minimize conflict among them and promote clearness. Many useful variants of the problem are in NP-Hard complexity. Thus, heuristic optimization methods are adopted to provide good and efficient solutions. Although several methods are proposed for static point label placement, very limited studies exist regarding dynamic environments. In this thesis, besides contributing to solve static problem, it is mainly aimed to provide heuristic optimization methods for dynamic environments where points are moving. A series of fast heuristics comprised of greedy construction and local search are presented as static methods. Having achieved good performance results for static problems, they are employed for dynamic problems to obtain efficient solutions. Furthermore, a dynamic Genetic Algorithm (GA) is proposed by incorporating Random Immigrants into GA with Masking. To evaluate the performance of proposed algorithms, a simulation environment where points are moving with various change rates is developed. The dynamic GA is tested on the simulation environment to analyze the effect of both standard and dynamic GA parameters on solution quality. The experiments demonstrate performance advantage of the dynamic GA over static GA for dynamic problems. Finally, the best fast heuristic method is tested on dynamic environments and its performance is compared with the dynamic GA. Choice between these two class of methods should be made by considering change characteristic of the problem.
Benzer Tezler
- Crew recovery optimization through disruption analysis and deep learning driven column generation
Aksaklık analizi ve derin öğrenme tabanlı sütun oluşturma ile ekip kurtarma optimizasyonu
AHMET HEREKOĞLU
Doktora
İngilizce
2024
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. ÖZGÜR KABAK
- Doğadan esinlenmiş hibrit bir optimizasyon algoritmasının yol planlama problemine uygulamasının istatistiksel sonuçları
Statistical results of applying a nature-inspired hybrid optimization algorithm to the path planning problem
MERVE GENÇ
Yüksek Lisans
Türkçe
2026
İstatistikArtvin Çoruh Üniversitesiİstatistik Ana Bilim Dalı
DOÇ. DR. KADRİ DOĞAN
- Afet lojistiğinde araç rotalama problemi ve geliştirilen iki aşamalı bir optimizasyon yöntemi ile uygulama
Vehicle routing problem and a case study with evolved a two level optimization solution in humanitarian logistics
MUSTAFA BAL
Yüksek Lisans
Türkçe
2020
Şehircilik ve Bölge Planlamaİstanbul Teknik ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
PROF. DR. HÜSEYİN MURAT ÇELİK
- Fotovoltaik güneş paneli maksimum güç noktası takibinde kullanılan sezgisel bozkurt algoritmasını iyileştirmek için yeni bir yöntemin geliştirilmesi ve uygulanması
A new method development to improve the heuristic gray wolf algorithm used in photovoltaic solar panel maximum power point tracking and its implementation
HASAN GÜNDOĞDU
Yüksek Lisans
Türkçe
2024
Elektrik ve Elektronik MühendisliğiYıldız Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALPASLAN DEMİRCİ
- Konvansiyonel ve mikro şebeke içeren güç sistemlerinde dinamik ekonomik yük ve emisyon dağıtımının sezgisel yöntemlerle analizi
Dynamic economic emission dispatch in power systems with and without microgrids by using heuristic algorithms
ESRA AYDIN
Yüksek Lisans
Türkçe
2022
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. BELGİN TÜRKAY