Genetik Algoritma

Genetik algoritma (GA), Charles Darwin'in doğal seçilim ve evrim teorisinden ilham alınarak geliştirilmiş, sezgisel arama ve optimizasyon yöntemidir. 1960'lı yıllarda John Holland tarafından temelleri atılan bu yöntem, biyolojik evrim süreçlerini — seçilim, çaprazlama (rekombinasyon) ve mutasyon — hesaplamalı bir çerçeveye aktararak karmaşık problemlerin çözümünde kullanılır. Genetik algoritmalar, kesin çözüm yöntemlerinin yetersiz kaldığı büyük ve çok boyutlu arama uzaylarında iyi kaliteli çözümler bulmak amacıyla bilgisayar bilimi, mühendislik, ekonomi ve biyoinformatik gibi pek çok alanda yaygın biçimde uygulanmaktadır.

Genetik algoritmaların kökeni, 1950'lerin sonlarında ve 1960'larda evrimsel hesaplama alanında yapılan ilk çalışmalara dayanır. Konrad Zuse ve Nils Aall Barricelli gibi araştırmacılar, bilgisayar ortamında evrimi simüle etmeye yönelik erken denemeler gerçekleştirmiştir. Ancak bu alanın asıl kurucusu olarak kabul edilen John Holland, 1975 yılında yayımladığı Adaptation in Natural and Artificial Systems (Doğal ve Yapay Sistemlerde Uyum) adlı kitabıyla genetik algoritmaları sistematik biçimde tanımlamış ve teorik temellerini oluşturmuştur.¹

Holland'ın öğrencisi David E. Goldberg, 1989 yılında yayımladığı Genetic Algorithms in Search, Optimization, and Machine Learning adlı eseriyle genetik algoritmaları geniş bir mühendislik kitlesine tanıtmış ve alanın popülerleşmesinde belirleyici rol oynamıştır. 1990'lı yıllardan itibaren bilgi işlem gücünün artmasıyla birlikte GA uygulamaları hız kazanmış; 2000'li yıllarla birlikte derin öğrenme ve büyük veri alanlarıyla entegre edilen hibrit yaklaşımlar geliştirilmiştir.

Genetik algoritmada bir çözüm adayı, biyolojideki kromozomla özdeşleştirilen bir birey (individual) olarak temsil edilir. Belirli sayıda bireyin bir araya gelmesiyle oluşan kümeye popülasyon adı verilir. Her birey, çözüm uzayındaki bir noktayı kodlayan bir veri yapısıdır. Klasik uygulamalarda bu yapı ikili (binary) dizilerden oluşur; ancak gerçel sayılı, permütasyon tabanlı veya ağaç yapılı temsiller de yaygın biçimde kullanılır.²

Bir bireyin her bir bileşeni gen, genin aldığı değer ise alel olarak adlandırılır. Bireyin tüm gen dizisini kapsayan yapı genotip; bu genotipten üretilen somut çözüm ise fenotip olarak tanımlanır.

Uygunluk fonksiyonu (fitness function), her bireyin çözüm kalitesini sayısal olarak değerlendiren temel ölçüttür. Bir optimizasyon probleminde uygunluk fonksiyonu, bireyin temsil ettiği çözümün amaç fonksiyonu değerine karşılık gelir. Algoritmanın başarısı büyük ölçüde uygunluk fonksiyonunun doğru tanımlanmasına bağlıdır; yanlış veya yetersiz tanımlanmış bir uygunluk fonksiyonu, algoritmanın yanlış yönde evrilmesine yol açar.

Genetik algoritma, yinelemeli bir döngü biçiminde çalışır. Her yineleme bir nesil (generation) olarak adlandırılır ve aşağıdaki aşamalardan oluşur:

Algoritma, genellikle rastgele üretilmiş bir başlangıç popülasyonuyla başlar. Popülasyon büyüklüğü, problemin karmaşıklığına ve hesaplama kapasitesine göre belirlenir; tipik olarak onlarca ile birkaç yüz birey arasında değişir. Başlangıç popülasyonunun çeşitliliği, algoritmanın arama uzayını geniş biçimde taraması açısından kritik öneme sahiptir.

Seçilim (selection) aşamasında, bir sonraki nesli oluşturmak üzere ebeveyn bireyler belirlenir. Uygunluk değeri yüksek olan bireylerin seçilme olasılığı daha fazladır; ancak düşük uygunluklu bireylerin de seçilebilmesi, genetik çeşitliliğin korunması açısından önem taşır. Yaygın seçilim yöntemleri şunlardır:

• Rulet tekerleği seçimi: Her bireyin seçilme olasılığı, uygunluk değerinin toplam uygunluğa oranıyla belirlenir.
• Turnuva seçimi: Rastgele seçilen küçük bir alt gruptan en uygun birey kazanan ilan edilir.
• Sıralama seçimi: Bireyler uygunluk değerlerine göre sıralanır ve seçilme olasılıkları sıralamaya göre atanır.

Çaprazlama (crossover / recombination), seçilen iki ebeveyn bireyin genetik bilgilerini birleştirerek yeni bireyler (döller) oluşturma işlemidir. Bu işlem, biyolojik rekombinasyonun hesaplamalı karşılığıdır. Başlıca çaprazlama türleri şunlardır:

