Tez No	İndirme	Tez Künye	Durumu
556925		A classification-based heuristic approach for dynamic environments / Dinamik ortamlar için tasarlanmış sınıflandırıcı tabanlı sezgisel bir yaklaşım Yazar:ŞEYDA YILDIRIM BİLGİÇ Danışman: DOÇ. DR. AYŞE ŞİMA UYAR Yer Bilgisi: İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Metasezgiseller = Metaheuristics ; Optimizasyon problemi = Optimization problem ; Sezgisel algoritmalar = Heuristic algorithms	Onaylandı Yüksek Lisans İngilizce 2019 79 s.
Son zamanlarda önerilen eniyileme yöntemlerinin çoğu statik eniyileme problemlerine odaklanmaktadır. Fakat, gerçek dünyadaki eniyileme problemleri çoğu zaman çeşitli belirsizliklere sahiptir. Bu gibi belirsizliklerin bir kaynağı da zamana göre değişen seçilim değeri fonksiyonlarıdır. Bu durum, zaman içinde ayrı ayrı veya eşzamanlı olarak değişebilecek problemin tanımlı değerleri, eniyilemede kullanılan amaç fonksiyonları ve kısıtlardan oluşan dinamik optimizasyon problemlerinde ortaya çıkar. Bu tür dinamik ortamlarda, bir eniyileme algoritması ortamdaki değişimlere uyum sağlamalı ve optimum olanı izleyebilmelidir. Bu durumda bir eniyileme metodu, dinamik bir ortamda meydana gelen değişimlere olan adaptasyon kapasitesi ve tepki verme hızı göz önünde bulundurarak başarılı sayılabilir. Son birkaç on yıl içinde, bu zorlu görev çeşitli sayıda çalışmaya ilham olmuştur. İlgi çeken bu araştırma konusu için farkı çözüm yaklaşımları ortaya koyulmuştur. Önerilen yöntemlerin birbirinden üstünlüğünü göstermek zordur. Çünkü, dinamizm özellikleri ortamdan ortama değişebilmektedir. Bu özellikler değişim sıklığı, değişim şiddeti, değişimin öngörülebilirliği ve değişimin periyodik olup olmamasına göre kategorize edilebilmektedir. Bir eniyileme yöntemi belirli değişim özelliklerine sahip ortamlarda etkin olabilirken, farklı bir ortam için başarısız olabilir. Bu nedenle, değişim özellikleri dinamik ortamlarda çalışacak efektif bir yöntem tasarımı için ele alınması gereken bir konudur. Bu tezin temelinde de değişim özelliklerini kullanan başarılı bir yaklaşım tasarımı amacı yatmaktadır. Önceki çalışmalardan bazıları dinamizmin doğasını anlamaya odaklanmıştır. Ancak, aralarından çok azı, dinamizmi karakterize ederek elde edilen bilgiyi daha iyi eniyileme algoritmaları tasarlamak için kullanmaktadır. Bu tezde, farklı değişim özellikleri altında farklı tepki vermek için karakterizasyon bilgilerinden faydalanan bir sınıflandırma tabanlı tek nokta arama algoritması tanıtılmıştır. Önerilen yöntem, dışarıdan bir müdahale gerekmeksizin farklı özellikteki değişimlere adapte olabilmesini sağlayan bir sınıflandırma mekanizması içermektedir. Değişimlere tepki vermek için kullandığı bu mekanizmalar, dinamik ortamlar için daha önceleri önerilen üst-sezgisel yaklaşımlara benzemektedir. Ortamdaki her değişim esnasında, önerilen algoritma öncelikle oluşan değişimi kategorize eder, değişime uyum sağlamak için bir sonraki değişime kadar değişim kategorisine uygun ve önceden belirlenmiş adımları uygular. Böylelikle arama uzayındaki tek nokta en iyi çözümü aranırken ortamda değişim olduğunda rastgele hareketler yapmak yerine belirli bir süre zarfında en iyi çözümü akıllıca takip etmesini kolaylaştıracak adımları uygular. Bu nedenle algoritma hızlı adapte olabilen genelleştirilmiş bir eniyileme çözümüdür. Daha önceki çalışmalarda dinamik ortam değişimlerini kategorize etmek için sunulan etkinliği kanıtlanmış metrikler bu çalışmadaki sınıflandırma yapısında kullanılmak üzere seçilmiştir. Bu metriklere ek olarak basit bir metrik de sunulmuştur. Etkin bir sınıflandırma için arama uzayına hakim olacak ajanlara ihtiyaç duyulmuştur. Bu ajanları dinamik ortama gözcü noktalar olarak verimli şekilde dağıtacak yöntem belirlenmiştir. Bu tezin ilk aşamasında, farklı tipte dinamizme sahip ortamlardan arama uzayını kapsayıcı ajanlar kullanılarak belirlenen metrikler hesaplanmıştır. Sınıflandırıcı modelini geliştirmek için gerekli öznitelikler hesaplanan metrikler ile sağlanmıştır ve elde edilen veri kümesine uygun sınıflandırma algoritması yapılan testler sonucu belirlenmiştir. Sınıflandırıcılar bu testlerin sonucunda doğruluk, hız ve gürbüzlük açısından değerlendirilmişlerdir. Önerilen algoritma, yapay oluşturulmuş test problemleri (Moving Peaks Benchmark) üzerinde test edilmiştir. Bu tezde sunulan yaklaşımın analizi için parametrelerinin başarıma etkisi hem sınıflandırma yöntemi hem de genel algoritma için etraflıca incelenmiştir. Bu tezin ikinci aşamasında, önerilen yöntemi oluşturan bileşenleri anlamak için deneyler yapılmıştır. Yöntemin daha iyi anlaşılması için kendini oluşturan ayrı algoritmalara bölünerek analiz edilmiştir. Ayrılan algoritmaların tek başına başarımı ölçülüp karşılaştırılmıştır. Ayrıca bu algoritmaların farklı kombinasyonları ve varyasyonları tanımlanıp yapılan deneyler sonucunda en iyi performansı veren kombinasyonun bu çalışmada sunulan yöntem olduğu gözlemlenmiştir. Tezin üçüncü aşamasında, önerilen yaklaşımımızın performansı literatürde dinamik ortamlar için geliştirilmiş benzer yapıdaki tek nokta arama tabanlı üst-sezgisel yaklaşımlarla karşılaştırılmıştır. Sunulan yaklaşımın karşılaştırılan yöntemlerden istatistiksel olarak daha etkin olduğu gösterilmiştir. Bu deneye ek olarak, gerçek hayata yakın bir dinamizmin yakalanması için dinamik ortamdaki değişimlerin rastgele olduğu bir test ortamı kurulup karşılaştırılan yöntemler bu deney kurulumda test edilmiştir. Yapılan deney sonucunda önerilen yaklaşımımızın adaptasyon yeteneğinin diğer yöntemlere kıyasla daha iyi olduğu gösterilmiştir. Bu tezin son aşamasında, sunulan mekanizmamızın kabiliyetini kanıtlamak için farklı dinamizm özelliklerine sahip ortamlar için de deneyler yapılmıştır. Bu sayede sınıflandırıcı yaklaşımın farklı dinamizm özelliklerine sahip ortamlarda da etkinliğini koruduğu gözlemlenmiştir. Deneysel sonuçlar umut vericidir ve önerilen sezgisel yaklaşımın dinamik eniyileme yöntemi olarak uygunluğunu ve gücünü göstermektedir. Bunun yanında yöntemimizin belirli kısıtları da bulunmaktadır. Kullanılan sınıflandırıcı için girdi verisi oluşturma işleminin doğrudan ajan sayısıyla doğru orantılı olarak hesaplama karmaşıklığına mal olduğu söylenebilir. Fakat, yöntemin bütününde ajanlar optimal çözümü bulmada aday çözüm olarak kullanılarak avantaj sağlamaktadırlar. Ajan sayısı ile sınıflandırıcının doğruluğu arasındaki ödünleşim daha optimize hale getirilerek, hesaplama karmaşıklığı ve zamanı açısından yöntemde iyileşme sağlanabilir. Ayrıca dinamik ortamdaki tepe sayısı değişimi sonucunda modelin yeniden eğitilme ihtiyacını keşfetmek için analizler yapılmıştır. Yapılan analizler sunulan sınıflandırıcının dinamik ortamdaki tepe sayısı parametresinden az da olsa etkilendiğini fakat eğitim kümesi farklı tepe sayısı bulunan ortamlarda alınan veriler ile genişletildiğinde daha genel bir sınıflandırıcı elde edilebildiği gösterilmiştir. Buna ek olarak, önerilen metot tek nokta arama tabanlı olarak geliştirilmiştir. Ancak, popülasyon tabanlı arama yöntemi olarak da uygulanabilir.
Most of the state-of-the-art methodologies focus on stationary optimization problems. However, real-world optimization problems often have various types of uncertainties. One source of such uncertainties is time-varying fitness functions. This occurs in dynamic optimization problems which consist of the instance, the objectives and the constraints that may change in time separately or simultaneously. In such dynamic environments, an optimization algorithm must adapt to the changes in the environment and be able to track the optimum. A solver can be considered successful by taking into consideration its adaptation capacity and speed for reacting changes occurs in a dynamic environment. This challenging task has attracted a wide range of studies over the last decades. Different solution approaches have been introduced for this challenging research topic. It is difficult to demonstrate the superiority of an approach to another since dynamism characteristics can vary in different environments. These characteristics can be categorized according to the frequency of change, the severity of change, the predictability of change and the periodicity of change. An optimization method may be useful in environments with specific change characteristics but may fail for a different environment. Therefore, the characteristic of changes is a crucial issue that needs to be addressed. Some of the earlier studies focus on understanding the nature of the changes. However, very few of them use the information obtained to characterize the change for designing better solver algorithms. In this thesis, a classification-based single point search algorithm, which makes use of the characterization information to react differently under different change characteristics, is introduced. The proposed method includes a classification mechanism that allows it to adapt to changes in various type automatically. The mechanisms it employs to react to the changes resemble hyper-heuristic approaches previously proposed for dynamic environments. During each change in the landscape, the proposed algorithm first categorizes the change that occurs. To adapt to those changes, it applies the predetermined steps according to the change category until the next change in the environment. In the first stage of this thesis, we applied several measures to extract features from the dynamic landscape. These features provide information for the classification process of dynamic environments. The proposed algorithm is tested using the Moving Peaks Benchmark generator. In the second stage of this thesis, experiments are performed to understand the underlying components of the proposed method. The method is analyzed to have a better comprehension by simply dividing it into separate algorithms. The performances of the separated algorithms are compared. Also, different combinations and variations of these algorithms have been described and analyzed. As a result of these experiments, it is observed that the best combination is the method presented in this study. In the third stage of this thesis, we compare the performance of our suggested approach with similar single point search-based hyper-heuristic approaches for dynamic environments in literature. The experimental results are promising and show the strength of the proposed heuristic approach as a dynamic optimization solver. In addition to this experiment, for maintaining dynamism as close as to real life, a test environment with random changes in the dynamic environment is established, and methods are tested in this experimental setup. As a result of this experiment, it has been shown that the adaptation ability of our proposed approach is better than other methods. In the final stage of this thesis, we run the experiments for different settings to prove the capability of our mechanism. It is observed that the classifier approach maintains its effectiveness in environments with different dynamism characteristics. Overall, experimental results are promising and demonstrate the appropriateness of the proposed approach as a dynamic optimization method. On the other hand, our method has certain limitations. The fact that the process of generating input data for classifier costs computational complexity directly proportional to the number of agents. However, the method turns that into an advantage by using the best agent as a candidate solution to find the optimum solution. Moreover, the trade-off between the agent count and the accuracy of the classifier can be examined further to be optimized. Improvements in this aspect will decrease computational complexity and save time to the approach. Finally, the proposed method is developed as a single point search algorithm. Still, the main idea in this study can be applied to population-based search algorithms.