Genetik algoritma nedir?
Problem çözme tekniklerinden biri olan sezgisel (buluşsal ya da heuristic) yaklaşım ile sonucun doğruluğunun kanıtlanabilirliğinden ziyade verilen spesifik bir problem için iyiye en yakın çözüm yollarına odaklanılır. Meta-sezgisel yaklaşımda ise spesifik bir probleme odaklanılmaz, problem bağımsız bir yaklaşımdır.
Örneğin bir futbol robotu için en iyi atış hızının elde edilmek istendiğini ve problemin çözümü için spesifik bir sezgisel yöntem kullanıldığını düşünelim. Elde edilen yöntem buluşsal bir yöntem olacaktır. Bunun nedeni aynı yöntemin basketbol robotu için en iyi atış hızını elde etmek için kullanılması durumunda çözüme ulaşılması için faydalı olacağı anlamına gelmemesidir. Her iki robota da uygulanabilecek, parametreleri olan bir strateji tanımlanırsa bu meta-buluşsal bir yaklaşım olacaktır.
Bazı problemlerin çözümünde sezgisel yaklaşımlar yeterli olmadığı için meta-sezgisel yaklaşımlar kullanılır. Optimum sonuca ulaşılamadığında veya problemin çözümü gereğinden fazla vakit aldığında yapay zeka, yapay sinir ağları ve optimizasyon çalışmalarında meta-sezgisel yaklaşımın önemi ön plana çıkmaktadır.
Genetik algoritma doğal seçilim sürecinden ilham alan meta-sezgisel bir algoritmadır. Evrimsel algoritma sınıfına giren genetik algoritmalar mutasyon, çaprazlama ve seleksiyon gibi biyolojiden esinlenilmiş operatörlere dayanır. Optimizasyon ve arama problemlerinde yaygın olarak kullanılmakta olup, bir sonraki neslin yavrularını üretmek amacıyla üreme için en uygun bireylerin seçildiği doğal seçilim sürecini yansıtır.
Her canlının hücrelerinde ne olduklarını kodlayan bir dizi DNA vardır. Bu genetik kod boy, saç rengi, parmak sayısı gibi birçok özelliği tanımlar. İnsan gibi bir organizmada hücreler DNA'da gömülü olan planı izleyerek büyür ve gelişir.
Bir canlı doğduktan sonra içgüdüsel olarak hayatta kalmak ister. Bu amaç doğrultusunda tüm canlılar kaynak, barınak ve kendilerini koruyabilecekleri araçlar için savaşırlar. Bulunduğu çevreye en iyi uyum sağlayanın, piramitte en üstte olma şansı daha yüksektir. Uygun olan DNA yaşamaya devam eder ve kopyalanır, uygun olmayan DNA ise popülasyonda yavaş yavaş yok olur. Üreme sırasında oluşan mutasyonlar tamamen rastgeledir ve doğada canlıyı daha iyi hale getirmek amacıyla bilinçli karar vericiler tarafından yapılmazlar.
Canlıların DNA’sında üreme sırasında bazı değişiklikler gerçekleşebilmektedir. DNA’nın hiç değişmemesi durumunda, bir süre sonra popülasyon yalnızca klonlardan oluşacaktır. Mavi ve kırmızı kuşlardan oluşan bir popülasyonun mavi çalılarda saklanması gerekiyorsa, mavi kuşlar yaşarken kırmızı kuşların tamamına yakını ölecektir.
Doğada bir popülasyonun tamamının yalnızca mavi kuşlardan oluşması gibi bir durum pek olası değildir. Muhtemelen bazı kuşlar maviden farklı bir renkte olacak ve kırmızı bir çalıda saklanmak gibi koşullarda mavi kuşlara oranla daha yüksek hayatta kalma şansına sahip olacaklardır. Bu durum gelecekte doğacak yavruların bazılarının kırmızıya daha yakın bir renge sahip olmasına ve popülasyonun renginin yavaş yavaş değişmesine neden olabilecektir.
Doğal seçilim süreci, bir popülasyonda genlerin çeşitli faktörler yardımıyla nesiller boyunca bulunduğu ortama uyum sağlayıp hayatta kalmasını kapsar. Başka bir deyişle, yüksek yeteneğe sahip organizma mevcut ortamda hayatta kalabilecek niteliktedir ve gelecek nesile yeni organizmalar üretir. Düşük yeteneğe sahip organizma ise mevcut ortamında hayatta kalmak ve neslinin tükenmesini önlemek için iki seçeneğe sahiptir: Birincisi gelecek nesile yüksek yetenekli yavru üretmesini sağlayabilecek iyi nitelikte bir organizma ile eşleşmek, ikincisi ise organizmayı daha güçlü hale getirmeyi amaçlayan ve mevcut ortamında hayatta kalabilmesini sağlayacak genetik mutasyondur. İki seçenekten birini elde etmiş olmasına rağmen organizmanın çevrenin gereksinimlerini karşılayamaması durumunda nesli zamanla tükenebilir. Çevrenin organizmaları etkilediği ve organizmaların da çevreden etkilendiği bilinmektedir. Süreç içerisinde hem organizmalarda hem de çevrede değişiklikler olacaktır.
Genetik algoritmaların doğal seçilim ile ilişkisi ise sosyal sistemler olan canlı ekosistemlerinde meydana gelen doğal değişimleri taklit etmeyi, psikolojik sonuçları değerlendirmeyi ve değişken yöntemleri modellemeyi amaçlamasıdır. Genetik algoritma popüler bir arama ve optimizasyon yöntemidir. Hem organizma hem de çevreye dayalı arama alanının kontrol edilmesiyle genetik algoritmada çözüm çeşitliliği arttırılmış olur.
Genetik algoritma için örnek bi pseudo kod tanımlaması ve flowchart çizimi aşağıdaki şekilde oluşturulabilir.
a) Pseudo (sözde) kod & b) Flowchart
Genetik algoritmaların nasıl çalıştığını daha iyi anlayabilmek için, kullanılan bazı terimlerin tanımlarının öğrenilmesi gerekmektedir. Bu terimler DNA, fitness fonksiyonu, popülasyon, seleksiyon, crossover, mutasyon olarak sıralanabilir.
DNA: Bir botun (robot anlamında kullanılan bir terimdir ve bilgisayar işlemlerini yarı-otomatik olarak tamamlayabilmektedirler) nasıl davrandığını veya göründüğünü tanımlayan dizidir.
a) Başlangıç-Bitiş üzerine problemin tanımı & b) Olası yollar
Yukarıda solda yer alan görselde görülen başlangıç karesinden bitiş karesine en kısa yoldan ulaşmak istediğimizi düşünelim. Sağda yer alan görselde ve aşağıdaki görsellerde de görülebilen yollar botun nasıl davranacağını/hareket edeceğini tanımlayan dizilerdir. Bunlar iki örnek DNA’dır.
a) & b) Botun izleyebileceği olası yollar
Uygunluk (Fitness) Fonksiyonu: Botun ne kadar iyi iş çıkardığını anlamak için kullanılan bir ölçüttür. Botun DNA’sındaki tüm hareketleri yaptıktan sonra aşağıda solda görülebilen sarı kareye ulaştığını varsayalım.
a) Botun durabileceği olası noktalardan biri & b) Botun konumu ile bitiş arasındaki mesafe
Bunun anlamı bitiş noktasına olan mesafenin, yukarıda sağda da görülebilen, S olduğudur. S’yi bulabilmek için aşağıdaki görselde görülebilecek Sx ve Sy’nin bulunması gerekir. Sx ve Sy bulunup formülde yerine konulduktan sonra fitness fonksiyonunun değerine ulaşılabilir. Fitness değeri ne kadar düşükse, bot o kadar iyi performans gösterir.
Fitness Fonksiyonu
Popülasyon: Bir grup botu ifade etmektedir. Genetik algoritmalar yalnızca bir botu kullanmakla yetinmez, tüm popülasyonu kullanır. Algoritma her zaman tamamen rastgele DNA’lara sahip bir başlangıç popülasyonu ile başlar.
Popülasyon
Seleksiyon (Selection): Popülasyondan en iyi botları seçme ve yeni bir popülasyon oluşturma işlemidir. Bunun için ilk aşamada popülasyon, fitness değerine göre küçükten büyüğe sıralanır. Ardından en iyi (fitness değeri en küçük olan) n adet bot seçilir. Seleksiyonda n sayısının seçimi için spesifik bir kural yoktur.
Çaprazlama (Crossover): Seleksiyon aşamasında seçilen en iyi botlardan iki tanesini alıp DNA’larının karıştırılmasıdır. Oluşan yeni bot, yavru (offspring) olarak adlandırılır. En iyi botların alınıp DNA’larının karıştırılması ile offspring dizisi oluşturulur.
Çaprazlama (Crossover)
Mutasyon (Mutation): Oluşan bazı yeni yavrularda genlerden bazıları düşük olasılıkla mutasyona uğrayabilir. Bu, bit dizisindeki bazı bitlerin değişeceği anlamına gelir. Mutasyon, popülasyon içindeki çeşitliliği korumak için meydana gelir.
Bir kromozomda mutasyon öncesi ve sonrası durum
Genetik algoritmaların limitleri
Birçok önemli problemin çözümü için kullanılabilen genetik algoritmaların bazı limitleri bulunmaktadır: Genetik algoritmalar karmaşıklıkta iyi ölçeklenmezler. Mutasyona maruz kalan elementlerin sayısının fazla olduğu yerde, arama uzayı boyutunda genellikle üstel bir artış olur. Bu sebeple genetik algoritmalar karmaşıklığın arttığı yerde iyi sonuç vermez. Birçok problemde, genetik algoritmalar problemin optimumu yerine yerel optimumlara ve hatta keyfi noktalara yakınsama eğilimine sahiptir.
Genetik algoritmanın çalışma mantığına değindikten sonra klasik bir problem olan sırt çantası problemini genetik algoritma kullanarak inceleyelim.
Knapsack (Sırt Çantası) Problemi
Vahşi doğada bir ay geçireceğimizi, taşıyabileceğimiz tek şeyin maksimum 30 kg alabilen bir sırt çantası olduğunu ve aşağıdaki tabloda yer alan her bir ürünün de kendi “hayatta kalma puanı” olduğunu düşünelim. Knapsack probleminde amacımız hayatta kalma puanlarını en üst düzeye çıkarmaktır.
Knapsack probleminde çantada yer alan ürünler ve hayatta kalma puanları
Örneğin, ip ve çakı alırsak 3+2 kg için 7+10 hayatta kalma puanı almış oluruz. Problemi beş adımda aşağıdaki şekilde çözümleyebiliriz:
Adım 1: Başlangıç. İlk aşamada popülasyonumuz her biri kendi kromozom setine sahip bireyleri içerecektir.
Genetik algoritmada birinci adım: Başlangıç
Adım 2: Uygunluk (Fitness) Fonksiyonu. Yukarıdaki görselde de görülebileceği üzere her bir kromozomda 6 adet öğe (gen) bulunmaktadır. A1 kromozomu değerlerine göre sırasıyla aşağıdaki tablolar oluşturulur ve fitness fonksiyonuna ulaşılır, daha sonra aynı işlemi diğer kromozomlara da uygulanır.
A1 kromozomu için örneği inceleyelim:
A1 kromozomu için fitness fonksiyonu [100110]
A1 için toplam hayatta kalma puanı
A2 kromozomu için örneği inceleyelim:
A2 kromozomu için fitness fonksiyonu [001110]
A2 için toplam hayatta kalma puanı
Toplam değerlerden de görülebileceği gibi A1, A2'ye göre daha yüksek toplam hayatta kalma puanı sunduğundan daha uygundur.
Adım 3: Seleksiyon. Bu aşamada uygun kromozomlar seçilip onların yeni nesiller üretmesine izin verilebilir. Ancak bu birkaç nesil sonrasında birbirine daha yakın kromozomlar oluşmasına ve dolayısıyla daha az çeşitliliğe yol açacaktır. Bu nedenle genellikle Roulette Wheel seçim yöntemi kullanılmaktadır. Roulette Wheel seçim yönteminde her iki ebeveyn de tek seferde seçilebilir. Bu yöntem stokastik evrensel seçim yöntemi olarak bilinir.
Adım 4: Çaprazlama (Crossover). Seleksiyon neticesinde oluşan en iyi botlardan iki tanesi seçilerek DNA’ları karıştırılır ve bot yavrular (offspring) oluşturulur.
Çaprazlama adımı
Adım 5: Mutasyon. Büyümeleri sırasında çocukların genlerinde, onları ebeveynlerinden farklı kılan bazı değişiklikler olur.
Mutasyon adımı
Yukarıdaki adımlar sonucunda üretilen yavrular, uygunluk fonksiyonu kullanılarak tekrar doğrulanır ve uygun olduğu düşünülürse, popülasyondan daha az uygun olan kromozomların yerini alır. Tüm süreç popülasyonda x’ten fazla yineleme için herhangi bir geliştirme yok ise, uygunluk fonksiyonu önceden tanımlanmış değerine ulaştıysa veya algoritma için önceden mutlak bir nesil sayısı tanımlanmış ve bu sayıya erişilmişse sonlandırılır.
Kaynaklar
- Veri Bilimi Okulu, Genetik Algoritma
- Research Gate, Mutation operators applied to chromosomes in the proposed genetic algorithm
- Towards Data Science, Introduction to genetic algorithms including example code
