:::: MENU ::::
Genetik Algoritma

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


GENETİK ALGORİTMA İLE BULANIK KURAL KÜMESİNİN OTOMATİK OLARAK OLUŞTURULMASINDA YENİ BİR YAKLAŞIM

“GENETİK ALGORİTMA İLE BULANIK KURAL KÜMESİNİN OTOMATİK OLARAK OLUŞTURULMASINDA YENİ BİR YAKLAŞIM” başlıklı Doktora tezi, Ersin KAYA tarafından hazırlanmış ve 23.12.2014 günü kabul edilmiştir.

İncelemek için:

genetik_algoritma_ile_bulanik_kural_kumesinin_otomatik_olarak_olusturulmasinda_yeni_bir yaklasim



An Adaptive Genetic Algorithm based on Population Diversity strategy

“An Adaptive Genetic Algorithm based on Population Diversity strategy” başlıklı çalışma Chen Lin tarafından yapılmış olup 2009 yılındaki Genetic and Evolutionary Computing, WGEC’09. 3rd International Conference on. IEEE, konferansında sunulmuştur.

Çalışmada mutasyon olasılığını popülasyon uygunluğunun ortalama karesel sapması temelinde dinamik olarak ayarlayan adaptif bir genetik algoritma önerilmiştir.

Genetik algoritmada;
Seçim işlemi popülasyon çeşitliliğini azaltır.
Çaprazlama işlemi popülasyon çeşitliliğini azaltmaz.(artırıp değiştirmediğine emin değilim!)
Mutasyon işlemi popülasyon çeşitliliğini artırır.

Mutasyon işleminin gerçekleştirilme olasılığı popülasyon çeşitliliğine etki eden en önemli unsurdur.

İlgili çalışmalar:

-Shen Yuan-xia, Zhang Cui-fang. A Modified Genetic Algorithm with Maintaining Diversity. Journal of system simulation. Vol.17 No.5, May 2005(1052-1053)

-Liu Zhi-ming,ZHOU Ji-liu,Chen Li. A Novel Genetic Algorithm Operator for Maintaining Diversity. Mini-Micro Ststem. Vol.24 No.5 2003.5

-Deng Li,Rui-Hua. An Improved Fuzzy Genetic Algorithm to suppress the Premature Convergence. Computer Science. 2007 Vol.34 No.11

Popülasyonun ortalama karesel sapması “ASD(average square deviation)” parametresi kullanılmıştır. ASD’nin büyük olması çeşitliliğin çok, küçük olması bireylerin birbirine benzediği anlamına gelmektedir.

Çalışmada ASD’ye bağlı olarak mutasyon olasılığı adaptif olarak değiştirilmiştir.

ASD her jenerasyonda aşağıdaki şekilde hesaplanmaktadır.

asd

Çalışmada;
1-Değerler gerçek sayı olarak kodlanmıştır.
2-Seçim işleminde hem belirli sayıda en iyi birey yeni jenerasyona aktarılmış, hem de Monte Carlo metoduyla iyi olan bireylerin birden fazla seçilmesine imkan tanınmıştır.
3-Çaprazlama işleminde birbirine en uzak olan iki birey alınır, böylece akraba evliliğinden kaçınılmış olur.
4-Mutasyon işlemi ASD parametresine bağımlı olarak yapılır. ASD düştükçe mutasyon olasılığı artırılır. İlişki aşağıdaki şekildedir:
pm

Çalışmayı indirmek için:

An_Adaptive_Genetic_Algorithm_based_on_Population_Diversity_strategy


Sayfalar:123