Dinamik Ortamlarda Evrimsel Algoritmalar: Nesiliçi Değişimin Yönetimi

Abstract

Evrimsel Algoritmalar, evrim teorisinin kavramına dayalı olarak statik ve dinamik problemleri çözmek adına geliştirilmiş hesaplama yöntemleridir. Evrimsel Algoritmaların doğadan esinlenen yapısı itibarı ile günümüzdeki değişken problemlere en çok uyum sağlayan algoritmalardır. Dinamik problemlere Evrimsel algoritmalar ile çözüm bulabilmek için değişen ortamın ve değişimin çok detaylı analiz edilmesi gerekmektedir. Yani ortam değiştikten sonra değişim çeşidine ve probleme bağlı olarak en uygun yol seçildiğinde Evrimsel Algoritmaların daha etkin bir şekilde çözüm bulunması sağlanabilir. Günümüzdeki gerçek problemlerde var olan değişimin rastgele olmasına rağmen, bu alandaki çalışmaların hemen hepsi değişimlerin sistematik bir şekilde, yani nesiller arası gerçekleştiğini varsayılarak yapılmıştır. Bu varsayım yeterli olmuş olsa da geliştirilmesi ve araştırılması gereken bir konu olarak karşımıza çıkmaktadır. Bu tezin asıl amacı ortamın nesil içi değiştiğini varsayarak, aşağıdaki yöntemlerden hangisinin daha etkin bir yol olduğunu deneysel sonuçlarla kanıtlamak. Bunlar: - Ortam değiştikten sonra neslin geri kalanını yeni ortama göre hesaplamak ve yeni bireyleri eski bireylerle değerlendirmek - Ortam değiştikten sonra neslin yaşamını durdurmak ve bir sonraki nesli eski nesilden türeterek devam etmek - Ortam değiştikten sonra neslin şimdiye kadar hesaplanan bireylerini tekrar yeni ortamda değerlendirmek - Ortam değiştikten sonra neslin geri kalan bireylerini eski ortama göre hesaplamaya devam etmek ve değişen ortamı bir sonraki nesle uygulamak Yukarıda sıralanan yöntemlerin hangisinin daha etkin bir yol olduğunun bilinmesi gerçek problemler üzerinde, yani değişimin neslin ortasında olduğu durumlarda daha etkin çalışan, zamandan ve kaynaktan tasarruf eden uygun Evrimsel Algoritma geliştirmemize yardımcı olacaktır.

Evolutionary algorithms (EAs), based on natural evolutionary theory, are computational methods for static and dynamic problems. Since EAs are naturally inspired, they seem to be more suitable to be applied to dynamic optimization problems. In order to apply EAs to the continuously changing real world problems, changes have to be analyzed in a detailed way. According to the type of change and problem instance, if method of managing changes can be predicted it will improve ability of problem solving of EAs. In nature changes are not happening in an organized way, although almost all researchers’ approach to dynamic changing environment was in that way, thus assuming that changes are happening between generations The main goal of the thesis is to examine and show the ability of methods on changing environments within generations by empirical way. The methods are: - Use the changed fitness function for all subsequent individuals, but keep the evaluations of the offspring already evaluated - Temporarily reduce the population size. The generation is terminated, and the offspring generated so far serve as basis to generate the next. - Re-evaluate all offspring already generated; ignore the change and continue to work with the old fitness function to the end of that generation - Ignore the change and continue to work with the old fitness function until all offspring of that generation have been evaluated. As a result, in real world problems where changes happen at any time, as in design of EAs within generation, knowing the ability of above methods will help us in organizing more effective EAs which are not time consuming as well as resources.