evrim ve temel ilkeler

EVRİMCİ ALGORİTMALAR

evrim

Evrimci Algoritmalar, tasarım ve gerçekleştirilmesinde evrim sürecinin hesaplamalı modellerinin esas alındığı bilgisayar tabanlı problem çözme sistemlerini tasvir etmekte kullanılan genel başlıktır [11]. “Evrimci Programlama”(Fogel, Owens ve Walsh 1966), “Evrim Stratejileri” (Rechenberg 1973) ve “Genetik Algoritmalar” (Holland 1975) bu alandaki baskın yöntemlerdir. Geliştiricilerinin benimsedikleri gösterim tarzı, seçim stratejileri, nüfus yönetimi ve genetik operatörlerin önemsenme derecesine göre farklılıklar arz ederler.

Temel İlkeler

Şekil 4.1’deki gösterimle tanımlanabilecek olan standart EA’nın çalıştırılabilmesi için tespit edilmesi gereken temel noktalar: kromozom gösterimi, seçim stratejisi, çoğalma operatörleri, ilk topluluğun yaratılması, sonlandırma kriteri ve değerlendirme fonksiyonudur. Bu noktaların belirlenmesinde probleme uygunluğu gözetilmelidir.

 1 Evrimci Algoritma akış diagramı

Kromozom Gösterimi

Uygun gösterimden kasıt, muhtemel çözümün bir dizi parametre ile temsil edilebileceği ilkesinin gayri ihtiyari kabulüne uygun olarak parametre sayısının belirlenmesidir. Parametreler, gösteriminde belirli bir alfabenin kullanıldığı genler olarak kodlanırlar. Genler bir araya gelerek kromozomları oluştururlar. Genlerin kromozom üzerindeki yerleri lokus adıyla anılır. Alfabe sembollerden, iki tabanlı sayılar olan {0,1}’den, tamsayılardan, gerçel sayılardan, matrislerden oluşabilir. EA’nın kullanılmaya başlandığı ilk zamanlarda, parametre değerleri için iki tabanlı gösterim daha uygun görülüp yaygın olarak kullanılmış olsa da gerçel değerli gösterim de mümkündür. Michalewicz, çalışmalarıyla göstermiştir ki arama uzayının doğasıyla uyumlu gösterimler daha iyi sonuçlar sağladığından daha verimlidir. Bu bağlamda, fonksiyon optimizasyonunda, kromozomların temsili için alt ve üst sınırlar dahilinde gerçel sayıların kullanımı alışılageldik iki tabanlı gösterime kıyasla

daha elverişlidir [7]. Yapılan çalışmada gerçel değerli gösterim kullanılmıştır. Gen bilimi terminolojisinde, belirli bir kromozomun gen içeriği, genotip olarak anılır. Genotip, bir organizmayı teşkil etmekte gerekli olan bilgiyi içerir. Teşkil edilmiş görüntü de fenotip olarak anılır. Aynı terimler EA için geçerlidir. Örneğin, bir tasarım işinde, belirli bir tasarımı temsil eden parametreler genotipi oluştururken gerçekleştirilen tasarım fenotiptir. Kromozomun uygunluk değeri, fenotipin başarımına dayanır. Bu da uygunluk fonksiyonu kullanılmak suretiyle kromozomdan hesaplanabilir.

Uygunluk fonksiyonu

Çözümü istenen her problem için bir uygunluk fonksiyonu belirlenmelidir. Uygunluk fonksiyonu, belirli bir kromozomun çözüme yakınlığının göstergesi olan uygunluk değerinin hesaplanmasında kullanılır [12, 13].

 Olgunlaşmamış Yakınsama

İlk topluluk rasgele değerlerle yaratıldığından bireylerin uygunluk değerleri ve belirli bir lokusa ait genler arasında ciddi farklılık olacaktır. Topluluk yakınsadıkça uygunluk değerlerinin varyansı azalır. Çözüme yakınlığının göstergesi olan uygunluk değerinin değişimine bağlı olarak karşılaşılabilecek sorunlar da vardır. İlki olgunlaşmamış(premature, erken) yakınsama ve ikincisi yavaş sonlanmadır(slow finishing) [12, 13].

Holland'ın şema teorisi, bireylere, uygunluk değeriyle orantılı çoğalma fırsatı tanınmasını önerir. Ancak topluluk nüfusunun sonlu olması zorunluluğu nedeniyle olgunlaşmamış yakınsama gerçekleşebilir. EA’nın nüfusu sınırlı topluluklarda etkin çalışabilmesi için bireylerin kazanacağı çoğalma fırsatı sayısının ne çok fazla ne de çok az olacak şekilde denetlenmesi gerekir. Uygunluk değeri ölçeklenerek, erken nesillerde, aşırı uygunluk değerli bireylerin toplulukta hakimiyet kurması engellenir.

 Yavaş Sonlanma

