Characterization of changes in dynamic multi-objective optimization problems

Abstract

Dinamik çok-amaçlı eniyileme problemleri (DÇAEP) on yıldan daha uzun bir süredir farklı alanlarda ‎çalışan araştırmacıların ilgisini çekmiştir. Zamana bağlı olarak, bir veya birden fazla amaç ‎fonksiyonundaki değişimler, kısıtlarda olan değişimler ve/ veya problem parametrelerinde olan ‎değişimler, DÇAEP’lerdeki dinamik davranış formlarına örnek olarak verilebilir. ‎Değişim ‏karakterizasyonu‎, ‎birçok dinamik çok amaçlı evrimsel algoritmanın ‏‎(DÇAEA) performansının, ‎değişimlere etkin bir şekilde adapte olunarak ve tepki verilerek iyileştirilmesi ‎‏için, en önemli aşamadır‏. ‏Bu ‎tezde‏, ‏ değişimin tespiti‏, değişimin büyüklüğünün tespiti ve değişimin tipinin tespiti olmak üzere üç ‏çeşit karakterizasyon tekniği sunulmuştur. İlk olarak, literatürde ‎sunulan test problemleri için ‏sensör‎-‎tabanlı farklı değişim tespit teknikleri sunduk‎. ‎Değişimin çok zor algılanabildiği ‎problemlere ‎yönelik olarak, popülasyon tabanlı ve sensör tabanlı yöntemleri içeren yeni bir melez yaklaşım da, ‎çalışma kapsamında sunulmuştur. Yöntemlerin performanslarını ‎doğrulamak için‎, ‎farklı ‏dinamizm özellikleri gösteren ve farklı tipten birçok test içeren kapsamlı bir test problem seti göz önüne alınmış olup‎, ‎yapılan çalışmalarda sunulan yöntemlerimiz alternatiflerinden, gerçek pozitif oran ve ‎kullanılan sensör sayılarına göre önemli ölçüde ‎daha iyi bir performans ortaya koyduğu ‏gözlemlenmiştir‎.‎Tezin ikinci aşamasında, DÇAEP’lerde değişimin büyüklüğünü tespit etmek için yeni bir teknik ‎‎önerilmiştir‎. ‎Farklı test problemleri ve değişim büyüklüğü seviyeleri kullanılarak gerçekleştirilen ‏‎deneysel çalışma, tekniğimizin performansını doğrulamaktadır. Ayrıca, değişim tespit ‎‎mekanizmalarının‏, ‏değişimin büyüklüğünü tespit tekniğinin ve yeni bir tepki mekanizmasının NSGA-‎II algoritmasına ‎entegrasyonu ile ortaya çıkan‎, ‎değişime duyarlı NSGA‎-‎II ‏‎(‎CR‎-‎NSGA‎-‎II‎) ‎algoritması olarak adlandırdığımız özgün bir ‎algoritmayı da, çalışmamız kapsamında önermekteyiz. ‎Algoritmamız, göz önüne alınan metriklerin ve test problemlerinin ‎büyük bir kısmı için önde gelen ‏DÇAEA’lardan daha iyi sonuçlar ‎vermiştir‎. ‎Değişimin ‏karakterizasyonuna yönelik üçüncü çalışma ‎olarak, DÇAEP’ler için değişimin tipinin tespitine yönelik bir yöntem sunulmaktadır. Buna ek olarak, ‎verilen bir DÇAEA ile ‎tip tespiti yöntemimizi içeren melez bir teknik de çalışma kapsamında ‏önerilmiştir‎. ‎Dört tip ve beş metrik için yedi test ‎problemi kullanarak yaptığımız deneysel çalışma, ‎melez tekniğimizin önemini ve tip tespit yöntemimizin ‎‎katkısını açık bir şekilde doğrulamaktadır.‎Son aşamada, önerilen teknikler gerçek bir dünya problemine uyarlanmıştır. Bu kapsamda, özellik kaymaları gösteren ‎veri ‏akışı sınıflandırılmasını ele alan yeni ve etkili bir sistem önerilmiştir‎. ‎Bu sistemin ilk yapı taşı‎, ‎‎Dinamik Filtre Tabanlı Özellik Seçimi olarak adlandırılan ve veri akışı işlemi süresince devamlı ‎olarak en ‏iyi kümeyi seçerek özellik kaymasını ele alan‎, ‎dinamik çok amaçlı bir evrimsel algoritmadır. ‎‎Ayrıca‎, ‎bu algoritma‎ ile birlikte çalışması için, yeni bir özellik kayması tespit yöntemi önerilmiştir. ‎‎Önerilen sistemde‎, ‎sadece bu ‏algoritma tarafından seçilen özelliklere yoğunlaşarak veri akışını ‎‎sınıflandıran Yapay Sinir Ağları kullanılmıştır‎. ‎Gerçekleştirilen deneysel çalışma‎, ‎sistemimizin ‏‎kullanılan veri kümelerinde sınıflandırma doğruluğu ve özellik kaymasından sonra iyileşme yeteneği ‎‎açısından referans algoritmalardan önemli ölçüde daha iyi performans gösterdiğini ortaya ‏‎koymaktadır.‎‎

Dynamic Multi-Objective Optimization Problems (DMOPs) have been gained a great attention from researchers in various domains for more than ten years. Changes in one or more objective functions, changes in constraints and/ or changes in problem parameters over time are example forms of dynamic behavior in DMOPs. Characterization of dynamism for DMOPs is an essential phase, which can be utilized for improving the performance of Dynamic Multi-Objective Evolutionary Algorithms (DMOEAs) by adapting and responding to the changes efficiently. In this thesis, we propose three types of characterization techniques which are detecting the occurrence of changes, detecting the severity of changes and detecting the type of changes in DMOPs. In the first phase of the thesis, we propose various sensor-based techniques for detecting the occurrence of changes in test problems presented in the literature. To deal with challenging problems that expose less detectable environmental changes, a new hybrid scheme is proposed that incorporates sensor-based schemes with the population-based ones. We validate the performance of our change detection schemes on a large set of test problems with all possible types, ‎where our techniques significantly outperform the other alternatives with respect to both true positive rates and the number of sensors invoked.As part of the thesis, a new technique is presented for detecting the severity of changes for DMOPs. We also propose a novel adaptive algorithm called change-‎responsive NSGA-II (CR-NSGA-II) that incorporates the change detection schemes, our technique ‎for detecting severity of change and a new response mechanism into the NSGA-II algorithm. Our algorithm ‎demonstrates significantly better results than the leading DMOEAs on majority of test problems based on various metrics for evaluating DOMEAs. As the third type of change characterization, we propose a type-‎detection mechanism for DMOPs. A hybrid technique is proposed by incorporating our ‎type ‎detection mechanism with a given DOMEA, which is validated with an empirical evaluation ‎by using seven ‎test problems from all four types of DMOPs. In the final phase, we apply our proposed techniques on a real-world problem. A new and ‎efficient ‎framework to deal with the classification of data streams when exhibiting feature drifts is proposed. ‎The first building block of the framework is a dynamic multi-objective evolutionary algorithm called ‎Dynamic Filter-Based Feature ‎‎Selection (DFBFS) algorithm, which handles feature drifts by ‎continuously selecting the ‎optimal set of features during the stream processing. In the proposed ‎framework, the Artificial Neural Network (ANN) is utilized to classify the data streams by ‎only focusing ‎on the selected features using the DFBFS algorithm.‎ The experimental evaluation validates our framework, as ‎it significantly outperforms reference algorithms in terms of classification accuracy and the ability of ‎fast recovery after the occurrence of feature drifts on the evaluated datasets.