Genetik Algoritma Süreci

Çözülmek üzere tanımlı bir problem verilmesi ve aday çözümlerin birer bit dizisi ile temsil edilmesi halinde, GA şu şekilde çalışır:
1.  N adet kromozom (problem için aday çözümler) içeren rastgele oluşturulmuş bir topluluk ile başla.
2.  Topluluktaki her  x kromozomu için  f(x) uygunluk değerini hesapla.
3.  Aşağıdaki adımları birey  n (topluluk büyüklüğü) oluşturuluncaya kadar tekrarla.
a.  Güncel topluluktan, yüksek uygunluk değerinin seçilme ihtimalini arttırdığını göz önünde bulundurarak, iki ebeveyn kromozom seç. Seçilim, aynı kromozomun birden çok defa ebeveyn olarak seçilmesine olanak verecek şekilde yapılır.
b.  Pc olasılığı (“çaprazlama olasılığı” ya da “çaprazlama oranı”) ile seçilen çifti iki yeni birey
oluşturmak üzere rastgele belirlenen bir noktadan çaprazla. Eğer çaprazlama gerçekleşmezse
ebeveynlerinin birebir kopyası olan iki çocuk oluştur.
c.  Pm olasılığı (“mutasyon olasılığı” ya da “mutasyon oranı”) ile, oluşan iki çocuğu tüm veya bazı locuslarında
mutasyona uğrat.
d.  Sonuçta elde edilen kromozomları yeni topluluğa ekle.
4.  Önceki topluluğu yeni topluluk ile değiştir.
5.  Sonlandırma koşulu sağlandıysa mevcut topluluktaki en iyi çözümü döndür, sağlanmadıysa 2. adıma dön.

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 olabilmesidi.

 

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

Kaynak