Rastgele Evrimsel Optimizasyon Arama
- Ortaya koyan
- Holland, J. H.
- Yıl
- 1975
- Tür
- Stochastic evolutionary metaheuristic
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Rastgele Genetik Algoritma (RGA), karmaşık, doğrusal olmayan veya birleştirilebilir uzaylarda tama yakın optimal çözümler aramak için biyolojik evrimi — seçilim, çaprazlama ve mutasyon — taklit eden popülasyon tabanlı bir meta sezgisel yöntemdir.
Rastgeleleştirilmiş operatörleri, onu yerel optimumlara karşı dayanıklı kılar ve mühendislik, çizelgeleme, makine öğrenmesi ve operasyonel araştırmalar alanlarında geniş çapta uygulanabilir hale getirir.
Yöntemin mantığı
Hayatta kalmak için rekabet eden bir aday çözüm popülasyonu hayal edin. Daha iyi çözümlerin ebeveyn olarak seçilme olasılığı daha yüksektir; yavruları iyi özellikleri miras alır ve yeniden birleştirir, ara sıra rastgele mutasyonlar ise yenilik getirir. Birçok nesil boyunca bu süreç, gradyan bilgisine ihtiyaç duymadan arama uzayının yüksek kaliteli bölgelerine yakınsar. Rastgele etiket, seçilim, çaprazlama ve mutasyonun hepsinin olasılıksal çekilişler içerdiğini vurgular, bu da kanonik GA'yı nadir deterministik varyantlardan ayıran ve ona küresel arama yeteneği kazandıran şeydir.
Tarih
John Holland, 1975'te Michigan Üniversitesi'nde genetik algoritmaların teorik temellerini tanıttı, Fraser'ın (1957) simüle edilmiş genetik sistemler üzerine yaptığı önceki çalışmalarından yararlandı. David Goldberg'in 1989 tarihli ders kitabı, mühendislik optimizasyonu için GA'ları popülerleştirdi. Seçilimin rastgele doğası, şema teoremi aracılığıyla biçimlendirildi ve yöntem, evrimsel hesaplama ve hesaplamalı zekanın temel taşı haline geldi.
Ne zaman kullanılır?
Rastgele Genetik Algoritma şu durumlarda kullanın: (1) arama uzayı büyük, çok modlu veya süreksiz ve gradyan tabanlı yöntemler başarısız olduğunda veya uygulanamadığında; (2) amaç fonksiyonu kara kutu, gürültülü veya değerlendirmesi pahalı ancak popülasyon düzeyinde örnekleme için elverişli olduğunda; (3) birleştirilebilir veya karma tamsayılı problemlerin verimli kesin çözücüleri olmadığında; (4) makul sayıda değerlendirme içinde bulunan tama yakın bir çözüm kabul edilebilir olduğunda. SGA'yı şu durumlarda KULLANMAYIN: problem dışbükey olduğunda veya gradyan mevcut ve ucuz olduğunda — klasik optimizasyon daha hızlı yakınsar; fonksiyon değerlendirmeleri son derece pahalı olduğunda (onlarca veya yüzlerce), popülasyon tabanlı yöntemler bütçeyi tüketebilir; veya kanıtlanabilir bir optimal çözüm gerektiğinde, çünkü GA'lar optimallik garantisi sunmaz.
Sınırlar ve dikkat edilmesi gerekenler
- Küresel optimumu bulma garantisi yoktur; çözüm kalitesi popülasyon büyüklüğüne, operatör seçimlerine ve nesil sayısına bağlıdır.
- Hesaplama açısından pahalıdır, pürüzsüz, düşük boyutlu problemler üzerinde gradyan tabanlı yöntemlere kıyasla — çok sayıda fonksiyon değerlendirmesi gereklidir.
- Hiperparametre ayarı (popülasyon büyüklüğü, çaprazlama oranı, mutasyon oranı) probleme bağlıdır ve genellikle deney gerektirir.
- Seçilim baskısı çok yüksekse veya mutasyon oranı çok düşükse erken yakınsama meydana gelebilir, bu da aramayı alt optimal bölgelere hapseder.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Gradyan bilgisi gerektirmez — kara kutu, süreksiz veya türevlenemez amaçlara uygulanabilir.
- Uygun kodlama ile birleştirilebilir, karma tamsayılı ve permütasyon arama uzaylarını doğal olarak işler.
- Tasarıma göre paralelleştirilebilir: duvar saati süresini azaltarak popülasyon paralel olarak değerlendirilebilir.
- Popülasyon çeşitliliği ve rastgele keşif sayesinde yerel optimumlara karşı dayanıklıdır.
- Son derece genişletilebilir: operatörler, kodlamalar ve seçilim şemaları alan özgü kısıtlamalar için özelleştirilebilir.
Uygulama alanları
- Üretim ve lojistikte iş-dükkanı ve akış-dükkanı çizelgelemesi
- Makine öğrenmesi işlem hatlarında özellik seçimi ve hiperparametre ayarı
- Makine ve inşaat mühendisliğinde yapısal ve topoloji optimizasyonu
- Operasyonel araştırmalarda gezgin satıcı ve araç rotalama problemleri
- Biyoenformatikte protein yapısı tahmini ve ilaç keşfi
- Sinir ağı mimarisi araması ve ağırlık optimizasyonu
Nasıl çalışır?
Nasıl çalışır?
Rastgele veya sezgisel tohumlama ile N aday çözümden (kromozom) oluşan bir başlangıç popülasyonu oluşturun. Her kromozom, karar uzayında uygun bir noktayı kodlar — seçilen problem temsiline bağlı olarak ikili dizeler, gerçek vektörler, permütasyonlar veya ağaçlar.
Amaç fonksiyonunu (veya bir vekilini) kullanarak popülasyondaki her birey için uygunluk f(x_i)'yi hesaplayın. Uygunluk, çözüm kalitesini ölçer; daha yüksek uygunluk daha iyi bir çözüm anlamına gelir. Minimizasyon problemleri için uygunluk genellikle maliyet fonksiyonunun tersi veya dönüşümü olarak tanımlanır.
Formül
f(x_i), \quad i = 1, \ldots, N
Ebeveynleri seçmek için rastgele bir seçilim operatörü uygulayın. Rulet çarkı (uygunluk-orantılı) seçilimi, her bireye uygunluğuna orantılı bir olasılık atar. Turnuva seçilimi, sıra seçilimi ve elitizm, seçilim baskısını kontrol eden yaygın varyantlardır.
Formül
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}p_c olasılığıyla (genellikle %0.6–0.9), yavrular üretmek için seçilen ebeveyn çiftlerini yeniden birleştirin. Tek noktalı, iki noktalı veya tekdüze çaprazlama, ebeveyn kromozomları arasında genetik materyal alışverişi yaparak her ikisinden de özellikler miras alan çocuklar oluşturur. Bu operatör, iyi yapı taşlarının sömürülmesini sağlar.
Düşük bir p_m olasılığıyla (genellikle gen başına %0.001–0.05), her yavru kromozomundaki bireysel genleri rastgele değiştirin. Mutasyon, genetik çeşitliliği korur, erken yakınsamayı önler ve algoritmanın yerel optimumlardan kaçabilmesini sağlar. Mutasyon oranı, probleme göre ayarlanmış kritik bir parametredir.
Mevcut popülasyonu yavrularla değiştirin (nesil değişimi) veya durağan durum güncellemeleri kullanın. Uygunluğu tekrar değerlendirin ve bir durdurma kriteri karşılanana kadar seçilim adımından tekrarlayın — maksimum nesil sayısı, bir uygunluk eşiği veya belirli sayıda nesil boyunca iyileşme olmaması.
Sık yapılan hatalar
- Çok yüksek bir mutasyon oranı kullanmak, algoritmayı etkili bir şekilde rastgele aramaya indirger ve birikmiş uygunluk kazançlarını bozar.
- Değiştirme stratejisinde elitizmi ihmal etmek, bulunan en iyi çözümün nesiller arasında kaybolmasına neden olabilir.
- İkili kodlanmış problemlere (veya tersi) gerçek değerli çaprazlama operatörleri uygulamak, kodlamayı bozar ve uygun olmayan yavrular üretir.
- Çok erken durdurma — yetersiz nesil — pratikte kötü çözüm kalitesinin en yaygın nedenidir.
- Kısıtları ele almayı ihmal etmek: kısıtlanmamış çaprazlama ve mutasyon genellikle problem kısıtlarını ihlal eder; ceza fonksiyonları veya onarım operatörleri açıkça dahil edilmelidir.
Sık sorulan sorular
Rastgele Genetik Algoritma, standart bir Genetik Algoritmadan nasıl farklıdır?
'Rastgele' etiketi, tüm temel operatörlerin — seçilim, çaprazlama ve mutasyon — olasılıksal çekilişler içerdiğini vurgular. Holland tarafından tanıtılan kanonik GA doğası gereği rastgeledir. Etiket, nadir deterministik varyantlardan (örneğin, deterministik kalabalıklaşma) ayırmak ve algoritmanın rastgelelik nedeniyle çalıştırmalar arasında değiştiğini netleştirmek için simülasyon/optimizasyon literatüründe kullanılır.
Popülasyon ne kadar büyük olmalı?
Orta boyutlu problemler için yaygın bir başlangıç noktası 50-200 bireydir. Daha büyük popülasyonlar çeşitliliği artırır ve erken yakınsamayı azaltır ancak nesil başına hesaplama maliyetini artırır. Kromozom uzunluğuna dayalı kaba kurallar (örneğin, gen sayısının 10 katı) mevcuttur, ancak ampirik ayarlama veya meta-optimizasyon genellikle gereklidir.
Ne zaman Parçacık Sürü Optimizasyonu veya Simüle Edilmiş Tavlama'yı Genetik Algoritma yerine tercih etmeliyim?
Parçacık Sürü Optimizasyonu (PSO), hız bilgisinden yararlandığı için sürekli gerçek değerli problemler üzerinde genellikle daha hızlıdır. Simüle Edilmiş Tavlama (SA), uygulaması daha basittir ve tek çözüm yörünge araması için etkili olabilir. GA'lar, arama uzayı birleştirilebilir olduğunda, çaprazlamanın çözüm yapılarını anlamlı bir şekilde yeniden birleştirdiğinde veya popülasyon çeşitliliğinin çok modlu manzaralar için değerli olduğu durumlarda tercih edilir.
Rastgele Genetik Algoritma yüksek boyutlu problemlere ölçeklenir mi?
Popülasyonun uzayı yeterince örnekleyecek kadar büyük olması gerektiğinden, performans çok yüksek boyutlarda (yüzlerce ila binlerce değişken) düşer. Bağlantı öğrenen GA'lar, dağılım algoritması tahminleri veya göçlü ada modelleri gibi özel varyantlar ölçeklenebilirliği ele alır ancak karmaşıklık ekler.
Bir Genetik Algoritmada kısıtları nasıl ele alırım?
Üç ana strateji kullanılır: (1) kısıt ihlalleri için uygunluğu azaltan ceza fonksiyonları; (2) uygun olmayan yavruları uygun bölgeye geri yansıtan onarım operatörleri; (3) yapım gereği yalnızca uygun çözümler üreten özel kodlamalar ve operatörler. Ceza tabanlı yöntemlerin uygulanması en kolay olanıdır ancak ceza katsayılarının dikkatli bir şekilde ayarlanmasını gerektirir.
İlgili yöntemler
Kaynaklar
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
ISBN: 978-0262581110Kopyalandı.Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.
ISBN: 978-0201157673Kopyalandı.