DIVERSITY AND PERMEABILITY IN PARALLEL GENETIC ALGORITHMS

Yıl 2012, Sayı: 027, 55 - 66, 16.04.2012

Gültekin Kuvat Nihat Adar

Öz

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.

Anahtar Kelimeler

Parallel genetic algorithms, migration methods, diversity, permeability

PARALEL GENETİK ALGORİTMALARDA FARKLILIK VE GEÇİRGENLİK

Öz

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.

Anahtar Kelimeler

Paralel genetik algoritmalar, göç yöntemleri, farklılık, geçirgenlik

Kaynakça

• [1] M. Lozano, F. Herrera and J.R. Cano, “Replacement strategies to preserve useful diversity in steady-state genetic algorithms”, Information Sciences 178, 4421-4433 (2008).
• [2] J. Denzinger and J. Kidney, “Improving migration by diversity”, The 2003 Congress on Evolutionary Computation, CEC'03, vol. 1, 700- 707 (2003).
• [3] T. Hiroyasu, M. Miki and M. Negami, “Distributed genetic algorithms with randomized migration rate”, IEEE Proc. of Systems, Man and Cybernetics Conference (SMC’99), vol. 1, 689-694 (1999).
• [4] M. Rebaudengo and M.S. Reorda, “An experimental analysis of effects of migration in parallel genetic algorithms”, EWPDP93:IEEE/Euromicro Workshop on Parallel and Distributed Processing, Gran Canaria (E), Gennaio, 232-238 (1992).
• [5] E. Alba and J.M. Troya, “Analyzing synchronous and asynchronous parallel distributed genetic algorithms”, Future Generation Computer Systems 17, 451-465 (2001).
• [6] E. Cantú-Paz, “Markov chain models of parallel genetic algorithms”, IEEE Transactions of Evolutionary Computation, Vol. 4, No. 3, 216-226 (2000).
• [7] E. Cantú-Paz, “Migration policies, selection pressure, and parallel evolutionary algorithms”, In Brave, S., Wu, A. (Eds.) Late Breaking Papers at the Genetic and Evolutionary Computation Conference. Orlando, FL (1999).
• [8] E. Cantú-Paz, “Topologies, migration rates, and multi-population parallel genetic algorithms”, GECCO-99:Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco, CA: Morgan Kaufmann, 91-98 (1999).
• [9] M. Nowostawski and R. Poli, “Parallel genetic algorithm taxonomy”, Proceedings of Third International Conference on Knowledge-based Intelligent Information Engineering Systems KES'99 (1999).
• [10] P.D. Surry and N.J. Radcliffe, “RPL2: A language and parallel framework for evolutionary computing”, Springer-Verlag LNCS 866, 628-637 (1994).
• [11] E. Alba and J.M. Troya, “A survey of parallel distributed genetic algorithms”, Complexity 4, 31-52 (1999).
• [12] Y. Maeda, M. Ishita and O. Li, “Fuzzy adaptive search method for parallel genetic algorithm with island combination process”, International Journal of Approximate Reasoning 41, 59-73 (2006).
• [13] J. Berntsson and M. Tang, “A convergence model for asynchronous parallel genetic algorithms”, The 2003 Congress on Evolutionary Computation, CEC'03, Vol. 4, 2627- 2634 (2003).
• [14] E. Alba, F Luna., A.J. Nebro and J.M. Troya, “Parallel heterogeneous genetic algorithms for continuous optimization”, Parallel Computing 30, 699-719 (2004).
• [15] S. Janson, E. Alba, B. Dorronsoro and M. Middendorf, “Hierarchical cellular genetic algorithm”, EvoCOP 2006, LNCS 3906, 111-122 (2006).
• [16] T. Matsumura and J.Okech, “Effects of chromosome migration on a parallel and distributed genetic algorithm”, Third International Symposium on Parallel Architectures, Algorithms and Networks, (I-SPAN'97), 357-361 (1997).
• [17] G. Kuvat, “Paralel Genetik Algoritmalarda Göç Yöntemleri ve Göç Parametrelerinin Dinamik Olarak Belirlenmesi”, Doktora Tezi, Eskişehir Osmangazi Üniversitesi Fen Bilimleri Enstitüsü (2009).
• [18] S. Oh, C.T. Kim and J. Lee, “Balancing the selection pressures and migration schemes in parallel genetic algorithms for planning multiple paths”, Proceedings of the 2001 IEEE International Conference on Robotics & Automation, Seoul, Korea, May 21-26, 3314-3319 (2001).
• [19] G. Kuvat, N. Adar, S. Canbek ve E. Seke, “Hızlı yakınsayan göç yönteminin farklı test fonksiyonları için incelenmesi”, 12. Elektrik, Elektronik, Bilgisayar, Biyomedikal Mühendisliği Ulusal Kongresi ve Sergisi, 313-316 (2007).
• [20] G. Kuvat, N. Adar, S. Canbek ve E. Seke, “Göç yöntemleri, göç oranı ve paralel genetik algoritmalar”, ASYU 2008 - Akıllı Sistemlerde Yenilikler ve Uygulamaları Sempozyumu, 138-142 (2008).
• [21] E. Alba and J.M. Troya, “Improving flexibility and efficiency by adding parallelism to genetic algorithms”, Statistics and Computing 12, 91-114 (2002).
• [22] J. Gu, X. Gu and C. Cuiwen, “A novel parallel quantum genetic algorithm for stochastic job shop scheduling”, Journal of Mathematical and Applications (accepted manuscript) (2008).
• [23] J. Choi, S. Oh and W. Pedrycz, “Identification of fuzzy relation models using hierarchical fair competition-based parallel genetic algorithms and information granulation”, Applied Mathematical Modeling (in press) (2008).
• [24] J. Choi, S. Oh and W. Pedrycz, “Structural and parametric design of fuzzy inference systems using hierarchical fair competition-based parallel genetic algorithms and information granulation”, International Journal of Approximate Reasoning 49, 631-648 (2008).
• [25] L. Singh and S. Kumar, “Migration based parallel differential evolution learning in asymmetric subsethood product fuzzy neural inference system: a simulation study”, IEEE Congress on Evolutionary Computation (2007).
• [26] Q. Li and Y. Maeda, “Distributed adaptive search method for genetic algorithm controlled by fuzzy reasoning”, IEEE International Conference on Fuzzy Systems, 2022-2027 (2008).