K-Point Crossover

Genetik algoritmalardaki crossing over kavramı malum; iki çözümü bir yerden kesip kesilen noktadan itibaren olan kısımları yer değiştiriyoruz, böylece elimizde 2 yeni sonuç oluyor.

 

OnePointCrossover.svg

 

Tek noktadan yapılan crossover işleminin yetersiz olması sonucu 2-point crossover, N-point crossover gibi yöntemler de çıkmış. Bu yöntemleri kullanarak çözümü birden fazla noktadan bölüp crossover’ı o noktalardan yapıyoruz. Maksat çözüm uzayındaki genetik çeşitliliği korumak.

 

kpoint

Aklıma gelen soru ise şu; bu crossover noktalarını uniform random olarak belirlediğimizi düşünelim. Bu olasılık da 0.5 olsun, yani bir noktanın crossover noktası (üstteki resimde yeşil çizgilerin kestiği noktalar yani) olma olasılığı 0.5. N-point crossover’daki N sayısının beklenen değeri bu durumda kaç olacaktır?

Her bölme noktasını var/yok şeklinde alacak olursak, elde edeceğimiz farklı bölme kombinasyonları, n çözüm kümesinin boyutu olmak üzere, |S| = 2^{n-1} tane olacak. Kesim noktalarının olduğu kümenin altküme sayısını bulmuş olduk aslında.

Bu 2^{n-1} elemana bakarsak, çözümü hiç kesmediğimiz 1 durum, 1 kez kestiğimiz n-1 durum … olduğunu görürüz. Genel olarak bakınca her k noktadan kesme işlemini \binom{n-1}{k} defa yapıyoruz. Toplam durum sayısı da 2^{n-1} olduğuna göre, E[n] beklenen değerini

(1)   \begin{equation*} E[n] = \frac{1}{2^{n-1}} \sum\limits_{k = 1}^{n-1} k \times \binom{n-1}{k} \end{equation*}

ile hesaplayabiliriz. Bunu da uzun uzun hesaplamaya gerek yok çünkü yukarıdaki denklem bize B(n-1, 0.5) binom dağılımının ortalama değerini veriyor. B(n, p) dağılımının ortalaması

(2)   \begin{equation*} \mu=np \end{equation*}

olduğuna göre, n elemanlı bir çözüm kümesi için sorunun cevabı \frac{n-1}{2} olacaktır.