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

Evrim Stratejisi (CMA-ES) — Kovaryans Matrisi Uyarlaması

Ortaya koyan
Nikolaus Hansen & Andreas Ostermeier
Yıl
2001
Tür
Derivative-free continuous black-box optimizer

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

Yazı boyutu

Ne işe yarar?

Kovaryans Matrisi Uyarlamalı Evrim Stratejisi'nin (Covariance Matrix Adaptation Evolution Strategy) kısaltması olan CMA-ES, Hansen ve Ostermeier tarafından 2001 yılında tanıtılan sürekli kara kutu işlevleri için modern, türevsiz bir optimize edicidir.

Çok değişkenli normal dağılımdan çekilen aday çözümlerin bir popülasyonunu korur ve parametre uzayının daha iyi bölgelerine doğru aramayı yönlendirmek için dağılımın ortalamasını, adım boyutunu ve tam kovaryans matrisini yinelemeli olarak günceller. Sürekli kara kutu optimizasyonu için fiili standart haline gelmiş ve sinir mimarisi araması (NAS) ile pekiştirmeli öğrenme politika optimizasyonunda yaygın olarak kullanılmaktadır.

Yöntemin mantığı

Bir tepelik arazideki en alçak noktayı aradığınızı hayal edin, ancak araziyi göremiyorsunuz - yalnızca tek tek konumları sorgulayabilir ve yüksekliklerini öğrenebilirsiniz. CMA-ES, yönlendirilmiş bir sürü gibi çalışır: mevcut en iyi tahmine etrafına bir yoklama noktası bulutu bırakır, her yoklama noktasının ne kadar iyi olduğunu ölçer ve ardından bulutu bir sonraki tur için yeniden şekillendirir. Bulut basit bir küre değildir - iyileşmeye yol açan yönleri hatırlayarak indiği vadinin uzatılmış, eğimli şeklini öğrenir. Ardışık nesiller boyunca bulut daralır ve kayıp yüzeyinin eğriliğiyle hizalanacak şekilde eğilir, bu da algoritmanın daha basit yöntemleri tuzağa düşürecek uzun dar vadilerde gezinmesini sağlar.

Tarih

Evrim stratejileri, biyolojik evrimden esinlenen popülasyon tabanlı optimize ediciler ailesi olarak 1960'lar ve 1970'lerde tanıtıldı. Kovaryans matrisi uyarlama mekanizması Hansen ve Ostermeier tarafından geliştirildi ve 2001 tarihli Evrimsel Hesaplama makalelerinde tam olarak açıklandı; bu makale, tamamen rastgeleleştirilmemiş kendi kendine uyarlamanın - arama yüzeyinin tam ikinci dereceden geometrisini başarılı adımların geçmişinden öğrenmenin - kötü koşullandırılmış ve ayrılabilir olmayan problemlerde önceki evrim stratejilerinden önemli ölçüde daha iyi performans gösterdiğini gösterdi. Hansen'in 2016 ders anlatımı (tutorial) algoritmayı ve kuramsal özelliklerini pekiştirerek CMA-ES'yi sürekli kara kutu optimizasyon kıyaslaması için standart referans yöntemi haline getirdi.

Ne zaman kullanılır?

CMA-ES, hedef işlevin sürekli, muhtemelen dışbükey olmayan, çok modlu veya gürültülü olduğu ve gradyan bilgisinin mevcut olmadığı veya hesaplanmasının çok pahalı olduğu durumlarda uygundur. İdeal boyut aralığı kabaca 10 ila 1000 parametredir; 10 boyutun altında daha basit yöntemler genellikle yeterlidir ve 1000'in üzerinde kovaryans matrisinin karesel bellek maliyeti engelleyici olabilir. İstatistiksel anlamda minimum örnek boyutu gereksinimi yoktur - algoritma kendi değerlendirme noktalarını üretir. CMA-ES, hiperparametre ayarlama, sinir mimarisi araması (NAS), pekiştirmeli öğrenme politika optimizasyonu ve simülatörün yalnızca kara kutu çıktıları sağladığı mühendislik tasarım problemleri için doğal bir uyumdur.

