Influence of Migration on Efficacy and Efficiency of Parallel Evolutionary Computing

Biełaszek, Sylwia; Rutkowski, Leszek; Byrski, Aleksander

doi:10.14313/jamris/4-2024/27

Abstract

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.

References

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.
Search in Google Scholar Back to article
Z. Skolicki, K. De Jong, The inϐluence of migration intervals on island models, 2005, pp. 1295–1302, doi: 10.1145/1068009.1068219.
Search in Google Scholar Back to article
D. Wolpert, W. Macready, “No Free Lunch Theorems for Optimization”, IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 67–82, 1997.
Search in Google Scholar Back to article
D. Sudholt, Parallel Evolutionary Algorithms, Berlin, Heidelberg, Springer Handbooks, Springer, 2015, doi: 10.1007/978-3-662-43505-2-46.
Search in Google Scholar Back to article
E. Cantu-Paz, “On the Effects of Migration on the Fitness Distribution of Parallel Evolutionary Algorithms”, no. UCRL-JC-138729, 2000, URL ht tps://www.osti.gov/biblio/791479.
Search in Google Scholar Back to article
D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison- Wesley, 1989, google-Books-ID: 2IIJAAAACAAJ.
Search in Google Scholar Back to article
R. Chiong, T. Weise, Z. Michalewicz, Variants of Evolutionary Algorithms for Real-World Applications, 2012, doi: 10.1007/978-3-642-23424-8.
Search in Google Scholar Back to article
Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer Science & Business Media, 1996, google-Books-ID: vlh-LAobsK68C.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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-43 69-5-8.
Search in Google Scholar Back to article
E. Cantú-Paz, D. E. Goldberg, “Efϐicient parallel 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.
Search in Google Scholar Back to article
Y. Sato, Y. Takai, M. Munetomo, “An efϐicient migration scheme for subpopulation-based asynchronously parallel genetic algorithms.”, Material: Proceedings of the ϐifth international conference on genetic algorithms, S.F. Ed., San Mateo, CA: Morgan Kaufmann, 1993, pp. 649.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article

Influence of Migration on Efficacy and Efficiency of Parallel Evolutionary Computing

Abstract

Paradigm

My account