Meta-heuristics for dynamic point label placement problem

Abstract

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