İçeriğe atla
Arama sonuçlarına dön

Differential Evolution — Küresel Stokastik Optimizasyon

Ortaya koyan
Rainer Storn & Kenneth Price
Yıl
1997
Tür
Population-based stochastic metaheuristic

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Differential Evolution (DE), Rainer Storn ve Kenneth Price tarafından 1997'de tanıtılan, sürekli parametre uzayları için tasarlanmış popülasyon tabanlı stokastik bir optimizasyon algoritmasıdır.

Mevcut popülasyon üyeleri arasındaki vektör farklarını birleştirerek aday çözümler üretir, bu da onu arama uzayı dışbükey olmayan, çok modlu veya gradyan tabanlı yöntemlere uygun olmayan durumlar için Genetik Algoritmalar ve Parçacık Sürü Optimizasyonuna güçlü ve parametre açısından cimri bir alternatif haline getirir.

Yöntemin mantığı

Bilinmeyen bir arazide en alçak vadiyi arayan bir grup kaşif hayal edin. Her adımda, her kaşif rastgele seçilmiş üç meslektaşını izler, ikisi arasındaki farkın bir adım boyutu faktörüyle ölçeklendirilmesiyle önerilen yönde hareket eder ve ardından yeni konumun veya eski konumun daha iyi arazi olup olmadığına karar verir. Birçok tur boyunca, tüm grup toplu olarak bulduğu en derin vadi etrafında yavaş yavaş kümelenir. Differential Evolution tam olarak bu şekilde çalışır: iki popülasyon vektörü arasındaki 'fark' arama yönünü oluşturur ve ölçek faktörü F her adımın ne kadar cesur olduğunu kontrol eder.

Tarih

Differential Evolution, Rainer Storn ve Kenneth Price tarafından 1997 tarihli önemli çalışmaları olan Journal of Global Optimization'da tanıtılmıştır. Algoritma, Price'ın genetik tavlama üzerine önceki çalışmalarından ve Storn'un kayan nokta geçişi deneylerinden doğmuştur. Şu anda DE/best/1/bin olarak adlandırılan orijinal varyant, standart kıyaslamalarda çağdaş evrimsel stratejilere ve genetik algoritmalara rakip ve genellikle üstün olduğunu kanıtlamıştır. Das, Mullick ve Suganthan (2016) tarafından yapılan kapsamlı bir inceleme, yirmi yılı aşkın varyantları, uyarlanabilir şemaları ve uygulamaları kataloglayarak DE'yi meta-sezgisel literatürdeki temel yöntemlerden biri olarak kabul ettirmiştir.

Ne zaman kullanılır?

Differential Evolution, amaç fonksiyonunun sürekli, muhtemelen türevlenemez veya çok modlu olduğu ve tüm parametreler için arama sınırlarının önceden bilindiği durumlarda uygundur. Gradyan bilgisi gerektirmez ve normal varsayım yapmaz, bu nedenle mühendislik tasarımı, hiperparametre ayarlama, simülasyon modellerinin kalibrasyonu ve herhangi bir kara kutu optimizasyon görevi için uygundur. Yaklaşık 10 kat parametre sayısı kadar bir popülasyon boyutu yaygın bir başlangıç noktasıdır. DE, yalnızca ayrık veya kombinatoryal problemler için uygulanmamalıdır; ayrıca güvenilir bir şekilde yakınsamak için en az 1 000 yineleme gerektirir — eğer fonksiyon değerlendirme bütçesi çok kısıtlıysa, Bayes optimizasyonu daha örnek verimli bir alternatiftir.