Olgunlaşmamış yakınsamaya karşıt sorun yavaş sonlanmadır. Epey nesil geçmesine rağmen topluluk yaklaştığı halde global minimumu konumlandıramayabilir. Ortalama uygunluk değeri yeterince yüksek değerli olup en iyi bireyin uygunluk değerine yakınsamış olabilir. Olgunlaşmamış yakınsamayı önlemede kullanılan yöntemler bu soruna karşı da kullanılır [12, 13, 14]. Kullanılan yöntemlerle topluluğun etkin uygunluk değerinin varyansı arttırılır.

Seçim

EA’da çözüme giden yol, bireylerin uygunluk değerinin artışını sağlayan gen içeriğinin edinilmesinden geçer. Bu sebeple, yeni nesili oluşturacak bireylerin seçimi hayati önemdedir. Önerilen çeşitli temel yaklaşımlar ve çeşitlemeleri mevcuttur. Sıklıkla kullanılan stratejiler, kesme seçimi, rulet tekerleği ve stokastik örneklemedir.

 Kesme Seçimi

“En Güçlüler Yaşar” prensibinden hareketle uygunluk değerine göre büyükten küçüğe sıralanan bireylerden belirlenen sayıda en yüksek değerli bireyler seçilir, diğerleri yok edilir.

 Stokastik Evrensel Örnekleme

James Baker(1987) tarafından önerilen yöntemde rulet stratejisine benzer yaklaşımla, bireyler doğru üzerine yerleştirilir. Seçilecek birey sayısına eşit sayıda işaretçinin, doğru üzerine eşit aralıklarla yerleştirilmesiyle örnekleme yapılır. Örneğin, seçilecek birey sayısı Npointer=6 olduğunda, örnekleme periyodu 1/Npointer=0.167 olur ve ilk işaretçinin yeri  [0, 1/NPointer] aralığında olmak koşuluyla rasgele seçilir [15].

Şekil 4. 2 Stokastik evrensel örnekleme

 Rulet tekerleği seçimi

Stokastik bir yöntemdir. Bireyler, uygunluk değerleriyle orantılı uzunluklarla, ardışık olarak bir doğru üzerine veya her bir diliminin alanı uygunluk değeriyle orantılı olacak şekilde rulet tekerleği üzerine yerleştirilirler. Üretilen rasgele sayının rastladığı aralığın sahibi birey seçilir. Önceden belirlenen birey sayısına ulaşılana dek işlem tekrarlanır [15, 16].

Şekil 4. 3 Rulet tekerleği seçimi

 Çoğalma

Uygunluk değerini gözeten seçim stratejisi sonucu seçilen kromozomların çaprazlanmasıyla yeni nesili oluşturan bireylerin üretildiği evre, çoğalmadır. Ebeveyn olarak iki kromozom seçildikten sonra gerçekleşen çaprazlama işlemi tek veya çok noktalı olabilir. Rasgele belirlenen noktadan ikiye ayrılan kromozomlardan baş ve kuyruk dizileri elde edilir. Şekil 4.4 ve Şekil 4.5’te görüldüğü gibi, baş veya kuyruk dizilerinin değiştokuşu sonrasında birleştirilen diziler yeni nesilin iki ferdi olarak kromozom havuzuna kaydedilirler.

. 4 Tek noktalı çaprazlama

 5 Çok noktalı çaprazlama

 Mutasyon

Faydası tartışılmaya devam etmekle birlikte sıkça kullanılan bir diğer genetik operatör mutasyondur. Rasgele seçilen kromozomdaki bir veya birkaç geni rasgele değişikliğe uğratan mutasyon operatörünün nesil başına uygulanma oranının düşük olması tavsiye edilir. Şekil 4.6’da tek noktada ve Şekil 4.7’de çok noktada mutasyon işlemi gösterilmiştir. İki tabanlı gösterimde, genin alabileceği değer { 0 , 1 } ile kısıtlı olduğundan  0à1’e, 1à0’a dönüşür. Gerçel sayılı gösterimde ise, gendeki değişim, rasgele belirlenen bir sayıyla yerdeğişimine bağlı olabileceği gibi mevcut değere mutasyon adımı olarak anılan küçük ilavelerle de gerçekleşebilir [7].

