Genetik Algoritmalar
Bu yazımızda temel olarak genetik algoritmalar, genetik algoritmalar nedir, genetik algoritmalar ve uygulama alanları konuları hakkında bilgiler vermeye çalışacağız.
Genetik Algoritmalar Nedir?
Genetik algoritmalar doğal biyolojik evrim mekanizmasını örnek alarak oluşturulan stokastik bir arama metodudur. Genetik algoritmalar, ilk defa Charles Darwin tarafından ortaya atılan, ”doğal sistemde güçlülerin hayatta kalması” diye özetlenebilecek doğal seçme ve doğal genetik mekanizmasına (genetiğin evrim tezine dayandırılan) dayanır. Genetik algoritmalar, problemin olası çözümlerinin oluşturduğu bir popülasyon üzerinde işlem yapar ve çözüm için en uygun bireyleri bir sonraki nesle taşıyarak bu bireylerin daha ileriki nesillerde çözüme daha da yakın bireyleri oluşturacağı ilkesini esas alır. Genetik algoritmalarda olasılığın rolü olmasına karşın gelişigüzel bir arama metodu değildir, etkinliği tabiattaki canlıların evriminden de görülebilir. Genetik algoritmalar konusunda ilk çalışmayı Michigan Üniversitesi’nden psikoloji ve bilgisayar bilimi uzmanı John Holland yapmıştır. Makine öğrenmesi (machine learning) konusunda çalışan Holland, Darwin’in evrim kuramından 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ılardan oluşan bir topluluğun çoğalma, çiftleşme, mutasyon vb. genetik süreçlerden geçerek başarılı yeni bireyler oluşturabildiğini gördü. Çalışmalarının sonucunu açıkladığı ”Adaptation in Natural and Artificial Systems” adlı çalışmasını 1975’te yayımlamasından sonra, geliştirdiği yöntemin adı Genetik Algoritmalar (GA) olarak
yerleşti. Ancak Holland’ın öğrencisi David E. Goldberg adlı inşaat mühendisi 1989’da konusunda bir klasik sayılan ”Genetic algorithms in search, optimization, and machine learning ” adlı kitabını yayımlayana dek genetik algoritmaların kullanımı yaygın değildi. Goldberg’in gaz boru hatlarının denetimi üzerine 1983 yılında yaptığı doktora tezi ona 1985 ”National Science Foundation” Genç Araştırmacı ödülünü kazandırdı ve genetik algoritmaların pratik kullanımının da olabilirliğini kanıtladı.
Genetik algoritmalar, doğal seçme ve doğal genetik kurallara dayanan bir arama türüdür. Doğal seçme, doğa koşullarına en fazla uyum sağlamış olan canlının neslini devam ettirmesi, uyum sağlayamamış olan türlerin ise elenmesidir. Canlılar nesilden nesile genlerini aktarırken, bu genler de doğal genetik kurallara göre başka genlerle çaprazlanır, değişime uğrar ve yeni genleri oluştururlar. Genetik algoritmalar da tabaattaki bu iki oluşumu birleştirerek en iyiyi (optimal noktayı) arar. Bir önceki neslin en uyumlu fertleri kullanılarak yeni neslin üyeleri oluşturulur. Bu yöntem sayesinde, klasik yöntemlerle çözülmesi çok zor kimi zaman da imkansız olan problemler çözülebilmektedir.
Geleneksel Arama Yöntemleri
Geleneksel arama yöntemleri üç ana başlık altında toplanabilir. Bunlar:
1) Hesaba dayalı yöntemler
2) Nümerik yöntemler
3) Olasılığa dayalı yöntemlerdir
Hesaba dayalı yöntemlerden ilki amaç fonksiyonunun gradyanının sıfıra eşit alınması sonucu çıkan nonlineer denklem takımının çözülmesi esasına dayanır. Arama her yöndeki türevi sıfır olan tepe veya çukur olması muhtemel noktalar civarında yapılır. Diğer bir yöntem ise tepe tırmanma (hill climbing) denilen, maksimum nokta hakkında bir tahminde bulunduktan sonra buna yakın herhangi bir noktanın gradyanı veya tersi yönde hareket edilerek arama yapılan yöntemdir. Yerel en iyi noktayı bulmak için mümkün olan en dik eğimli yönde yürünür. Ancak çok sayıda dönme noktası içeren bir fonksiyonda çok sayıda tepe oluşur. Hangi tepenin en iyi çözüm olduğu bilinemez.
Hesaba dayalı yöntemlerin en önemli eksikliği aramaya başlanacak noktanın çözüm için çok önemli olmasıdır. Birden çok tepe noktasına sahip arama uzaylarında çözüm lokal tepe noktasında kalabilir. Diğer bir eksiklik ise amaç fonksiyonun türevlerinin var olmasının gerekliliğidir. Teorik olarak hesabı kolay kuadratik amaç fonksiyonları bulunabilmesine karşın gerçek hayatta karşılaşılanlar teoriden uzaktır. Parça parça süreksizlikler içerebileceği gibi, gürültülü ortamlardan elde edildikleri için pek çok tepe noktalı olabilirler. Genel olarak hesaba dayalı yöntemler ancak sınırlı sayıda uygulamalar için kullanışlıdır.
Nümerik yöntemlerde ise amaç, sürekli olan gerçel sayı aralıklarını belirli sayıda parçalara bölerek parçaların amaç fonksiyon değerlerine bakıp yeni parçaların denenmesidir. Bu tip arama yöntemlerinin eksikliği ise arama uzayının geniş olması ve noktaların birer birer ele alınmasının zorunluluğudur. Rastgele arama (Random Search) yöntemleri, diğer arama yöntemlerinin bu zayıf yönlerinden dolayı artan bir ilgiyle incelenmektedir. Bununla beraber, rastgele bir yönde tepe tırmanma veya rastgele noktalar seçerek bunların amaç fonksiyonlarını bulma gibi düşünceler rastgele arama yöntemlerinin dışında tutulmalıdır, çünkü etkin değildirler. Genetik algoritmalar, bu gibi rastgele arama yöntemlerinden farklı olarak, olasılığı, kodlanmış parametre uzayında işlem yapmada bir araç olarak kullanırlar.