Genetik algoritma

Genetik algoritmalar, doğada gözlemlenen evrimsel mekanizmalara benzer mekanizmalar kullanarak çalışan eniyileştirme yöntemidir. Çok boyutlu uzayda belirli bir maliyet fonksiyonuna göre en iyileştirme amacıyla iterasyonlar yapan ve her iterasyonda en iyi sonucu üreten kromozomun hayatta kalması prensibine dayanan en iyi çözümü arama yöntemidir.

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ığı, evrim yasalarını genetik algoritma içinde eniyileştirme problemleri için kullandığı çalışmaları “Adaptation in Natural and Artificial Systems” adlı kitabında bir araya getirmiştir.

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 global çö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. Problem için olası pek çok çözümü temsil eden bir çözüm kümesi genetik algoritma terminolojisinde nüfus veya popülasyon adını alır. Popülasyonlar 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 mekanizmaları tarafından oluşturulurlar.

Genetik algoritmada kullanılan kavramlar, biyolojideki evrim teorisine benzer anlamda kullanılmaktadır. Doğal yaşamda popülasyonlar bireylerin bir arada bulunmasıyla oluşmaktadır. GA algoritması için oluşturulan popülasyon da çok sayıda bireyin bir araya gelmesiyle, başka bir deyişle çok sayıda olası çözüm adaylarının bir araya gelmesiyle oluşmaktadır. Aday çözümler, probleme uygun şekilde kodlanmış diziler halinde tutulurlar. Bu diziyi oluşturan her bir elemana birey denir ve her bir birey arama uzayında belirli bir bölgeyi temsil eder.

Genetik algoritmada ilk başlangıç bireyleri genellikle rastgele olarak üretilirler fakat bu bir zorunluluk değildir. Özellikle çok kısıtlı optimizasyon problemlerinde, başlangıç bireylerini oluşturmak için, tanımlanan kısıtlamaların bir kısmına dikkat edilerek daha iyi adaylar oluşturulabilinir. Bireylerin, uygunluk fonksiyonu işlemine tabi tutulması sonucunda, çözümün optimal çözüme ne kadar yaklaştığını değerlendiren uygunluk değeri belirlenir. Başlangıç popülasyonu oluşturulmuş genetik algoritma üç evrim operatörüyle çalışır. Bunlar; seçim, çaprazlama ve mutasyon operatörleridir. Genel olarak bu operatörlerin her biri, yeni nesilde oluşacak olan popülasyonun her bireyine uygulanır.

Seçim işlemi, popülasyondaki bireyleri uygunluk değerlerine bağlı olarak, yeni bireyleri oluşturmak için, ebeveyn birey seçmesi işlemidir. Çaprazlama operatörü, seçim işleminden sonra uygulanır ve ebeveyn bireylere ait kromozomların belirli kısımlarının karşılıklı yer değiştirmesini ve böylece yeni özellikte bireylerin oluşmasını ifade eder. Mutasyon işlemi ise yeni oluşan bireyin kromozomlarından herhangi birinin içindeki bir geni mutasyon olasılığına bağlı olarak değiştirme işlemidir.

Genetik algoritma işlemini sonlandırmak için çeşitli yöntemler bulunmaktadır. Bu yöntemler; algoritmanın çalışması esnasında istenen çözüm bulunduğunda, GA’nın başlangıcında tanımlanan toplam iterasyon sayısına ulaşıldığında veya uygunluk değeri sürekli olarak sabit kaldığında, bulunan en iyi bireyin temsil ettiği çözüm, problem için bulunmuş en uygun çözüm olarak sunulur.

Genetik algoritmada; kısıtlara uyum sağlayan çözüme ulaşmak için algoritma yapısının oluşturulması ve parametrelerin belirlenmesi gerekmektedir. Aşağıda bu kavramlara ve algoritma için gerekli olan parametrelere yer verilmiştir.

Yapısında probleme ait en küçük bilgiyi taşıyan birime gen denir. GA’nın kullandığı programlama yapısında bu gen yapıları programcının tanımlamasına bağlıdır. Bir genin yapısında sadece ikili tabandaki (binary) sayıları içerebileceği gibi, gray, tam sayı, gerçel sayı veya ağaç biçimini ve farklı sembolik ifadeleri de içerebilir. Kodlama biçimi, GA’nın performansını oldukça önemli oranda etkiler; fakat kodlama biçimi programa bağlı olduğundan bütün problemler için geçerli en uygun kodlama biçimini söylemek imkânsızdır. Michalewicz belli bir problem tipi için yapmış olduğu çalışmada gerçel sayı gösteriminin daha çabuk sonuca ulaştığını göstermiştir.

Bir veya birden fazla gen yapısının bir araya gelerek problemin çözümüne ait bilgilerin bir kısmını oluşturan dizilere kromozom denir. Kromozom, GA yaklaşımında üzerinde durulan en önemli birim olduğu için bilgisayar ortamında iyi ifade edilmesi gerekir.

Olası çözüm bilgilerini içeren bireylerin bir araya gelmesiyle oluşan topluluğa popülasyon denir. Popülasyondaki birey sayısı problemin özelliğine göre, genetik algoritmayı tasarlayan tarafından belirlenir.

Popülasyon büyüklüğü problemin çözüm süresini etkilemektedir. Popülasyondaki birey sayısının gereğinden fazla olması çözüm süresini uzatırken, birey sayısının az olması popülasyonun istenen çözüm değerine ulaşılamamasına sebep olabilir. Problemin özelliğine göre seçilecek olan popülasyondaki birey sayısı genetik algoritmayı hazırlayan kişi tarafından iyi belirlenmelidir. Grefensette, GA için en uygun popülasyon büyüklüğünün 10 ile 160 birey arasında olmasının uygun olacağını öne sürmüştü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, çizelgeleme problemleri, sosyal ve ekonomik planlama problemleri için diğer eniyileme yöntemlerinin yanında başarılı sonuçlar vermektedir.

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.

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. Ancak bazı durumlarda genetik algoritmalar yerel en iyi çözüme, genel en iyi çözümden daha çabuk ulaşırlar ve algoritma bu noktada sonuçlanır. Bu durumla karşılaşıldığında, bu durumu önlemek için (genel en iyi çözüme ulaşabilmek için) ya arama uzayındaki çeşitlilik arttırılır ya da uygunluk fonksiyonu her üreme aşamasında değiştirilir.