Şekil 4. 6 Tek noktada mutasyon

7 Çok noktada mutasyon

 Yakınsama

EA’nın doğru gerçekleştirildiği uygulamalarda, kromozom topluluğundaki en iyi ve ortalama uygunluk değerleri, bireylerin, evrim sonucu gelişimiyle biribirine ve global optimuma yakınsar. Uygunluk kriterini sağlayan birey yakınsamıştır denir. Topluluk ortalamasının, en iyi bireyin uygunluk değerine yakınsadığı durumda topluluk yakınsamış olur. Topluluk ve kromozomun yakınsamasından başka, genin yakınsaması da tanımlanmıştır. Bir nesildeki kromozomların belirli bir lokusu %95 oranında aynı gene sahipse gen yakınsamıştır denir [12, 17].

Tersten Sıralama ve Yeniden Düzenleme

Genlerin sıralanışı çok önemlidir. Sıralamayı değiştirerek arama uzayını genişleten bir operatör tersten sıralamadır. Bu operatör, bir kromozom üzerindeki genlerden rasgele belirlenmiş iki lokus arasında kalanları ters sırayla yerleştirir.

 Çift Değerlilik ve Baskınlık

İleri hayat formlarında, kromozomlar ikili sarmal düzenindedir, genler iki şerit üzerine kodlanmıştır. Biribirinin alternatifi iki genin kodlandığı yapı, çift değerli(diploid) kromozom adıyla anılır. Bugüne kadar olan EA çalışmaları tek şerit üzerine kodlanmış genlerle gerçekleştirilmiştir. Tek şeritli yapı haploid kromozom adıyla anılır. Çift değerliliğin sağlayabileceği faydalar olmasına karşı programlama ve işlem kolaylığı sağlamasından dolayı haploid yapı tercih edilmiştir. Zamana bağlı değişimin sözkonusu olabileceği ortamlarda farklı iki çözümü barındıran diploid kromozomlar avantajlıdır. Aynı parametreyi kodlayan genlerden biri baskın diğeri çekinik olacaktır ve ortamdaki değişimle genler de baskınlık/çekiniklik özelliğini değiştirebilecektir. Çift değerlilik, gende evrim sürecinden daha hızlı değişim sağlar [7].

 Epistasis

Genlerarası etkileşim epistasis adıyla anılır. Bir genin uygunluk değerine katkısı, diğer genlerin sahip olduğu değerlere bağlıdır. Epistasis çok fazla ise EA verimli olmayacaktır. Çok düşük olduğunda ise diğer yöntemlerin başarımı EA’ya göre yüksek olacaktır [7].

Aldanma

Evrim süreci işledikçe, global optimumu sağlayacak olan şemaların veya yapıtaşlarının toplulukta görülme sıklığı artacaktır. Bu optimal şemalar, çaprazlama operatörüyle, nesiller geçtikçe biraraya toplanır ve global optimum sonucu sağlar. Global optimumu bulunmasına katkı sağlamayacak şemaların görülme sıklığının artışı ıraksamaya sebep olacaktır. Bu sonuç, aldanma olarak bilinir. Aldanma için epistasis gerekli fakat yeterli değildir.

 Evrimci Algoritmaların Çalışması

Yaratıcılarınca dahi tam olarak anlaşılamadığı halde, doğal seçim sürecine benzeşimle evrim geçirerek problem çözen bilgisayar programları [18] olan EA’nın iyi çalışmasını garantileyebilmek amacıyla deneye dayalı kuralların bulunmasına dönük araştırmaların sonucu ulaşılmış ve kabul görmüş bir genel teori henüz yoktur [12]. Yine de başarılı uygulamalar geliştirilmesinde yardımcı olan ve EA’nın başarısını kısmen izah edebilen iki ekol vardır. Sırasıyla izah edilmiş olan bu iki yaklaşım Şema Teoremi ve Yapıtaşı Hipotezi’dir [12]. Şema teorisinin bir özelliği de EA’nın sahip olduğu aleni ve üstü örtülü paralellik(koşutluk) özelliklerinden ikincisini açıklamasıdır. Aleni paralellik, çözüm sağlayacağı umulan birden fazla parametre  Arama Uzayında Keşif ve Keşfin Kullanımı

Global maksimumun bulunması için etkin optimizasyon algoritmasının kullanması gereken iki teknik, arama uzayının yeni ve bilinmeyen bölgelerini araştırmak üzere yapılan keşif ve daha önce tetkik edilen noktalardan elde edilen bilginin daha iyi noktalar bulmak üzere kullanılmasıdır. İyi bir arama algoritması, çelişen iki gereklilik arasında bir denge noktası bulmalıdır.

