Genetik Algoritmalar
Genetik Algoritmalar evrimsel hesaplamanın bir parçasıdır. Bu alan Yapay Zekâ’nın hızla gelişen bir dalıdır. Genetik algoritmalar Darwin’ in evrim teorisinden etkilenerek geliştirilmiştir. Basitçe açıklayacak olursak problemler evrimsel bir süreç kullanılarak bu süreç sonunda en iyi sonucu veren çözüme erişmeye çalışmaktadır. Başka bir ifadeyle çözüm evrimleşmektedir. Evrimsel hesaplama 1960’larda I.Rechenberg’in Evrim Stratejileri (“Evolutionsstrategie”) adlı çalışmasında tanıtılmıştır. Daha sonra fikri diğer araştırmacılar tarafından geliştirilmiştir. Genetik algoritmalar John Holland tarafından icat edilmiş ve öğrencileri ve iş arkadaşları tarafından geliştirilmiştir. 1992 yılında John Koza, genetik algoritmaları kullanarak programları evrimleştirerek belli işleri yapmakta kullandı. Bu yönteme “genetik programlama” adını verdi. LISP dilinde programlar Ayrıştırma Ağaçları” (“Parse Tree”) şeklinde ifade edildiği için LISP diliyle geliştirilmiştir. Ayrıştırma Ağaçları genetik algoritmaların çalıştığı temel nesnedir.
Biyolojik Altyapı
Kromozom: Tüm yaşayan organizmalar hücrelerden oluşur. Her hücrede aynı kromozom kümeleri bulunur. Kromozomlar DNA dizileri olup, tüm organizmanın örneği olarak hizmet ederler. Bir kromozom gen adı verilen DNA bloklarından oluşur. Her gen belirli bir proteini kodlar. Basitçe, her genin, örneğin göz rengi gibi bir özelliği kodladığı söylenebilir. Bir özellik için olası ayarlar, (Örn. Mavi, Yeşil) alel olarak adlandırılır. Her gen kromozom üzerinde kendine ait bir konuma sahiptir. Bu konuma yörünge (“locus”) adı verilir. Tüm genetik malzeme kümesine (tüm kromozomlar) genom adı verilir. Genom üzerindeki belli gen kümelerine genotip adı verilir. Genotipler, doğumdan sonra gelişmeyle fenotiplere - canlının göz rengi, zekâ v.b. fiziksel ve zihinsel özellikleri- dönüşür.
Tekrar Üretim: Tekrar üretim sırasında, yeniden birleşme (veya çaprazlama) ilk önce ortaya çıkar. Atalardan gelen genler yepyeni bir kromozom üretmek için bir araya gelirler. Bu yeni yaratılmış nesil daha sonra mutasyona uğrayabilir. Mutasyon DNA elemanlarının değişmesidir. Bu değişimler genellikle atalardan gen kopyalanması sırasındaki hatalardan kaynaklanır. Bir organizmanın uygunluğu (“fitness”) organizmanın yaşamındaki başarısıyla (hayatta kalma) ölçülür.
Arama Uzayı Eğer bir problemi çözüyorsak, genellikle çözümler arasındaki en iyi olanını arıyoruz demektir. Mümkün tüm çözümlerin uzayına (istenen çözümün aralarından bulunduğu çözümler kümesi) arama uzayı (durum uzayı) adı verilir. Arama uzayındaki her nokta bir olası çözümü temsil eder. Her olası çözüm değeri (uygunluğu) ile problem için “işaretlenebilir”. Genetik algoritmalar yardımıyla arama uzayındaki olası çözümler arasından en iyi çözümü araştırırız. Çözümü aramak, arama uzayında aşırı noktaları (azami veya asgari) aramak ile aynı anlamdadır. Zaman zaman arama uzayı iyi tanımlanmış olabilir, ama bu arama uzayında sadece bir kaç noktayı biliyor olabiliriz. GA kullanma sürecinde, çözüm bulma süreci diğer noktaları (olası çözümleri) evrim sürdükçe üretir. Sorun, arama çok karmaşık olabilir. Nereden başlanacağı veya nereye bakılacağı bilinemeyebilir. Uygun çözümün bulunması için birçok yöntem vardır, fakat bu yöntemler en iyi çözümü üretmeyebilir. Bu yöntemlerin bazıları, tepe tırmanma (“hill climbing”), yasak arama (“tabu search”), benzetimli tavlama (“simulated annealing”) ve genetik algoritmalardır. Bu yöntemler sonucu bulunan çözümler genellikle iyi çözümler olarak kabul edilir, çünkü sık sık en iyiyi bulmak ve ispatlamak mümkün değildir.
NP-Zor (“NP-Hard”) Problemler: “Geleneksel” yolla çözülemeyecek problem sınıfına bir örnek NP (“Non-deterministic Polynomial Time”) problemlerdir. Hızlı (Çokterimli) algoritmaların uygulanabildiği birçok görev vardır. Ancak algoritmik olarak çözülemeyen bazı problemler de vardır. Çözüm bulmanın çok zor olduğu önemli problemler vardır, fakat çözüm bulununca bu çözümü kontrol etmek kolaydır. Bu gerçek “NP-Complete” Problemleri ortaya çıkarır. NP Nondeterministic Polynomial anlamına gelir ve bunun anlamı çözüm (Nondeterministic algoritma yardımıyla) “tahmin” edilebilir ve kontrol edilebilir. NP Problemlere örnek olarak tatmin problemini, gezgin satıcı problemini veya sırt çantası problemini verebiliriz. Daha fazla örnek için “A Compendium of NP Optimization Problems” sitesi incelenebilir.
Genetik Algoritma
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)
Yukarıda da görüldüğü gibi, genetik algoritmanın akışı oldukça kolaydır. Birçok parametre ve ayar farklı problemler için farklı şekillerde gerçekleştirme için vardır. Sorulması sorulan ilk soru kromozomun nasıl kodlanacağıdır. Daha sonra çaprazlama ve mutasyon, GA’nın iki basit işleci adreslenecektir. 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.
Kodlama
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.
Seçim
GA Akış şemasından da bildiğimiz gibi, kromozomlar toplum içerisinden çaprazlama için ata olmak için seçilmektedir. Problem bu kromozomları nasıl seçileceğidir. Darwin’in evrim teorisine göre en iyi olan yeni yavruyu yaratmak için yaşamına devam eder. Seçim düzeneklerine rulet tekeri seçimi, Boltzman seçimi, turnuva seçimi, sıralama seçimi, sabit durum seçimi ve diğerleri verilebilir.
Rulet Tekeri Seçimi: Atalar uygunluklarına göre seçilirler. Daha iyi kromozomlar, daha fazla seçilme şansına sahip olanlardır. Toplumdaki tüm kromozomların yerleştirildiği bir rulet tekerini hayal edelim. Rulet tekeri üzerindeki kromozomun yerinin boyutu kromozomun uygunluğuyla orantılıdır. Daha uygun olan kromozom daha geniş bir kısma sahip olur. Bir bilye rulet tekerine atılmakta ve bilyenin durduğu yerdeki kromozom seçilir. Daha uygun olan kromozomlar böylece daha fazla sayıda seçilecektir. Süreç aşağıdaki algoritma ile anlatılabilir. Toplam: Toplumdaki tüm kromozomların uygunluk toplamını hesaplar - S. Seçim: (0,S) aralığından rasgele bir sayı üretilir - r. Döngü: Toplum üzerinden gidip 0’dan itibaren uygunlukların toplamını al - s, s r’den büyük olduğu zaman dur ve bulunduğumuz yerdeki kromozomu döndür. Elbette, aşama bir her toplum için bir kez yapılmaktadır.
Sıralama Seçimi: Bir önceki seçim düzeneğinde uygunluk değerleri arasında büyük farklar oluşunca problemler ortaya çıkacaktır. Örneğin, eğer en iyi kromozomun uygunluğu diğer tüm kromozomların toplamının %90’ı ise diğer kromozomların seçilme şansı çok azalacaktır. Sıralama seçimi ilk önce toplumu sıralar ve her kromozom uygunluk değeri olarak sırasını kullanır. En kötü 1 uygunluğunu, ikinci kötü 2,…., en iyi N (toplumdaki kromozom sayısı) uygunluğunu alır. Uygunluk sıraya göre belirlendiği zaman durum değişmektedir. Bu şekilde tüm kromozomların seçilme şansı olacaktır. Ancak bu yöntem daha yavaş yakınsama neden olabilir, çünkü en iyi kromozomlar birbirlerinden çok farklı değillerdir. Sabit Durum Seçimi: Bu özel bir ata seçme yöntemi değildir. Bu tip seçimin ana fikri, toplumun var olan kromozomlarının büyük bir kısmının yeni nesle aktarılmasıdır. Sabit durum seçimi şu şekilde çalışmaktadır. Her yeni nesilde yüksek uygunluk değerine sahip kromozomlar yeni yavruları oluşturmak için seçilir ve düşük uygunluk değerine sahip yavrular kaldırılarak yerlerine bu yeni oluşturulan yavrular koyulur. Toplumun geri kalan kısmı aynen yeni nesle aktarılır.
Seçkinlik (Elitizm): Seçkinliğin ana fikri daha önce açıklandı. Çaprazlama ve Mutasyon yöntemleriyle yeni bir nesil oluştururken, en iyi kromozomları kaybetme olasılığımız vardır. Seçkinlik, en iyi kromozomların (ya da bir kısmının) ilk önce kopyalanıp yeni nesle aktarıldığı yöntemin adıdır. Geri kalan kromozomlar yukarıda anlatılan yöntemlerle üretilir. Seçkinlik GA’nın başarımını hızlı bir şekilde arttırabilir, çünkü bulunan en iyi çözümün kaybolmasını önler.
Kaynaklar