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

Genetik Algoritma — Evrimsel Optimizasyon

Ortaya koyan
John Henry Holland
Yıl
1975
Tür
Population-based metaheuristic

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

Yazı boyutu

Ne işe yarar?

Genetik algoritma (GA), John Henry Holland (1975) tarafından tanıtılan ve doğal seçilim prensiplerini taklit eden, popülasyon tabanlı bir meta-sezgisel optimizasyon yöntemidir.

Aday çözümlerden oluşan bir popülasyonu sürdürür ve bunları seçilim, çaprazlama ve mutasyon operatörleri aracılığıyla iteratif olarak iyileştirir; bu da onu klasik gradyan tabanlı yöntemlerin başarısız olduğu kesikli, dışbükey olmayan ve çok modlu arama uzaylarında özellikle güçlü kılar.

Yöntemin mantığı

Zor bir probleme binlerce olası cevap olduğunu ve en iyisini bulmak için bir formül olmadığını hayal edin. Genetik algoritma, her bir aday cevabı bir popülasyondaki birey olarak ele alır. Her nesilde en uygun bireyleri tutar, iyi özelliklerini karıştırmak için onları birlikte yetiştirir ve yenilik katmak için zaman zaman yavruları mutasyona uğratır. Çok sayıda nesil boyunca popülasyon, bir gradyanı takip ederek değil, evrimin organizmaları zamanla nasıl şekillendirdiğini taklit ederek daha iyi ve daha iyi çözümlere doğru sürüklenir.

Tarih

Genetik algoritma, John Henry Holland tarafından 1975 tarihli Adaptation in Natural and Artificial Systems adlı kitabında tanıtıldı; bu kitap, bir şema (yapı taşı) kavramını biçimlendirdi ve çaprazlama ile seçilimin neden aramayı daha uygun bölgelere doğru yönlendirdiğine dair temel teorik analizi sağladı. Holland'ın öğrencileri — özellikle David Goldberg — 1980'lerde mühendislik uygulamaları aracılığıyla GA'ları popülerleştirdi. Kalyanmoy Deb daha sonra çerçeveyi çok amaçlı ayarlara genişletti ve yaygın olarak benimsenen NSGA-II algoritması (2002) ile sonuçlandı. Bugün GA'lar, yerel iyileştirme ile evrimsel aramayı birleştiren hibrit yöntemlerde aktif araştırmalarla birlikte evrimsel hesaplamada standart bir araç olmaya devam etmektedir.

Ne zaman kullanılır?

Genetik algoritmalar, arama uzayının büyük, kesikli, türevlenemez veya yüksek derecede çok modlu olduğu — gradyan tabanlı çözücülerin çalışamadığı veya yerel optimumlara takılıp kaldığı — durumlarda uygundur. Sürekli, kategorik, ikili ve sıralı değişken türlerine uygulanırlar ve herhangi bir normallik veya dağılım varsayımı getirmezler. Tek gereksinim hesaplanabilir bir uygunluk fonksiyonudur. Analitik veya dışbükey bir formülasyonun mevcut olduğu problemler için klasik yöntemler (doğrusal programlama, gradyan inişi) daha hızlıdır ve tercih edilmelidir. Anlamlı yakınsama için yeterli iterasyon (tipik olarak 1.000 neslin oldukça üzerinde) gereklidir; çok az nesil çalıştırmak en yaygın başarısızlık modudur.

Sınırlar ve dikkat edilmesi gerekenler

  • Küresel optimuma yakınsama garantisi yoktur; sonuçlar çalıştırmadan çalıştırmaya değişebilir.
  • Hesaplama açısından pahalıdır: her nesil tüm popülasyonun değerlendirilmesini gerektirir, bu da uygunluk fonksiyonu yavaş olduğunda yasaklayıcıdır.
  • Performans, hiperparametre seçimlerine — popülasyon boyutu, çaprazlama olasılığı ve mutasyon oranı — duyarlıdır ve bunlar genellikle probleme özgü ayarlama gerektirir.
  • Düzgün, dışbükey veya iyi yapılandırılmış problemler için, klasik gradyan tabanlı veya doğrusal yöntemler daha hızlı ve daha güvenilir olacaktır.

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

