AN EFFECT ANALYSIS OF THE PARALLEL MIGRATING BIRDS OPTIMIZATION ALGORITHM PARAMETERS

Year 2020, , 41 - 49, 30.06.2020

Gültekin Kuvat , Abdullah Tülek

https://doi.org/10.22531/muglajsci.630528

Abstract

Migration is the process of sending selected solutions from a sub-population to the neighboring sub-population at specified intervals in parallel metaheuristic algorithms (PMAs). Topology, migration rate (MR), migration interval (MI), migration policy and communication model are the factors which characterize the nature of migration. Identification of relationship between migration parameters and an accurate selection of such parameter values increase the performance of PMAs. The number of sub-populations (NS) denotes the number of different populations in which algorithm can perform simultaneous searches. In this study, Migrating Birds Optimization (MBO) Algorithm, no migration performed, was applied for four different NS values. Additionally, Parallel Migrating Birds Optimization (PMBO) Algorithm is executed using five MR values, five MI values and four NS values and obtained fitness values are provided. According to the results, PMBO algorithm outperforms MBO in 99% of case studies. Therefore, the contribution of migration to the performance of the algorithm is evidently demonstrated. Furthermore, the values obtained during the iterations are shown on graph to investigate the effect of MI and MR changes on search performance of algorithms. As MI decreases, it is confirmed that the algorithm produces good results in early steps of iterations, making faster searches. MR has a greater effect on performance if MI is kept low. If MI increases, the changes in MR have less affect. Additionally, the effect of MI, MR, NS values and their correlation on fitness value is analyzed with analysis of variance (ANOVA). According to the analysis, MI is identified to be the most significant factor. The least significant factor is NS. Combinations of such parameters are analyzed and it was shown that MR*MI combination has the most significant effect on performance.

Keywords

Parallel Migrating Birds Optimization Algorithm, migration parameters

Thanks

The numerical calculations reported in this paper were partially performed at TUBITAK ULAKBIM, High Performance and Grid Computing Center (TRUBA resources). Thanks for their support.

References

