DIVERSITY AND PERMEABILITY IN PARALLEL GENETIC ALGORITHMS

Abstract

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.

Keywords

• Parallel genetic algorithms,migration methods,diversity,permeability

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

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.

Keywords

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

References

1. [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. [2] J. Denzinger and J. Kidney, “Improving migration by diversity”, The 2003 Congress on Evolutionary Computation, CEC'03, vol. 1, 700- 707 (2003).
3. [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. [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. [5] E. Alba and J.M. Troya, “Analyzing synchronous and asynchronous parallel distributed genetic algorithms”, Future Generation Computer Systems 17, 451-465 (2001).
6. [6] E. Cantú-Paz, “Markov chain models of parallel genetic algorithms”, IEEE Transactions of Evolutionary Computation, Vol. 4, No. 3, 216-226 (2000).
7. [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. [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. [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. [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. [11] E. Alba and J.M. Troya, “A survey of parallel distributed genetic algorithms”, Complexity 4, 31-52 (1999).
12. [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. [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. [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. [15] S. Janson, E. Alba, B. Dorronsoro and M. Middendorf, “Hierarchical cellular genetic algorithm”, EvoCOP 2006, LNCS 3906, 111-122 (2006).
16. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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).