Sezgisel Yöntemlerin Kesin Yöntemler ile Melezlenmesi Yoluyla Bilgisayar Ağlarında Güvenilirlik Probleminin Eniyilenmesi
Hybridizing Metaheuristics with Exact Techniques for Optimization of Reliability Problem in Computer Networks
Yazar: ÖMER ÖZKAN
Danışman: DOÇ. DR. MURAT ERMİŞ ; DOÇ. DR. İLKER BEKMEZCİ
Hava Harp Okulu Komutanlığı / Havacılık ve Uzay Teknolojileri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Doktora, 2016
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Metasezgiseller = Metaheuristics ; İstatistiksel deney tasarımı = Statistical experimental design

Özet:
Bu tezde güvenilir bilgisayar ve haberleşme ağlarının tasarım problemleri için kesin yöntemlerin ileri sezgisel yöntemlerle melezlenmesi konusu araştırılmaktadır. Önerilen yöntemler iki farklı güvenilir haberleşme ağı tasarımı problemine uygulanmıştır. Birinci problem olarak ağ güvenilirliği kısıtı altında toplam ağ maliyetini enküçüklemeyi amaçlayan Güvenilir Bilgisayar Ağı Tasarımı (GBAT) problemi ele alınmıştır. Bu problem literatürde oldukça iyi çalışılmış bir problemdir. Problemin NP-zor (NP-hard) karmaşıklığa sahip olmasından dolayı yeni melez ileri sezgisel yöntemler geliştirilmiştir. Yöntem olarak iki probleme özgü ileri sezgisel yöntem (Tavlama Benzetimi (TB) ve Genetik Algoritma (GA)) ile bu yöntemlerin Dal & Sınır (D&S) algoritması ile melezlendiği algoritmalar önerilmektedir. İkinci problem ise bir Güvenilir Kablosuz Çoklu Ortam Algılayıcı Ağ Tasarımı (GKÇOAAT) problemini içermektedir. Kablosuz Çoklu Ortam Algılayıcı Ağ (KÇOAA)'lar için ağ güvenilirliğinin tanımı düğümlerin yerleştirilmesi ile birlikte bağlanabilirlik ve kapsamayı içeren yapısıyla diğer geleneksel haberleşme ağlarının ağ güvenilirliği tanımından farklılıklar göstermektedir. Bu nedenle KÇOAA'lar için yeni bir bilgi toplama güvenilirliği tanımı yapılmıştır. İlave olarak problemin amacı algılayıcıların yerleşimini yapmak ve verilen bütçe kısıtı altında arazi ve cihaz özelliklerini de dikkate alarak KÇOAA için bilgi toplama güvenilirliğini enbüyüklemeye çalışmaktır. Problem tanımı düşman bölgesinde gözetleme yapmak amacını içerecek şekilde literatürde ilk defa yapılmıştır. Yerleştirme, bağlanabilirlik ve kapsamayı birleştiren güvenilir KÇOAA tasarımı problemi NP-zor karmaşıklığa sahip olduğu için kesin bir yöntem ile ileri sezgisel yöntemlerin melezlendiği yeni bir melezleme önerilmektedir. Öncelikle probleme özgü TB ve GA geliştirilmiştir. Birinci uygulamadan daha farklı bir yapıda bir D&S algoritması Melez TB (MTB), Melez GA (MGA) ve Melez GA Temelli Matsezgisel (MGATM) içerisine algılayıcıların oryantasyonlarını kesin olarak yapabilmek amacıyla kullanılmıştır. MGATM'nin yapısında birinci popülasyonda aktarma düğümlerinin kesin olarak yerleşimini yapabilmek amacıyla ağ akışı temelli bir Karma Tamsayılı Doğrusal Programlama (KTDP) modeli de bulunmaktadır. Yapılan koşumlar sonucunda ileri sezgisel yöntemlerin kesin bir yöntemle melezlenmesiyle elde edilen algoritmaların diğer yöntemlerden kabul edilebilir süreler içerisinde daha iyi performans gösterdiği tespit edilmiştir.

Abstract:
This thesis investigates the integration of exact algorithm(s) with metaheuristics for reliable computer and communication network design problems. The proposed approaches are applied in two different reliable communication network design problems. The initial problem is the reliable computer network design problem that minimizes the total network cost under network reliability requirement. The problem is a well studied problem in the literature. Since the problem has NP-hard complexity, new hybrid metaheuristics are developed. The proposed methods combine metaheuristics (i.e. Simulated Annealing (SA) and Genetic Algorithm (GA)) with Branch and Bound (B&B) algorithm as well as two problem-specifically designed SA and GA methods are proposed. The second problem covers a reliable Wireless Multimedia Sensor Network (WMSN) design problem. The network reliability definition of WMSNs is different than the other traditional communication networks since it involves connectivity and coverage issues with node placement. Therefore a new information gathering network reliability definition is done for WMSNs. Besides the aim of the problem is to deploy sensor nodes to maximize the WMSN information gathering network reliability under a given budget constraint by considering terrain and device specifications. The problem definition is done for the first time in the literature for getting surveillance from an enemy zone. The reliable WMSN design problem with deployment, connectivity and coverage has NP-hard complexity, therefore a new hybridization of an exact algorithm with metaheuristics is proposed. Initially, problem spesific SA and GA approaches are created. A different B&B approach than the one in the first problem is embedded into Hybrid Simulated Annealing (HSA), Hybrid Genetic Algorithm (HGA) and Hybrid Genetic Algorithm Based Matheuristic (HGABM) to orient the sensors exactly. HGABM has also a Mixed Integer Linear Programming (MILP) network flow based model which is used to find the exact deployment points of the relay nodes in the initial population. Computational results show that hybrid algorithms have better performances than the others in reasonable computation times.