• Baştürk A. and Akay R., "Performance Analysis of the Coarse-Grained Parallel Model of the Artificial Bee Colony Algorithm", Information Sciences, 253, 34-55, (2013).
• Asadzadeh L., "A parallel artificial bee colony algorithm for the job shop scheduling problem with a dynamic migration strategy", Computers & Industrial Engineering, 102, 359-367, (2016).
• Gülcü Ş. and Kodaz H., "A novel parallel multi-swarm algorithm based on comprehensive learning particle swarm optimization", Engineering Applications of Artificial Intelligence, 45, 33-45, (2015).
• Tu K.Y. and Liang Z.C., "Parallel computation models of particle swarm optimization implemented by multiple threads", Expert Systems with Applications, 38(5), 5858-5866, (2011).
• Alba E., Nebro A. J. and Troya J. M., "Heterogeneous Computing and Parallel Genetic Algorithms", Journal of Parallel and Distributed Computing, 62(9) 1362-1385, (2002).
• Doorly D. J. and Peiró J., "Supervised Parallel Genetic Algorithms in Aerodynamic Optimisation", Artificial Neural Nets and Genetic Algorithms, Vienna, (1998).
• Mühlenbein H., Schomisch M. ve Born J., "The parallel genetic algorithm as function optimizer", Parallel Computing, 17(6-7) 619-632, (1991).
• Randall M. and Lewis A., "A Parallel Implementation of Ant Colony Optimization", Journal of Parallel and Distributed Computing, 62(9), 1421-1432, (2002).
• Wang H., Rahnamayan S. and Wu Z., "Parallel differential evolution with self-adapting control parameters and generalized opposition-based learning for solving high-dimensional optimization problems", Journal of Parallel and Distributed Computing, 73, 62-73, (2013).
• Xiaofang Y., Ting Z., Yongzhong X. and Xiangshan D., "Parallel chaos optimization algorithm with migration and merging operation", Applied Soft Computing, 35, 591-604, (2015).
• Rebaudengo M. and Reorda M. S., "An experimental analysis of the effects of migration in parallel genetic algorithms", 1993 Euromicro Workshop on Parallel and Distributed Processing, Gran Canaria, (1993).
• Alba E. and Troya J. M., "Improving flexibility and efficiency by adding parallelism to genetic algorithms", Statistics and Computing, 12(2), 91-114, (2002).
• Duman E., Uysal M. and Alkaya A. F., "Migrating Birds Optimization: A new metaheuristic approach and its performance on quadratic assignment problem", Information Sciences, 217, 65-77, (2012).
• Makas H., "Güncel en iyileme algoritmalarının paralel ve birlikte uygulamaları ve performans analizleri", Doktora Tezi, Sakarya Üniversitesi Fen Bilimleri Enstitüsü, Bilgisayar ve Bilişim Mühendisliği Anabilim Dalı, Sakarya, (2015).
• Karaboğa D., Yapay Zeka Optimizasyon Algoritmaları, Kayseri: Nobel Akademik Yayıncılık, 207-208, (2014).
• Öz D., "Göç Eden Kuşlar Algoritmasinda Kaos Fonksiyonlarinin Kullanilmasi," Gazi Üniversitesi Fen Bilimleri Dergisi, 225-233, (2016).
• Tongur V. ve Ülker E., "Tek Boyutlu Kesme Probleminin Göçmen Kuşlar Optimizasyon Algoritması ile Çözümü", Uluslararası Bilgisayar Bilimleri ve Mühendisliği Konferansı, Tekirdağ, (2016).
• Tongur V. and Ülker E., "The Analysis of Migrating Birds Optimization Algorithm with Neighborhood Operator on Traveling Salesman Problem", Intelligent and Evolutionary Systems, 5, 227-237, (2015).
• Makas H. and Yumuşak N., "New cooperative and modified variants of the migrating birds optimization algorithm", Electronics, Computer and Computation (ICECCO), 2013 International Conference, Ankara, (2013).
• Gao L. and Pan Q.-K., "A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem", Information Sciences, 372, 655-676, (2016).
• Zhang B., Pan Q.-K., Gao L., Zhang X.-L., Sang H.-Y. and Li J.-Q., "An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming", Applied Soft Computing, 52, 14-27, (2017).
• Gao K., Suganthan P. N. and Chua T. J., "An enhanced migrating birds optimization algorithm for no-wait flow shop scheduling problem", 2013 IEEE Symposium on Computational Intelligence in Scheduling (CISched), Singapore, (2013).
• Pan Q.-K. and Dong Y., "An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimisation", Information Sciences, 277, 643-655, (2014).
• Ramanathan L. and Ulaganathan K., "Nature-inspired Metaheuristic Optimization Technique-Migrating bird’s optimization in Industrial Scheduling Problem", SSRG International Journal of Industrial Engineering (IJIE), 1(3) 1-6, (2014).
• Benkalai I., Rebaine D., Gagné C. and Baptiste P., "The migrating birds optimization metaheuristic for the permutation flow shop with sequence dependent setup times", IFAC-PapersOnLine, 49(12), 408-413, (2016).
• Tongur V. and Ülker E., "Migrating Birds Optimization for Flow Shop Sequencing Problem", Journal of Computer and Communications, 02(04), 142-147, (2014).
• Niroomand S., Hadi-Vencheh A., Şahin R. and Vizvári B., "Modified migrating birds optimization algorithm for closed loop layout with exact distances in flexible manufacturing systems", Expert Systems with Applications, 42(19), 6586-6597, (2015).
• Öz D., "An improvement on the Migrating Birds Optimization with a problem-specific neighboring function for the multi-objective task allocation problem", Expert Systems with Applications, 67, 304-311, (2017).
• Makas H. and Yumuşak N., "System ident cation by using migrating birds optimization algorithm: a comparative performance analysis", Turkish Journal of Electrical Engineering & Computer Sciences, 24, 1879-1900, (2016).
• Makas H. and Yumuşak N., "Balancing exploration and exploitation by using sequential execution cooperation between artificial bee colony and migrating birds optimization algorithms", Turkish Journal of Electrical Engineering and Computer Sciences, 24(6), 4935-4956, (2016).
• https://www.sfu.ca/~ssurjano/griewank.html [online], (06.10.2019)
• Erdem, İ., Minitab Uygulamalı İstatistik Yöntemler, Seçkin Yayıncılık, Ankara, 2017.