Genetik algoritma

Çalışma prensibi

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.

Temel Kavramlar

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.

Gen yapısı ve kodlama

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.

Kromozom yapısı

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.

Popülasyon

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.

Kullanım alanları

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.