Ana içeriğe atla

Genetik Algoritmalar Bölüm IV (Seçim)

GA Akış şemasından da bildiğimiz gibi, kromozomlar toplum içerisinden çaprazlama için ata olmak için seçilmektedir. Problem bu kromozomları nasıl seçileceğidir. Darwin’in evrim teorisine göre en iyi olan yeni yavruyu yaratmak için yaşamına devam eder. Seçim düzeneklerine rulet tekeri seçimi, Boltzman seçimi, turnuva seçimi, sıralama seçimi, sabit durum seçimi ve diğerleri verilebilir.

Rulet Tekeri Seçimi: Atalar uygunluklarına göre seçilirler. Daha iyi kromozomlar, daha fazla seçilme şansına sahip olanlardır. Toplumdaki tüm kromozomların yerleştirildiği bir rulet tekerini hayal edelim. Rulet tekeri üzerindeki kromozomun yerinin boyutu kromozomun uygunluğuyla orantılıdır. Daha uygun olan kromozom daha geniş bir kısma sahip olur.

Bir bilye rulet tekerine atılmakta ve bilyenin durduğu yerdeki kromozom seçilir. Daha uygun olan kromozomlar böylece daha fazla sayıda seçilecektir.
Süreç aşağıdaki algoritma ile anlatılabilir.
Toplam: Toplumdaki tüm kromozomların uygunluk toplamını hesaplar - S.
Seçim: (0,S) aralığından rasgele bir sayı üretilir - r.
Döngü: Toplum üzerinden gidip 0’dan itibaren uygunlukların toplamını al - s, s r’den büyük olduğu zaman dur ve bulunduğumuz yerdeki kromozomu döndür.
Elbette, aşama bir her toplum için bir kez yapılmaktadır.
Sıralama Seçimi: Bir önceki seçim düzeneğinde uygunluk değerleri arasında büyük farklar oluşunca problemler ortaya çıkacaktır. Örneğin, eğer en iyi kromozomun uygunluğu diğer tüm kromozomların toplamının %90’ı ise diğer kromozomların seçilme şansı çok azalacaktır.
Sıralama seçimi ilk önce toplumu sıralar ve her kromozom uygunluk değeri olarak sırasını kullanır. En kötü 1 uygunluğunu, ikinci kötü 2,…., en iyi N (toplumdaki kromozom sayısı) uygunluğunu alır.
Uygunluk sıraya göre belirlendiği zaman durum değişmektedir.

Bu şekilde tüm kromozomların seçilme şansı olacaktır. Ancak bu yöntem daha yavaş yakınsama neden olabilir, çünkü en iyi kromozomlar birbirlerinden çok farklı değillerdir.
Sabit Durum Seçimi: Bu özel bir ata seçme yöntemi değildir. Bu tip seçimin ana fikri, toplumun var olan kromozomlarının büyük bir kısmının yeni nesle aktarılmasıdır.
Sabit durum seçimi şu şekilde çalışmaktadır. Her yeni nesilde yüksek uygunluk değerine sahip kromozomlar yeni yavruları oluşturmak için seçilir ve düşük uygunluk değerine sahip yavrular kaldırılarak yerlerine bu yeni oluşturulan yavrular koyulur. Toplumun geri kalan kısmı aynen yeni nesle aktarılır.
Seçkinlik (Elitizm): Seçkinliğin ana fikri daha önce açıklandı. Çaprazlama ve Mutasyon yöntemleriyle yeni bir nesil oluştururken, en iyi kromozomları kaybetme olasılığımız vardır. Seçkinlik, en iyi kromozomların (ya da bir kısmının) ilk önce kopyalanıp yeni nesle aktarıldığı yöntemin adıdır. Geri kalan kromozomlar yukarıda anlatılan yöntemlerle üretilir. Seçkinlik GA’nın başarımını hızlı bir şekilde arttırabilir, çünkü bulunan en iyi çözümün kaybolmasını önler.

1.Bölüm
2.Bölüm
3.Bölüm
4.Bölüm

Yorumlar