Güçlü yönleri

  • Kesikli, türevlenemez ve çok modlu hedef manzaralarında çalışan ve gradyan tabanlı yöntemlerin bozulduğu yerlerde işe yarar.
  • Herhangi bir dağılım varsayımı getirmez — gereken tek girdi hesaplanabilir bir uygunluk fonksiyonudur.
  • Geniş bir değişken türü yelpazesini doğal olarak işler: sürekli, ikili, kategorik ve sıralı.
  • Popülasyon çeşitliliği, arama uzayının birden fazla bölgesinin eş zamanlı keşfedilmesine olanak tanır, bu da erken yerel optimum tuzağı riskini azaltır.
  • Yüksek derecede genişletilebilir: alana özgü çaprazlama ve mutasyon operatörleri, kısıtlama işleme ve çok amaçlı varyantlar (örneğin, NSGA-II) literatürde iyi kurulmuştur.

Uygulama alanları

  • Mühendislik tasarımı optimizasyonu: yapılar, devreler veya mekanik sistemler için optimal parametre yapılandırmalarını bulma.
  • Zamanlama ve rota problemleri: iş atölyesi zamanlaması, araç rotalama ve ders programı oluşturma gibi kombinatoryal arama uzayının tükenmez arama için çok büyük olduğu durumlar.
  • Makine öğrenmesi: hiperparametre ayarlama, sinirsel mimari arama ve özellik seçimi.
  • Operasyon araştırması: tedarik zinciri optimizasyonu, portföy tahsisi ve karmaşık kısıtlamalar altında kaynak ataması.
  • Biyoenformatik: dizi hizalama, protein yapısı tahmini ve gen düzenleyici ağ çıkarımı.

Nasıl çalışır?

Nasıl çalışır?

1

Genellikle arama uzayında rastgele oluşturulan aday çözümlerden (bireylerden) oluşan bir popülasyon oluşturulur. Her birey, potansiyel bir çözümü — örneğin ikili bir dize, gerçek değerli bir vektör veya bir permütasyon olarak — kodlar ve popülasyon boyutu, başlangıçtan itibaren arama uzayının ne kadar geniş örneklemlendiğini belirleyen anahtar bir parametredir.

2

Popülasyondaki her birey, o çözümün problem hedefine göre ne kadar iyi olduğunu nicelendiren bir uygunluk fonksiyonu (fitness function) ile puanlanır. Uygunluk fonksiyonu, kullanıcının sağlaması gereken tek alan-spesifik bileşendir; hesaplanabilir herhangi bir ölçüm olabilir — bir simülasyon çıktısı, bir maliyet formülü veya bir model hata metriği.

3

Daha yüksek uygunluğa sahip bireyler, bir sonraki nesil için ebeveyn olmak üzere tercihen seçilir. Yaygın seçilim mekanizmaları arasında turnuva seçilimi, rulet tekerleği (uygunluk-orantılı) seçilimi ve sıra tabanlı seçilim bulunur. Seçilim baskısı, yüksek kaliteli çözümleri kullanma ile popülasyon çeşitliliğini koruma arasındaki ödünleşmeyi kontrol eder.

4

Seçilen ebeveynler, iki ebeveyn kodlamasının bölümlerinin yeni bir birey oluşturmak üzere birleştirildiği çaprazlama (rekombinasyon) ve bireysel genlere küçük rastgele değişikliklerin uygulandığı mutasyon yoluyla yavrular üretir. Çaprazlama olasılığı ve mutasyon oranı kritik ayarlama parametreleridir: çok az mutasyon erken yakınsamaya neden olur, çok fazla arama rastgele bir yürüyüşe dönüştürür.

5

Değerlendir → seç → üret döngüsü, belirli sayıda nesil boyunca veya bir yakınsama kriteri karşılanana kadar (örneğin, nesil penceresinde iyileşme olmaması) devam eder. Tüm nesiller boyunca bulunan en iyi birey çözüm olarak döndürülür. Küresel optimuma yakınsamanın garanti edilmediği göz önüne alındığında, yüksek riskli problemler için birden fazla bağımsız çalıştırma önerilir.

