Impact of sensor detection schemes on performance of evolutionary dynamic optimization techniques


Thesis Type: Postgraduate

Institution Of The Thesis: Marmara University, Institute for Graduate Studies in Pure and Applied Sciences, Turkey

Approval Date: 2015

Thesis Language: English

Student: LOKMAN ALTIN

Supervisor: Haluk Rahmi Topcuoğlu

Abstract:

Sensör Tabanlı Değişim Yakalama Şemalarının Evrimsel Dinamik Optimizasyon Tekniklerinin Performansına Etkisi Dinamik bir optimizasyon probleminde hedef fonksiyon, problem kısıtları veya karar değişkenleri değişebilir. Durağan bir optimizasyon probleminin aksine amaç, değişen en iyi çözümü olabildiğince yakın takip edebilmektir. Evrimsel algoritmalar dinamik optimizasyon problemlerini çözmede en sık kullanılan tekniklerdendir. Dinamik ortamdaki algoritmalar ortamdaki değişimin önceden bilindiğini, özellikle bazı değerlendirme problemleri için, ya da değişimin berlilenmesi gerektiğini varsayarlar. Bununla birlikte, dinamik ortamdaki değişimin olduğu anların belirlenmesi bir çok evrimsel dinamik optimizasyon tekniği için kritik bir süreçtir. Bu çalışmada, çeşitli sensor tabanlı değişim yakalama şemalarının performans değerlendirmesi iyi bilinen iki dinamik optimizasyon problemi olan Hareket Eden Tepeler ve Dinamik Çanta Problemi ile değerlendirildi. Değişim yakalama şemalarının performansları, yakalanan değişimlerin ortamdaki toplam değişime oranı ve değişimi yakalamak için kullanılan sensör sayısına göre değerlendirildi. Ayrıca, sensörlerin ortamdaki değişimin şiddetini tespit etme kapasitesi değerlendirildi. Tespit edilen değişimler bilinen dinamik optimizasyon sezgisellerinin parametrelerini değiştirmede kullanıldı. Belirlenen dört dinamik optimizasyon tekniği üzerinde, sensör tabanlı değişim yakalama ve şiddetini ölçme şemaları ile dinamik optimizasyon sezgiselleri üzerinde performans artışı gözlendi. Deneysel sonuçlar, hibrit yaklaşımımızın birçok farklı karakteristikteki dinamik ortamlarda, referans algoritmalardan daha iyi performans ortaya koyduğunu gösterdi. ABSTRACT Impact of Sensor Detection Schemes on Performance of Evolutionary Dynamic Optimization Techniques In a dynamic optimization problem, the objective function, the problem constraints or the decision variables may change over time, where the main motivation is to track the global optimum value as close as possible. Most of the real world problems in different domains have various characteristics of dynamism. Evolutionary algorithms are among the most common techniques that have been developed to address dynamic optimization problems. They either assume that changes in the environment are known a priori, especially for some of the benchmark problems, or they have to detect the changes. Detecting the points in time where a change occurs in the landscape is a critical issue for a large number of evolutionary dynamic optimization techniques. In this thesis, we focus on performance evaluation of various sensor-based detection schemes by using two well known dynamic optimization problems, which are moving peaks benchmark (MPB) and dynamic knapsack problem (DKP). Our empirical study validates the performance of sensor-based detection schemes considered in this study, by using the average rate of correctly identified changes and the number of sensors invoked to detect a change. We also propose a new mechanism to evaluate the capability of the detection schemes for severity of changes. Additionally, a novel hybrid approach is proposed by integrating the change detection schemes with evolutionary dynamic optimization (EDO) techniques in order to set algorithm-specific parameters dynamically. Four EDO techniques are enhanced with detection schemes, where the ratio of change severity values are utilized to set the values of algorithm-specific parameters. The experimental evaluation validates that our extensions outperform the reference techniques for various characteristics of dynamism.