ارائه الگوریتم فراابتکاری برای حل مسائل بهینه‌سازی عددی با الهام از مفهوم تاوه در فیزیک شاره
نویسندگان
دانشکده مهندسی برق و کامپیوتر، دانشگاه صنعتی نوشیروانی بابل، بابل
چکیده
یکی از مسائل مهم در مهندسی، یافتن نقاط بهینه سراسری توابع مورد استفاده است. یافتن چنین نقطه‌ای در برخی از توابع به‌علت‌هایی نظیر تعداد ابعاد بالا یا عدم توانایی مشتق‌گیری از تابع، به‌راحتی امکان پذیر نیست. همچنین در مدل‌سازی مهندسی روابط بسیاری از توابع در اختیار نیست اما به‌صورت جعبه سیاه می‌توان به آنها ورودی داد و از آنها خروجی گرفت. از این‌رو با دلایل مطرح شده، الگوریتم‌های فراابتکاری ارائه می‌شوند.
در این مقاله الگوریتمی‌فراابتکاری برگرفته از رفتار تاوه‌ها در فیزیک شاره ارائه شده است. الگوریتم از دیدگاه فنی از تاوههایی ساخته می‌شود. هر تاوه شامل چند ذره است. ذرات با استفاده از ماتریس دوران ارائه شده حرکت میکنند. این حرکت موجب جستجوی محلی می‌شود. همچنین هر تاوه با انتخاب یکی از تاوه‌های دیگر با الگوریتم انتخاب، سعی در فرار از بهینه محلی و رسیدن به بهینه سراسری دارد. الگوریتم با عملگرهای خود به اکتشاف و استخراج در تابع مورد نظر میپردازد. نوآوری دیگر این مقاله، ارائه دو معیار ارزیابی جدید برای الگوریتم‌های بهینه‌سازی است. این دو معیار رفتار و همگرایی الگوریتم‌ها را در طی مسیر رسیدن به نقطه بهینه سراسری و یا افتادن در بهینه محلی، نشان می‌دهند. الگوریتم پیشنهادی پیاده‌سازی شده و با الگوریتم‌های بهینه‌سازی عددی مرز دانش مورد ارزیابی و مقایسه قرار گرفته است. مشاهده شد که روش پیشنهادی می‌تواند روی اکثر توابع معیار، از بیست و چهار تابع معیار در ابعاد مختلف، به نتایج بهتری نسبت به سایر روش‌ها دست یابد. ( تمام کدها در صفحه http://web.nit.ac.ir/ h.omranpour/ در دسترس است).
در این مقاله الگوریتمی‌فراابتکاری برگرفته از رفتار تاوه‌ها در فیزیک شاره ارائه شده است. الگوریتم از دیدگاه فنی از تاوههایی ساخته می‌شود. هر تاوه شامل چند ذره است. ذرات با استفاده از ماتریس دوران ارائه شده حرکت میکنند. این حرکت موجب جستجوی محلی می‌شود. همچنین هر تاوه با انتخاب یکی از تاوه‌های دیگر با الگوریتم انتخاب، سعی در فرار از بهینه محلی و رسیدن به بهینه سراسری دارد. الگوریتم با عملگرهای خود به اکتشاف و استخراج در تابع مورد نظر میپردازد. نوآوری دیگر این مقاله، ارائه دو معیار ارزیابی جدید برای الگوریتم‌های بهینه‌سازی است. این دو معیار رفتار و همگرایی الگوریتم‌ها را در طی مسیر رسیدن به نقطه بهینه سراسری و یا افتادن در بهینه محلی، نشان می‌دهند. الگوریتم پیشنهادی پیاده‌سازی شده و با الگوریتم‌های بهینه‌سازی عددی مرز دانش مورد ارزیابی و مقایسه قرار گرفته است. مشاهده شد که روش پیشنهادی می‌تواند روی اکثر توابع معیار، از بیست و چهار تابع معیار در ابعاد مختلف، به نتایج بهتری نسبت به سایر روش‌ها دست یابد. ( تمام کدها در صفحه http://web.nit.ac.ir/ h.omranpour/ در دسترس است).
کلیدواژه‌ها
عنوان مقاله [English]
A Meta-heuristic Algorithm for Global Numerical Optimization Problems inspired by Vortex in fluid physics
نویسندگان [English]
- N. Mashhadi Mohammad Reza
- H. Omranpour
One of the most important issues in engineering is to find the optimal global points of the functions used. It is not easy to find such a point in some functions due to the reasons such as large number of dimensions or inability to derive them from the function. Also in engineering modeling, we do not have the relationships of many functions, but we can input and output them as a black box. Therefore, the meta-heuristic algorithms are presented.
In this paper, a meta-heuristic algorithm based on the behavior of vortices in fluid physics is presented. Technically, the algorithm is made up of vortices. Each vortex contains some particles. The particles move by the presented rotation matrix. This movement causes the local search. Also by selecting another vortex through the selection algorithm, each vortex attempts to escape the local optima and reach the global optima. The algorithm will explore and exploit the given function using its operators. Another innovation of this paper is the introduction of two new evaluation criteria for optimization algorithms. These two criteria show the behavior and convergence of algorithms along the way to reach the global optimal point or fall into the local optima. The proposed algorithm has been implemented, evaluated and compared with the numerical optimization state of the art algorithms. It was observed that the proposed method was able to achieve better results than most of the other methods in the major of twenty-four standard functions in different dimensions. (All codes available at http://web.nit.ac.ir/ h.omranpour/.).
کلیدواژه‌ها [English]
- Numerical Optimization
- Meta-heuristic algorithms
- Search Space
- Evaluation Criteria
- Vortex Optimization Algorithm (VOA)
1. Mirjalili, S., Song Dong, J., Sadiq, A. S., and Faris, H., “Genetic Algorithm: Theory, Literature Review, and Application in Image Reconstruction”, Studies in Computational Intelligence, Vol. 811, pp. 69–85, 2020.
2. Whitley, D., “A Genetic Algorithm Tutorial”, Statistics and Computing, Vol. 4, No. 2, pp. 65-85. 1994.
3. Kennedy J., and Eberhart, R., “Particle Swarm Optimization”, Proceedings of ICNN’95 - International Conference on Neural Networks, Vol. 4, pp. 1942–1948, 2002.
4. Chan, C. L. and Chen, C. L., “A Cautious PSO with Conditional Random” Expert Systems with Applications, Vol. 42, No. 8, pp. 4120–4125, 2015.
5. Pham D. T. and Karaboga, D., “Genetic Algorithms, Tabu Search, Simulated Annealing, Neural Networks” Intelligent Optimisation Techniques, Vol. 1, pp. 51–240, 2000.
6. Mirjalili, S., “SCA: A Sine Cosine Algorithm for Solving Optimization Problems”, Knowledge-Based Systems., Vol. 96, pp. 120–133, 2016.
7. Yang, X.-S., Deb, S., Fong, S., He, X., and Zhao, Y.-X., “From Swarm Intelligence to Metaheuristics: Nature-Inspired Optimization Algorithms”, Computer, Vol. 49, No. 9, pp. 52–59, 2016.
8. Wolpert, D. H. and Macready, W. G., “No Free Lunch Theorems for Optimization,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 67–82, 1997.
9. Dasgupta, D., and Michalewicz, Z., Eds., Evolutionary Algorithms in Engineering Applications, Berlin, Heidelberg: Springer Berlin Heidelberg, 1997,
10. Yang X.-S., Optimization Techniques and Applications with Examples. Hoboken, New Jersey, John Wiley & Sons, 2018
11. Holland, J. H., “Genetic Algorithms,” Scientific American., Vol. 267, No. 1, pp. 66–73, 1992.
12. Beyer, H.-G. and Schwefel, H.-P., “Evolution strategies – A comprehensive introduction”, Natural Computing, Vol. 1, No. 1, pp. 3–52, 2002.
13. Koza, J.-R., Genetic Programming: on the Programming of Computers by Means of Natural Selection, Cambridge, Massachusetts. The MIT Press, 1998.
14. Dorigo, M. and Stützle, T., “Ant Colony Optimization: Overview and Recent Advances”, Handbook of Metaheuristics, Vol. 146, pp. 227–263, 2010.
15. Lu, X. and Zhou, Y., “A Novel Global Convergence Algorithm: Bee Collecting Pollen Algorithm”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 5227 LNAI, pp. 518–525, 2008.
16. Pinto, P. C., Runkler, T. A., and Sousa, J. M. C., “Wasp Swarm Algorithm for Dynamic MAX-SAT Problems”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 4431 LNCS, No. PART 1, pp. 350–357, 2007.
17. Karaboga, D., and Basturk, B., “Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 4529 LNAI, pp. 789–798, 2007.
18. Yang X. S., and Deb, S., “Cuckoo Search via Levy Flights”, 2009 World Congress on Nature and Biologically Inspired Computing, NABIC 2009 - Proceedings, pp. 210–214, 2010.
19. Yang, S., Jiang, J., and Yan, G., “A Dolphin Partner Optimization”, Proceedings of the 2009 WRI Global Congress on Intelligent Systems, GCIS 2009, Vol. 1, pp. 124–128, 2009.
20. Kaveh, A. and Farhoudi, N., “A New Optimization Method: Dolphin Echolocation”, Advances in Engineering Software, Vol. 59, pp. 53–70, 2013.
21. Yang, X.-S. S., “A New Metaheuristic Bat-Inspired Algorithm BT - Nature Inspired Cooperative Strategies for Optimization (NICSO 2010)”, Studies in Computational Intelligence, Vol. 284, pp. 65–74, 2010.
22. Yang, X. S., “Firefly Algorithm, Stochastic Test Functions and Design Optimisation”, International Journal of Bio-Inspired Computation, Vol. 2, No. 2, pp. 78–84, 2010.
23. Oftadeh, R., Mahjoob, M. J., and Shariatpanahi, M., “A Novel Meta-Heuristic Optimization Algorithm Inspired by Group Hunting of Animals: Hunting Search”, Computers & Mathematics with Applications, Vol. 60, No. 7, pp. 2087–2098, 2010.
24. Askarzadeh, A., and Rezazadeh, A., “A New Heuristic Optimization Algorithm for Modeling of Proton Exchange Membrane Fuel Cell: Bird Mating Optimizer”, International Journal of Energy Research, Vol. 37, No. 10, pp. 1196–1204, 2013.
25. Gandomi, A. H., and Alavi, A. H., “Krill Herd: A New Bio-Inspired Optimization Algorithm”, Communications in Nonlinear Science and Numerical Simulation, Vol. 17, No. 12, pp. 4831–4845, 2012.
26. Pan, W. T., “A New Fruit Fly Optimization Algorithm: Taking the Financial Distress Model as an Example”, Knowledge-Based Systems, Vol. 26, pp. 69–74, 2012.
27. Mucherino, A., Seref, O., Seref, O., Kundakcioglu, O. E., and Pardalos, P., “Monkey Search: a Novel Metaheuristic Search for Global Optimization”, AIP Conference Proceedings, Vol. 953, No. 1, pp. 162–173, 2007.
28. Roth, M., and Wicker, S., “Termite: A Swarm Intelligent Routing Algorithm for Mobilewireless Ad-Hoc Networks”, Studies in Computational Intelligence, Vol. 31, pp. 155–184, 2006.
29. Mirjalili, S., Mirjalili, S. M., and Lewis, A., “Grey Wolf Optimizer”, Advances in Engineering Software, Vol. 69, pp. 46–61, 2014.
30. Abualigah, L., Shehab, M., Alshinwan, M., and Alabool, H., “Salp Swarm Algorithm: a Comprehensive Survey”, Neural Computing and Applications 2019 32:15, Vol. 32, No. 15, pp. 11195–11215, 2019.
31. Mirjalili S., and Lewis, A.,“The Whale Optimization Algorithm”, Advances in Engineering Software, Vol. 95, pp. 51–67, 2016.
32. Heidari, A. A., Faris, H., Mirjalili, S., Aljarah, I., and Mafarja, M., “Ant Lion Optimizer: Theory, Literature Review, and Application in Multi-layer Perceptron Neural Networks”, Studies in Computational Intelligence, Vol. 811, pp. 23–46, 2020.
33. Erol O. K., and Eksin, I., “A New Optimization Method: Big Bang–Big Crunch”, Advances in Engineering Software, Vol. 37, No. 2, pp. 106–111, 2006.
34. Du, H., Wu, X., and Zhuang, J., “Small-World Optimization Algorithm for Function Optimization”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 4222 LNCS-II, pp. 264–273, 2006.
35. Hatamlou, A., “Black Hole: A New Heuristic Optimization Approach for Data Clustering”, Information Sciences, Vol. 222, pp. 175–184, 2013.
36. Mirjalili, S., Mirjalili, S. M., and Hatamlou, A., “Multi-Verse Optimizer: a Nature-Inspired Algorithm for Global Optimization”, Neural Computing and Applications 2015 27:2, Vol. 27, No. 2, pp. 495–513, 2015.
37. Kaveh A., and Khayatazad, M., “A New Meta-Heuristic Method: Ray Optimization”, Computers & Structures, Vol. 112–113, pp. 283–294, 2012.
38. Atashpaz-Gargari, E., and Lucas, C., “Imperialist Competitive Algorithm: An Algorithm for Optimization Inspired by Imperialistic Competition”, 2007 IEEE Congress on Evolutionary Computation, CEC 2007, pp. 4661–4667, 2007.
39. Ray, T., and Liew, K. M., “Society and Civilization: An Optimization Algorithm Based on the Simulation of Social Behavior”, IEEE Transactions on Evolutionary Computation, Vol. 7, No. 4, pp. 386–396, 2003.
40. Doʇan, B., and Ölmez, T.,“A New Metaheuristic for Numerical Function Optimization: Vortex Search Algorithm”, Information Sciences, Vol. 293, pp. 125–145, 2015.
41. Ting, L., and Klein, R., Viscous Vortical Flows, Vol. 374. Berlin, Heidelberg: Springer Berlin Heidelberg, 1991.
42. Saffman, P. G., Vortex Dynamics. Cambridge: Cambridge University Press, 1993.
43. Tayyab, M., Cheema, T. A., Malik, M. S., Muzaffar, A., Sajid, M. B., and Park, C. W., “Investigation of Thermal Energy Exchange Potential of a Gravitational Water Vortex”, Renewable Energy, Vol. 162, pp. 1380–1398, 2020.
44. Sugimoto, N., “Nonlinear Interaction Between Vortex and Wave in Rotating Shallow Water”, Vortex Structures in Fluid Dynamic Problems, Vol. 1, pp. 33-52, 2017.
2. Whitley, D., “A Genetic Algorithm Tutorial”, Statistics and Computing, Vol. 4, No. 2, pp. 65-85. 1994.
3. Kennedy J., and Eberhart, R., “Particle Swarm Optimization”, Proceedings of ICNN’95 - International Conference on Neural Networks, Vol. 4, pp. 1942–1948, 2002.
4. Chan, C. L. and Chen, C. L., “A Cautious PSO with Conditional Random” Expert Systems with Applications, Vol. 42, No. 8, pp. 4120–4125, 2015.
5. Pham D. T. and Karaboga, D., “Genetic Algorithms, Tabu Search, Simulated Annealing, Neural Networks” Intelligent Optimisation Techniques, Vol. 1, pp. 51–240, 2000.
6. Mirjalili, S., “SCA: A Sine Cosine Algorithm for Solving Optimization Problems”, Knowledge-Based Systems., Vol. 96, pp. 120–133, 2016.
7. Yang, X.-S., Deb, S., Fong, S., He, X., and Zhao, Y.-X., “From Swarm Intelligence to Metaheuristics: Nature-Inspired Optimization Algorithms”, Computer, Vol. 49, No. 9, pp. 52–59, 2016.
8. Wolpert, D. H. and Macready, W. G., “No Free Lunch Theorems for Optimization,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 67–82, 1997.
9. Dasgupta, D., and Michalewicz, Z., Eds., Evolutionary Algorithms in Engineering Applications, Berlin, Heidelberg: Springer Berlin Heidelberg, 1997,
10. Yang X.-S., Optimization Techniques and Applications with Examples. Hoboken, New Jersey, John Wiley & Sons, 2018
11. Holland, J. H., “Genetic Algorithms,” Scientific American., Vol. 267, No. 1, pp. 66–73, 1992.
12. Beyer, H.-G. and Schwefel, H.-P., “Evolution strategies – A comprehensive introduction”, Natural Computing, Vol. 1, No. 1, pp. 3–52, 2002.
13. Koza, J.-R., Genetic Programming: on the Programming of Computers by Means of Natural Selection, Cambridge, Massachusetts. The MIT Press, 1998.
14. Dorigo, M. and Stützle, T., “Ant Colony Optimization: Overview and Recent Advances”, Handbook of Metaheuristics, Vol. 146, pp. 227–263, 2010.
15. Lu, X. and Zhou, Y., “A Novel Global Convergence Algorithm: Bee Collecting Pollen Algorithm”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 5227 LNAI, pp. 518–525, 2008.
16. Pinto, P. C., Runkler, T. A., and Sousa, J. M. C., “Wasp Swarm Algorithm for Dynamic MAX-SAT Problems”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 4431 LNCS, No. PART 1, pp. 350–357, 2007.
17. Karaboga, D., and Basturk, B., “Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 4529 LNAI, pp. 789–798, 2007.
18. Yang X. S., and Deb, S., “Cuckoo Search via Levy Flights”, 2009 World Congress on Nature and Biologically Inspired Computing, NABIC 2009 - Proceedings, pp. 210–214, 2010.
19. Yang, S., Jiang, J., and Yan, G., “A Dolphin Partner Optimization”, Proceedings of the 2009 WRI Global Congress on Intelligent Systems, GCIS 2009, Vol. 1, pp. 124–128, 2009.
20. Kaveh, A. and Farhoudi, N., “A New Optimization Method: Dolphin Echolocation”, Advances in Engineering Software, Vol. 59, pp. 53–70, 2013.
21. Yang, X.-S. S., “A New Metaheuristic Bat-Inspired Algorithm BT - Nature Inspired Cooperative Strategies for Optimization (NICSO 2010)”, Studies in Computational Intelligence, Vol. 284, pp. 65–74, 2010.
22. Yang, X. S., “Firefly Algorithm, Stochastic Test Functions and Design Optimisation”, International Journal of Bio-Inspired Computation, Vol. 2, No. 2, pp. 78–84, 2010.
23. Oftadeh, R., Mahjoob, M. J., and Shariatpanahi, M., “A Novel Meta-Heuristic Optimization Algorithm Inspired by Group Hunting of Animals: Hunting Search”, Computers & Mathematics with Applications, Vol. 60, No. 7, pp. 2087–2098, 2010.
24. Askarzadeh, A., and Rezazadeh, A., “A New Heuristic Optimization Algorithm for Modeling of Proton Exchange Membrane Fuel Cell: Bird Mating Optimizer”, International Journal of Energy Research, Vol. 37, No. 10, pp. 1196–1204, 2013.
25. Gandomi, A. H., and Alavi, A. H., “Krill Herd: A New Bio-Inspired Optimization Algorithm”, Communications in Nonlinear Science and Numerical Simulation, Vol. 17, No. 12, pp. 4831–4845, 2012.
26. Pan, W. T., “A New Fruit Fly Optimization Algorithm: Taking the Financial Distress Model as an Example”, Knowledge-Based Systems, Vol. 26, pp. 69–74, 2012.
27. Mucherino, A., Seref, O., Seref, O., Kundakcioglu, O. E., and Pardalos, P., “Monkey Search: a Novel Metaheuristic Search for Global Optimization”, AIP Conference Proceedings, Vol. 953, No. 1, pp. 162–173, 2007.
28. Roth, M., and Wicker, S., “Termite: A Swarm Intelligent Routing Algorithm for Mobilewireless Ad-Hoc Networks”, Studies in Computational Intelligence, Vol. 31, pp. 155–184, 2006.
29. Mirjalili, S., Mirjalili, S. M., and Lewis, A., “Grey Wolf Optimizer”, Advances in Engineering Software, Vol. 69, pp. 46–61, 2014.
30. Abualigah, L., Shehab, M., Alshinwan, M., and Alabool, H., “Salp Swarm Algorithm: a Comprehensive Survey”, Neural Computing and Applications 2019 32:15, Vol. 32, No. 15, pp. 11195–11215, 2019.
31. Mirjalili S., and Lewis, A.,“The Whale Optimization Algorithm”, Advances in Engineering Software, Vol. 95, pp. 51–67, 2016.
32. Heidari, A. A., Faris, H., Mirjalili, S., Aljarah, I., and Mafarja, M., “Ant Lion Optimizer: Theory, Literature Review, and Application in Multi-layer Perceptron Neural Networks”, Studies in Computational Intelligence, Vol. 811, pp. 23–46, 2020.
33. Erol O. K., and Eksin, I., “A New Optimization Method: Big Bang–Big Crunch”, Advances in Engineering Software, Vol. 37, No. 2, pp. 106–111, 2006.
34. Du, H., Wu, X., and Zhuang, J., “Small-World Optimization Algorithm for Function Optimization”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 4222 LNCS-II, pp. 264–273, 2006.
35. Hatamlou, A., “Black Hole: A New Heuristic Optimization Approach for Data Clustering”, Information Sciences, Vol. 222, pp. 175–184, 2013.
36. Mirjalili, S., Mirjalili, S. M., and Hatamlou, A., “Multi-Verse Optimizer: a Nature-Inspired Algorithm for Global Optimization”, Neural Computing and Applications 2015 27:2, Vol. 27, No. 2, pp. 495–513, 2015.
37. Kaveh A., and Khayatazad, M., “A New Meta-Heuristic Method: Ray Optimization”, Computers & Structures, Vol. 112–113, pp. 283–294, 2012.
38. Atashpaz-Gargari, E., and Lucas, C., “Imperialist Competitive Algorithm: An Algorithm for Optimization Inspired by Imperialistic Competition”, 2007 IEEE Congress on Evolutionary Computation, CEC 2007, pp. 4661–4667, 2007.
39. Ray, T., and Liew, K. M., “Society and Civilization: An Optimization Algorithm Based on the Simulation of Social Behavior”, IEEE Transactions on Evolutionary Computation, Vol. 7, No. 4, pp. 386–396, 2003.
40. Doʇan, B., and Ölmez, T.,“A New Metaheuristic for Numerical Function Optimization: Vortex Search Algorithm”, Information Sciences, Vol. 293, pp. 125–145, 2015.
41. Ting, L., and Klein, R., Viscous Vortical Flows, Vol. 374. Berlin, Heidelberg: Springer Berlin Heidelberg, 1991.
42. Saffman, P. G., Vortex Dynamics. Cambridge: Cambridge University Press, 1993.
43. Tayyab, M., Cheema, T. A., Malik, M. S., Muzaffar, A., Sajid, M. B., and Park, C. W., “Investigation of Thermal Energy Exchange Potential of a Gravitational Water Vortex”, Renewable Energy, Vol. 162, pp. 1380–1398, 2020.
44. Sugimoto, N., “Nonlinear Interaction Between Vortex and Wave in Rotating Shallow Water”, Vortex Structures in Fluid Dynamic Problems, Vol. 1, pp. 33-52, 2017.
)