Metaheuristic methods for the obstacle neutralization problem


Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2016

Tezin Dili: İngilizce

Öğrenci: RAMAZAN ALGIN

Danışman: ALİ FUAT ALKAYA

Özet:

ETKİSİZLEŞTİRME PROBLEMİ İÇİN METASEZGİSEL ÇÖZÜM METOTLARININ GELİŞTİRİLMESİ VE UYGULANMASI Bu tez çalışmasında bir askeri deniz senaryosu olarak gerçek hayatta karşılığı olan ve gerçek bir problemden ilham alınarak tanımlanmış Etkisizleştirme Problemi (EP) üzerinde teorik ve deneysel çalışmalar yapılarak yeni çözüm yöntemleri geliştirilmiştir. EP’de bir ajan bulunmakta ve problemin amacı bu ajanın belirli bir başlangıç noktasından hedef noktasına, disk şeklinde engellerin (mayın) bulunduğu bir ortamda, en hızlı ve en güvenli şekilde ulaşmasını sağlamaktır. Ajan belli bir masraf karşılığında verilen etkisizleştirme sayısını aşmamak koşuluyla engelleri etkisizleştirme kabiliyetine sahiptir.Bu tez çalışmasında EP’yi çözmek için çeşitli metasezgilseller kullanılmıştır. Karınca sistemi algoritması, karınca kolonisi algoritması, göç eden kuşlar algoritması, genetik algoritma ve benzetimli tavlama metasezgiselleri EP için geliştirilip uygulanmıştır. Metasezgisellerin yanında EP, ZIMPL dili kullanılarak modellenmiştir ve bu model SCIP çözücüsü kullanılarak kesin çözüm elde edilmiştir. Yapılan deneyler hem gerçek hem de rassal örnekler üzerinde gerçekleştirilmiştir. Geliştirilen metasezgisellerin bulduğu çözümler SCIP çözücüsünün sonuçlarıyla küçük ve orta boyutlu problem örnekleri üzerinde kıyaslamalı bir şekilde verilmiştir. Yapılan çalışmalar sonucunda, geliştirdiğimiz metasezgisellerin uygun zaman içerisinde en iyiye yakın sonuçlar elde edildiği görülmüştür. Kesin çözüm algoritması büyük boyutlu örnekler için uygun olmadığı için bu tip örneklerde metasezgisellerin kullanılması uygundur. ABSTRACT METAHEURISTIC METHODS FOR THE OBSTACLE NEUTRALIZATION PROBLEM Within the scope of this thesis both theoretical and computational research have been conducted for developing new solution methods for Obstacle Neutralization Problem (ONP) which is actually a military navy scenario and it is inspired from a real problem. In this thesis, we develop metaheuristics for the ONP which is a path planning problem where the aim is to safely and swiftly traverse an agent from a given start point to a target point through a plan of potential mine or threat discs in the plane. A neutralization capability is given to the agent. He can neutralize the threats without exceeding the given neutralization limit. To solve the ONP, ant system, ant colony system, migrating birds optimization, genetic algorithm and simulated annealing algorithms are developed and customized. In addition to these metaheuristics SCIP solver is used to find exact solution. ONP is modeled with ZIMPL language to become ready for SCIP solver. We provide computational experiments both on real-world and synthetic data to empirically assess their performance. The results of the metaheuristics are compared with exact solutions on small and moderate instances. The comparison results present that our algorithms find near-optimal solutions in reasonable execution times. For larger instances SCIP is not applicable because of high run time complexity, therefore, metaheuristics developed for ONP are suitable for larger instances. When the agent neutralizes a threat, neutralization cost of this threat is added to the total cost.