Sınırlar ve dikkat edilmesi gerekenler

  • Yetersiz iterasyon sayısı varsa yakınsama yavaş olabilir; 1 000'den az nesil genellikle suboptimal bir sonuç verir; en iyi çözümün iyileşmesi için yeterli zaman tanınmalıdır.
  • Performans, F ve CR seçimine duyarlıdır — kötü ayarlanmış parametreler erken yakınsamaya veya aşırı yavaş ilerlemeye neden olabilir.
  • Yalnızca ayrık veya kombinatoryal arama uzayları için tasarlanmamıştır; ayrık uzantılar mevcuttur ancak daha az standarttır.
  • Her yineleme, her değerlendirme hesaplama açısından pahalı olduğunda maliyetli olabilen NP kez amaç fonksiyonunun değerlendirilmesini gerektirir.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Gradyan bilgisi gerektirmez — türevlenemez ve gürültülü olanlar dahil herhangi bir kara kutu amaç fonksiyonu ile çalışır.
  • Arama gücüne kıyasla çok az kontrol parametresi (F, CR, NP) vardır, bu da onu yapılandırması nispeten kolaylaştırır.
  • Gradyan tabanlı optimize edicilerin yerel optimumlara yakınsadığı çok modlu manzaraları doğal olarak işler.
  • Popülasyon değerlendirmeleri bağımsızdır ve çok çekirdekli sistemlerde duvar saati süresini azaltarak doğrudan paralelleştirilebilir.
  • Basit bir güncelleme kuralı kullanarak birçok kıyaslamada Genetik Algoritmalar ve Parçacık Sürü Optimizasyonu ile rekabetçidir.

Uygulama alanları

  • Amaç fonksiyonlarının analitik olmadığı simülasyon ve ajan tabanlı modellerin kalibrasyonu.
  • Arama uzayının sürekli ve sınırlı olduğu makine öğrenmesi boru hatları için hiperparametre optimizasyonu.
  • Anten tasarımı, yapısal optimizasyon ve kontrolcü ayarlama gibi mühendislik tasarım problemleri.
  • Mühendislik ve doğa bilimlerinde sinir ağlarını eğitmek ve doğrusal olmayan modelleri uydurmak.
  • Portföy ağırlık optimizasyonu ve finansal zaman serisi modellerinde parametre tahmini.

Nasıl çalışır?

Nasıl çalışır?

1

NP sayıda aday çözüm vektöründen oluşan bir popülasyon, her parametre için önceden tanımlanmış arama sınırları içinde rastgele ve düzgün bir şekilde çekilir. Arama sınırları, algoritma başlamadan önce kullanıcı tarafından belirtilmelidir; DE bunları problemden çıkaramaz. İyi bir başlangıç popülasyonu, algoritmanın en başından itibaren umut verici bölgeleri kaçırmamasını sağlamak için tüm uygun uzayı kapsar.

2

Popülasyondaki her hedef vektör için, rastgele üç farklı vektör seçilir. Üçüncüsüne ölçeklendirilmiş farkı ekleyerek bir mutant vektör oluşturulur: v = x_r1 + F*(x_r2 - x_r3), burada F ölçek faktörüdür (tipik olarak 0.4–1.0). Bu fark tabanlı adım, DE'yi diğer evrimsel algoritmalardan ayıran ve gradyan hesaplaması gerektirmeden kendine uyarlanabilir yönsel bilgi sağlayan şeydir.

3

Bir deneme vektörü, mutant vektör ve orijinal hedef vektör öğe öğe karıştırılarak oluşturulur. Her öğe, CR olasılığıyla (geçiş oranı, tipik olarak 0.5–1.0) mutanttan ve aksi takdirde hedef vektörden alınır; en az bir öğe her zaman mutanttan alınır. Bu adım, keşif ve sömürü arasındaki dengeyi kontrol eder: yüksek bir CR mutantı destekler, düşük bir CR mevcut çözümün daha fazlasını korur.

4

Deneme vektörü amaç fonksiyonu üzerinde değerlendirilir ve hedef vektörle karşılaştırılır. Deneme, eşit veya daha iyi bir amaç değeri elde ederse, bir sonraki nesilde hedefi değiştirir; aksi takdirde hedef değişmeden kalır. Bu açgözlü bire bir seçim, popülasyonun bozulmasını önler ve bulunan en iyi çözümün monoton iyileşmesini sağlar.

5

