Geri Dön

Meta-heuristics for dynamic point label placement problem

Dinamik nokta etiketi yerleştirme problemi için meta-sezgisel yöntemler

  1. Tez No: 604295
  2. Yazar: ORKUN AKİLE
  3. Danışmanlar: PROF. DR. FATİH ERDOĞAN SEVİLGEN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2019
  8. Dil: İngilizce
  9. Üniversite: Gebze Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 118

Ö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

  1. 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

    İngilizce

    2024

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. ÖZGÜR KABAK

  2. 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

    Türkçe

    2020

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Şehir ve Bölge Planlama Ana Bilim Dalı

    PROF. DR. HÜSEYİN MURAT ÇELİK

  3. Hyper-heuristics for online path planning of unmanned aerial vehicles

    İnsansiz hava araçlarinin çevrimiçi güzergah planlamasi için üst sezgisel yöntemler

    ENGİN AKAR

    Yüksek Lisans

    İngilizce

    İngilizce

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. HALUK RAHMİ TOPCUOĞLU

  4. Gelişmiş model kullanılan fv dizilerde meta sezgisel algoritmalar ile kısmi gölgelenme koşullarında mgnt optimizasyonunun gerçekleştirilmesi

    Implementation of mgnt optimization in partial shading conditions with meta- heuristic algorithms in pv arrays using advanced model

    KEZBAN KOÇ

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    Elektrik ve Elektronik MühendisliğiGazi Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MEHMET DEMİRTAŞ

  5. 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

    Türkçe

    2024

    Elektrik ve Elektronik MühendisliğiYıldız Teknik Üniversitesi

    Elektrik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ALPASLAN DEMİRCİ