Tarih 19. yüzyılın ortalarını gösterdiğinde kaşif rahip Darwin, canlı türlerinin ortak atalardan farklılaşarak evrimleştiği tezini ortaya atarak bilim dünyasında bitmek bilmeyen tartışmaların fitilini ateşlemiştir. 1859’da “Türlerin Kökeni” kitabı yayınlayan Darwin, doğada güçlü olan canlıların hayatta kaldığını, koşullara adapte olamayan türlerin elendiğini teorize etmiştir. Yavruların çeşitli nedenlerle ebeveynlerinden birazcık farklılık göstermeleri, sabit koşullar altında çoğu bireye dezavantaj sağlarken, değişen çevresel koşullarla birlikte bazılarına hayatta kalma konusunda avantaj sağlamaktadır. Avantajlı olanlar daha kolay ürer ve bu özelliklerini gelecek nesillere daha çok aktarırlar. Bu şekilde nesil ve popülasyon bazında avantajlı özellikler sayıca artar, dezavantajlı özellikler giderek azalır. Bu eleme-seçilim mekanizmasına Doğal Seçilim denir (Bakırcı, 2014) .

 En iyi olan yaşar kanununa bağlı olarak işleyen ve bir popülasyon üyelerinin rekabet sonucu elenmelerini modelleyen Genetik Algoritma Yöntemi, her ne kadar  1967 yılında Bagley tarafından keşfedilmişse de (ardından Rosenberg, De Jong) kuramsal olarak John Holland, meslektaşları ve Michigan üniversitesindeki öğrencileri tarafından geliştirilmiştir (Altay, 2015:8). Holland’ın 1975 yılında yayınlanan “Doğal ve Yapay Sistemlerde Uyarlama” adlı kitabı  ­Genetik Algoritmaları, doğada gözlemlenen evrimsel süreci taklit ederek çalışan arama ve en iyileme yöntemi olarak tarif eder. Algoritmanın amacı; karmaşık çok boyutlu arama uzayında en iyi kromozonların hayatta kalarak belirli bir durağanlık sonunda bütünsel en iyi çözümü aramaktır. ­Genetik Algoritmalar, evrimsel süreci simüle ederek, modeli belirli kısıtlar ve amaç fonksiyonu altında çözerek en iyilemeye çalışır.Yöntem özellikle polinom zamanda çözülemeyen zor problemleri (NP Hard) çözmek için evrim sürecinin bilgisayar aracılığıyla kodlandığı, en iyi  ya da en iyiye yakın sonuçların hesaplandığı bir sezgisel arama yöntemidir.

Bununla birlikte ilerleyen zamanlarda yöntem birçok alanda kullanılmıştır. Holland’ın ardından teorik yöntemi pratiğe döken Goldberg (1989) ‘’Genetic Algorithms in Search, Optimization and Machine Learning’’ kitabını yayımlamıştır. Ardından 1992’de John Koza, belirli görevleri yerine getirmek ve program geliştirmek için Genetik Algoritmayı kullanmış ve  metodunu “genetik programlama” olarak adlandırdı (Bozdogan 2003a:22). Günümüzde nerdeyse her alanda kullanılan yöntemin performansı gerek hibrit yöntemlerle gerekse de opsiyonel olarak gelişmektedir. Yöntemin en önemli ayrıcalığı, birçok arama algoritması lokal minima sorunu yaşarken, ­Genetik Algoritma bununla baş etmesidir (Minerva ve Paterlini, 2002:19). ­Genetik Algoritmada kromozomlar kendini devamlı kombine ettiği için (çaprazlama ve mutasyonlar sayesinde) araştırma uzayı devamlı genişler.

Genetik Algoritmanın Adımları

­Genetik Algoritmanın çalışma akış diyagramı aşağıdaki şemada gösterildiği gibi işlenmektedir.

Genetik Algoritmada Kullanılan Kavramlar

Algoritma işleyişinde kullanılan terimler ve analojiler konuyu anlama bakımından önemlidir. Algoritma elemanları ve tanımları aşağıda verilmiştir.

