Sensör yerleştirme probleminin genetik algoritma ve parçacık sürü optimizasyonu ile çözümü
Genetic algorithm and particle swarm optimization solution for sensor placement problem
Yazar: ALİ TOZAN
Danışman: YRD. DOÇ. DR. FATİH ERDOĞAN SEVİLGEN
Gebze Yüksek Teknoloji Enstitüsü / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2007
Konu: Mühendislik Bilimleri = Engineering Sciences
Dizin: Genetik algoritmalar = Genetic algorithms ; Optimizasyon problemi = Optimization problem ; Sensörler = Sensors

Özet:
Askeri ve sivil alanda, çesitli sensörlerin, bir arazi üzerine, o araziyi en etkin sekildegözetlemesi için yerlestirilmesi oldukça önemlidir. Sensör yerlestirme probleminde bir araziüzerine, belirli sayıda sensörün araziyi maksimum kapsaması için konuslandırılabileceği enuygun noktaların bulunması hedeflenmektedir. Yapılan çalısmada arazi modellenirken sayısalyükseklik haritalarıyla gerçek yükseklik verileri kullanılmıstır. Sensör modeli olarak çokyönlü bir sensör modeli gelistirilmis ve görülebilirlik hesaplamalarıyla arazinin sensörlertarafından ne oranda kapsandığı hesaplanmıstır.En uygun sensör pozisyonlarının bulunması için literatürde optimizasyon problemleriiçin sıklıkla kullanılan Genetik Algoritma (GA) ve Parçacık Sürü Optimizasyonu (PSO)yöntemleri probleme uyarlanmıstır. Ayrıca bu yöntemleri daha da gelistirmek amacıyla,?ndirgenmis Değisken Komsuluk Arama Metodu, GA ve PSO yöntemlerinin iterasyonlarındauygulanmıstır. Problem algoritmalara uyarlanırken, çözüm kümesinin gösteriminde kullanılansensör pozisyonları için reel sayılar kullanılmıstır. Haritalarda bulunmayan yükselti bilgileridoğrusal ara değerleme ile hesaplanmıs ve problemin çözümü için reel sayı yaklasımıgetirilmistir. Problemin GA ve PSO uyarlamalarında reel sayı yaklasımının getirilmesiliteratürdeki diğer arastırmalara göre farklılık göstermektedir.Yapılan deneylerde elde edilen sonuçlara göre GA yönteminin PSO yöntemine göredaha iyi sonuçlar verdiği gözlemlenmistir. Ayrıca yerel arama yönteminin farklı arazi çesitleriiçin PSO yöntemini iyilestirdiği fakat GA yöntemini iyilestirmediği görülmektedir.

Abstract:
Surveillance of a terrain with various sensors and finding the most suitable positions ofsensors is so important in military and public domains. ?Given n observers and a terrain,where should we place them in order to maximize the overall coverage of terrain?? is themain question of the sensor placement problem. In this study, the terrain is modelled withdigital elevation maps. Sensors are modelled as an omnidirectional obsever and the visibilityof terrain is computed using line of sight algorithms.In order to find the most efficient sensor positions, Genetic Agorithm (GA) and ParticleSwarm Optimization (PSO) methods are applied to the problem. Also Reduced VariableNeighborhood Search is applied as a local search routine in GA and PSO iterations. Inproblem representation, real valued numbers are used to represent sensor positions. Moreover,lineer interpolation method is applied for missing elvation information in digital maps. Maindifference of GA and PSO aplication for sensor placement problem from literature is applyingreal valued sensor position representation on the problem.In experiments, GA is outperformed PSO method according to the results. Also localsearch improves PSO method for different kinds of terrains but does not improve GA.