Tez Arşivi

Hakkımızda

Tez aramanızı kolaylaştıracak arama motoru. Yazar, danışman, başlık ve özete göre tezleri arayabilirsiniz.


İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Anabilim Dalı / Bilgisayar Mühendisliği Bilim Dalı

A classification-based heuristic approach for dynamic environments

Dinamik ortamlar için tasarlanmış sınıflandırıcı tabanlı sezgisel bir yaklaşım

Teze Git (tez.yok.gov.tr)

Bu tezin tam metni bu sitede bulunmamaktadır. Teze erişmek için tıklayın. Eğer tez bulunamazsa, YÖK Tez Merkezi tarama bölümünde 556925 tez numarasıyla arayabilirsiniz.

Özet:

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 ...

Özetin tamamını okumak için tez.yok.gov.tr adresine gidin.

Summary:

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 ...

For full summary, please go to tez.yok.gov.tr.