:::: MENU ::::
Evrimsel Hesaplama

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


Farksal Gelişim (Differential Evolution) Algoritması Nasıl Çalışır?

Diferansiyel Gelişim Algoritması (Differential Evolution Algorithm) başlıklı yazının altına yapılmış olan sitemli bir istek yorumu nedeniyle dilim döndüğünce Farksal Gelişim (Differential Evolution) Algoritması Nasıl Çalışır? adım adım anlatmaya çalışacağım.

Öncelikle evrimsel hesaplama algoritmaları ne için kullanılır? Bunu ilk bakışta anlamak zor gelebilir çünkü henüz tam olarak anladığımı iddia etmem de uygun olmamakla beraber Optimizasyon(Optimization), Sürekli Optimizasyon(Continuous Optimization), Kombinatoryal Optimizasyon (Combinatorial Optimization) kavramlarını bilmeniz, anlamanız için çok faydalı olacaktır. O yüzden Kombinatoryal Optimizasyon (Combinatorial Optimization) Nedir? yazısını okumanızı tavsiye ediyorum.

İlgili kaynakta da belirtildiği üzere “Bir çözüm tekniği olarak sezgisel, herhangi bir şeyin bulunmasını garanti etmeyen bir “arama” (seeking) metodu olarak tanımlanmaktadır”. Basit olması açısından 5 boyutlu x^2 fonksiyonunun çözümü için DE ile sezgisel arama işlemi nasıl yapılıyor inceleyelim.

5 boyutlu x^2 fonksiyonunu ne anlama geliyor?
f(x)=x1*x2*x3*x4*x5 şeklinde de gösterilebilir. Örneğin 5 boyutlu bilgimiz(1,1,1,1,1) olursa çıktımız 1^2+1^2+1^2+1^2+1^2=5 olacaktır. Yine aynı şekilde (5,5,5,5,5) olursa çıktımız 5^2+5^2+5^2+5^2+5^2=125 olacaktır. 1 boyutlu olsaydı f(x)=x1^2 ve 2 boyutlu olsaydı f(x)=x1^2+x2^2 şeklinde olacaktı.

Peki bu fonksiyonun minimum olduğu durum neresi? Yani hangi değerleri aldığı zaman bu fonksiyon minimum değerini alır. Fonksiyonun içerisinde verilen değerlerin karelerinin toplamı olduğundan sonucun negatif olması mümkün değildir ama girdi parametreleri negatifte olabilir. Örneğin (5,5,5,5,5) ile (-5,-5,-5,-5,-5) aynı sonucu yani 125 değerini vermektedir. Açıkça görüleceği üzere bu fonksiyonun minimum değeri 0’dır ve (0,0,0,0,0) değerlerini alması gerekmektedir.

Şimdi problemimiz için değer aralığımızın -100 ile +100 arasında olduğunu varsayalım. Yani en büyük değerimiz anlaşılacağı üzere (100,100,100,100,100)=50000 ve (-100,-100,-100,-100,-100)=50000 olacaktır. Demek ki 5 boyutlu Küre(Sphere) fonksiyonumuz için -100 ve +100 aralığında en büyük fonksiyon çıktı değeri 50000 iken en küçük değerimiz 0 olmaktadır.

Peki evrimsel hesaplama algoritmaları veya DE burada ne işe yarıyor? En can alıcı nokta burası çünkü zaten sonucu belli olan bir fonksiyonu çözmek ne işe yarayacak? Bu işe ilk başladığımda bana da çok anlamsız gelmişti, fakat öğrendikçe hoşuma gitmeye başladı 🙂 Zaten bütün olaylar böyle değil mi?

Şimdi DE algoritmasını sözde kod ile anlatmaya çalışalım. (Daha sonra Matlab ile ilgili bölümleri adım adım kodlayıp inceleyeceğiz)

1. Popülasyon problemin çözüm uzayı aralığında uniform dağılıma uygun olarak rastgele bir şekilde oluşturulur.
2. Sonlandırma kriterine erişilinceye kadar 3-6.adımları tekrar ediniz.
3. Popülasyondaki her bir birey i için 4-6.adımlar işlenir.
4. n1,n2,n3 bireyleri birbirinden ve i’den farklı olarak rastgele bir şekilde popülasyon içinden seçilir.
{Buradan da anlaşılacağı üzere DE en az 4 birey ile çalışmaktadır. Biz örnek olarak 10 birey ile çalıştığını varsayacağız. }
5. Popülasyondaki her birey için bir mutant bir de trial bireyler oluşturulur. Aşağıdaki şekilde mutant bireyi y olarak, trial bireyi z olarak belirtilerek nasıl hesaplandığı gösterilmektedir.
yz
6. Üretilen trial bireyin amaç fonksiyonu mevcut bireyin amaç fonksiyonundan daha iyiyse(minimizasyon için küçükse, maksimizasyon için büyükse) trial birey mevcut birey yapılarak popülasyon güncellenmiş olur.