Mutasyon, geçiş ve seçim, bir yakınsama kriteri karşılanana kadar yeterli sayıda nesil (genellikle 1 000 veya daha fazla) boyunca tekrarlanır — örneğin, en iyi amaç değerindeki değişiklik bir tolerans eşiğinin altına düşer veya maksimum yineleme sayısına ulaşılır. Son popülasyondaki en iyi vektör, algoritmanın çözümüdür.

Sık yapılan hatalar

  • DE'yi çok az iterasyonla çalıştırmak (yaklaşık 1 000'in altında) en yaygın hatadır — algoritma yakınsamak için yeterli nesle sahip olmamıştır ve sonuç önsel olarak kabul edilmelidir; değerlendirme bütçesi kısıtlıysa Bayes optimizasyonuna geçin.
  • Ölçek faktörü F'yi çok düşük ayarlamak çeşitliliği erken çökertir; çok yüksek ayarlamak yakınsamayı engeller. F'yi [0.4, 1.0] aralığında başlatın ve ampirik olarak ayarlayın.
  • Arama sınırlarının atlanması veya yanlış belirtilmesi kritik bir hatadır — DE popülasyonu başlatmak için sınırları kullanır ve sınırlar çok dar veya yoksa anlamsız sonuçlar üretecektir.
  • DE'yi tek seferlik bir çalıştırma olarak ele almak, çok modlu manzaralarda risklidir — farklı rastgele tohumlardan birden fazla bağımsız deneme çalıştırın ve çalıştırmalar boyunca bulunan en iyi çözümü raporlayın.

Sık sorulan sorular

Ölçek faktörü F ve geçiş oranı CR'yi nasıl seçerim?

En yaygın kabul gören varsayılanlar DE/best/1/bin stratejisi için F = 0.8 ve CR = 0.9'dur. Pratikte, F adım boyutunu kontrol eder — yaklaşık 0.4–1.0 değerleri tipiktir — ve CR mutantın hedefi ne kadar değiştirdiğini kontrol eder. Popülasyon çok hızlı yakınsarsa, F'yi artırın veya CR'yi düşürün. Uyarlanabilir DE varyantları (jDE, JADE), bu parametreleri çalışma sırasında otomatik olarak ayarlar, bu da manuel ayarlama pratik olmadığında makul bir seçimdir.

Kaç nesil gereklidir?

Genel bir kural olarak, en az 1 000 nesil önerilir. Yüksek boyutlu problemler (çok sayıda parametre) veya karmaşık manzaralar için daha fazla iterasyon gerekebilir. En iyi çözümün amaç değerini nesiller boyunca izleyin: yüzlerce iterasyon boyunca değişmemişse, DE muhtemelen yakınsamıştır — veya durgunlaşmıştır, bu durumda taze bir rastgele tohumla yeniden çalıştırmak tavsiye edilir.

DE, Genetik Algoritmalar ve Parçacık Sürü Optimizasyonu ile nasıl karşılaştırılır?

Her üçü de sürekli optimizasyon için popülasyon tabanlı meta-sezgisel yöntemlerdir. DE tipik olarak GA'lardan daha az kontrol parametresi kullanır ve PSO'ya kıyasla daha basit, deterministik bir güncelleme kuralına sahiptir. Birçok standart kıyaslamada DE, her ikisiyle de rekabetçidir veya onlardan daha iyi performans gösterir, ancak performans probleme bağlıdır. Seçim genellikle evrensel bir sıralama yerine aşinalık ve mevcut uygulamalara dayanır.

DE, tamsayı veya kategorik parametreleri işleyebilir mi?

DE sürekli uzaylar için tasarlanmıştır. Tamsayı parametreleri, her güncellemeden sonra sürekli çözümü en yakın tamsayıya yuvarlayarak karşılanabilir, ancak bu bir yaklaşımdır. Planlama veya yönlendirme gibi tamamen kategorik veya kombinatoryal problemler — ayrık uzaylar için tasarlanmış Karınca Kolonisi Optimizasyonu veya Tabu Arama gibi yöntemlerle daha iyi hizmet verilir.

İlgili yöntemler

Kaynaklar

  1. Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.

    DOI kaynağını aç
    Kopyalandı.
  2. Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.

    DOI kaynağını aç
    Kopyalandı.