Kromozomların kodlanması bir problem çözümüne başlarken sorulması gereken ilk sorudur. Kodlama problemin kendisine yoğun şekilde bağlıdır.
İkili kodlama: İkili kodlama en çok kullanılan yöntemdir, çünkü ilk GA araştırmaları bu kodlama yöntemini kullanıldı ve görece basit bir yöntemdir. İkili kodlamada, her kromozom bit (0 veya 1) karakter dizilerinden oluşmaktadır.
Kromozom A: 101100101100101011100101
Kromozom B: 111111100000110000011111
İkili kodlama, fazla olasılıkta kromozomlar verir, bunlara düşük sayıda alel içerenler de dahildir. Ancak, bu yöntem çoğu problem için doğal bir kodlama değildir ve çaprazlama ve/ya mutasyondan sonra düzeltmeler yapılması gerekir.
Örnek Problem: Sırt çantası problemi
Problem: Elimizde değeri ve boyutu verilmiş olan nesneler var. Sırt çantasının kapasitesi verilmiştir. Elimizdeki nesneler sırt çantasına azami sayıda çantanın kapasitesini aşmayacak şekilde yerleştirilmelidir.
Kodlama: Her bit, şeyin sırt çantasında olup olmadığını belirtiyor.
Çaprazlama Yöntemleri:
Tek Noktalı Çaprazlama: Tek bir kesme noktası seçilir, ilk atanın kromozomundan kesme noktasına kadar baştan itibaren alınır ve geri kalan kısım ikinci atanın kesme noktasından sonraki kısmıyla birleştirilip yavrunun kromozomu oluşturulur (11001011+11011111 = 11001111 ).
İki Noktalı Çaprazlama: İki kesme noktası seçilir, kromozomun başından ilk kesme noktasına kadar olan ikili karakter dizisi ilk atadan, iki kesme noktası arasındaki kısım ikinci atadan ve ikinci kesme noktasından sonraki kısım tekrar ilk atadan alınarak yeni yavru oluşturulur (11001011 + 11011111 = 11011111).
Tek biçimli çaprazlama: Bitler atalardan rasgele olarak seçilip kopyalanır (11001011 + 11011101 = 11011111 ).
Aritmetik çaprazlama: Bazı aritmetik bit işlemleri atalar üzerinde uygulanarak yeni yavru oluşturulur (VE işlemi 11001011 + 11011111 = 11001001).
Mutasyon Yöntemleri:
Bit ters çevirme: Seçilen bitler terslerine çevrilir. (Bkz. Şekil 4.8 Yeni Bit= (NOT)Eski Bit işlemi 11001001 => 100010001)
Permütasyon Kodlama: Permütasyon kodlama, gezgin satıcı problemi veya görev sıralama gibi sıralama problemlerinde kullanılabilir. Permütasyon kodlamada, her kromozom sıra’da konum belirten numara karakter dizisinden oluşur.
Kromozom A: 1 5 3 2 6 4 7 9 8
Kromozom B: 8 5 6 7 2 3 1 4 9
Permütasyon kodlama, sıralama problemleri için yararlıdır. Bazı problemlerde bazı çaprazlama ve mutasyon türleri için kromozomların tutarlılığı için (örneğin içerisinde gerçek sırayı tutan) düzeltmeler yapılması gerekmektedir.
Örnek Problem: Gezgin satıcı problemi
Problem: Şehirler ve bu şehirler arasındaki uzaklıklar verilmektedir. Gezgin satıcı tüm bu şehirleri dolaşmak zorundadır. Fakat gereğinden fazla dolaşmamalıdır. En küçük dolaşma uzunluğunu verecek olan şehir dolaşma sırası bulunmalıdır.
Kodlama: Kromozom şehirlerin gezgin satıcının dolaşacağı sırasını tutar.
Çaprazlama yöntemleri (Tek Noktalı Çaprazlama): Bir kesme noktası seçilir, kesme noktasına kadar ilk atadan, kesme noktasından sonraki kısımlar da ikinci atadan olmak üzere permütasyonlar kopyalanır. Aynı sayılar olmayan sayılarla değiştirilerek tutarlı yeni yavru elde edilir. Bundan çok farklı, daha fazla sayıda yöntem de uygulanabilir.
(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)
Mutasyon Yöntemi (Sıra Değiştirme): İki sayı seçilir ve yerleri değiştirilir.
(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)
Değer kodlama: Gerçek sayılar gibi karmaşık değerlerin kullanıldığı problemlerde doğrudan değer kodlama kullanılabilir. İkili kodlamanın bu tip problemler için kullanılması problemlerin zorlaşmasına neden olacaktır.
Değer kodlamada, her kromozom bazı değerlere eşittir. Değerler problemle ilgili herhangi bir şey olabilir. Gerçek sayılar, karakterler veya herhangi nesneler olabilir.
Değer kodlama ile kodlanmış kromozom örnekleri:
Kromozom A: 1.2324 5.3243 0.4556 2.3293 2.4545
Kromozom B: ABDJEIFJDHDIERJFDLDFLFEGT
Kromozom C: (geri), (geri), (sağ), (ileri), (sol)
Değer kodlama bazı özel problemler için iyi bir seçimdir. Ancak, bu tip kodlamada probleme özgü yeni çaprazlama ve mutasyon yöntemleri geliştirmek gereklidir.
Örnek Problem: Bir sinir ağı için ağırlıkları bulma
Problem: Bir sinir ağı belirlenmiş mimariyle birlikte verilmektedir. Ağdan beklenen değeri almak için sinir ağındaki sinirler arasındaki ağırlıklar istenmektedir.
Kodlama: Kromozomlardaki gerçek değerler sinir ağındaki ağırlıkları temsil eder.
Çaprazlama yöntemi: İkili kodlamadaki tüm çaprazlamalar kullanılabilir.
Mutasyon Yöntemi (Küçük bir sayı ekleme -Gerçek sayı kodlama için-): Seçilen değerlere küçük bir sayı eklenir (veya çıkarılır).
(1.29 5.68 2.86 4.11 5.55) => (1.29 5.68 2.73 4.22 5.55)
Ağaç Kodlama: Ağaç kodlama genellikle evrimleşen program veya ifadeler için kullanılmaktadır. Örneğin genetik programlama için
Ağaç kodlamada her kromozom bazı nesnelerin ağacıdır, örneğin işlevler veya programlama dilindeki komutlar gibi. Ağaç kodlama evrimleşen programlar veya ağaç şeklinde kodlanabilecek herhangi diğer yapılar için uygundur. LISP programlama dilinde programların ağaç şeklinde temsil edilmesi nedeniyle LISP bu iş için en çok kullanılan dildir. LISP’te bu ağaçlar kolayca ayrıştırılıp, çaprazlama ve mutasyon kolayca yapılmaktadır.
Örnek Problem: Verilen değer çiftlerini yaklaştıran fonksiyonu bulma
Problem: Girdi ve çıktılar verilmektedir. Görev tüm girdiler için en iyi çıktıları veren fonksiyonun üretilmesidir.
Kodlama: Kromozomlar ağaçta fonksiyonlar şeklinde temsil edilir.
Çaprazlama: Bir kesme noktası her iki atada da seçilir, atalar bu noktada bölünür ve kesme noktasının altında kalan parçalar değiştirilerek yeni yavrular oluşturulur.
Mutasyon (İşlev veya Numara değiştirme): Seçilen düğümler yer değiştirilir.
1.Bölüm
2.Bölüm
3.Bölüm
4.Bölüm
Hiç yorum yok:
Yorum Gönder