En önemli kısım olan 5.aşamayı biraz daha detaylandıralım:

mutant birey oluşturulurken rastgele seçilen 2 bireyin farkı ile ölçekleme faktörü çarpılır ve rastgele seçilen 3.birey ile toplanır. Algoritmanın geliştiricileri F değerinin 0-2 arasında olması gerektiğini belirtmişlerdir. Probleme bağlı olmakla beraber önerilen parametre 0.8’dir.

Mevcut birey ile kıyaslanacak trial birey oluşturulurken ise CR parametresi devreye girmektedir Çaprazlama Oranı (Crossover Rate) olarak Türkçeleştirilebilecek bu parametre üretilen bir rastgele sayı ile kıyaslanarak bireyin boyutlarının mevcut bireyden mi yoksa mutant bireyden mi alacağını belirlemektedir. Olası tüm boyutların aynısının mevcut bireyden alınıp, mevcut birey ile trial bireyin aynı olmaması için en az bir boyutta mutant birey’den veri almak için j=jrand şartı koyulmuştur. CR parametresi 0-1 arasında seçilebilir. Önerilen değer 0.9’dur.

Şimdi adım adım kodlama ve oluşan sonuçları inceleyelim:

Başlangıç parametrelerini ayarlayalım:

Matlab’da Sphere.m dosyası içerisinde fonksiyonumuzu yazmamız gerekmektedir.

1. Popülasyon problemin çözüm uzayı aralığında uniform dağılıma uygun olarak rastgele bir şekilde oluşturulur ve amaç fonksiyonuna ilgili değerler gönderilerek obj değişki içerisinde fonksiyonun sonuçları oluşur.

İlk popülasyon aşağıdaki şekilde oluşmaktadır:

ilk-populasyon

Amaç fonksiyonu değerleri hesaplanır:

amac-fonksiyonu

Buradan en küçük değerin 10.bireye ait olduğu (5326.882578155483) görülmektedir.

4. n1,n2,n3 bireyleri birbirinden ve i’den farklı olarak rastgele bir şekilde popülasyon içinden seçilir. Bu işlem aşağıdaki şekilde kodlanabilir:

5. Popülasyondaki her birey için mutant ve trial bireyler aşağıdaki şekilde oluşturulabilir:

6. Üretilen trial bireyin amaç fonksiyonu mevcut bireyin amaç fonksiyonundan daha iyiyse(minimizasyon için küçükse, maksimizasyon için büyükse) trial birey mevcut birey yapılarak popülasyon güncellenmiş olur.

Bu şekilde 1.adım(iterasyon) tamamlanmış olur ve sonlandırma kriterine ulaşılıncaya kadar bu işlemler tekrar edilebilir.

Kabaca bir yorum yapmak gerekirse DE bireyler arasındaki farka göre yeni bir birey üretip, ürettiği birey mevcutlardan daha iyiyse yer değiştirme stratejisine dayalı bir yaklaşımdır.

1000 iterasyon sonucunda eldeki popülasyon ve amaç fonksiyonu değerleri de aşağıdadır:
En küçük değer: 1.297122623639887e-55 {Bilimsel gösterimin ne demek olduğunu bilmiyorsanız, öğrenmeniz faydanızadır.}

de-sphere-sonuc

DEA.m olarak isimlendirdiğim Matlab dosyası aşağıdadır.

Unutmamanız gerekenler bu yaklaşımlar rastgelelik üzerine bina edildiğinden her defasında farklı sonuçlar elde edilmektedir. Bu yüzden bilimsel çalışmalarda bu tarz algoritmalar aynı şartlar altında 30,50,100 kere çalıştırılıp, ortalamaları alınarak değerlendirilirler.

Umarım faydalı olmuştur. Bir eksik var ise hem benim kendimi düzeltmem, hem de insanların yanlış öğrenmemesi adına uyarırsanız çok sevinirim.

Bu yazının yazılmasına sebep olan Tınne’ye de teşekkür ederim. İlgili yorumlar aşağıdadır. 5 Mart’ta söz vermeme rağmen ancak yazabildim, umarım gecikmemişimdir. Kolay Gelsin.

tinne

Kaynaklar:
http://www.cleveralgorithms.com/nature-inspired/evolution/differential_evolution.html
http://www1.icsi.berkeley.edu/~storn/code.html