Genetik Algoritmalar ve Tarihçesi
Genel Bilgiler
Modern bilimde veri kümeleri arasındaki ilişkileri tecrübelerden de faydalanarak belirlemek üzerinde çokça çalışılan ve araştırılan bir taslaktır. Günümüzdeki araştırma konuları ve problemleri eskiye nazaran çok daha karışıktır. Bu karışıklık problemi etkileyen parametre sayısının fazlalığından ve problemin çözüm kümesinin boyutunun büyümesinden kaynaklanmaktadır. Bundan dolayı elinizdeki verilerin analizi ve sonucu bu verilerden kestirme yöntemlerinin önemi araştırmacılar için gittikçe artmaktadır. Faydalı iyi bir veri analiz yöntemi şu kriterlere göre değerlendirilebilir. İyi tahmin veya sonucu kestirmeye yönelik olmalı sistemin içindeki her bir mekanizmanın analiz edilebilmesi ve sonuçların mümkün olabilecek çözüm uzayı kümesinde olmasıdır. Bu tür problemlerdeki çözüm kümesinin büyüklüğü bir taraftan elde edilen çözümün değerlendirilmesinde zorluk çıkarırken diğer taraftan lineer yöntemlerin uygulanmasını imkansız kılacaktır.
Geçmişte araştırmacılar tarafından çalışılan parametreler arasındaki ilişkiler genelde deneme yoluyla zor olan örneklerde karmaşık veya sabit olmayan ilişkiler için yapılmış; fakat parametre sayısı artınca çözümsüzlük veya elde edilen çözümü değerlendirememe problemini getirmiştir. İstatistiksel yöntemler araştırmacılara ilişkileri bulmada faydalı olan ilk araçlardandır. İstatistiksel yöntemlerde:
1) Verinin normal toplandığı
2) Verinin eşitlik ilişkisinin belirli bir formda olması (ör: lineer quadratic veya polinomsal)
3) Değişkenlerin bağımsız olması gerekir.
Eğer problem bu kriterleri sağlarsa istatistiksel yöntem ilişkileri bulmada faydalı olabilir. Oysa gerçek hayatta problemler bu kriterleri nadiren sağlarlar.
Modern sonuç kestirme veya sonuç geliştirme algoritmaları bu kriterlerle sınırlandırılamazlar. Neural network (Yapay sinir ağları) veya Artificial intelligence (Yapay zeka) teknikleri karmaşık ilişkileri kapsamayabilir; fakat mekanizmanın önemli ilişkilerini tanımlayabilen güçlü tahmin modelleridir. Buna rağmen diğer bir teknik Genetik Algoritma ve Genetik Programlama teknikleri çok daha güçlüdürler ve karışık çözüm uzayını daha da geniş bulabilirler. Bağımsız olan veri ve parametreler ile mekanizmanın ilişkilerini bulmada başarılı örnekleri vardır.
Genetik Algoritma biyolojik bir sistemin çevresine adaptasyonunda kullandığı metodun örneklendirilmesidir. Bilgisayarda bu tür çok parametreli optimum bulma problemlerine ve makine öğrenme problemlerine çözüm modeli olarak alınabilir.
Doğal adaptasyondan esinlenen GA’ nın basit olarak iskeleti:
a) Bireyin bulunduğu ortamda hayatta kalmak için kendi kendisini değiştirerek ortama uygun hale gelmesi
b) Bu adaptasyon boyunca yeni üretilecek nesillere bu özellikler ile birlikte mümkün olabilecek daha çok değişim aktarılarak bireylerin daha çok uyumlu hale getirilmesi olarak özetlenebilir.
Mühendislikte bilimde ekonomide finansmanda v.s. deki problemleri çözmede kullanılan arama teknikleri hesap-temelli ve direkt arama teknikleri olarak sınıflandırılabilir. Eğer problemler sayısal veya analitik olarak iyi tanımlanabiliyorsa veya çözüm uzayı küçük ve tek ise hesap temelli arama tekniği daha iyi çalışır. Buna rağmen hesap-temelli teknik mühendislik optimizasyoların da gittikçe artan optimum bulma fonksiyonlarında oldukça zayıf kalır. Sadece fonksiyon bilgisi gerekli olan Doğrudan arama tekniği hesap-temelli teknikten daha kısa sürede işler ve daha etkilidir. Doğrudan arama tekniğinin esas problemi ulaşılabilen bilgisayar zamanı ile optimal çözümün kesinliği arasındaki bağıntıdır (Genetic Algorithms in Search Optimization and Machine Learning Goldberg 1989).
Genetik algoritmalar doğada gözlemlenen evrimsel sürece benzer bir şekilde çalışan arama ve eniyileme yöntemidir. Karmaşık çok boyutlu arama uzayında en iyinin hayatta kalması ilkesine göre bütünsel en iyi çözümü arar.
Genetik algoritmaların temel ilkeleri ilk kez Michigan Üniversitesi'nde John Holland tarafından ortaya atılmıştır. Holland 1975 yılında yaptığı çalışmaları “Adaptation in Natural and Artificial Systems” adlı kitabında bir araya getirmiştir. İlk olarak Holland evrim yasalarını genetik algoritmalar içinde eniyileme problemleri için kullanmıştır.
Genetik algoritmalar problemlere tek bir çözüm üretmek yerine farklı çözümlerden oluşan bir çözüm kümesi üretir. Böylelikle arama uzayında aynı anda birçok nokta değerlendirilmekte ve sonuçta bütünsel çözüme ulaşma olasılığı yükselmektedir. Çözüm kümesindeki çözümler birbirinden tamamen bağımsızdır. Her biri çok boyutlu uzay üzerinde bir vektördür.
Genetik algoritmalar problemlerin çözümü için evrimsel süreci bilgisayar ortamında taklit ederler. Diğer eniyileme yöntemlerinde olduğu gibi çözüm için tek bir yapının geliştirilmesi yerine böyle yapılardan meydana gelen bir küme oluştururlar. Problem için olası pekçok çözümü temsil eden bu küme genetik algoritma terminolojisinde nüfus adını alır. Nüfuslar vektör kromozom veya birey adı verilen sayı dizilerinden oluşur. Birey içindeki her bir elemana gen adı verilir. Nüfustaki bireyler evrimsel süreç içinde genetik algoritma işlemcileri tarafından belirlenirler.
Problemin bireyler içindeki gösterimi problemden probleme değişiklik gösterir. Genetik algoritmaların problemin çözümündeki başarısına karar vermedeki en önemli faktör problemin çözümünü temsil eden bireylerin gösterimidir. Nüfus içindeki her bireyin problem için çözüm olup olmayacağına karar veren bir uygunluk fonksiyonu vardır. Uygunluk fonksiyonundan dönen değere göre yüksek değere sahip olan bireylere nüfustaki diğer bireyler ile çoğalmaları için fırsat verilir. Bu bireyler çaprazlama işlemi sonunda çocuk adı verilen yeni bireyler üretirler. Çocuk kendisini meydana getiren ebeveynlerin (anne baba) özelliklerini taşır. Yeni bireyler üretilirken düşük uygunluk değerine sahip bireyler daha az seçileceğinden bu bireyler bir süre sonra nüfus dışında bırakılırlar. Yeni nüfus bir önceki nüfusta yer alan uygunluğu yüksek bireylerin bir araya gelip çoğalmalarıyla oluşur. Aynı zamanda bu nüfus önceki nüfusun uygunluğu yüksek bireylerinin sahip olduğu özelliklerin büyük bir kısmını içerir. Böylelikle pek çok nesil aracılığıyla iyi özellikler nüfus içersinde yayılırlar ve genetik işlemler aracılığıyla da diğer iyi özelliklerle birleşirler. Uygunluk değeri yüksek olan ne kadar çok birey bir araya gelip yeni bireyler oluşturursa arama uzayı içerisinde o kadar iyi bir çalışma alanı elde edilir. Probleme ait en iyi çözümün bulunabilmesi için;
Bireylerin gösterimi doğru bir şekilde yapılmalı
Uygunluk fonksiyonu etkin bir şekilde oluşturulmalı
Doğru genetik işlemciler seçilmeli.
Bu durumda çözüm kümesi problem için bir noktada birleşecektir. Genetik algoritmalar diğer eniyileme yöntemleri kullanılırken büyük zorluklarla karşılaşılan oldukça büyük arama uzayına sahip problemlerin çözümünde başarı göstermektedir. Bir problemin bütünsel en iyi çözümünü bulmak için garanti vermezler. Ancak problemlere makul bir süre içinde kabul edilebilir iyi çözümler bulurlar. Genetik algoritmaların asıl amacı hiçbir çözüm tekniği bulunmayan problemlere çözüm aramaktır. Kendilerine has çözüm teknikleri olan özel problemlerin çözümü için mutlak sonucun hızı ve kesinliği açısından genetik algoritmalar kullanılmazlar. Genetik algoritmalar ancak;
Arama uzayının büyük ve karmaşık olduğu
Mevcut bilgiyle sınırlı arama uzayında çözümün zor olduğu
Problemin belirli bir matematiksel modelle ifade edilemediği
Geleneksel eniyileme yöntemlerinden istenen sonucun alınmadığı alanlarda etkili ve kullanışlıdır.
Genetik algoritmalar parametre ve sistem tanılama kontrol sistemleri robot uygulamaları görüntü ve ses tanıma mühendislik tasarımları planlama yapay zeka uygulamaları uzman sistemler fonksiyon ve kombinasyonel eniyileme problemleri ağ tasarım problemleri yol bulma problemleri sosyal ve ekonomik planlama problemleri için diğer eniyileme yöntemlerinin yanında başarılı sonuçlar vermektedir.
Diğer yöntemlerden farkı
Genetik algoritmalar problemlerin çözümünü parametrelerin değerleriyle değil kodlarıyla arar. Parametreler kodlanabildiği sürece çözüm üretilebilir. Bu sebeple genetik algoritmalar ne yaptığı konusunda bilgi içermez nasıl yaptığını bilir.
Genetik algoritmalar aramaya tek bir noktadan değil noktalar kümesinden başlar. Bu nedenle çoğunlukla yerel en iyi çözümde sıkışıp kalmazlar.
Genetik algoritmalar türev yerine uygunluk fonksiyonunun değerini kullanır. Bu değerin kullanılması ayrıca yardımcı bir bilginin kullanılmasını gerektirmez.
Genetik algoritmalar gerekirci kuralları değil olasılıksal kuralları kullanır.
Tarihçe
Michigan Üniversitesinde psikoloji ve bilgisayar bilimi uzmanı olan John Holland bu konuda ilk çalışmaları yapan kişidir. Mekanik öğrenme (machine learning) konusunda çalışan Holland Darwin’in evrim kuramında etkilenerek canlılarda yaşanan genetik süreci bilgisayar ortamında gerçekleştirmeyi düşündü. Tek bir mekanik yapının öğrenme yeteneğini geliştirmek yerine böyle yapılarda oluşan bir topluluğun çoğalma çiftleşme mutasyon vb. genetik süreçlerden geçerek başarılı (öğrenebilen) yeni bireyler oluşturabildiğini gördü. Araştırmalarını arama ve optimumu bulma için doğal seçme ve genetik evrimden yola çıkarak yapmıştır. İşlem boyunca biyolojik sistemde bireyin bulunduğu çevreye uyum sağlayıp daha uygun hale gelmesi örnek alınarak optimum bulma ve makine öğrenme problemlerinde bilgisayar yazılımı modellenmiştir.
Çalışmalarının sonucunu açıkladığını kitabının 1975’te yayınlanmasından sonra geliştirdiği yöntemin adı Genetik Algoritmalar (ya da kısaca GA) olarak yerleşti. Ancak 1985 yılında Holland’ın öğrencisi olarak doktorasını veren David E. Goldberg adlı inşaat mühendisi 1989 da konusunda bir klasik sayılan kitabını yayınlayana dek genetik algoritmaların pek pratik yararı olmayan bir araştırma konusu olduğu düşünülüyordu. İlk olarak Hollanda’ da makine öğrenme sistemlerine yardımcı olarak kullanılmış daha sonra De Jong Goldberg ve diğerleri tarafından analiz edilmiştir. Goldberg GA’nın çok sayıda kollara ayrılmış gaz borularında gaz akışını düzenlemek ve kontrol etmek için uygulamasını tanımlamıştır. Ayrıca kendisinin kullandığı makine öğrenmesi nesne tanıma görüntü işleme ve işlemsel arama gibi alanlarda kullanıldığını vurgulamıştır.
Goldberg’in gaz boru hatlarının denetimi üzerine yaptığı doktora tezi ona sadece 1985 National Science Foundation Genç Araştırmacı ödülünü kazandırmakla kalmadı genetik algoritmaların pratik kullanımının da olabilirliğini kanıtladı. Ayrıca kitabında genetik algoritmalara dayalı tam 83 uygulamaya yer vererek GA’nın dünyanın her yerinde çeşitli konularda kullanılmakta olduğunu gösterdi.
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