Sade rasgele arama, keşif konusunda iyi olduğu halde keşfin kullanımı söz konusu değildir. Tepe-tırmanma yöntemi ise az keşif yapmasına karşı keşfin kullanımı konusunda başarılıdır. Bu iki yöntemin birleştirilerek kullanımı gayet verimli olabilir. Ancak, daha fazla keşif yapmaya karar vermeden önce mevcut keşfin kullanımına ne kadar süreyle devam edileceği konusunda dengenin bulunması kolay olmayabilir.

Holland göstermiştir ki EA, keşif ve keşif kullanımını aynı anda ve en uygun şekilde birleştirmektedir. Teoride doğru olmasına karşın, uygulamada, kaynağı Holland’ın basitleştirici kabulleri olan kaçınılmaz sorunlar mevcuttur. Bu kabuller:

1.      Toplululuk nüfusu sonsuzdur.

2.      Uygunluk fonksiyonu, çözümün işe yararlığı için doğru göstergedir.

3.      Kromozomdaki genlerarası etkileşim bariz değildir.

Birinci kabulün, uygulamada gerçekleştirilmesinin imkansızlığına bağlı olarak EA stokastik hataya açık olacaktır. Test fonksiyonlarının nispeten kolayca sağladığı ikinci ve üçüncü kabullerin, gerçek problemlerde sağlanması daha güç olabilir [12].

 Kullanılabilirlik

Geleneksel EA uygulamalarının çoğunluğu, fonksiyonların sayısal optimizasyonunda yoğunlaşmıştır. Süreksizlik içeren, çok-tepeli, gürültülü verilerin ve fonksiyonların optimizasyonunda diğer yöntemlerden daha başarılı olduğu gösterilmiş olan EA, rasgele verilerin modellenmesi için çok uygundur [13].

Öğrenme yeteneğine sahip sistemlere yönelik uygulamaları da olan EA’nın, ekonomik modelleme ve piyasa işlemleri [13] gibi belirli bir durumu analiz ederken kural tabanlı gelişim göstermesi sağlanabilir.

Evrimci Yapay Sinir Ağları

Yapay Sinir Ağları ve Evrimci Arama süreçlerinin ortak kullanımı ile türetilen Evrimci Yapay Sinir Ağları (EYSA), sağladığı öğrenme yeteneği olan daha etkin yapay sistemler tasarım olanağı ile ilgi görmektedir. Ayrı ayrı, çeşitli amaçlarla kullanılan bu yaklaşımların etkileşimli kullanımı konu olduğunda bahsedilebilecek uygulamalar, YSA bağlantı ağırlık değerlerinin, YSA yapısının ve YSA öğrenme kurallarının belirlenmesidir [20, 21, 22]. Genel çerçevesi Şekil 4.8’de verilen etkileşimli üç evrim süreciyle başarımı en iyileştirilmiş YSA tasarımı gerçekleştirilebilir. Gerçekleştirilen uygulamada, zaman serisi modellemede kullanılan YSA’ nın bağlantı değerleri geri yayınım algoritmasının yanısıra evrimci algoritma kullanımıyla belirlenmiştir.

Şekil 4. 8 Evrimci Yapay Sinir Ağı genel yapısı

EYSA Bağlantı Ağırlıklarının Evrimi

YSA’da öğrenme, denetimli veya denetimsiz gerçekleşebilir. Önceden belirlenmiş uygunluk kriteri gerçeklenmek üzere ağırlıkların ayarlanma süreci olan denetimli öğrenmede en sık kullanılan eğitim algoritması geriyayınımdır(backpropagation). Gradyan azaltarak arama yapan yöntem, YSA çıktısı ile hedef değer arasındaki

farktan doğan hatanın karesinin ortalaması veya bu ortalamanın karekökünün minimizasyonunu hedefler. Daha önce de belirtildiği üzere, çok tepeli fonksiyonlarda yerel minimum problemiyle başedemez ve türevlenemeyen fonksiyonlarla işlem yapamaz. Başarılı uygulamaları görmek ve daha detaylı bilgi edinmek için [20, 21, 22]’ye ve referanslarına bakılabilir.

Yerel minimum probleminin üstesinden gelmekte, uygunluk değerlendirmesi için YSA’nın hata kriteri seçilerek, evrim sürecine işlerlik kazandırılabilir. Sürecin belli başlı adımları aşağıda verilmiştir.

