Influence of migration on efficacy and efficiency of parallel evolutionary computing

• Autorzy: Biełaszek Sylwia , Rutkowski Leszek , Byrski Aleksander

Identyfikatory

DOI

10.14313/JAMRIS/4‐2024/27

• Języki publikacji: EN

Abstrakty

EN

Metaheuristics, such as evolutionary algorithms (EAs), have been proven to be (also theoretically, see, for example, the works of Michael Vose [1]) universal optimization methods. Previous works (Zbigniew Skolicki and Kenneth De Jong [2]) investigated impact of migration intervals on island models of EAs in their works. Here we explore different migration intervals and amounts of migrating individuals, complementing Skolicki and DeJong’s research. In our experiments, we use different ways of selecting migrants and pave the way for further research, e.g., involving different topologies and neighborhoods. We present the idea of the algorithm, show experimental results.

Słowa kluczowe

EN

parallel evolutionary computing; metaheuristics; migration

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2024
• Tom: Vol. 18, No. 4
• Strony: 1--12
• Opis fizyczny: Bibliogr. 18 poz., rys.

Twórcy

autor

Biełaszek Sylwia

• AGH University of Science and Technology, Al. Mickiewicza 30, Krakow 30-059, Poland

autor

Rutkowski Leszek

• AGH University of Science and Technology, Al. Mickiewicza 30, Krakow 30-059, Poland

autor

Byrski Aleksander

• AGH University of Science and Technology, Al. Mickiewicza 30, Krakow 30-059, Poland

• https://orcid.org/0000-0001-6317-7012

Bibliografia

• [1] L. D. Davis, K. De Jong, M. D. Vose, L. D. Whitley, W. Miller, Eds., Evolutionary Algorithms, Vol. 111 of The IMA Volumes in Mathematics and its Applications, New York, NY, Springer, 1999, [Online]. Available: doi: 10.1007/978-1-4612-1542-4.
• [2] Z. Skolicki, K. De Jong, The influence of migration intervals on island models, 2005, pp. 1295–1302, doi: 10.1145/1068009.1068219.
• [3] D. Wolpert, W. Macready, “No Free Lunch Theorems for Optimization”, IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 67–82, 1997.
• [4] D. Sudholt, Parallel Evolutionary Algorithms, Berlin, Heidelberg, Springer Handbooks, Springer, 2015, doi: 1 0 . 1 0 0 7 / 9 7 8 - 3 - 6 6 2 -43505-2-46.
• [5] E. Cantu-Paz, “On the Effects of Migration on the Fitness Distribution of Parallel Evolutionary Algorithms”, no. UCRL-JC-138729, 2000, URL https://www.osti.gov/biblio/791479.
• [6] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989, google-Books-ID: 2IIJAAAACAAJ.
• [7] R. Chiong, T. Weise, Z. Michalewicz, Variants of Evolutionary Algorithms for Real-World Applications, 2012, doi: 10.1007/978-3-642-23424-8.
• [8] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer Science & Business Media, 1996, google-Books-ID: vlh-LAobsK68C.
• [9] E. Cantú-Paz, Master-Slave Parallel Genetic Algorithms, Genetic Algorithms and Evolutionary Computation, Boston, MA, Springer, 2001, doi: 10.1007/978-1-4615-4369-5-3.
• [10] E. Cantú-Paz, Fine-Grained and Hierarchical Parallel Genetic Algorithms, Genetic Algorithms and Evolutionary Computation, Boston, MA, Springer, 2001, doi: 10.1007/978-1-4615-4369-5-8.
• [11] E. Cantú-Paz, D. E. Goldberg, “Efficient paralel genetic algorithms: theory and practice”, Computer Methods in Applied Mechanics and Engineering, vol. 186, no. 2–4, pp. 221–238, 2000, doi: 10.1016/S0045-7825(99)00385-0.
• [12] Y. Sato, Y. Takai, M. Munetomo, “An efficient migration scheme for subpopulation-based asynchronously parallel genetic algorithms.”, Material: Proceedings of the fifth international conference on genetic algorithms, S.F. Ed., San Mateo, CA: Morgan Kaufmann, 1993, pp. 649.
• [13] H. Braun, “On solving travelling salesman problems by genetic algorithms”, Parallel Problem Solving from Nature, Lecture Notes in Computer Science, H.P. Schwefel and R. Manner, Eds. Berlin, Heidelberg: Springer, 1991, pp. 129–133, doi: 10 .1007/BFb0029743.
• [14] E. Cantú-Paz, D. E. Goldberg, On the Scalability of Parallel Genetic Algorithms, vol. 7, 1999, pp. 429–449, doi: 10.1162/evco.1999.7.4.429.
• [15] M. Nowostawski, R. Poli, “Parallel genetic algorithm taxonomy”, 1999 Third International Conference on Knowledge-Based Intelligent Information Engineering Systems. Proceedings (Cat. No.99TH8410), 1999, pp. 88-92, doi: 10.1109/KES.1999.820127.
• [16] M. Ruciński, D. Izzo, F. Biscani, “On the impact of the migration topology on the island model”, Parallel Computing, Issues, vol. 36, no. 10–11, pp. 555–571, 1993, doi: 10.1016/j.parco.2010.04.002.
• [17] D. Whitley, S. Rana, R. Heckendorn, “The Island Model Genetic Algorithm: On Separability, Population Size and Convergence”, Journal of Computing and Information Technology, vol. 7, Dec. 1998.
• [18] Z. Skolicki, K. De Jong, “The importance of a two-level perspective for island model design”, Conference: Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, IEEE Xplore, 2007, doi: 10.1109/CEC.2007.4425078.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).