Sık yapılan hatalar

  • Çok az nesil çalıştırmak en yaygın hatadır: yetersiz nesil ile algoritma yakınsamaz, bu nedenle yalnızca küçük bir iterasyon bütçesi mevcut olduğunda analitik veya gradyan tabanlı yöntemler tercih edilmelidir.
  • Erken yakınsama — popülasyonun çok erken çeşitlilik kaybetmesi — yerel olarak optimal ancak küresel olarak suboptimal bir sonuç üretir; bunu önlemek için yeterli popülasyon boyutunu ve mutasyon oranını koruyun.
  • Kötü tanımlanmış veya yanlış belirtilmiş bir uygunluk fonksiyonu kullanmak, algoritmik doğruluğa bakılmaksızın yanıltıcı sonuçlar üretir; GA'yı çalıştırmadan önce uygunluk fonksiyonunu bağımsız olarak doğrulayın.
  • Gradyan inişin veya doğrusal programlamanın yeterli olacağı düzgün, dışbükey bir probleme GA uygulamak, hesaplama kaynaklarını boşa harcar ve gereksiz stokastiklik getirir.
  • Tek bir çalıştırmayı tekrarlanabilirliği kontrol etmeden çözüm olarak bildirmek; yüksek riskli uygulamalar için algoritmayı birden çok kez çalıştırın ve sonuçların dağılımını bildirin.

Sık sorulan sorular

Genetik algoritma, gradyan inişten nasıl farklıdır?

Gradyan inişi türevlenebilir bir hedef gerektirir ve yerel gradyanı aşağı doğru takip eder. Genetik algoritma yalnızca aday çözüm için uygunluğun hesaplanabilmesini gerektirir; bir gradyanı takip etmek yerine bir popülasyonu evrimleştirerek arama yapar, bu nedenle gradyan inişin başarısız olduğu veya takılıp kaldığı kesikli, türevlenemez ve çok modlu manzaraları işleyebilir.

Kaç nesil ve ne kadar büyük bir popülasyona ihtiyacım var?

Evrensel kurallar yoktur; her ikisi de arama uzayının karmaşıklığına bağlıdır. Çok küçük bir popülasyon veya çok kısa bir çalıştırma, erken yakınsama riski taşır. Pratik bir başlangıç ​​noktası olarak, 50-200 popülasyon boyutları ve 100-1.000 nesil sayısı literatürde yaygındır, ancak zorlu problemler rutin olarak daha fazlasını gerektirir. Keyfi durdurma kriterlerini sabitlemek yerine her zaman yakınsama eğrilerini inceleyin.

Genetik algoritmanın küresel optimumu bulması garanti midir?

Hayır. GA'lar sezgiseldir ve sonlu zamanda küresel optimuma yakınsama garantisi vermez. Deterministik garantiler için tam sayı programlama çözücüleri gibi kesin yöntemlere ihtiyacınız vardır. Yüksek riskli kararlar için GA'yı birden çok kez çalıştırın, sonuçların dağılımını bildirin ve en iyi çözümü bilinen herhangi bir sınıra göre karşılaştırın.

Simüle tavlama veya parçacık sürü optimizasyonu yerine ne zaman bir GA seçmeliyim?

GA'lar, çözümün doğal olarak kombinatoryal bir yapı (permütasyonlar, ikili dizeler) olarak kodlandığı veya çok amaçlı uzantıların gerektiği durumlarda tercih edilme eğilimindedir. Parçacık sürü optimizasyonu genellikle sürekli tek modlu problemlerde daha hızlıdır. Simüle tavlama, iyi tanımlanmış bir komşuluğa sahip kombinatoryal problemler için uygulaması daha basittir. Pratikte, birine karar vermeden önce iki veya üç yöntemi küçük bir problem örneğinde karşılaştırmak tavsiye edilir.

İlgili yöntemler

Kaynaklar

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    Yayın kaynağını aç
    Kopyalandı.
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ISBN: 9780471873396
    Kopyalandı.