Genetik Algoritma Nedir? Genetik Algoritma Nasıl Çalışır?

Genetik Algoritma, evrimsel hesaplama algoritmalarının ilki ve en bilinenidir. Charles Darwin’in “En güçlü ve en akıllı bireyler değil, değişime en iyi adapte olan bireyler yaşam mücadelesini sürdürür” mealindeki bir sözü üzerine bina edildiği belirtilen Genetik Algoritma, optimizasyon problemlerini çözmeyi amaçlamaktadır.

En iyi adapte olan bireyler kısmını daha iyi anlatabilmek için şu şekilde bir örnek verilebilir. Örneğin bir ülkedeki nüfusun kalitesini kontrol altına almak istiyorsunuz. Bunu insanları iyi insanlar ve kötü insanlar olarak ayırıp, sonra kötü insanları yok edip, daha sonra iyi insanların iyi insanlarla çiftleşmeleri sonucunda iyi çocuk bireylerle toplumun kalitesini artırmayı teorik olarak hedefleyebilirsiniz lakin her zaman iyi anne babalardan iyi çocuklar doğmayabilir. Ayrıca kötü bireyleri yok etmekte epey vahşice bir yaklaşım oldu 🙂

Canlının en küçük yapı taşı hücredir. Genetik Algoritma hücre yapısını taklit ederek bilgileri saklar.

Bilgiler temel GA’da ikili(binary) formda tutulmaktadır. Sonraki süreçte sürekli ve ayrık değerler ile çalışan GA’larda önerilmiştir.

En temel anlamda bir GA aşağıdaki akış şemasına uygun çalışır:

Yukarıdaki adımları Knapsack (Sırt Çantası) Problemi üzerinde ayrıntılı olarak anlatıp, izah etmeye çalışalım.

Örneğin maksimum 30 kg alan çantanıza alacağınız eşyalarla doğada yaşamaya çalışacaksınız ve bunun için Survival Points kısmını maksimum yapmaya çalışacaksınız. Hangi ürünleri yanınıza alacaksınız?

Mesela Glucose + Sleeping Bag=35 kg olduğundan ikisi birlikte alınamamaktadır. Bu iki eşya puanı en yüksek olanlar olduğu için direk onları seçtim ama ağırlık kısıtına takıldım, o yüzden başka ürünler seçmeliyim.

Şimdi bu problemi Genetik Algoritma ile çözülecek hale getirelim.
6 farklı ürün olduğundan maksimum 6 ürün alabiliriz, minimum 0 ürün alabiliriz. Bir ürünün alınıp, alınmayacağını ise 0 ve 1 sayıları ile belirtebiliriz. Başlangıçta kendi belirleyeceğimiz kadar birey ile popülasyonu oluşturuyoruz:

Burada A1,A2,A3,A4 bireylerimizdir. Hepsi 6 boyutludur.

Şimdi sırada amaç fonksiyonu yazmada. Amacımız en çok Survival Points değerine ulaşmak, dolayısıyla seçtiğimiz ürünlerin değerlerini toplamamız gerekiyor lakin maksimum çanta ebatımız 30 kg, bunu göz önünde bulundurmalıyız.

A1 kromozomu için [100110] hesaplayalım:

A2 kromozomu için [001110] hesaplayalım:

Burada A1’in A2’ye göre daha fit olduğu görülmektedir.

Yeni bireyleri oluşturmak için bu fit bireyler kullanılır. Seçim işlemi için farklı yöntemler kullanılsa da biz burada Rulet Tekerleği Seçim Yöntemi ile aşağıdaki şekilde seçim yapılır:

Böylece her zaman en fit bireyler değil rastgeleliğe bağlı olarak daha düşük fitlikteki bireylerde seçilebilir.

İki atay birey seçildikten sonra çaprazlama (crossover) işlemi aşağıdaki şekilde yapılır. Literatürde bu işleme tek noktalı çaprazlama ismi verilmiştir.

Çok noktalı çaprazlama yapmak istersek:

Bu işlemin sonucunda iki ata bireyden iki yavru birey oluşturulmuş olur.

Bireyler atalarından özellik almakla beraber çevresel faktörlerde onların gelişimini etkilemektedir. Bu işleme de mutasyon adı verilir.

Mutasyon en basit haliyle bir boyuttaki bilginin terslenmesiyle yapılabilir.

Böylece yeni bireyler oluşmuş olur, bu bireylerin amaç fonksiyonu değeri hesaplandıktan sonra belirlenmiş olan sonlanma kriterine kadar süreç devam eder.

Sonlandırma kriteri ne olabilir?
-Başta belirlenmiş sabit jenerasyon sayısı kadar gelişim yapılır ve durdurulur.
-Başta belirlenmiş bir sayı kadar jenerasyonda amaç fonksiyonu gelişi olmazsa durdurulur.
-Amaç fonksiyon değeri belirlenmiş bir değere ulaştıysa durdurulur.

Kaynaklar:

Introduction to Genetic Algorithm & their application in data science

https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_fundamentals.htm
https://www.neuraldesigner.com/blog/genetic_algorithms_for_feature_selection