Genetik Algoritmanın Tanımı
Genetik algoritma doğadaki evrim mekanizmasını örnek alan bir arama metodudur ve bir veri grubundan özel bir veriyi bulmak için kullanılır. Genetik algoritmalar 1970’lerin başında John Holland tarafından ortaya atılmıştır. Genetik Algoritmalar Evrimsel Genetik ve Darwin’in Doğal seleksiyonuna benzerlik kurularak geliştirilmiş “iteratif ” ihtimali bir arama metodudur.
Genetik algoritmalar doğada geçerli olan en iyinin yaşaması kuralına dayanarak sürekli iyileşen çözümler üretir. Bunun için “iyi”nin ne olduğunu belirleyen bir uygunluk (fitness) fonksiyonu ve yeni çözümler üretmek için yeniden kopyalamadeğiştirme (mutation) gibi operatörleri kullanır. Genetik algoritmaların bir diğer önemli özelliği de bir grup çözümle uğraşmasıdır. Bu sayede çok sayıda çözümün içinden iyileri seçilip kötüleri elenebilir.
Genetik algoritmaları diğer algoritmalardan ayıran en önemli özelliklerden biri de seçmedir. Genetik algoritmalarda çözümün uygunluğu onun seçilme şansını arttırır ancak bunu garanti etmez. Seçim de ilk grubun oluşturulması gibi rasgeledir ancak bu rasgele seçimde seçilme olasılıklarını çözümlerin uygunluğu belirler.
Genetik Algoritmaları (GA) diğer metodlardan ayıran noktalar şu şekilde sıralanabilir:
(recombination)
GA sadece bir arama noktası değil bir grup arama noktası (adaylar ) üzerinde çalışır. Yani arama uzayında yerel değil global arama yaparak sonuca ulaşmaya çalışır. Bir tek yerden değil bir grup çözüm içinden arama yapar.
GA arama uzayında bireylerin uygunluk değerini bulmak için sadece “amaç - uygunluk fonksiyonu” (objective-fitness function ) ister. Böylelikle sonuca ulaşmak için türev ve diferansiyel işlemler gibi başka bilgi ve kabul kullanmaya gerek duymaz.
Bireyleri seçme ve birleştirme aşamalarında deterministik kurallar değil “ olasılık kuralları” kullanır.
Diğer metodlarda olduğu gibi doğrudan parametreler üzerinde çalışmaz. Genetik Algoritmalar optimize edilecek parametreleri kodlar ve parametreler üzerinde değil bu kodlar üzerinde işlem yapar. Parametrelerin kodlarıyla uğraşır. Bu kodlamanın amacı orjinal optimizasyon problemini kombinezonsal bir probleme çevirmektir.
Genetik algoritma ne yaptığı konusunda bilgi içermez nasıl yaptığını bilir. Bu nedenle kör bir arama metotudur.
Olasılık kurallarına göre çalışırlar. Programın ne kadar iyi çalıştığı önceden kesin olarak belirlenemez. Ama olasıklıkla hesaplanabilir.
GA kombinezonsal bir atama mekanizmasıdır.
Genetik Algoritmalar yeni bir nesil oluşturabilmek için 3 aşamadan geçer:
1. Eski nesildeki her bir bireyin uygunluk değerini hesaplama.
2. Bireyleri uygunluk değerini göz önüne alarak (uygunluk fonksiyonu ) kullanılarak seçme.
3. Şeçilen bireyleri çaprazlama (crossover) mutasyon (mutation) gibi genetik operatörler kullanarak uyuşturma.
Algoritmik bakış açısından bu aşamalar mevcut çözümleri lokal olarak değiştirip birleştirmek olarak görülebilir.
Genetik Algoritmalar; başlangıçta bilinmeyen bir arama uzayından topladığı bilgileri yığıp daha sonraki aramaları alt arama uzaylarına yönlendirmek için kullanılır.
Kodlama Yöntemleri
Kodlama planı Genetik algoritmanın önemli bir kısmını teşkil eder. Çünkü bu plan bilginin çerçevesini şiddetle sınırlayabilir. Öyle ki probleme özgü bilginin bir kromozomsal gösterimiyle temsili sağlanır. Kromozom genellikle problemdeki değişkenlerin belli bir düzende sıralanmasıdır. Kromozomu oluşturmak için sıralanmış her bir değişkene “gen” adı verilir. Buna göre bir gen kendi başına anlamlı genetik bilgiyi taşıyan en küçük genetik yapıdır. Mesela; 101 bit dizisi bir noktanın x-koordinatının ikilik düzende kodlandığı gen olabilir. Aynı şekilde bir kromozom ise Bir ya da daha fazla genin bir araya gelmesiyle oluşan ve problemin çözümü için gerekli tüm bilgiyi üzerinde taşıyan genetik yapı olarak tanımlanabilir. Örnek vermek gerekirse; 100011101111 x1 y1 x2 y2 koordinatlarından oluşan iki noktanın konumu hakkında bize bilgi verecektir.
Bu parametreleri kodlarken dikkat edilmesi gereken en önemli noktalardan biri ise kodlamanın nasıl yapıldığıdır. Örnek olarak kimi zaman bir parametrenin doğrusal ya da logaritmik kodlanması GA performansında önemli farka yol açar.
Kodlamanın diğer önemli bir hususu ise kodlama gösteriminin nasıl yapıldığıdır. Bu da yeterince açık olmamakla birlikte GA performansını etkileyen bir noktadır. Bu konu sonradan anlatılacaktır.
Uygunluk Teknikleri
Başlangıç topluluğu bir kez oluşturulduktan sonra evrim başlar. Genetik algoritma bireylerin uygunluk ve iyiliklerine göre ayrılıp fark edilmesine gerek duyar. Uygunluk topluluktaki bir kısım bireyin problemi nasıl çözeceği için iyi bir ölçüdür. O problem parametrelerini kodlamayla ölçülür ve uygunluk fonksiyonuna giriş olarak kullanılır. Yüksek ihtimalle uygun olan bu üyeler tekrar üreme çaprazlama ve mutasyon operatörleriyle seçilirler.
Bazı problemler için bireyin uygunluğu bireyden elde edilen sonuç ile tahmin edilen sonuç arasındaki hatadan bulunabilir. Daha iyi bireylerde bu hata sıfıra yakın olur. Bu hata genellikle girişin tekrar sunulacak kombinezonlarının ortalaması veya toplamıyla hesaplanır (değerler değişkenlerden bağımsızdır). Beklenen ve üretilen değer arasındaki korelasyon etkeni uygunluk değerini hesaplamak için kullanılabilir. (Koza 1994).
Objektif fonksiyonu (Değerlendirme fonksiyonu) her bir kromozomun durumunu değerlendirmek için mekanizmayı sağlayan ana bir kaynaktır. Bu GA ve sistem arasında önemli bir bağlantıdır. Fonksiyon giriş olarak kodu çözülmüş şekilde kromozom (Phenotype) alır ve kromozomun performansına bir ölçü olarak bir objektif değer üretir. Bu diğer kromozomlar için de yapıldıktan sonra yapıldıktan sonra bu değerler kullanılarak uygun değerler uygunluk fonksiyonuyla hesaplanıp belli bir düzende planlanır. Bu planlamayı sağlayan ve uygunluk teknikleri olarak bilinen birçok yöntem vardır. Çoğu ortak kullanılan bu yöntemler şunlardır:
1. Pencereleme
Populasyonda en kötü kromozomun objektif değerinin Vw olduğunu kabul edersek her bir kromozomun i ve en kötü kromozomu arasında farkla orantılı bir uygunluk değeri fi atanabilir. Bu durum matematiksel olarak şu şekilde ifade edilebilir:
Fi=c±/Vi-Vw
Burada Vi kromozom i ‘nin objektif değeri ve c ise uygunluğun negatif çıkmamasını sağlayacak kadar büyük bir sayıdır. Eğer bir maksimizasyon problemiyle karşılaşılırsa denklemde pozitif işaret kabul edilir. Diğer yandan minimizasyon gerekliyse negatif işaret kabul edilir.
N
F=1/(1+å|Rpi-Rdi|)(2.2)
i=1
2. Lineer Normalizasyon
Objektif fonksiyonun maksimize veya minimize durumuna göre kromozomlar objektif değerin artma veya azalma düzenine göre sıralanır. En iyi kromozoma rastgele en iyi bir uygunluk fbest atanarak sıralanmış düzende diğer kromozomların uyguluğu lineer bir fonksiyonla bulunur:
Fi=fbest-(i-1).d
Burada d eksilme oranıdır. Bu teknik populasyonun ortalama objektif değerini ortalama uygunluk içerisinde ayrıntılarıyla planlamayı sağlar.
Bu iki teknikten başka kullanıcının kendisinin belirleyeceği başka yöntemler de mevcuttur.
Genetik
-
İnsanlarda Kaç Kromozom Vardır?
-
Sık görülen mikrodelesyon sendromları nelerdir?
-
Bilim insanları kromozomları nasıl inceler?
-
Arkea'da Kromozomlar ve DNA Replikasyonu
-
DNA Onarım Mekanizmaları Nelerdir?
-
DNA hasarına neden olan etkenler nelerdir?
-
XYY Süper Erkek Sendromu - JACOB’S, Sendromu
-
Bitki doku kültürü çalışmaları ile haploid bitkiler elde edilebilir
-
Gram pozitif bakterilerden genomik DNA izolasyon protokolü
-
E. coli bakterisinden genomik DNA izolasyon protokolü
-
DNA’nın Keşfi
-
İnsan Genom Projesi Nedir ? Amaçları Nelerdir ?
-
Genomik mikrodizilimlerle ikilenme teşhisi yöntemi
-
Gen duplikasyonu ve amplifikasyonu nedir?
-
DNA ile RNA Arasndaki Farklar ve Benzerlikler Nelerdir