Gen: Bireylerin kalıtsal karakterlerini belirleyip, nesilden nesile aktaran kalıtım materyalidir. Her bir gen bir özelliği taşır. ­Genetik Algoritmada bir sayı ile ifade edilir. 0 veya 1 gibi.

Kromozom: Genlerin bir dizi halinde birleşerek oluşturdukları  yapılara denir. Algoritmada bir bireyi tarif eder.

0 1 0 1 1 0 1 1 0 1 1 0

Popülasyon: Birden çok bireyin (kromozom) bir araya gelerek oluşturduğu topluluğa denir. Algoritmada aday çözümler topluluğunu temsil eder. İsteğe göre popülasyon havuzundaki birey sayısı belirlenir. Genellikle 10 ya da katları olarak atanabilir.

Amaç Fonksiyonu: Hangi bireylerin hayatta kalacağını hangisinin eleneceğini belirleyen ve iterasyonlar sonucunda en optimal çözümü tespit eden sonuç kriteridir. Fonksiyonun tipine göre en büyük ya da küçük değerlere sahip olan bireyler seçilir.

Seleksiyon :    Popülasyon içerisinde amaç fonksiyonu tarafından hayatta kalabilen bireylerin seçilmesidir. Diğer kromozomlar elenecek, kalanlar tekrar algoritmaya tabii olacaktır.  Bu sayede güçlü bireylerin hayatta kalması hedeflenir. Güçlü bireyler tekrar üreme işlemine girer. Bunun için literatürde bir çok yöntem bulunur. Bunlara; Rassal Üreme, Rulet Çarkı Yöntemi, Beklenen Değer Yöntemi, Boltzmann Yöntemi, Sıralı Seçim Yöntemi, Turnuva Yöntemi, Elitizm Yöntemi gibi örnekler verilebilir. Bu opsiyonların her biri denenerek uygun çözüm aranabilir.

Çaprazlama: Çaprazlama (Crossing-over)  bu süreçte  kullanılan en önemli operatördür. Amacı popülasyonda olmayan bireyleri yaratarak bireyler arasındaki çeşitliliğin arttırılmasıdır (Altay, 2015:15).  

Algoritma içeresinde her çift için çaprazlama olabilmesi için bir olasılık katsayısı  belirlenir. Bu olasılığa bağlı olarak çaprazlama yapılıp yapılmayacağı belirlenir (Vural, 2015:16).

Mutasyon: Mutasyon, GA’da global bir arama gerçekleştirmek için kullanılan başka bir parametre veya operatördür. Bu esnada kromozomdaki bir gen değişikliğe uğrar. Mutasyon  içinde çok küçük bir olasılıkta bir katsayı  belirlenir. Böylece arama süreci bir bölgeden başka bir bölgeye atlayarak lokal minimadan kurtulur (Liu ve Bozdogan, 2008b:17).

Sonuç olarak döngü optimal çözümü buluna kadar aramaya devam eder. Eğer amaç fonksiyonunda belirli bir durağanlık sağlanırsa sona gelinir ve en iyi çözüme ulaşılır.

REGRESYON MODEL SEÇİMİNDE GENETİK ALGORİTMA KULLANIMI

Çok Değişkenli Lineer Regresyon modellerinin seçiminde Genetik Algoritma kullanımı ilk olarak Goldberg (1988) tarafından sunulmuştur. Bağımsız değişken sayısının çok fazla olduğu regresyon modellerinin her birinin test edilmesi gerek zaman açısından gerekse de maliyet açısından zordur. (Paterlini ve Minerva 2010), iki ayrı veri setine uyguladıkları analizlerde, Stepwise regresyon ile  Genetik Algoritma regresyon yöntemlerini karşılaştırmıştır. Sonuç olarak ikinci yöntemin daha anlamlı sonuçlar ürettiğini ve de Stepwise yönteminin lokal minimada takıldığını belirlemiştir. Bununla birlikte çalışmamızda 1 adet bağımlı değişken, 25 adet bağımsız değişken mevcuttur. Basit bir hesaplamayla toplamda  adet (yaklaşık olarak 70 milyon) altset arasından en uygununu bulmak, neredeyse imkansızdır.