• Tek noktalı çaprazlama: Kromozom üzerinde rastgele belirlenen bir kesim noktasından ebeveynlerin genleri değiş tokuş edilir.
• Çok noktalı çaprazlama: Birden fazla kesim noktası kullanılarak daha karmaşık gen karışımları elde edilir.
• Tekdüze çaprazlama (uniform crossover): Her gen, ebeveynlerden eşit olasılıkla alınır.

Mutasyon, bir bireyin genlerinde düşük olasılıkla gerçekleştirilen rastgele değişikliklerdir. Bu işlem, popülasyonun yerel optimumlara sıkışmasını önler ve arama uzayında yeni bölgelerin keşfedilmesine olanak tanır. İkili kodlamada mutasyon genellikle bir bitin 0'dan 1'e veya 1'den 0'a çevrilmesi biçiminde gerçekleşir. Mutasyon olasılığı genellikle düşük tutulur (%0,1–%5 aralığında), aksi takdirde algoritma rastgele aramaya dönüşür.

Bazı uygulamalarda elitizm stratejisi benimsenerek mevcut neslin en iyi bireyleri değiştirilmeden bir sonraki nesle aktarılır. Bu yaklaşım, algoritmanın her nesilde en az bir önceki nesil kadar iyi bir çözüme sahip olmasını güvence altına alır. Çaprazlama ve mutasyon işlemlerinden geçen döller ile elitist bireyler bir araya getirilerek yeni popülasyon oluşturulur.

Kaynak: Vikipedi

Genetik algoritmanın performansı büyük ölçüde aşağıdaki parametrelerin doğru ayarlanmasına bağlıdır:

Bu parametreler arasındaki denge, keşif (exploration; yeni bölgelerin aranması) ile sömürü (exploitation; bilinen iyi bölgelerin derinlemesine incelenmesi) ikilemi olarak tanımlanır ve optimizasyon literatüründe temel bir tasarım sorununu oluşturur.

Genetik algoritmalar, çok sayıda alanda pratik uygulama bulmuştur:

Mühendislik tasarımı: Yapısal optimizasyon, anten tasarımı, devre düzeni ve hava aracı şekillendirme problemlerinde kullanılmaktadır. NASA'nın 2006 yılındaki ST5 uydu programında anten tasarımı genetik algoritmayla gerçekleştirilmiştir.³

Çizelgeleme ve lojistik: Gezgin satıcı problemi (TSP), araç rotalama, üretim çizelgeleme ve personel planlaması gibi NP-zor kombinatoryal problemlerde etkili sonuçlar elde edilmektedir.

Makine öğrenmesi ve yapay sinir ağları: Hiperparametre optimizasyonu, özellik seçimi ve sinir ağı mimarisi arama (nöroevrim) alanlarında yaygın biçimde kullanılmaktadır. Neuroevolution of Augmenting Topologies (NEAT) bu uygulamanın önemli örneklerinden birini oluşturur.

Biyoinformatik: Protein yapısı tahmini, ilaç molekülü tasarımı, gen ifadesi analizi ve filogenetik ağaç oluşturma gibi hesaplamalı biyoloji problemlerinde kullanılmaktadır.

Oyun ve yapay zeka: Oyun oynama stratejilerinin öğrenilmesi ve yapay zeka ajanlarının davranış kurallarının evrimsel yöntemlerle geliştirilmesinde uygulanmaktadır.

Temel genetik algoritma modeli üzerine pek çok varyant geliştirilmiştir:

Birden fazla çelişen amaç fonksiyonunu aynı anda optimize etmek üzere tasarlanmış bu varyantlar, Pareto-optimal çözüm kümeleri üretir. NSGA-II (Non-dominated Sorting Genetic Algorithm II) ve MOEA/D bu alandaki en yaygın algoritmalardandır.⁴

Popülasyonun birden fazla alt gruba (ada modeli) bölünerek paralel işlemciler üzerinde ayrı ayrı evrildiği yaklaşımlardır. Adalar arasındaki göç operatörü, çeşitliliğin korunmasını sağlar.

Rainer Storn ve Kenneth Price tarafından 1995 yılında önerilen diferansiyel evrim, çaprazlama operatörü yerine vektör farkı tabanlı bir pertürbasyon mekanizması kullanır ve sürekli optimizasyon problemlerinde yüksek performans gösterir.

Genetik algoritmalar güçlü bir araç olmakla birlikte bazı önemli sınırlılıklar barındırmaktadır. Algoritmanın çözüme yakınsaması garanti edilmemekte; özellikle parametre seçimi yetersiz kaldığında yerel optimumlara takılma riski ortaya çıkmaktadır. Uygunluk fonksiyonunun her değerlendirmesi hesaplama maliyeti gerektirdiğinden, yüksek maliyetli simülasyonlarla birleştirildiğinde toplam hesaplama süresi önemli ölçüde uzayabilir. Bunun yanı sıra, neden belirli bir çözüme ulaşıldığını açıklamak güçtür; bu durum yorumlanabilirlik açısından bir dezavantaj oluşturur. Son olarak, hiperparametre ayarının problem bazında deneyim gerektirmesi, yöntemin genel kullanımını zorlaştırmaktadır.