Paralel genetik algoritmalarda farklılık ve geçirgenlik

Abstract

Paralel genetik algoritmalar (PGA’lar) farklı bireylere sahip birden fazla alt popülasyon üzerinde genetik algoritma (GA) çalıştırarak arama yapan bir en iyileme algoritmasıdır. PGA’ların başarılı bir arama yapmasını etkileyen en önemli unsurlardan biri kullanılan göç yöntemidir. Göç yöntemleri, seçilen bireylerin hangi alt popülasyonlara gönderileceğini belirler. Göç eden birey, alt popülasyondaki arama kalitesini ve buna bağlı olarak algoritma başarısını etkiler. PGA’ların GA’lardan daha başarılı sonuçlar üretmesi, göç işleminin farklılığa olan katkısının bir sonucudur. Bu nedenle, tercih edilen göç yönteminin farklılığı arttıracak bir etkisinin olması istenir. Bu çalışmada, farklı göç yöntemleri için performans sonuçları ve farklılık değerleri verilmiş ve elde edilen sonuçlar karşılaştırılmıştır. Bunun yanında göç bireylerinin alt popülasyonlar arasında doğru ve etkin taşınması yeni bir kavram olarak geçirgenlik ile ifade edilmiştir. Farklı göç yöntemleri için geçirgenlik değerlendirmesi yapılmış ve geçirgenliğin algoritma performansına katkısı incelenmiştir.

Parallel genetic algorithms (PGAs) are optimization algorithms that search by running genetic algorithm (GA) on more than one subpopulation with different individuals. One of the most important factors that affects successful search of PGAs is the migration method employed. Migration methods determine the subpopulations where selected individuals will migrate to. The migrating individual affects quality of the search at the subpopulation, and consequently the success of the algorithm. The reason that PGAs offer more successful results than GAs is the contribution of the migration process to diversity. Therefore, the preferred migration method should have an impact that increases the diversity. In this study, performance results and diversity values have been provided for different migration methods and the obtained results have been compared. Additionally, migration of individuals among subpopulations properly and effectively has been expressed by the permeability as a new concept. Permeability evaluation has been carried out for different migration methods and contribution of the permeability to performance of the algorithm has been investigated.