Genetik Algoritmasının babası olarak kabul edilen John Holland 1970’lerin başında algoritmanın orijinal halini geliştirmiştir. Genetik algoritması Sezgisel Arama Algoritmasıdır. Doğal seçilim ve genetik konularından esinlenerek mutasyon ve çarprazlama yöntemlerini de kullanarak verilen probleme çözüm sunmayı hedefler. Doğada ortama uyum sağlayan bireylerin daha uzun yaşadığı ve kendilerini geliştirdikleri halde türlerini daha uzun devam ettirdikleri bilinmektedir. Genetik algoritmasında da aynı temel mevcuttur. Daha iyi çözüm kümelerinin gelecek nesillere aktarılması daha olasıdır. Popülasyondaki bireyler daha uygun olan bireylerin şansı daha yüksek olacak şekilde belli sayıda eşleşir. Yeni bireyler meydana getirirken iki birey kromozomları arasında parça değişimi(krossing over) yapılarak yeni birey yani bir nevi çocuk meydana getirirler. Belli bir olasılığa bağlı olarak yeni meydana gelen bireyin genleri üzerinde mutasyona uğrayabilir. Daha uygun bireylerin eşleşme şansı yüksek olduğu için uygun bireyler hayatlarını devam ettirir, kötü bireyler ise popülasyondan elenmiş olur. Doğal seçilim süreci algoritmada işletilmiş olur.
İlk önce kullanabileceğimiz terimlerin açıklamalarını yapalım her ihtimale karşıJ
Doğal seçilim : Çevreye daha iyi uyum sağlayan bireylerin, bu elverişli özelliklere sahip olmayan diğer bireylere göre yaşama ve üreme şanslarının daha yüksek olması ve bunun sonucu olarak genlerini yeni kuşaklara aktarabilmelerini sağlayan evrimsel sürece verilen isimdir.
Kromozom : Kromozomlar gen adı verilen kalıtım ünitelerinin anne-babalardan çocuklara, dolayısı ile kuşaktan kuşağa kalıtılmasını sağlayan yapılardır. Kromozomların üzerinde; her türlü fiziki ve kimyasal özelliklerimizi taşıyan genler bulunur. Kromozom sayıları canlı türlerinde farklılık gösterir.
Gen : Ebeveynden çocuklarına geçen belirli bir karakteristiği taşıyan kromozom lokuslarında dizilen en küçük kalıtsal biyolojik birimdir.
Alel gen : Bir karakterin kalıtımından sorumlu gen çeşitlerinin her biridir.
Genotip : Bir canlının sahip olduğu genlerin toplamıdır.
Genom : Bir kalıtım birimi. Bir organizmanın kalıtım materyalinde bulunan genetik şifrelerin tamamını simgeler.
Parça değişimi: Çift halde bulunan kromozomların yaptığı parça değişimine verilen addır. Bunun sonucunda genetik rekombinasyon meydana gelir, yani farklı kromozomlarda bulunan genlerin alelleri birbiriyle yer değiştirir.
Mutasyon : Bir canlının genomu içindeki DNA ya da RNA diziliminde meydana gelen kalıcı değişmelerdir. Mutasyona sahip bir organizma ise mutant olarak adlandırılır.
Algoritma çalışma sistemi bu yöndedir gelin daha detaylı bir şekilde adım adım açıklayalım.
Özet Adımlar
Adımları sürüden esinlenildiği davranışlara karşılık gelen algoritmadaki işlemleriyle destekledim. Böylece algoritmanın orijinalini okuduğunuzda ve aşağıda algoritmanın detaylı örneklendirilmesinde kafa karışıklığı yaşamayacağınızı umuyorum.
| Esinlenen davranışlar | Algoritmada karşılık gelen eylem |
| Popülasyondaki bireylerin kromozom sayısını belirle ve kromozomdaki genleri rastgele yükle ve çevreye uygunluklarını hesapla. | Parametre boyutu belirle ve parametre sayısı kadar eleman içeren rastgele çözüm kümeleri oluştur. Oluşturulan çözüm kümelerinin uygunluk değerleri bulunur. |
| Eşleşme gerçekleştirecek bireyleri seç. | Rulet, Turnuva gibi yöntemler kullanarak eşleşme yapacak bireyler seçilir. |
| Seçilen bireyler arasında parça değişimi gerçekleştirilerek yeni bir birey meydana getirilir. | Seçilen iki çözüm kümesinin tek noktalı çarprazlama, çift noktalı çarprazlama gibi farklı parça değişim yöntemleri kullanarak çözüm kümelerinden seçilen parametreler ile yeni bir çözüm kümesi meydana getirilir. |
| Oluşturulan bireyin genleri üzerinde mutasyon gerçekleşebilir. | Eğer belli bir olasılık sağlanırsa oluşan çözüm kümesinde bir parametre rastgele olarak değiştirilir. |
| Belirlenen tekrar sayısına ulaşıncaya kadar 2. Aşamaya geri dönülür. | Maksimum iterasyona ulaşıncaya kadar 2. Aşamaya geri dönülür. |
Algoritmada Tanımlar ve Detaylı Çözüm
Bu bölümde algoritmadaki önemli değişkenlerden bahsedeceğim. Ayrıca paragrafa noktayla başlayan yer alan değerler aşağıda örneklerde kullanacağım değer olacak. Uygunluk fonksiyonu için Optimizasyon Test Fonksiyonlarından Sphere Fonksiyonu örnek olarak kullanılacaktır. Optimizasyon için Test Fonksiyonları makalemden test fonksiyonlarının ne olduğunu ve Sphere Fonksiyonu ile ilgili detayları bulabilirsiniz.
Problem : Algoritmada çözüm aradığımız problemdir ve genellikle bir matematiksel formülle belirtilir.
- Biz iki sayının karelerinin toplamının en küçük değeri arayacağız yani Sphere Test Fonksiyonu. Örnek olması açısından kolay ve basit olan Sphere Test Fonksiyonunu seçtim. Biz burada x1 ve x2 iki parametre değerlerini algoritmada arayacağız. Gerçek hayatta bu problemi çözmek için sezgisel optimizasyon algoritmaları kullanmayacağınıza eminim J .
Uygunluk fonksiyonu : Algoritmada problem için bulduğumuz çözüm kümelerinin iyilik derecesini bulmamıza yarayan formül. Sizin probleminize göre matematik modelinizi kendiniz belirlemeniz gerekir. Bu bölüm için sezgisel optimizasyon algoritmaları adlı makaleyi tekrar okumanızı tavsiye ediyorum. Biz yukarıdaki test problemimiz Sphere’nin fonksiyonunu uygunluk fonksiyonu olarak kullanacağız.
- Sphere Formülü:
yani iki parametre için x12 + x22
Popülasyon Boyutu: Popülasyondaki birey sayısının toplamıdır. Yani bir iterasyondaki çözüm kümesi sayısı.
- 10
Paremetre Boyutu: Uygunluk fonksiyonumuzda bilinmeyen değişkenlerin sayısını ifade eder. Genetik algoritmamızda kromozom sayımızda denilebilir.
- Görüldüğü üzere bizim problemimizde x1 , x2 olmak üzere 2 parametremiz var.
Paremetre Aralığı: Parametrelerin alabileceği en büyük ve en küçük değerlerdir. Sizin probleminize göre parametre aralığını kendiniz belirlemeniz gerekir. Ne kadar nokta atışı parametre değer aralığı ayarlarsanız. Algoritmanızdan o kadar iyi sonuçlar elde edebilirsiniz.
- En küçük = -5.2, En büyük = 5.2 yani -5.2 ≤ xi ≤ 5.2. Ayrıca isterseniz her parametrenin en küçük ve en büyük değerlerini ayrı olarak belirleyebilirsiniz. Ben bu problemde iki parametre içinde aynı değer aralıkları belirledim.
Maksimum İterasyon: Algoritmanın çalışacağı maksimum döngü sayısını belirtir. Her bir iterasyonda tüm işlemler tekrar eder. Maksimum iterasyonu ne kadar büyük tutarsanız algoritmanın en uygun değeri bulma olasılığı artacaktır. Fakat buda size zaman ve hız kaybı yaşatacaktır. Bu yüzden en uygun maksimum iterasyonu ihtiyaçlarınıza göre belirleyiniz.
- 100
Seçilme yöntemi: Yeni birey meydana getirecek bireylerin seçim yöntemidir. Bir nevi doğacak çocuk için anne baba yani ebeveyn seçmek gibide düşünebiliriz. Seçim yapılırken doğal seçilimin gerçekleşmesi için ortama daha uygun bireylerin seçim olasılıkları yüksek olmalıdır. Seçim yöntemlerinin bazıları aşağıda anlatılacaktır.
- Rulet yöntemi
Seçilme sayısı veya oranı: Bir popülasyonda bir iterasyon için kaç tane ebeveyn seçileceğin belirtir. Bir iterasyonda oluşacak yeni çözüm kümesine doğrudan etki eder.
- 10 veya %50
Parça değişim yöntemi: Üreme için seçilen bireylerin çözüm kümeleri arasında parametre değiş tokuş şeklinin nasıl yapılacağını belirleyen yöntemdir.
- Tek noktalı çarprazlama
Mutasyon oranı: Genellikle 0 ile 1 arasında sayı oluşturulur. Eğer bu sayı mutasyon oranından küçük ise oluşan yeni bireyin bir geninde mutasyon gerçekleştirilir.
- 0.01
1- a) Bireylerin gen değerlerinin rastgele belirlenmesi : İlk aşama olarak her çözüm kümesi için parametre boyutu kadar en küçük ve en büyük parametre değerlerine göre rastgele çözüm kümesi oluşturulur. Uygunluk değerleri uygunluk fonksiyonu ile hesaplanır.
| Parametre değeri atama formülü [f.1]: | Xik = lbj + rand(0,1) x (ubj – lbj) |
i = Seçilen çözüm kümesinin indeks numarası
k = i seçilen çözüm kümesinde seçilen parametrenin indeks numarası
Xik = Seçilen çözüm kümesinin geçerli parametre numarası
rand(0,1) = 0 ile 1 arasında rastgele sayı
lbj = Parametrenin alabileceği minimum sayı
ubj = Parametrenin alabileceği maksimum sayı
Kromozom sayısı 2 olduğu için parametre sayımız 2 ydi. Xi =[ Xi1, Xi2]
X11 = 1.0 + rand(0,1) x (5.0 – 1.0) = 3.8 -> Birinci çözüm kümesi 1. parametre için
X12 = 1.0 + rand(0,1) x (5.0 – 1.0) = 2.5 -> İkinci çözüm kümesi 2. parametre için
X1 = [3.8, 2.5]
Bu yöntem ile 2 rastgele çözüm kümesi oluşturulur. Örnek olarak:
X2 = [-1.1, 1.2]
X3 = [-1.5, -2.2]
X4 = [3.5, -4.2]
X5 = [3.1, 1.2]
Şimdi bir çözüm kümesinin örnek olarak bizim uygunluk değerini hesaplayalım.
X1 = [3.8, 2.5] à U1 = 3.82 + 2.52 = 20.69
Diğerleri de aynı yöntem ile hesaplanır ve alttaki sonuçlar bulunur.
U1 = 20.69, U2 = 2.65, U3 = 7.09, U4 = 29.89, U5 = 11,05
BAŞLA
2-) Seçilme yüzdesi veya sayısı kadar seçim yapılması : Bizim popülasyon sayımız 20, seçim yüzdemiz ise %50 bu nedenle 20*(50/100) = 10 tane çift seçimi yapmamız gerekiyor. Bu eşleşmeleri yaparken her bir eşleşme için bireyler seçmemiz lazım. Seçim yöntemlerinden örneklerle yeri gelmişken bahsedelim:
Seçim yöntemleri:
Çift seçimi yapılırken çeşitli yöntemlerden yararlanabilirsiniz. Meşhur olanlardan Rulet Tekerleği Yöntemi ve Turnuva Yönteminden bahsedeceğim.
2-A) Rulet Tekerleği Yöntemi:
Çarkıfelek yarışmasını hatırlamayanınız yoktur heralde? Çark çevrilir ve ok hangisi seçenekte durursa o seçenek seçilmiş olur. Çarkta aynı seçenek ne kadar fazla alanda olursa okun o seçeneğe denk gelme olasılığı artar. Rulet yöntemi bu yöntem ile seçimini gerçekleştirir. Tüm uygunluk değerleri toplanır ve uygunluk değerlerinin iyi olanlara çarkta daha büyük alana sahip olacak şekilde formülüze edilir.
Bizim bulduğumuz uygunluk değerleri:
U1 = 20.69 ,U2 = 2.65, U3 = 7.09, U4 = 29.89, U5 = 11.05
Maksimizasyon problemler için:
En büyük değere uyarlama için yani uygunluk değeri büyük değerse daha iyi sonuç ifade ediyorsa aşağıdaki yöntem uygulanır.
Tüm uygunluk değerlerini toplayalım:
To = 
= 20.69+2.65+7.09+29.89+11.05 = 71.37
Şimdi sırayla yüzdeler belirlememiz gerekir. Bunun için uygunluk değerinin ne kadarlık kısıma denk geldiğine bakalım: Yüzdei = (100*Ui) / To
Yüzde1 = 29, Yüzde2 = 4, Yüzde3 = 10, Yüzde4 = 42, Yüzde5 = 15
Minimizasyon problemler için:
Bizim problemimizde minimizasyon yani düşük uygunluk değerleri daha iyi çözümler olduğunu belirtiyor. O yüzden küçük değerler rulet çarkından daha büyük yüzde ayrılması lazım. Yukarıdakiler aynen uygulanır sadece ilk önce tüm uygunluk değerleri 1’e uyarlanır.
U1 = 20.69, U2 = 2.65, U3 = 7.09, U4 = 29.89, U5 = 11.05
O1 = 1/20.69 = 0.05
O2 = 1/2.65 = 0.38
O3 = 1/7.09 = 0.14
O4 = 1/29.89 = 0.03
O5 = 1/11.05 = 0.09
- Adım olarak tüm oranlar toplanır
To = 
= 0.05 + 0.38 + 0.14 + 0.03 + 0.09 = 0,69
Şimdi sırayla yüzdeler belirlememiz gerekir. Bunun için uygunluk değerinin ne kadarlık kısıma denk geldiğine bakalım: Yüzdei = (100*Oi) / To
Yüzde1 = 7, Yüzde2 = 55, Yüzde3 = 20, Yüzde4 = 5, Yüzde5 = 13
Şimdi minimizasyon içinde maksimizasyon içinde aynı yöntemi uygulayacağız. Yüzdelere bağlı seçim yapmamız gerekiyor. Bunun için değişik yöntemler uygulanabilir. Bizim kullanacağımız yöntem 0 ile 100 arasında rastgele sayı üreteceğiz ve sırayla tüm uygunluk değerlerini 100 den çıkarmaya başlayacağız. Ne zaman ki ürettiğimiz rastgele sayı bulduğumuz sayının içindeyse seçtiğimiz sayıyı bulduk demektir. Bir örnekle açıklayalım:
- arası rastgele bir sayı üretmiş olalım : 0.45 -> 0.45*100 = 45
0-100 arası rastgele ürettiğimiz sayı 45 oldu. Şimdi 100 den sırayla bulduğumuz yüzdeleri çıkartalım.
Yüzde5 = 100 – 13 = 87 -> 87 45’ten küçük değil
Yüzde4 = 87 – 5 = 82 -> 82 45’ten küçük değil
Yüzde3 = 82 – 20 = 62 -> 62 45’ten küçük değil
Yüzde2 = 62 – 55 = 7 -> 7 45’ten küçük
İlk seçilen birey 2. Birey oldu. Aynı yöntemle bir birey daha seçelim
0-1 arası rastgele bir sayı : 0.65 -> 0.65*100 = 65
Yüzde5 = 100 – 13 = 87 -> 87 65’ten küçük değil
Yüzde4 = 87 – 5 = 82 -> 82 65’ten küçük değil
Yüzde3 = 82 – 20 = 62 -> 62 65’ten küçük
İkinci seçilen birey ise 3. Birey oldu. Böylece çarprazlama yapacağımız bireyleri bulmuş olduk. Bir dip not eğer ikiside aynı birey çıktıysa ayrı bireyler oluncaya kadar seçim adımını tekrarlatabilirsiniz.
2-B) Turnuva Yöntemi:
Bu yöntemde popülasyon içinden rastgele 4 birey seçilir. Bu bireylere A,B,C,D diyelim. İlk A ile B karşılaştırılır. Uygunluk değeri daha olan birey seçilir. Sonrada C ile D karşılaştırılır yine uygunluk değeri iyi olan birey seçilir. Böylece uygunluk değeri iyi olan iki bireyimiz seçilmiş olur.
Şimdi örnek verelim rastgele seçilen bireylerimiz 2,3,1,4 olsun
U1 = 20.69, U2 = 2.65, U3 = 7.09, U4 = 29.89, U5 = 11.05
U2 < U3 olduğu için U2 daha iyi uygunluk değerine sahip o yüzden seçilen birey 2. Birey
U1 < U4 olduğu için U1 daha iyi uygunluk değerine sahip o yüzden seçilen birey 1. Birey
3-) Bireylerin Kromozomları Arasında Parça Değişimi : Seçim yöntemleriyle seçilen 2 bireyin kromozomları arasında parça değişimiyle yeni bir birey meydana getirilme olayıdır. Parça değişimi için çeşitli yöntemler mevcut. Bunlardan bazıları aşağıda açıklanacaktır.
Parça Değişimleri:
Parça değişim örnekleri için parametre boyutu 8 olan örnek iki çözüm kümesi kullanılacaktır. 2 parametreli örneklerde parça değişim yöntemleri çok anlaşılmayacağı için bu örnek çözüm kümeleri kullanılacaktır.
X1 = [1.1, -2.1, 3.0, 4.2, -2.5]
X2 = [2.2, 0.5, -4.4, -1.5, 1.2]
3.A-)Tek Noktalı Çarprazlama Yöntemi
Parametre noktalarından biri rastgele seçilir. O noktaya kadar 1. Bireyden o noktadan sonrası ikinci bireyden genler alınır. Örneğin rastgele seçilen noktamız 2’nin sonu olsun:
X1 = [1.1, -2.1, 3.0, 4.2, -2.5] İkinci parametre dahil başlangıçtan itibaren
X2 = [2.2, 0.5, -4.4, -1.5, 1.2] İkinci parametreden sonra
1.Yeni birey = [1.1, -2.1, -4.4, -1.5, 1.2]
İstenilirse tam tersi şekilde 2.bireyde oluşturulabilir:
2.Yeni birey = [2.2, 0.5, 3.0, 4.2, -2.5]
3.B-)Çift Noktalı Çarprazlama Yöntemi
Bu yöntemde ilk ve son parametreler dahil edilmeden aralarında iki nokta seçilir. Bu iki nokta arasındaki genler birinci bireyden kalan genler 2. Bireyden alınarak yeni birey oluşturulur. Örnek noktalarımız 2’nin sonu ve 4’ün sonu olsun:
X1 = [1.1, -2.1, 3.0, 4.2, -2.5] İkinci parametre sonundan dördüncü parametre sonuna
X2 = [2.2, 0.5, -4.4, -1.5, 1.2] Kalan kısım
1.Yeni birey = [2.2, 0.5, 3.0, 4.2, 1.2]
İstenilirse kırmızı kesimle 2.Yeni bir birey oluşturulabilir.
2.Yeni birey = [1.1, -2.1,-4.4, -1.5, -2.5]
3-) Mutasyon : Mutasyon oranına bağlı olarak oluşturulan yeni bireyimizin geninde mutasyon gerçekleştirmektir. Örneğin mutasyon oranımız 0.01 olsun, 0 ve 1 arasında rastgele sayı oluşturalım eğer 0.01 den küçükse mutasyon olayını gerçekleştirebilir. Orandan anlaşılacağı üzere mutasyon olasılığımız yüzde bir. Diyelim ki oluşturulan rastgele sayı 0.009 olsun, 0.01’den küçük olduğu için mutasyon olayımız gerçekleşir. Mutasyon içinse yeni bireyimiz [1.1, -2.1, -4.4, -1.5, 1.2] olsun. Rastgele bir parametre indeksi seçilir. Seçilen parametre 2 olsun, parametre 2’ye [f.1] formülü uygulanır yani rastgele yeni değer belirlenir. Yeni rastgele değerimiz 3.4 olsun böylece yeni bireyimiz [1.1, 3.4, -4.4, -1.5, 1.2] olur.
| Parametre değeri limit kontrolü [f.2]: | Eğer Xit>ubi→ Xit= ubi |
| Eğer Xit<lbi→ Xit= lbi |
i = Seçilen çözüm kümesinin indeks numarası
k = i seçilen çözüm kümesinde seçilen parametrenin indeks numarası
Xik = Seçilen çözüm kümesinin geçerli parametre numarası
lbj = Parametrenin alabileceği minimum sayı
ubj = Parametrenin alabileceği maksimum sayı
Yukarıdaki işlemlerden sonra parametre değer aralık dışına çıkılmaması için uygulanabilir. İsteğe bağlıdır. Bizim parametre aralığımız -5.12 ile 5.12 aralığındaydı. Örneğin X1,1 değerini 6.5 bulsaydık 5.2’ye, -6.4 bulsaydık -5.2 ye eşitleyecektik çünkü parametre sınırları aşılmış olacaktı.
