Genetik Algoritma

Genetik Algoritma ve Evrimsel Hesaplama

Genetik algoritma populasyon tabanlı stokastik bir algoritmadır. Her birey problemin çözümü olmaya adaydır. Bireyleri değerlendirme fonksiyonu probleme yönelik olarak çalışan en önemli kısımdır. Doğal seçim işlemi, uygunluk değeri en yüksek bireyin seçilmesini sağlar.

Populasyon: Çözüm kümesini oluşturan bireylerin tümüdür.

Mutasyon: Bir kromozomda rasgele yapılan değişikliktir.

Mating: Bireyler arasındaki eşlemedir.

Kromozom: Çözüm için kullanılan bireylerdir.

Populasyon→Eşleme Havuzu→Seçilen eşler→Eşleme→Yeni Nesil→Yeni Populasyon

Algoritmanın Çalışması

1- Başlangıç populasyonunu oluştur.

2- Her kromozomu uygunluk fonksiyonunda değerlendir.

3- Yeni populasyonlar için yeni kromozomlar oluştur. (Seçme, Çaprazlama, Mutasyon, Elitizm)

4- 2. ve 3. adımı bir çözüm bulunancaya kadar ya da belirli iterasyona gelene kadar tekrarla.

5- En iyi kromozomu çözüm olarak al.

Genetik Algoritmanın Performansını Etkileyen Faktörler

-Kromozom sayısı artarsa çalışma süresi artar. Azaltmak çeşitliliği yok eder.

– Mutasyon oranı yüksek bir değer olursa kararlı noktaya erişmek zor olur.

– Kaç noktalı çaprazlama yapılacağı faydası açısından önemlidir.

– Bireylerin değerlendirilmesi performansı etkiler.

– Uygunluk değerlendirmesinin yapılışı: Eğer tam bir değerlendirme fonksiyonu oluşturulmamışsa çalışma süresi uzar hatta hiçbir zaman çözüm bulunamayabilir.

Genetik Algoritmanın Avantajları

– Tek çözüm değil birden fazla optimum çözüm elde edilir.

– Çok sayıda parametrelerle çalışma imkanı olması.

– Amaç fonksiyonunu geniş bir spektrumda araştırması

– Karmaşık amaç fonksiyonu parametrelerini optimize eder.

İşlemler

– Çözümün vey bireyin gösterimi ve başlangıç populasyonunun oluşturulması

– Bireylerin değerlendirilmesi

– Bireylerin yeni topluluk için seçilmesi

– Yeni bir jenerasyon oluşturma

Populasyon Oluşturma

Bilinen bir çözüm kümesi alınır. Rasgele bireyler oluşturulur. Belirli kriterleri sağlayan bireyler oluşur.

Bireylerin Değerlendirilmesi

Kromozomların çözüme uygunluk değerleri belirlenir. Her bir problem için uygun bir değerlendirme fonksiyonu kullanılması gerekir. Tüm bireyler için değerlendirme yapılır. Probleme yönelik çalışan kısımdır.

Yeni Populasyon Oluşturma

Birey seçme, Elitizm, Seçilen iki bireyi çaprazlama, Bir bireyin herhangi bir geninin mutasyon işlemiyle rasgele değiştirilmesi.

Belirli sayıda en iyi olan bireyler ile yeni populasyon oluşturulur. Kötü bireyler populasyona katılmaz.

Rasgele Birey Seçme

Birey 1 f(x):45                %25 B1

Birey 2 f(x):21               %25 B2

Birey 3 f(x):9                 %25 B3

Birey 4 f(x):75               %25 B4

Rulet Tekerleği Birey Seçme

Birey 1 f(x):45            45/(21+75+9+45)=%30

Birey 2 f(x):21            21/(21+75+9+45)=%14

Birey 3 f(x):9              9/(21+75+9+45)=%6

Birey 4 f(x):75             75/(21+75+9+45)=%50

Turnuva Seçimi

Rasgele seçilen iki bireyden uygunluk derecesi yüksek olan bir sonraki populasyona aktarılır. İşlem populasyondaki kromozom sayısı kadar tekrarlanır.

Elitizm

Belirli sayıdaki en iyi birey hiçbir işleme tabii tutulmadan doğrudan yeni jenerasyona aktarılır. Elit birey sayısı arttıkça çözümdeki çeşitlilik azalır. Elit birey alınmazsa yeni jenerasyonun en iyi bireyi bir öncekinin en iyi bireyinden daha kötü olabilir.

Seçilen İki Bireyin Çaprazlanması

Rasgele çaprazlama noktaları seçilir. Yeni bireylerden ikiside populasyona aktarılabilir. Yeni elde edilen bireyden uygunluk seviyesi daha yüksek olan alınabilir.

Mutasyon

Herhangi bir sebep olmadan bir genin rasgele değiştirilmesidir. Populasyona çeşitlilik kazandırır. Mutasyon oranı 0.01 ile 0.0001 arasında seçilir.

**Genetik algoritmayla ilgili örnek bir problemi ve çözümünü bir sonraki yazımda paylaşacağım. Umarım işinize yarar.

Kolay gelsin..