Genetik Operatörler
Kullanılan genetik operatörler, varolan nesil (population) üzerine uygulanan işlemlerdir. Bu işlemlerin amacı, daha iyi özelliğe sahip yeni nesiller üretmek ve arama algoritmasının alanını genişletmektir.
3 tip genetik operatör vardır:- Seleksiyon (Selection / Reproduction)
- Çaprazlama (Crossover)
- Mutasyon (Mutation)
1. Seleksiyon (Selection / Reproduction)
Yeniden üretme operatörü, hazır topluluktan uygun olan bireylerin seçilmesi ve bunların sonraki topluluğa kopyalanarak hayatta kalmalarıyla ilgilidir. Seçim modeli, tabiatın hayatta kalabilmek için uygunluk mekanizması modelidir. Yeniden üretme işleminde, bireyler onların uygunluk fonksiyonlarına göre kopya edilirler. Uygunluk fonksiyonu, mümkün olduğu kadar yükseltilmesi gereken bazı faydalı ve iyi ölçülerdir. Topluluk uzayındaki her bir bireyin uygunlukları baz alınarak ne kadar sayıda kopyasının olacağına karar verilir. En iyi bireylerden daha fazla kopya alınır, en kötü bireylerden kopya alınmaz. Bu hayatta kalmak için uygunluk stratejisinin GA ya sağladığı avantajdır.
1.1. Rulet Tekerleği Seçimi
GA tarafından üretilen döllerin sayısını belirlemede birkaç yol vardır. Birbirine yakın parametrelerden kaçınmak için uygun bir seçim metodu kullanılmalıdır. Tekrar üretme başlangıcında basit bir yöntem “roulette wheel selection” (rulet tekerleğiyle seçim)'e göre bireylerin uygunluk değerlerini bir rulet tekerleğinde hazırlar. Rasgele tekerleğin döndürülmesinden sonra, bireyin bir sonraki nesil için seçilmesi, tekerlek üzerinde kapladığı alanla doğrudan bağlantılıdır. Bu yöntem düşük uygunluğa sahip bireylere de seçilme hakkı verir.
N
Pseçilen=Fi / å Fi (2.4)
i=1
Fi: i. Eleman için uygunluk değeri
N: Birey sayısı
Ebeveynler uygunluklarına göre seçilirler. Kromozomlar ne kadar iyiyse, o kadar seçilme şansları fazladır. Şöyle bir rulet tekerleği düşünün.
Şekil 1. Rulet tekerleği ile seçim
Sonra bir bilye atılır ve kromozomu seçer. Daha fazla uygunluğu olan kromozomlar daha çok seçilecektir. Bu aşağıdaki algoritmayla simule edilebilir:
1. [Sum] Populasyondaki tüm kromozom uygunlukları toplamını hesapla – toplam S.
2. [Select] (0,S) – r aralığından rastgele bir sayı üret.
3. [Loop] Populasyon boyunca git ve uygunlukları 0’dan toplam s ‘e kadar topla. Eğer toplam s , r ‘den büyükse dur ve olduğun yerdeki kromozomu geri gönder.
Tabii ki 1. basamak her populasyon için bir kez performe edilir.
1.2 Rank Seçimi
Yukarıdaki seçim eğer uygunluklar çok fazla değişiyorsa bazı problemlere yol açacaktır. Mesela en iyi kromozom uygunluğu tüm rulet tekerleğinin %90’ı ise diğer kromozomların seçilme şansları çok az olacaktır. Rank seçimi önce populasyonu sıralar ve daha sonra her kromozom uygunluğu bu sıralamadan sonra alır. En kötüsü 1 uygunluğunu alacak, ikinci en kötü 2 ve en iyisi N uygunluk değerini alacak ki N de populasyondaki kromozom sayısıdır.
Sayıları düzenlemek için uygunlukları değiştirdikten sonra durumun nasıl değiştiğini aşağıdaki şekilde görebilirsiniz:
Şekil 2. Rankingden önceki durum (Uygunluk grafiği) ve Rankingden sonraki durum (düzenli sayıların grafiği)
Bundan sonra her kromozomun seçilme hakkı olacaktır. Fakat bu metod daha yavaş gibidir, çünkü en iyi kromozomlar diğerlerinden fazla değişiklik göstermez.
1.3 Steady-State Seçimi (Kararlı Hal)
Bu yerine geçme yöntemleri olarak da adlandırılabilirler. Bu ebeveynleri seçmek için kısmi bir metod değildir. Bu seçimin ana fikri kromozomların büyük kısmı bir sonraki nesilde hayatta kalmak zorundadır.
O zaman GA şu şekilde çalışır. Yeni çocuklar oluşturmak için her nesilde güzel iyi uygunluklu birkaç kromozom seçilir. Sonra kötü düşük uygunluklu bazı kromozomlar atılır ve yeni çocuk onun yerine yerleştirilir. Populasyonun geri kalan kısmı yeni nesilde hayattadır. Yani kısaca bu yöntemde alt populasyon oluşturulduktan sonra uygunluklar hesaplanır, en kötü kromozomlar yerlerini başlangıç populasyonundaki en iyi kromozomlara terk eder.
1.4 Elitizm
Bu da yerine geçme metodu olarak bilinir. Elitizm fikriyle zaten daha önce tanışılmıştı. Mutasyon ve çaprazlamalarla yeni nesil oluştururken en iyi kromozomu seçmek için büyük bir şansa sahip oluruz.
Elitizm en iyi kromozomu ya da birkaç en iyi kromozomları yeni nesile kopyalama metodunun adıdır. Gerisi klasik yolla yapılır. Elitizm çok hızlı bir şekilde GA’ nın performansını arttırır çünkü en iyi bulunan çözümü kaybetmeyi önler.
Ayrıca Musbaka ve Oranlama yöntemleri de vardır.
2. Çaprazlama (Crossover)
Amaç, ana (parent) kromozom genlerinin yerini değiştirerek çocuk (child) kromozomlar üretmek ve böylece varolan uygunluk değeri yüksek olan kromozomlardan, uygunluk değeri daha yüksek olan kromozomlar elde etmektir. Burada önemli olan bir konuda , çaprazlama noktasının çaprazlamadan elde edilecek çocuk kromozomların uygunluk değerleri üzerindeki etkisidir. Bu işlem yapılırken her zaman sonuçlar önceden tahmin edilemez. Bu yüzden gelişigüzel yapılan değişikliklerde sonucun mükemmelliğe doğru gitmesi için belirli kriterler bulmak için çalışılır. Kromozomlardaki genlerin yapısı ve etkileri araştırılarak, bu genlere yapılan müdahalelerle bireye bazı iyi özellikler kazandırılabilir. Çaprazlamadan elde edilecek çocuk kromozomların uygunluk değeri bir önceki ana kromozomlardan daha yüksek olmayabilir.
Tablo 1.'de biyolojik çaprazlamaya bir örnek verilmiştir:
Tablo 1. Biyolojik çaprazlama örneği
Benzer şekilde GA, çaprazlama işlemini uygunluk değerlerine göre seçilmiş iki ebeveyn bireyden, iyi özellikte yeni bireyler elde etmek için kullanır. Çaprazlama rasgele seçilmiş iki çift katarın içindeki alt küme bilgilerin değiştirilmesi işlemdir. Kendi içindeki bilgilerini 1. Pozisyondan itibaren, katarın uzunluğunun bir eksik pozisyonuna kadar, aradaki bilgi kısmen karşılıklı bireyler arasında yer değiştirilir.
Eğer iki bireyin problemin çözümünde bazı etkileri var ise onların bir parçaları faydalı, iyi veya uygun nitelenebilecek bilgi taşımaktadır. Çaprazlama belki problemin çözümünde, bu faydalı bilgileri birleştirerek, daha çok etkili yeni bireyler üretecektir. Tablo 2.'de ikili kodda verilmiş bir katarda, örnek 2 bitlik bir çaprazlama işlemi verilmiştir.
Tablo 2. İki bitlik çaprazlama örneği
Çaprazlamadan başka tersinme denilen bir üreme yöntemi daha vardır. Holland bunu tanımlayarak kromozom uzunluğu çok olan bireylerde çaprazlama yerine bunun kullanılmasını performans açısından önermiştir. Tersinme (inversion) bir kromozomu oluşturan genlerden ardışık bir grubun kendi içerisinde birbirleriyle yer değiştirerek ters dizilmeleridir. Örneğin:011110101 kromozomu (her genin bir bit olduğu varsayımı ile) 5. ve 8. Gen kromozomları arasında tersindiğinde ortaya 011101011 kromozomu çıkar.
Tersinme genellikle kromozom uzunluğu fazla olan populasyonlara uygulanır.
3. Mutasyon (Mutation)
Amaç, varolan bir kromozomun genlerinin bir ya da birkaçının yerlerini değiştirerek yeni kromozom oluşturmaktır. Yeniden ve sürekli yeni nesil üretimi sonucunda belirli bir süre sonra nesildeki kromozomlar birbirlerini tekrarlama konumuna gelebilir ve bunun sonucunda farklı kromozom üretimi durabilir veya çok azalabilir. İşte bu nedenle nesildeki kromozomlarının çeşitliğini artırmak için kromozomlardan bazıları mutasyona uğratılır. Açıklandığı gibi mutasyonun birinci maksadı bir populasyonun içindeki değişimi tanımlamaktır. Mutasyon populasyonlarda çok önemlidir. Öyle ki burada ilk populasyon mümkün olan tüm alt çözümlerin küçük bir alt kümesi olabilir ve ilk populasyondaki tüm kromozomların önemli biti sıfır olabilir. Halbuki o bitin problemin çözümü için 1 olması gerekebilir ve bunu da çaprazlama düzeltemeyebilir. Bu durumda o bit için mutasyon kaçınılmazdır. Genellikle önerilen mutasyon oranı 0.005/bit/generasyondur. Bu işlem çaprazlamadan sonra gelir. Mutasyonun yapılıp yapılmayacağını bir olasılık testi belirler. Örneğin yeni neslin ortalama uygunluğu £ Eski neslin ortalama uygunluğu ise; x. Kromozomun y. Bitini değiştir denilebilir. Bu yeni çocuğu rast gele değiştirir. İkili kodlama için rast gele seçilmiş bitlerden 0’ları 1, 1’leri 0 yaparız.
Tablo 3. bit katarında hazırlanmış bir mutasyon operatörünü göstermektedir:
Tablo 3. Mutasyon operatörü 
