Genetik Algoritma Parametreleri | Mobile App Developer

Genetik Algoritma Parametreleri

Genetik algoritmanın performansını etkileyen önemli etmenlerden biri kontrol parametrelerinin belirlenmesidir. Kontrol parametrelerinin seçimi problem tiplerine göre farklılık göstermektedir. Farklı problem ve kodlama türlerine göre en uygun kontrol parametrelerin belirlenmesi için birçok çalışma yapılmıştır. Aşağıda GA kontrol parametreleri olan popülasyon büyüklüğü, çaprazlama olasılığı, mutasyon olasılığı, kuşak farkı, seçim yöntemi ve fonksiyon ölçeklemesi açıklanmaktadır.

1.Popülasyon Büyüklüğü

Genetik algoritmanın ilk adımı başlangıç popülasyonunun oluşturulmasıdır. Başlangıç popülasyonunu oluşturan bireylerin uygunluk değerleri GA performansını etkileyen unsurlardan biridir. Popülasyon oluşturan bireylerin sayısı küçük seçildiğinde iterasyonlar daha hızlı olacak ancak algoritmanın yerel optimuma takılma şansı artacaktır. Popülasyonun çok büyük seçilmesi çözüm kalitesini arttıracak ancak algoritmanın adımları daha uzun zaman alacaktır. Goldberg 1985’de, yalnızca kromozom uzunluğuna bağlı bir popülasyon büyüklüğü hesaplama yöntemi önermiştir. Golderg birçok araştırmacının popülasyon büyüklüğünü 30-200 aralığında seçtiğini belirtmiştir. Popülasyon büyüklüğünü kromozom uzunluklarını dikkate alarak belirlenmesinde seçilen yöntemlerden biri n kromozom uzunluğu olmak üzere popülasyon büyüklüğünün [n, 2n] arasında seçilmesidir. Popülasyon büyüklüğünün küçük bir değer olarak belirlenmeye çalışılmasının başlıca nedeni GA’nın diğer meta-sezgisel yöntemlerle çözüm süresi olarak rekabetçi olabilmesidir.

2.Çaprazlama Oranı

Çaprazlama GA’ların arama uzayının benzer fakat araştırılmamış bölgelerine ulaşmayı sağlayan bir arama operatörüdür. Gen takası genetik algoritmanın motoru kabul edilir. Basitçe olay iki ebeveyn kromozomun arasında belirlenen parçaların takasıdır. Kromozom çiftleri P(c) olasılığı ile çaprazlamaya uğramak üzere seçilirler. Çaprazlama olasılığını yüksek seçilmesi bir önceki nesle ait kromozomların daha fazla bozulmasına sebep olur. Bu bozulma sonucu çok iyi uygunluk değerlerine sahip kromozomlarında yok olmasına ve iyi çözümlerin kaybolmasına neden olur. Çaprazlama oranı kromozomların çaprazlanmasının hangi olasılıkla olacağını gösteren kullanıcı tanımlı olasılıktır. Örneğin, çaprazlama oranının 0.9 olması popülasyondaki bireylerin %90’inin çaprazlama operatörüne maruz kalacağını gösterir. En iyi çaprazlama yöntemi uygulamaya göre farklılık göstermektedir .

3.Mutasyon Oranı

GA’daki mutasyon operatörü BT’daki rastsal bozulma işlemine benzemektedir. Mutasyon nesiller arasında genetik değişkenliği sağlayan kromozomlardaki bozulma yapısıdır. Çocuk bireylerin bazı genleri rastlantısal olarak değişim gösterir. Genetik algoritmada kullanılan mutasyon operatörü iterasyonlar gerçekleşirken yerel optimum noktalarda çözümün sıkışmasının önüne geçer. Mutasyon P(m) olasılığı ile bir kromozomdaki her bitte meydana gelebilir. Eğer mutasyon olasılığı çok artarsa, genetik arama rastsal bir aramaya dönüşür ve en iyi çözüme ulaşmak zorlaşır. Mutasyon oranının düşük seçilmesi ise çözüm uzayının farklı noktalarına erişimi zorlaştırır. Genellikle kromozomlardaki bir genin rastsal değişim olasılığı %1 veya daha düşük seçilmektedir.

4.Kuşak Farkı

Her popülasyondaki yeni kromozom oranıdır. Çaprazlama ve mutasyon gibi genetik operatörlerin uygulanması için seçilen kromozom sayısıdır. Bu değerin yüksek seçilmesi bir sonraki jenerasyonda birçok yeni kromozomun olacağı anlamına gelir. Kromozomların uygunluk değerlerinin yüksek olması seçilme şanslarını arttırır.

5.Seçim Stratejisi

Bir sonraki popülasyonu oluşturacak bireylerin seçiminde kullanılan farklı seçim stratejileri mevcuttur. Seçim stratejisi popülasyonda yer alan kromozomların uygunluk seviyelerine bağlıdır. Uygunluk oranı seçimi, sıra seçimi ve turnuva seçimi seçim stratejileri içinde en sık kullanılanlardır. Kuşak farkının yüksek olması bir sonraki jenerasyonun büyük bölümünün yavrular tarafından oluşturulması anlamına gelmektedir. Bir sonraki jenerasyon tamamen yavrulardan oluşursa ebeveynler içinde en iyi değere sahip birey yok olmuş olur. Bu sorun elitlik uygulanarak ortadan kaldırılabilir. Elitlik uygulandığında, popülasyondaki en iyi bireyler hiçbir zaman yok olmaz ve sonraki jenerasyonlara aktarılırlar. Kuşak farkı belirli bir dengede tutulursa bir sonraki popülasyona belirli sayıda yavru birey ve belirli sayıda en iyi uygunluk değerine sahip ebeveyn birey dahil edilir.

6. Uygunluk Fonksiyonunun Ölçeklemesi

Uygunluk fonksiyonunun ölçeklenmesinde rank, oransal, doğrusal, üstsel ölçekleme gibi yöntemler mevcuttur. Problemin yapısına göre en uygun ölçekleme yönteminin seçilmesi genetik algoritmanın performansının etkileyen önemli kontrol parametrelerinden biridir.

Bulent SIYAH | 10 Mart 2012