Genetik Algoritma, popülasyon adı verilen bir dizi çözüm (kromozomlarla temsil edilen) ile başlatılır. Bir nüfustan çözümler alınır ve yeni bir nüfus oluşturmak için kullanılır. Bu, yeni nüfusun eskisinden daha iyi olacağı ön kabulü vardır. Yeni çözümler (offsprings) oluşturmak üzere seçilen çözümler, uygunluk değerlerine göre seçilir (Bozdogan, 2003a:17). Son olarak amaç fonksiyon değerinde durgunluk ve tekrarlar saptandığında algoritma nihai çözüme ulaşır.

Genetik Algoritma aracılığıyla en uygun regresyon modelinin seçilmesi süreci aşağıdaki adımlarla tanımlanabilir:

i) Mümkün regresyon modelleri için genetik kodlama şeması oluşturulması

Her regresyon modeli, dizedeki her geni-bağımsız değişkeni temsil edecek şekilde ikili (binary) kodla tariflendirilerek  bir dizi-kromozom oluşturulur. Burada değişkeninin (ya da genin) varlığını (1) veya yokluğunu (0) temsil eder. Her dize aynı uzunluğa sahiptir, ancak her biri farklı ikili kodlama içerir. Her kromozom bir  regresyon modelini  temsil eder.

Örneğin, k = 5 değişkenli bir regresyon modeli olsun. Kromozom ise [ 0 1 0 1 1 ] şeklinde kodlansın. Dikkat edilirse 5 gen mevcuttur. Sonuç olarak bu modelin en uygun olduğunu varsayarlırsa, modeli açıklayan değişkenler; ikinci, dördüncü ve beşinci bağımsız değişkenler olarak tespit edilirken, bir ve üçüncü değişkenler bağımlı değişkeni açıklama da anlamsız olarak belirmiştir.

ii) Model için başlangıç popülasyonun üretilmesi

Popülasyon büyüklüğü (yani, monte edilen model sayısı(n)) Genetik Algoritma’nın önemli bir parametresidir. Popülasyon büyüklüğü,  bir popülasyonda kaç kromozom olduğunu belirtir. Çok az kromozom varsa, Genetik Algoritma çaprazlama(crossover) gerçekleştirmek için az imkan bulur ve arama alanının sadece küçük bir kısmını araştırır. Öte yandan, çok fazla kromozom varsa, Genetik Algoritma yavaşlar. Araştırmalar, bazı sınırlardan sonra (esas olarak kodlamaya ve soruna bağlı olan) popülasyon boyutunu arttırmanın yararlı olmadığını göstermektedir. İlk önce n rastgele üreme modellerinin ilk popülasyonunu başlatılır.

iii) Modellerin performanslarını değerlendirmek için bir uygunluk (amaç) fonksiyonun belirlenmesi

Literatürde regresyon model seçimi için Genetik Algoritma kullanımında bir çok amaç fonksiyonu AIC (Paterlini ve Minerva, 2010), kNN (Oluleye vd. 2014), ICOMP (Liu ve Bozdogan 2008b)  kullanılmıştır. Araştırıcının inisiyatifine bağlı olan süreç, tutarlı ve sıralanabilir olmalıdır. Çalışmamızda amaç fonksiyonu olarak ICOMP (IFIM) bilgi kriteri kullanılacaktır. Buna göre en son nesil içerisinde en düşük puana sahip olan kromozom-birey hedef modelimiz olacaktır.

iv) Yeni nesiller üretmek için, ebeveynlerin çiftleşmesi ve üreme yöntemlerinin seçilmesi

