Genetik algoritmalar Darwin’in Evrim teorisinden esinlenilerek üretilmiştir. Bir problemin çözümü evrimsel süreç kullanılarak çözülmektedir.
Algoritma toplum adı verilen ve kromozomlarla temsil edilen bir çözüm kümesi ile başlamaktadır. Bir toplumdaki çözümler yeni toplumların üretilmesinde kullanılmaktadır. Bu işlem, yeni toplumun eskisinden daha iyi olacağı umuduyla yapılmaktadır.
Yeni çözümler (yavru) üretmek için alınan çözümler uygunluklarına (fitness) göre seçilmektedir. Daha uygun olan tekrar üretim için daha fazla şansa sahiptir.
Bu süreç belli bir durum (örneğin belli sayıda toplum veya en iyi çözümün gelişmesi) karşılanana kadar tekrar edilmektedir.
Basit Genetik Programlama Taslağı
- Başlangıç: n kromozom oluşan rasgele toplum oluşturulur (problemin olası çözümleri)
- Uygunluk: Toplumdaki her x kromozomu için f(x) uygunluk değeri değerlendirilir.
- Yeni Toplum: Aşağıdaki adımlar izlenerek yeni toplum üretilir;
- Seçim: Toplumdan uygunluklarına göre iki ata seçilir (daha uygun olanın seçilme şansı daha fazladır)
- Çaprazlama: Çaprazlama olasılığı ile ataları yeni yavru oluşturmak için birbirleriyle eşleştirilir. Eğer çaprazlama yapılmazsa, yavru ataların tıpatıp aynısı olacaktır.
- Mutasyon: Mutasyon olasılığı ile yeni yavru üzerinde her yörünge için mutasyon işlemi yapılacaktır.
- Kabul: Yeni yavru, yeni topluma eklenir.
- Değiştir: Yeni toplum algoritmanın tekrar işlenmesinde kullanılır.
- Deney: Eğer bitiş durumu sağlandıysa, durup toplumdaki en iyi çözüm döndürülür.
- Döngü: Adım 2’ye gidilir. (Kaynak)
Bir sonraki soru çaprazlama için ataların nasıl seçileceğidir. Bu farklı birçok yolla yapılabilir, ancak ana fikir daha iyi ataların daha iyi yavrular üreteceği düşüncesiyle seçilmesidir. Bu şekilde en iyi çözümün kaybedilmemesi için seçkinlik, en iyi çözümün değiştirilmeden yeni nesle aktarılması, böylece en iyi çözümün yaşatılması uygulanabilir.
GA İşleçleri
Genetik algoritma taslağında görebileceğimiz gibi, çaprazlama ve mutasyon genetik algoritmanın en önemli kısımlarıdır. Başarım en çok bu iki işleçten etkilenir. Bu işleçlerden bahsetmeden önce kromozomlardan daha fazla bahsetmek gereklidir.
Kromozomun Kodlanması: Bir kromozom temsil ettiği çözüm hakkında bir şekilde bilgi içermelidir. En çok kullanılan kodlama ikili karakter dizisidir. Bu yöntemle kromozom şu şekilde görülmektedir:
Kromozom 1 : 1101100100110110
Kromozom 2 : 1101111000011110
Her kromozom ikili karakter dizisi şeklinde temsil edilmektedir. Karakter dizisindeki her bit çözümün bir özelliğini temsil eder. Bir başka olasılık tüm karakter dizisinin bir sayıyı temsil etmesidir.
Elbette, birçok başka kodlama yöntemi vardır. Kodlama daha çok çözülen probleme bağlıdır. Örneğin bazı problemler için tamsayı veya gerçek sayı şeklinde kodlamak gerekirken, bazı problemlerde permütasyon şeklinde kodlamaya ihtiyaç vardır.
Çaprazlama: Kodlamaya karar verdikten sonra, çaprazlama işlemiyle devam edebiliriz. Çaprazlama, atalardaki seçili genler üzerinde işlem yapar ve yeni yavrular oluşturur. Bunun en basit şekli, rasgele bir kesme noktası (çaprazlama noktası) seçip, bu noktadan önceki her şeyi ilk atadan, sonraki her şeyi ikinci atadan alıp birleştirerek yavruyu oluşturmaktır.
Çaprazlama aşağıdaki şekilde gösterilebilir: ( | kesme noktasıdır):
Kromozom 1: 11011 | 00100110110
Kromozom 2: 11011 | 11000011110
Yavru 1 : 11011 | 11000011110
Yavru 2 : 11011 | 00100110110
Çaprazlamanın birçok yolu mevcuttur, örneğin birden fazla kesme noktası seçilebilir. Çaprazlama daha da karmaşık olabilir ve tamamen kromozomların kodlanmasına bağlıdır. Özel problemler için yapılmış özel çaprazlamalar genetik algoritmanın başarımını arttırabilir.
Mutasyon: Çaprazlama işlemi gerçekleştirildikten sonra, mutasyon işlemi yapılır. Mutasyonun amacı, toplumdaki tüm çözümlerin çözülen problemlerin bir yerel uygun değerine düşmesinin önüne geçmektir. Mutasyon işlemi çaprazlama sonucu oluşan yavruyu rasgele değiştirmektedir. İkili kodlamada rasgele seçilmiş bir kaç biti 1’i 0’a, 0’ı 1’e şeklinde değiştirmek bir mutasyondur.
Asıl Yavru 1: 1101111000011110
Mutasyon Geçirmiş Yavru 1:1100111000011110
Asıl Yavru 2: 1101100100110110
Mutasyon Geçirmiş Yavru 2:1101101100110110
Mutasyon tekniği (çaprazlama tekniği de) kromozomların kodlamasına çoğunlukla bağlıdır. Örneğin permütasyon şeklinde kodlamada mutasyon rasgele seçilen iki genin yer değiştirmesi olarak gerçekleştirilir.
GA’nın Parametreleri
Çaprazlama Olasılığı: Bu parametre çaprazlamanın ne kadar sıklıkla yapılacağını belirtir. Eğer herhangi bir çaprazlama yoksa yavrular ataların aynısı olacaktır. Eğer bir çaprazlama yapılırsa yavrular ataların parçalarından oluşur. Eğer çaprazlama olasılığı %100 ise yavrular tamamen çaprazlama ile yapılır. Eğer %0 ise yavrular ataların kromozomlarının aynısına sahip olurlar. (Bu yeni toplumun aynı olduğu anlamına gelmez)
Çaprazlama, yeni kromozomların eski kromozomların iyi parçalarını alıp daha iyi olacakları düşüncesiyle yapılır, ancak eski toplumun bazı parçalarının bir sonraki nesle aktarılması da iyidir.
Mutasyon Olasılığı: Kromozom parçalarının ne kadar sıklıkla mutasyon geçireceğini belirtir. Eğer mutasyon yoksa yavrular çaprazlamadan hemen sonra değiştirilmeden üretilir (veya doğrudan kopyalanır). Eğer mutasyon varsa, yavruların kromozomlarının bir veya daha fazla parçası değişir. Eğer mutasyon olasılığı %100 ise tüm kromozom değişecektir. %0 ise hiçbir şey değişmez. Mutasyon genellikle GA’nın yerel aşırılıklara düşmesini engeller. Mutasyonlar çok sık oluşmamalıdır, çünkü GA rasgele aramaya dönüşebilir.
Toplum Büyüklüğü: Toplumdaki kromozom (birey) sayısını belirtir. Eğer çok az birey varsa, GA’nın çaprazlama yapacağı olasılıklar azalacaktır ve arama uzayının çok küçük bir kısmı araştırılacaktır. Eğer çok fazla birey varsa, GA bayağı yavaşlayacaktır. Araştırmalar bazı sınırlardan sonra çok büyük toplumların kullanılmasının yararlı olmadığını göstermiştir, bu problemin daha hızlı bir şekilde çözülmesine yardımcı olmamaktadır.
1.Bölüm
2.Bölüm
3.Bölüm
4.Bölüm
Hiç yorum yok:
Yorum Gönder