1.      Kromozomların, ağırlık değeri olarak atanması

2.      Uygunluk değerinin hesaplanması

3.      Uygunluk değerini gözeterek çoğalma sürecinin başlatılması

4.      Genetik operatörleri kullanarak yeni neslin elde edilmesi

Kromozomları oluşturan ağırlık değerlerinin gösterimi ve benimsenen evrim süreci, evrimci eğitim sürecinin iki ana başlığını teşkil eder. Ağırlık değerlerinin temsilinde gerçel sayılı veya iki tabanlı gösterim kullanılabilir.

 İki Tabanlı Gösterim

Her ağırlık değeri, sabit uzunluklu bit dizisi ile temsil edilir. Kromozomlar ise bit dizilerinin biribirine eklenmesiyle elde edilir. İki tabanlı gösterim kullanıldığı durumlarda doğrudan iki tabanında kodlamanın yanısıra Gray kodu, üssel kodlama veya daha karmaşık bir kodlama kullanılabilir. Gösterimin çözünürlüğü, belirlenmeye çalışılan ağırlık değerinin hassasiyetini belirlediğinden hayati önem

taşır. Çok kısa gösterim yakınsamayı imkansızlaştırabilecekken uzun gösterim işlem yükünü ve süresini arttırır. Kullanılacak bit sayısının optimizasyonu, kodlamada kullanılacak değer aralığı, kodlama yöntemi açık problemdir [7].

İki tabanlı gösterimin noksanlarını gidermek üzere her bir ağırlığa karşılık bir gerçel sayı ataması önerilen yöntemde kromozomlar, değerlerin dizi oluşturacak tarzda sıralanmasıyla oluşturulur [23, 21, 22]. Çaprazlama işlemi, diziyi herhangi bir noktadan bölerek gerçekleşebileceği gibi genleri bölerek basamak düzeyinde de gerçekleşebilir. Ebeveynlerin ortalamasını alan çaprazlama, rasgele mutasyon ve arama uzayına özel tanımlanabilecek işlemler, genlerin uygunluk değerini arttıracak gelişimi sağlayan diğer genetik operatörlerdir. Montana ve Davis, çalışmalarında gelişime açık evrimci yaklaşımın eğitim süresinin, ilgilendikleri problem için, geriyayınım algoritmasına göre daha kısa olduğu sonucuna ulaşmışlardır [21]. Benzer sonuca ulaşan Bartlett ve Downs EYSA’nın boyutlarının artımıyla yakınsama süreleri arasındaki farkın evrimci algoritmalar lehine açıldığı sonucuna ulaşmışlardır. Bu sonucun genel olarak doğru olduğunun teyit edilmesi için daha fazla çalışma yapılması gerekmektedir [21].

 Evrimci Eğitim ve Geriyayınımlı Eğitim Karşılaştırması

EA gibi global arama algoritmalarına dayanan ve yerel minimumlara yakalanmayan evrimci eğitim, daha önce de belirtildiği üzere, karmaşık, çok tepeli ve türevlenemeyen fonksiyonların da dahil olduğu geniş bir problem uzayına çözüm sağlayabilmesi sebebiyle caziptir. Hata fonksiyonun türevine ihtiyaç duymaması nedeniyle türevlenemeyen hata fonksiyonlarıyla karşılaşıldığında sıkıntı yaşamaz. Ayrıca, eğitilmek istenen YSA’nın türüyle ilgili kısıtlama getirmez. Algoritmik açıdan, EA’nın ve özel olarak EA’nın global örnekleme yeteneği ince ayar yapabilme yeteneğinin önüne çıkar. Üç katmanlı ve ileri beslemeli YSA’lar için belirtilen avantajlarına karşı, evrimci algoritmaların hesaplama maliyeti yüksektir [22].

 Hibrid Eğitim Yaklaşımı

Evrimci eğitimin etkinliği, EA’nın global örnekleme yeteneği ve yerel arama yaklaşımının ince ayar becerisiyle birleştirilerek arttırılabilir. Yüksek uygunluk değeri vaad eden bir bölgenin bulunması için EA kullanımını takiben bölgede arama yapmak üzere yerel arama yöntemleri işletilebilir.

Belew, ağırlıkların ilk değer atamasını EA kullanarak yaptıktan sonra bulduğu yeterince iyi değerleri iyileştirmek için geri-yayınım algoritması kullanmıştır [21]. Sistemin başarımı, sade EA’ya ve sade geri-yayınıma göre nispeten artmıştır.