Genetik Algoritma Süreci

Çözülmek üzere tanımlı bir problem verilmesi ve aday çözümlerin birer bit dizisi ile temsil edilmesi halinde, GA şu şekilde çalışır:
1.  N adet kromozom (problem için aday çözümler) içeren rastgele oluşturulmuş bir topluluk ile başla.
2.  Topluluktaki her  x kromozomu için  f(x) uygunluk değerini hesapla.
3.  Aşağıdaki adımları birey  n (topluluk büyüklüğü) oluşturuluncaya kadar tekrarla.
a.  Güncel topluluktan, yüksek uygunluk değerinin seçilme ihtimalini arttırdığını göz önünde bulundurarak, iki ebeveyn kromozom seç. Seçilim, aynı kromozomun birden çok defa ebeveyn olarak seçilmesine olanak verecek şekilde yapılır.
b.  Pc olasılığı (“çaprazlama olasılığı” ya da “çaprazlama oranı”) ile seçilen çifti iki yeni birey
oluşturmak üzere rastgele belirlenen bir noktadan çaprazla. Eğer çaprazlama gerçekleşmezse
ebeveynlerinin birebir kopyası olan iki çocuk oluştur.
c.  Pm olasılığı (“mutasyon olasılığı” ya da “mutasyon oranı”) ile, oluşan iki çocuğu tüm veya bazı locuslarında
mutasyona uğrat.
d.  Sonuçta elde edilen kromozomları yeni topluluğa ekle.
4.  Önceki topluluğu yeni topluluk ile değiştir.
5.  Sonlandırma koşulu sağlandıysa mevcut topluluktaki en iyi çözümü döndür, sağlanmadıysa 2. adıma dön.

 

1.Kromozomların Kodlanması

Bir problemin çözümünde Genetik Algoritmalar kullanılacaksa çözümün ilk adımı kromozomların nasıl kodlanacağına karar vermektir. Kodlama yaklaşımı çözümün başarısına doğrudan etki eder ve problemin
türüne ve özelliklerine göre farklılık gösterir.

2.Seçilim

GA’da bir sonraki nesle geçiş sırasında, yeni topluluğu oluşturmak için mevcut topluluktan çaprazlama ve mutasyon işlemlerine tabi tutulacak bireylerin seçilmesi gerekir. Teoriye göre iyi olan, bir başka deyişle uygunluk değeri yüksek olan bireyler yaşamını sürdürmeli ve bu bireylerden yeni bireyler oluşturulmalıdır. Bu nedenle tüm seçilim yöntemlerinde uygunluk değeri fazla olan bireylerin seçilme olasılığı daha yüksek tutulur. Seçilim sırasında dengenin gözetilmesi gerekir. Çok güçlü bir seçilim, o seviyede yüksek uygunluğa sahip bireylerin topluluğu kaplamasını ve çözüme ulaşmak için gereken çeşitliliğin azalmasını beraberinde getirir. Çok zayıf bir seçilim ise aşırı yavaş bir evrime neden olur.

3.Çaprazlama

GA’da çaprazlama işlemi, iyi çözümlerin farklı bölümlerini birleştirip daha iyi çözümler oluşturabilmek amacıyla kullanılır. Çaprazlamanın en kolay yolu rastgele bir çaprazlama noktası belirleyip, bu noktadan önceki bölümü ilk ebeveynden, sonraki bölümü ise diğer ebeveynden alarak yeni bir birey oluşturmaktır.
Tek Noktalı Çaprazlama: En temel çaprazlama yöntemidir. Rastgele bir çaprazlama noktası seçilir ve iki ebeveynin o noktadan sonra gelen kısımları değiş tokuş edilir.

4.Mutasyon

Bireyin bir sonraki nesle geçirilmesi sırasında kromozomu olu turan karakter dizisinde yapılan rastgele değişikliğe mutasyon denir. Mutasyon, oluşan yeni çözümlerin önceki çözümü kopyalamasını önleyerek çeşitliliği sağlamak ve sonuca daha hızlı ulaşmak amacıyla gerçekleştirilir. Mutasyon olasılığı çok düşük  (%0.01 gibi) tutulmalıdır. Yüksek mutasyon olasılığı uygun çözümleri de bozacak ve GA’nın çalışma sırasında problemlerle karşılaşılmasına yol açacaktır.

5.Seçkincilik (elitizim)

Seçilim, çaprazlama ve mutasyon işlemleri sonrasında mevcut topluluğun en iyi uygunluk değerine sahip bireyi bir sonraki nesle aktarılamayabilir. Bunu önlemek için bu işlemlerden sonra, bir önceki topluluğun en iyi (elit) bir veya daha çok bireyi, yeni oluşturulan topluluğa doğrudan aktarılır.

Kaynak

Yorum ekle


Güvenlik kodu
Yenile