Sınırlar ve dikkat edilmesi gerekenler

  • Boyut sayısına göre karesel bellek ve nesil başına hesaplama maliyeti, boyut indirgeme türevleri olmadan kabaca 1000 parametrenin ötesinde uygulanabilirliği sınırlar.
  • Yeniden başlatmalar yokluğunda yerel bir optimuma yakınsar; yüksek derecede çok modlu arama yüzeyleri için, birden fazla yeniden başlatma (IPOP-CMA-ES veya BIPOP-CMA-ES) gereklidir.
  • Ayrık veya kombinatoryal arama alanlarına uygun değildir - yöntem doğası gereği sürekli reel değerli vektörler üzerinde tanımlanmıştır.

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

Güçlü yönleri

  • Gradyan bilgisi gerektirmez - gürültülü veya simülasyon tabanlı olanlar da dahil olmak üzere herhangi bir çağrılabilir (callable) hedef işlev üzerinde çalışır.
  • Kovaryans uyarlaması yoluyla arama yüzeyinin yerel eğriliğini öğrenir; böylece arama dağılımı sabit olan, gradyan kullanmayan yöntemlerin başarısız olduğu uzamış ve kötü koşullanmış arama uzaylarında gezinebilir.
  • Hedef işlevin sırayı koruyan dönüşümlerine ve arama uzayının döndürmelerine karşı değişmezdir, bu da onu geniş bir problem geometrisi çeşitliliğinde dayanıklı kılar.
  • Orta ila yüksek boyutlu sürekli problemler (10-1000 parametre) için tek bir ayarlanabilir hiperparametre - başlangıç adım boyutu - ile iyi uyum sağlar.

Uygulama alanları

  • Sinir ağı mimarileri ve pekiştirmeli öğrenme ajanları dahil olmak üzere makine öğrenimi modelleri için hiperparametre ayarlama.
  • Sinir mimarisi araması (NAS) - sürekli gevşetme yoluyla ayrık kodlanmış mimari parametrelerinin optimizasyonu.
  • Politikanın sürekli bir vektörle parametrelendirildiği durumlarda pekiştirmeli öğrenme politika optimizasyonu.
  • Yalnızca simülatör çıktılarının mevcut olduğu aerodinamik şekil optimizasyonu ve yapısal parametre uyumu gibi mühendislik tasarım optimizasyonu.
  • Bilimsel model kalibrasyonu - olasılığın türevlenemez veya hesaplama açısından pahalı olduğu durumlarda simülasyon modellerini deneysel verilere uyarlama.

Nasıl çalışır?

Nasıl çalışır?

1

Algoritma, başlangıç çözüm vektörü ve başlangıç adım boyutu (sigma) ile başlatılır. Kovaryans matrisi, kimlik matrisi - mükemmel küresel bir arama bulutu - olarak başlar. Popülasyon boyutu ayarlanır, tipik olarak 4 + floor(3 * ln(boyut)) civarında.

2

Her nesilde, mevcut çok değişkenli normal dağılımdan, ortalama vektörü, adım boyutu ve kovaryans matrisi ile tanımlanan bir aday çözümler popülasyonu örneklenir. Dağılım çok değişkenli normal olduğundan, örnekler hem mevcut en iyi tahmini hem de arama uzayının öğrenilmiş şeklini yansıtır.

3

Her aday çözüm hedef işleva iletilir ve bir uygunluk puanı alır. Gradyan bilgisi gerekmez - yalnızca her örneklenmiş noktadaki skaler hedef değer gereklidir. Bu, CMA-ES'yi gürültülü, türevlenemez ve simülasyon tabanlı hedefler için uygun hale getirir.

4

Ortalama, daha iyi sıralanmış çözümlere doğru hareket ettirilir. Kovaryans matrisi ve adım boyutu, iyi iyileştirmeler üreten yönlerin bir sonraki nesilde daha olası hale gelmesi için iki tamamlayıcı uyarlama yolu - rank-bir (rank-one) ve rank-mu güncellemeleri - kullanılarak güncellenir. Bu, CMA-ES'nin arama yüzeyinin yerel geometrisini öğrendiği temel mekanizmadır.

