Büyük Ölçekli Küresel Optimizasyon için Kriter Fonksiyonları

Benchmark Functions for Large-Scale Global Optimization(Büyük Ölçekli Küresel Optimizasyon için Kriter Fonksiyonları)

Son yıllarda çok sayıda metasezgisel optimizasyon algoritması üretilmiştir. Simulated Annealing (SA), Evolutionary Algorithms (EAs), Differential Evolution (DE), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO) ve Estimation of Distribution Algorithms (EDAs) bunlardan bazılarıdır.

Bu çözücüler büyük ve kompleks problemlerle karşılaştıkları zaman çözüm yeteneklerini kaybetmektedirler. Yüzlerce karar değişkenin olduğu problemlerde ürettikleri çözümler az karar değişkenine sahip problemleri çözmekteki başarılarına göre oldukça kötüdür.

Bu durumun ana sebebi arama uzayının büyümesiyle çözüm kalitesinin düşmesiyle alakalıdır.

Problemin boyutu büyüdükçe çözüm uzayı üssel olarak artmaktadır dolayısıyla araştırma uzayı da büyümektedir verilen makul bir sürede bu uzayı tarayarak uygun bir çözüm üretmek isteyen metasezgisel optimizasyon algoritmaları bu konuda sıkıntı çekmektedir.

Bazı durumlarda problemin boyutu büyüdükçe problemin karakteristiği de değişmektedir. Örneğin Rosenbrock fonksiyonu 2 boyut için unimodal olarak tanımlanırken, daha büyük boyutlarda multimodal olarak tanımlanmaktadır.

Bu sebeplerden dolayı düşük boyutlarda güzel sonuçlar veren algoritmalar büyük boyutlara geldiği zaman kaliteli çözüm sunamamaktadır.

Teorik ve pratik olarak metasezgiselleri büyük boyutlu problemler için iyileştirme çalışmaları ilgi görmektedir.

İlk pratik yaklaşım olarak bu çözücülerin paralelleştirilmesi önerilmiş ve gerçeklenmiştir. Daha sonra cooperative coevolution(birlikte evrim) umut verici bir yöntem olarak ortaya çıkmıştır. Bu alanda yapılan çalışmaların ölçeklenebilirliliğini kıyaslamak için bazı benchmark fonksiyonları ayarlanmıştır. Büyük ölçekli sayısal optimizasyon çalışmaları için kriter fonksiyonları paketi sağlanmıştır.

Problemin boyutu büyüdükçe problemin zorluğu artmaktadır. Fakat bazı büyük boyutlu problemler diğerlerinden kolaydır. Örneğin bir problemin karar değişkenleri birbirinden bağımsız ise problem alt parçalara bölünebilir ve daha kolay bir şekilde çözüm sağlanabilir. Böyle durumlarda çizgi arama(line search) ve açgözlü metod(greedy method) problemin verimli bir şekilde çözümüne gidebilir. Bu tarz problemler ayrılabilir(separable) olarak adlandırılırlar.

Ayrılabilir(Separable) Fonksiyon:

n değişkenli bir fonksiyon tek değişkene sahip n adet fonksiyonun toplamı şeklinde yazılabiliyorsa ayrılabilir fonksiyon olarak adlandırılır. Bir f(x) fonksiyonu ayrılabilir ise parametreleri(xi) bağımsız olarak adlandırılır.

Ayrılabilir olmayan fonksiyonlarda ayrılabilir olmayan(non-separable) olarak adlandırılır.

Ayrılabilir olmayan fonksiyonlar m-nonseparable function şeklinde adlandırılır. Burada fonksiyonun parametrelerinden(xi) m adeti bağımsız değildir. Eğer ayrılabilir olmayan bir fonksiyonun iki parametresi(xi) bağımsız değilse fully-nonseparable olarak adlandırılır. Bu yazıda nonseparable denildiği zaman aksi belirtilmediği sürece fully-nonseparable fonksiyonlardan bahsedilmektedir.

Ayrılabilirliği belirlemek farklı problemlerin zorluğunu ölçmekte işimize yaramaktadır.

Separable problemler kolay, fully-nonseparable problemler zor olarak tanımlanmaktadır. Bu ikisinin arasında da partially separable(kısmen ayrılabilir) problemler bulunmaktadır.

Büyük boyutlu problemler 4 bölüme ayrılmıştır.
1. Separable(Ayrılabilir) Fonksiyonlar
2. Partially-separable(Kısmen Ayrılabilir) Fonksiyonlar(az sayıda değişkeni bağımsız ekserisi bağımlı olan)
3. Partially-separable(Kısmen Ayrılabilir) Fonksiyonlar(birden fazla bağımsız m-ayrılabilir olmayan alt bileşeni olan )
4. Fully-nonseparable(Tamamen Ayrılabilir Olmayan) Fonksiyonlar

Farklı ayrılabilirlik derecelerine sahip fonksiyonları üretebilmek için aşağıdaki 6 temel fonksiyon kullanılmıştır.

1. The Sphere Function (separable)
2. The Rotated Elliptic Function (nonseparable)
3. Schwefel’s Problem 1.2 (nonseparable)
4. Rosenbrock’s Function (nonseparable)
5. The Rotated Rastrigin’s Function (nonseparable)
6. The Rotated Ackley’s Function (nonseparable)

Orijinalleri ayrılabilir olan 2,5 ve 6.fonksiyonlara “Salomon’s random coordinate rotation technique” tekniği uygulanarak ayrılabilir olmayan hale getirilmiştir. {Ayrıntılar: R. Salomon, “Re-Evaluating Genetic Algorithm Performance under Coordinate Rotation of Benchmark Functions. A Survey of Some Theoretical and Practical Aspects of Genetic Algorithms,” Biosystems, vol. 39, no. 3, pp. 263–278, 1996.}

Test ortamı için 20 kıyas fonksiyonu üretilmiştir. Problem boyutu olarak D=1000 önerilmiştir. Ayrılabilirlik derecesi olarak m=50 önerilmiştir. Kullanıcılar m parametresini değiştirebilirler.

TEMEL FONKSİYONLAR

1-Sphere Fonksiyonu

2-Döndürülmüş Eliptik(Rotated Elliptic) Fonksiyon

Orijinal eliptik fonksiyonu ayrılabilirdir. 10^6 sayısı condition(durum/şart) sayısı olarak tanımlanır ve Sphere fonksiyonunun eliptik fonksiyona çevrilmesini sağlar. Fonksiyonu ayrılabilir olmayan yapmak için ortogonal matris kullanılır. Sonuç olarak üretilmiş Döndürülmüş Eliptik(Rotated Elliptic) Fonksiyon:

3-Döndürülmüş Rastrigin (Rotated Rastrigin) Fonksiyon

Orijinal Rastrigin fonksiyonu ayrılabilirdir.Fonksiyonu ayrılabilir olmayan yapmak için ortogonal matris kullanılır. Sonuç olarak üretilmiş Döndürülmüş Rastrigin(Rotated Rastrigin) Fonksiyon:

Rastrigin fonksiyonu klasik bir multimodal fonksiyondur. Boyut arttıkça lokal optimumların sayısı da üssel olarak artar.

4-Döndürülmüş Ackley(Rotated Ackley) Fonksiyon

Orijinal Ackleyfonksiyonu ayrılabilirdir.Fonksiyonu ayrılabilir olmayan yapmak için ortogonal matris kullanılır. Sonuç olarak üretilmiş Döndürülmüş Ackley(Rotated Ackley) Fonksiyon: