Dinamik ortamlar için istatiksel metotlar kullanan çoklu evrimsel algoritmalar

Abstract

Gerçek dünyada karşılaştığımız birleşimsel (ing: combinatorial) optimizasyon problemleri doğası gereği dinamik bir yapıya sahiptir. Dinamik ortamlarda bulunması gereken optimum nokta zamanla değişeceğinden, sezgisel yaklaşımlar ancak bu ortamlara iyi adapte edilirse başarılı olabilir. Çevresel değişiklik, optimizasyon algoritmalarının her iki tarafında da (kısıtlar ve/veya amaç fonksiyonu) meydana gelebilir. Değişikliği ele almanın en basit yolu, algoritmayı yeniden başlatmaktır. Ancak, yeni optimal çözüm öncekinden çok uzak olmayabilir. Bu nedenle, yeniden başlatma fikri kullanışlı değildir. Bunun yerine, şimdiye kadar edinilen bilgiler mevcut ortama uyum sağlamak için faydalı olabilir. Bu uyarlamayı gerçekleştirmek için bazı dinamik ortam kriterleri dikkate alınmalıdır: (i): değişim sıklığı, (ii): değişikliğin şiddeti, (iii): döngü uzunluğu/döngü doğruluğu, (iv): değişimin öngörülebilirliği. Yukarıda bahsedilen problemleri ele alabilmek için literatürde hem deterministik hem de sezgisel yöntemler kullanılmıştır. Bu yöntemler yetersiz kalınca Metasezgisel algoritmalar kullanılmaya başlanmıştır. Genetik Algoritmalar, Metasezgisel algoritmaların, Evrimsel Algoritmalar alt sınıfına düşen ve türlerin doğadaki biyolojik evriminden ilham alan çok popüler optimizasyon algoritmalarıdır. GA'lar, literatürdeki büyük başarılarına rağmen, değişen ortamlarda genetik çeşitliliklerini kaybederler. Bunun nedenleri olarak şunları söyleyebiliriz: (i): faydalı çözümleri kaybetmek ve (ii): problemin değişkenleri arasındaki ilişkileri kullanamamak. Bu tezde, birinci sorun için, bir çoklu kromozom yapısı uygulanarak bir örtük bellek şeması geliştirilmiştir. İkinci sorun için, problemin değişkenleri (bir kromozomdaki genler olarak da bilinir) arasındaki ilişkilerden yararlanmak için bir Bayes Ağı kullanımıştır. Epistasis, gerçek biyolojik hayatta bir kromozomdaki genlerin etkileşimi anlamına gelir. Daha açık olarak, bir genin etkisi, başka bir genin/genlerin varlığına veya yokluğuna bağlıdır. Bu tezde, genlerin etkileşimlerinden faydalanmak için, çoklu gösterilimin yanı sıra, iyi bilinen bir Dağıtım Tahmini Algoritması olan Bayesçi Optimizasyon Algoritması, önerilen algoritmaya enjekte edilmiştir. Bu tezde, dinamik ortam optimizasyon problemleri ile baş edebilmek için GA tabanlı istatistiksel metotlar kullanan çok kromozomlu bir algoritma önerilmiştir. İlk olarak, örtük bir bellek şeması elde etmek için GA'ya çoklu gösterilim eklenmiştir. Genetik operatörler örtük bellek üzerinde icra edilirken uygunluk değeri hesaplamaları çözüm adaylarının fenotipleri üzerinden yürütülmüştür. Ayrıca, önerilen algoritmanın varyantları literatürde önceden tanıtılmış olan bazı göçmenlik yöntemleri kullanılarak oluşturulmuş, farklı parametre değerleri ile nasıl davrandıkları gözlenmiştir. Önerilen algoritmayı test etmek için üç farklı problem çözülmüştür: Ayrıştırılabilir Birleşim Tabanlı Fonksiyonlar, Dinamik Sırt Çantası Problemi ve Çok boyutlu Sırt Çantası Problemi. Ayrıştırılabilir Birleşim Tabanlı Fonksiyonlar, çeşitli karmaşıklık düzeyleri içerdikleri için dinamik optimizasyon problemlerinde sıkça kullanılan kıyaslama problemleridirler. Bu fonksiyonlarda her bir çözüm adayı dört bitlik bölümlere ayrılır ve her bölümün uygunluk değerleri ayrı ayrı hesaplandıktan sonra bulunan değerler toplanıp çözüm adayının genel uygunluk değeri bulunur. Sırt Çantası Problemi, bilgisayar bilimlerinde sıkça karşılaşılan bir problem formatıdır. Bu problemde, pahada (getirisi) ağır, yükte hafif nesnelerin toplanması hedeflenmekte ve bunu yaparken getiriyi maksimuma çıkarırken yükü minimumda tutmaya çalışılır. Gerçek dünya problemleri üzerindeki etkilerini görmek için bu problemin dinamik versiyonu çözüldü. Finansal yönetim ve endüstride, birçok gerçek dünya sorunu bu problem ile ilgilidir. Örneğin, kargo yükleme, üretim planlaması, sermaye bütçelemesi, proje seçimi ve portföy yönetimi bu problem ile çözülebilen örneklerdir. Çok boyutlu Sırt Çantası Problemi, normal versiyonundan farklı olarak, birden fazla kaynak içeren ve her bir kaynağın kendine ait kısıtları olan versiyonudur. Bu problem, tek bir kısıt yerine kaynak sayısı kadar kısıt olduğundan çözülmesi daha zordur. Yukarıda bahsedilen problemleri çözmek için iki farklı dinamik ortam yöntemi kullanılmıştır. Bunlardan birincisi XOR jeneratörü, diğer ise Normal Dağılım metotu ile yeni veri setleri oluşturmaktır. Sonuç olarak, bu tezde, dinamik optimizasyon problemlerini çözmek için hem istatistiksel bir yöntem hem de örtük bir bellek şeması kullanan bir GA önerilmiştir. Önerilen yöntemin dinamik ortamlardaki davranışını izlemek için üç farklı problem çözülmüştür. Daha sonra performansı literatürdeki en yeni bir yöntem ile karşılaştırılmıştır. Sonuçlar, önerilen yöntemin dinamik optimizasyon problemlerini çözmede oldukça etkili olduğunu göstermiştir.