5

Algoritma, bir durdurma kriteri karşılanana kadar örnekleme-değerlendirme-güncelleme döngüsünü tekrarlar: maksimum işlev değerlendirme sayısı, ortalama veya adım boyutundaki değişiklik üzerinde bir tolerans veya kovaryans matrisinin dejenerasyonunun tespiti. Tüm nesiller boyunca bulunan en iyi çözüm döndürülür.

Sık yapılan hatalar

  • Başlangıç adım boyutunu çok küçük ayarlamak, aramayı dar bir komşulukta tuzağa düşürür ve keşfi engeller; çok büyük ve erken nesiller optimumdan uzakta değerlendirmeleri boşa harcar. Yaygın bir kural, optimumun başlangıç noktasının yaklaşık üç sigma içinde yer alacak şekilde sigma'yı ayarlamaktır.
  • CMA-ES'yi çok düşük boyutlu problemlere (beş parametreden az) uygulamak genellikle israftır - daha basit ızgara araması veya Nelder-Mead yeterlidir ve CMA-ES'nin popülasyon ek yükü yarar sağlamaz.
  • Çok modlu bir arama yüzeyi üzerinde yalnızca tek bir CMA-ES örneği çalıştırmak, global optimumu kaçırma riskini taşır; arama yüzeyinin yüksek derecede çok modlu olduğu bilindiğinde çoklu başlatma veya popülasyon tabanlı yeniden başlatma stratejileri (IPOP/BIPOP) kullanın.
  • Yeniden başlatma doğrulaması yapmadan döndürülen en iyi çözümü gerçek global optimum saymak yaygın bir hatadır — hedef işlev yüksek derecede dışbükey olmadığında sonucu her zaman birden fazla bağımsız çalıştırmayla doğrulayın.

Sık sorulan sorular

CMA-ES, basit bir genetik algoritmadan nasıl farklıdır?

Klasik bir genetik algoritma bir popülasyonu korur ve sabit operatörlerle çaprazlama ve mutasyon uygular. CMA-ES bunun yerine popülasyonu çok değişkenli normal bir dağılımdan örnekler olarak modeller ve bu dağılımı - ortalamasını, adım boyutunu ve tam kovaryans matrisini - hangi çözümlerin başarılı olduğuna dayanarak sürekli olarak uyarlar. Bu, CMA-ES'nin kayıp yüzeyinin şeklini öğrenmesini ve sabit operatörlere sahip bir genetik algoritmadan çok daha verimli bir şekilde ilişkili, kötü koşullandırılmış alanlarda gezinmesini sağlar.

CMA-ES global optimumu bulmayı garanti eder mi?

Hayır. CMA-ES, tek bir çalıştırmanın yerel bir optimuma yakınsayabileceği anlamında yerel bir arama yöntemidir. Çok modlu arama yüzeyleri için, arama uzayının kapsamını iyileştirmek üzere birden fazla bağımsız yeniden başlatma - muhtemelen artan popülasyon boyutlarıyla (IPOP-CMA-ES) - önerilir.

Ayarlanacak en önemli hiperparametre nedir?

Başlangıç adım boyutu sigma, en etkili tek hiperparametredir. İyi bir sezgisel, optimumun başlangıç noktasının kabaca üç sigma içinde yer alacak şekilde ayarlanmasıdır. Popülasyon boyutu ve maksimum değerlendirme sayısı ikincil kontrollerdir; varsayılan popülasyon boyutu formülü (4 + floor(3 * ln(boyut))) pratikte iyi çalışır.

CMA-ES gürültülü hedef işlevleri işleyebilir mi?

Evet. CMA-ES yalnızca popülasyondan sıra bilgisi - mutlak işlev değerleri değil - kullandığı için gürültüye nispeten dayanıklıdır. Yüksek derecede gürültülü değerlendirmeler için, popülasyon boyutunu artırmak veya aday başına birden fazla değerlendirmeyi ortalamak dayanıklılığı daha da artırabilir.

İlgili yöntemler

Kaynaklar

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    DOI kaynağını aç
    Kopyalandı.
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

    Yayın kaynağını aç
    Kopyalandı.