Çiftleşme bir çaprazlama işlemi olarak gerçekleştirilir. Bu işlem Genetik Algoritmada kullanılan en önemli operatördür ve amacı popülasyona yeni bireyler yaratarak bireyler havuzundaki çeşitliliği arttırmaktır (Altay, 2015:15)  Geçiş için seçilen bir model, çaprazlama olasılığı (pm )  ile kontrol edilir. Çaprazlama olasılığı) genellikle araştırmacı tarafından belirlenir.  = 0 çarpma olasılığı, basitçe çiftleşme havuzunun üyelerinin bir sonraki nesle taşınması ve hiçbir yavru üretilmemesi anlamına gelir (Tek hücreli canlıların üreme şekli olan mitoz bölünme gibi). Çaprazlama olasılığı  = 1, çiftleşme havuzundan seçilen iki ana model arasında her zaman çiftleşmenin (çaprazlama) meydana geldiğini gösterir; bu nedenle gelecek nesil sadece yavru modellerden oluşacaktır (önceki nesilden hiçbiri yeni nesilde olmayacaktır).

Çaprazlama işlemi sırasında, geçiş noktası olarak her ana model çifti (dizeleri) boyunca rastgele bir nokta seçilir. Herhangi bir ebeveyn çifti için, kromozom geçiş noktasında iki parçaya bölünür ve bu noktanın sağındaki iki kromozomun kısımları iki yavru kromozomu oluşturmak için ebeveynler arasında değiştirilir. Her bir kromozomun uzunluğu boyunca rastgele seçilen bir nokta, modellerin kırıldığı ve daha sonra iki yeni model oluşturmak üzere başka bir ana parçaya yeniden bağlandığı çaprazlama noktası olur (Bozdogan, 2003a:23). Birçok çaprazlama operasyon seçeneği bulunmaktadır. Bunlardan en çok kullanılanları şu şekilde özetlenebilinir.

  • Tek noktalı çaprazlama

En basit çaprazlama yöntemidir. Keyfi olarak iki gen arasında bir nokta seçilir. Ardından kromozomun sağ tarafındaki genler karşılıklı olarak değiştirilerek iki adet yavru oluşturulur.

•   İki noktalı çaprazlama

Aynı bir noktalı çaprazlama yönteminde olduğu gibi, burada da kromozom iki nokta da parçalanır ve karşılıklı genler yer değiştirir.

  • Tekdüze (Uniform) çaprazlama

Daha fazla noktalı çaprazlama yöntemidir. Her kesim noktası arasındaki parçaların karşılıklı olarak değişimidir. Tesadüfi belirlenen genler arasındaki değişimi içerir.

Ayrıca kullanıcı ‘elitizm kuralı’ olarak adlandırılan seçim opsiyonuna da sahiptir. Yani iyi çözümlerden en az bir tanesi yeni popülasyona değişmeksizin geçer. Bulunan en iyi çözüm çalışmanın sonuna kadar canlı kalacaktır.

v) Yeni yavru modellerinin bileşimini değiştirmek için mutasyon uygulanması

Modellerin mutasyonu, arama işleminin sınırlı bir alanda arama yapmak yerine daha verimli başka bir alana atlayabilmesi için yeni değişken kombinasyonları oluşturmanın başka bir yolu olarak kullanılır. Rastgele seçilen bir genin 0 ila 1 veya 1 ila 0 arasında değişebileceği bir mutasyon oranı veya olasılığı (pm ) belirtilerek mutasyona izin verilir. Bu nedenle, rasgele seçilen bir bağımsız değişken modele eklenir veya modelden kaldırılır. Belirli çaprazlama ve mutasyon oranlarına bağlı olarak, ikinci nesil tamamen yavru modellerden ya da yavru ve ebeveyn modellerinin bir karışımından oluşacaktır. İkinci jenerasyondaki modeller daha sonra üçüncü jenerasyonu üretmeye gider; süreç, araştırıcı tarafından kontrol edilen belirli sayıda nesil için birbiri ardına devam eder. Algoritma artık birbirine yakın amaç değerleri üretmeyi sürdürürse süreç sonlandırılır.

