215E225 TÜBİTAK 3001 PROJESİ SONUÇ RAPORU
Genetik Algoritma Adımları
GA’nın ilk adımı turnuva seçimidir (Miller ve Goldberg, 1995). Turnuva seçilimi, popülasyondan rastgele olarak belirli sayıda (bu çalışmada 5 olarak seçilmiştir) eleman seçer. Bu seçtiği elemanlardan uygunluk değeri en yüksek olanı seçim sonucu olarak belirler. Popülasyona uygulanan iki turnuva seçiminin sonucunda iki tane eleman elde edilir.
Turnuva seçimiyle elde edilen bu iki eleman, tek noktalı çaprazlama operasyonunun girdileri olarak kullanılır. Tek noktalı çaprazlama operasyonunda, ağaç olarak düşünebileceğimiz iki matematiksel ifade, her birinden rastgele seçilmiş birer düğüm noktasından yer değiştirirler. Temel olarak ifade ağacının parçaları yer değiştirmiş olur. Ortaya çıkan iki yeni ifadeden uygunluk değeri daha fazla olan çaprazlama işleminin sonucu olarak seçilir. İfade ağaçlarının parçaları yer değiştirdiği için ifadelerin toplam operatör sayılarında bir değişim olmaz. Örnek olarak Şekil 7’deki gibi iki ifadenin çaprazlama işleminin iki girdisi olduğunu varsayarsak;
1. ifade:
^ + J 2 > ! J 13
2. ifade:
& | J 4 + 7 J
Şekil 7. Birinci çaprazlama örneği
Eğer birinci ifadenin “>” noktası ve ikinci ifadenin “+” noktası çaprazlama noktaları olarak seçilirse, çaprazlama operasyonundan sonra yeni ifadeler Şekil 8’deki gibi olur;
1. ifade:
^ + J 2 + 7 J
2. ifade:
& | J 4 > ! J 13
Şekil 8. İkinci çaprazlama örneği
Çaprazlama işleminin sonucu olarak çok uzun ifadeler oluşabileceğinden bir limitleme yapılmıştır. Projemizde bu değer 80 olarak seçilmiştir.
Çaprazlama işleminden elde edilen yeni ifade, mutasyon operasyonundan geçirilir. Mutasyon operasyonu, %5 olasılıkla, ifadenin bir operatörünü rastgele seçilen başka bir operatörle değiştirir. Son işlem olan mutasyonun ardından ortaya çıkan ifade, bir sonraki jenerasyonun elemanlarından biri olur. Ayrıca, popülasyon içinde uygunluk değeri en yüksek eleman sonraki jenerasyona değişmeden aktarılır. Bu metot, GA’da elitizm kullanımı olarak bilinmektedir.
Projemizde kullanılan GA yönteminin algoritması Şekil 9’da sözde kod (pseudo code) şeklinde verilmiştir.
1: do
2: initialize yeniPopülasyon
3: for i <- 0 to popülasyonBoyutu do
4: Elitism(popülasyon,yeniPopülasyon)
5: ilkSecim <- TurnuvaSeçilimi(popülasyon)
6: ikinciSecilim<-TurnuvaSeçilimi(popülasyon)
7: yeniEleman <- Çaprazlama(ilkSecilim,ikinciSecilim)
8: Mutasyon(yeniEleman)
9: yeniPopülasyon.Ekle(yeniEleman)
10: end for
11: enUygun<- yeniEleman,fittest
12: while enUygun.uygunluk <= 71,99
Şekil 9. GA yöntemi algoritması
Turnuva seçimiyle elde edilen bu iki eleman, tek noktalı çaprazlama operasyonunun girdileri olarak kullanılır. Tek noktalı çaprazlama operasyonunda, ağaç olarak düşünebileceğimiz iki matematiksel ifade, her birinden rastgele seçilmiş birer düğüm noktasından yer değiştirirler. Temel olarak ifade ağacının parçaları yer değiştirmiş olur. Ortaya çıkan iki yeni ifadeden uygunluk değeri daha fazla olan çaprazlama işleminin sonucu olarak seçilir. İfade ağaçlarının parçaları yer değiştirdiği için ifadelerin toplam operatör sayılarında bir değişim olmaz. Örnek olarak Şekil 7’deki gibi iki ifadenin çaprazlama işleminin iki girdisi olduğunu varsayarsak;
1. ifade:
^ + J 2 > ! J 13
2. ifade:
& | J 4 + 7 J
Şekil 7. Birinci çaprazlama örneği
Eğer birinci ifadenin “>” noktası ve ikinci ifadenin “+” noktası çaprazlama noktaları olarak seçilirse, çaprazlama operasyonundan sonra yeni ifadeler Şekil 8’deki gibi olur;
1. ifade:
^ + J 2 + 7 J
2. ifade:
& | J 4 > ! J 13
Şekil 8. İkinci çaprazlama örneği
Çaprazlama işleminin sonucu olarak çok uzun ifadeler oluşabileceğinden bir limitleme yapılmıştır. Projemizde bu değer 80 olarak seçilmiştir.
Çaprazlama işleminden elde edilen yeni ifade, mutasyon operasyonundan geçirilir. Mutasyon operasyonu, %5 olasılıkla, ifadenin bir operatörünü rastgele seçilen başka bir operatörle değiştirir. Son işlem olan mutasyonun ardından ortaya çıkan ifade, bir sonraki jenerasyonun elemanlarından biri olur. Ayrıca, popülasyon içinde uygunluk değeri en yüksek eleman sonraki jenerasyona değişmeden aktarılır. Bu metot, GA’da elitizm kullanımı olarak bilinmektedir.
Projemizde kullanılan GA yönteminin algoritması Şekil 9’da sözde kod (pseudo code) şeklinde verilmiştir.
1: do
2: initialize yeniPopülasyon
3: for i <- 0 to popülasyonBoyutu do
4: Elitism(popülasyon,yeniPopülasyon)
5: ilkSecim <- TurnuvaSeçilimi(popülasyon)
6: ikinciSecilim<-TurnuvaSeçilimi(popülasyon)
7: yeniEleman <- Çaprazlama(ilkSecilim,ikinciSecilim)
8: Mutasyon(yeniEleman)
9: yeniPopülasyon.Ekle(yeniEleman)
10: end for
11: enUygun<- yeniEleman,fittest
12: while enUygun.uygunluk <= 71,99
Şekil 9. GA yöntemi algoritması