GA sonucunda elde edilen en iyi Regresyon modelleri ve ICOMP(IFIM) Skorları: Örnek Şablon

En uygun regresyon modeli seçimi için GA uygulaması kullanılabilir. Bunu için gerekli adımlar şu şekilde olmalıdır.

İlk olarak gen popülasyonun kaç bireyden oluşacağına karar verilir. Yukarıda da bildirtildiği gibi sayı ne çaprazlama (cross-over) imkanını sekteye uğratacak kadar az, ne de  algoritmanın çalışmasına yavaşlatacak kadar çok olmalıdır. Yapılan simülasyon neticesinde  popülasyon büyüklüğünün (N) 30 olması uygun olacaktır.

Çaprazlama türü olarak  literatürde en çok rağbet gören ‘İki noktalı çaprazlama (two point cross-over)’ yöntemi kullanılmış ardından algoritmanın belirli bir bölgede tekrara düşmesini engelleyecek ve evrimleştirecek mutasyon oranı veya olasılığı (pm ) katsayısı belirlenmiştir. Bu sayı yaygın kullanıldığı haliyle 0,01 yani %1 olarak atanmıştır. Ayrıca algoritmaya opsiyonel olarak ‘Elitizm Kuralı’ şartı konulmuştur. Böylece kaliteli ebeveynlerdin en az bir tanesi yeniden oğul döllere değişmeksizin geçecektir. Algoritmanın bu şekilde en fazla 50  kuşak çalışması yeterlidir. Bunun nedeniyse algoritmanın belirli bir durgunluk halinden sonra gereksiz performans sergilemesini önlemektir. Amaç fonksiyonu olarak ICOMP (IFIM) bilgi kriteri kullanımı tercih edildi.

Mümkün alt setler içinde en iyi 30 regresyon modelini gösteren tablo aşağıda verilmiştir.

Tablo da görüldüğü gibi en son kuşağın oluşturduğu popülasyon içerisinde en düşük ICOMP(IFIM) skoru listenin en başındaki gen kombinasyonudur. Sonuca göre datadaki 10, 12, 23, 24 ve 25 numaralı değişkenlerin oluşturduğu regresyon modeli en uygun  alt set  olarak belirmektedir.

Regresyon uygulamalarında en uygun model seçimi için GA uygulaması prosedürü bu şekilde gerçekleşebilmekte olup, bütünleşik teknikler ile performans gelişimi sağlanabilir.

KAYNAKLAR

BAKIRCI, Ç. M.:  2011      “Evrim Mekanizmaları – 9 : Crossing-Over  Kromozomal Gen Değişimi ,” Evrim Ağacı, https://evrimagaci.org/evrim-mekanizmalari-9-crossingover-kromozomal-gen-degisimi-244, Accessed 06/21/2019. “Darwin’in Evrim Teorisi Nedir, Neler Söyler?,” Evrim Ağacı .

ALTAY, A.: 2015                Genetik Algoritma Ve Bir Uygulama, Fen Bilimleri Enstitüsü.İstanbul Teknik Üniversitesi

GOLDBERG, D. E.:  1988                “Genetic Algorithms and Machine Learning,” Machine Learning, 3, 95–99.

BOZDOGAN, H.: 2003b  “Intelligent Statistical Data Mining with Information Complexity and Genetic Algorithms,” in Statistical Data Mining and Knowledge Discovery, ed. by Bozdogan, H. Chapman and Hall/CRC.

MİNERVA, T., PATERLİNİ,  S.: 2002          “Evolutionary Approaches for Statistical Modelling,” Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02  Cat. No.02TH8600

LİU, M.,BOZDOGAN,  H.: 2008a “Multivariate Regression Models with Power Exponential Random Errors and Subset Selection Using Genetic Algorithms With Information Complexity | Liu | European Journal of Pure and Applied Mathematics,” European Journal Of Pure And Applıed Mathematıcs, 1, 4–37.