A Stigmergy-Based Differential Evolution
Source abstract
Abstract
Metaheuristic algorithms are techniques that have been successfully applied to solve complex optimization problems in engineering and science. Many metaheuristic approaches, such as Differential Evolution (DE), use the best individual found so far from the whole population to guide the search process. Although this approach has advantages in the algorithm’s exploitation process, it is not completely in agreement with the swarms found in nature, where communication among individuals is not centralized. This paper proposes the use of stigmergy as an inspiration to modify the original DE operators to simulate a decentralized information exchange, thus avoiding the application of a global best. The Stigmergy-based DE (SDE) approach was tested on a set of benchmark problems to compare its performance with DE. Even though the execution times of DE and SDE are very similar, our proposal has a slight advantage in most of the functions and can converge in fewer iterations in some cases, but its main feature is the capability to maintain a good convergence behavior as the dimensionality grows, so it can be a good alternative to solve complex problems.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Metaheuristic Optimization Algorithms Research · Advanced Multi-Objective Optimization Algorithms · Evolutionary Algorithms and Applications
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Sciences, Centro Universitario de Ciencias Exactas e Ingenierías-Universidad de Guadalajara, Av. Revolución 1500, Col. Olímpica, Guadalajara 44430, Jalisco, Mexico
Department of Engineering, Universidad Anáhuac México, Avenida Universidad Anáhuac 46, Col. Lomas Anáhuac, Huixquilucan 52786, Estado de Mexico, Mexico
References (66)
Show source-provided references
1. Recent Advances on Bioinspired Computation10.1155/2014/934890 ↗
2. Bio-inspired computation: Where we stand and what’s next10.1016/j.swevo.2019.04.008 ↗
3. Exploration and exploitation in evolutionary algorithms10.1145/2501654.2501658 ↗
4. A New Heuristic Optimization Algorithm: Harmony Search10.1177/003754970107600201 ↗
5. A new meta-heuristic algorithm for continuous engineering optimization: Harmony search theory and practice10.1016/j.cma.2004.09.007 ↗
6. Geem, Z.W. (2009). Music-Inspired Harmony Search Algorithm: Theory and Applications, Springer.10.1007/978-3-642-00185-7 ↗
7. Differential Evolution—A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces10.1023/A:1008202821328 ↗
8. Mezura-Montes, E., Velázquez-Reyes, J., and Coello, C.A.C. (2006, January 8–12). A comparative study of differential evolution variants for global optimization. Proceedings of the GECCO’06—Genetic and Evolutionary Computation Conference, Seattle, WA, USA.10.1145/1143997.1144086 ↗
9. Kennedy, J., and Eberhart, R. (December, January 27). Particle swarm optimization. Proceedings of the ICNN’95—International Conference on Neural Networks, Perth, WA, Australia.
10. Tan, Y., and Zhu, Y. (2010). Fireworks Algorithm for Optimization. LNCS, Springer.10.1007/978-3-642-13495-1_44 ↗
11. Tan, Y. (2015). Fireworks Algorithm, Springer.10.1007/978-3-662-46353-6 ↗
12. Yang, X.S. (2012). Flower Pollination Algorithm for Global Optimization. Unconventional Computation and Natural Computation, Springer.10.1007/978-3-642-32894-7_27 ↗
13. GSA: A Gravitational Search Algorithm10.1016/j.ins.2009.03.004 ↗
14. Łukasik, S., and Żak, S. (2009). Firefly Algorithm for Continuous Constrained Optimization Tasks. Computational Collective Intelligence. Semantic Web, Social Networks and Multiagent Systems, Springer.10.1007/978-3-642-04441-0_8 ↗
15. Yang, X.S. (2009). Firefly Algorithms for Multimodal Optimization. Stochastic Algorithms: Foundations and Applications, Springer.10.1007/978-3-642-04944-6_14 ↗
16. Yang, X.S., and Deb, S. (2009, January 9–11). Cuckoo Search via Lévy flights. Proceedings of the 2009 World Congress on Nature Biologically Inspired Computing (NaBIC), Coimbatore, India.10.1109/NABIC.2009.5393690 ↗
17. Karaboga, D. (2005). An Idea Based on Honey Bee Swarm for Numerical Optimization, Erciyes University. Technical Report—TR06.
18. A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm10.1007/s10898-007-9149-x ↗
19. Meng, X., Liu, Y., Gao, X., and Zhang, H. (2014). A New Bio-inspired Algorithm: Chicken Swarm Optimization. LNCS, Springer.10.1007/978-3-319-11857-4_10 ↗
20. Raghul, S., and Jeyakumar, G. (2021). Parallel and Distributed Computing Approaches for Evolutionary Algorithms—A Review. Advances in Intelligent Systems and Computing, Springer.10.1007/978-981-16-1740-9_35 ↗
21. Buck, I. (2007). GPU computing with NVIDIA CUDA. ACM SIGGRAPH 2007 Courses on—SIGGRAPH’07, ACM Press.10.1145/1281500.1281647 ↗
22. GPU parallelization strategies for metaheuristics: A survey10.1080/17445760.2018.1428969 ↗
23. Gravitational search algorithm using CUDA: A case study in high-performance metaheuristics10.1007/s11227-014-1360-1 ↗
24. Parallel differential evolution with self-adapting control parameters and generalized opposition-based learning for solving high-dimensional optimization problems10.1016/j.jpdc.2012.02.019 ↗
25. Qin, A.K., Raimondo, F., Forbes, F., and Ong, Y.S. (2012, January 7–11). An improved CUDA-based implementation of differential evolution on GPU. Proceedings of the GECCO’12: 14th International Conference on Genetic and Evolutionary Computation, Philadelphia, PE, USA.10.1145/2330163.2330301 ↗
26. Krömer, P., Platoš, J., and Snášel, V. (2013, January 16–19). A brief survey of differential evolution on Graphic Processing Units. Proceedings of the 2013 IEEE Symposium on Differential Evolution (SDE), Singapore.10.1109/SDE.2013.6601456 ↗
27. de P. Veronese, L., and Krohling, R.A. (2010, January 18–23). Differential evolution algorithm on the GPU with C-CUDA. Proceedings of the IEEE Congress on Evolutionary Computation, Barcelona, Spain.10.1109/CEC.2010.5586219 ↗
28. Massively parallel differential evolution—Pattern search optimization with graphics hardware acceleration: An investigation on bound constrained optimization problems10.1007/s10898-010-9590-0 ↗
29. Krömer, P., Snåšel, V., Platoš, J., and Abraham, A. (2011, January 12–16). Many-threaded implementation of differential evolution for the CUDA platform. Proceedings of the 13th annual conference on Genetic and evolutionary computation—GECCO’11, Dublin, Ireland.10.1145/2001576.2001791 ↗
30. Particle Swarm Optimization and Differential Evolution for model-based object detection10.1016/j.asoc.2012.11.027 ↗
31. A co-evolutionary differential evolution algorithm for solving min–max optimization problems implemented on GPU using C-CUDA10.1016/j.eswa.2011.10.015 ↗
32. Zhou, X., Wu, Z., and Wang, H. (2012, January 14–16). Elite Opposition-Based Differential Evolution for Solving Large-Scale Optimization Problems and Its Implementation on GPU. Proceedings of the 2012 13th International Conference on Parallel and Distributed Computing, Applications and Technologies, Beijing, China.10.1109/PDCAT.2012.70 ↗
33. Zibin, P. (2021). Performance Analysis and Improvement of Parallel Differential Evolution. arXiv.
34. Social Insect Colonies as Complex Adaptive Systems10.1007/s100219900038 ↗
35. An individual approach to modelling emergent structure in termite swarm systems10.1504/IJMIC.2008.018181 ↗
36. Korošec, P., Tashkova, K., and Šilc, J. (2010, January 18–23). The differential Ant-Stigmergy Algorithm for large-scale global optimization. Proceedings of the IEEE Congress on Evolutionary Computation, Barcelona, Spain.10.1109/CEC.2010.5586201 ↗
37. Revisiting stigmergy in light of multi-functional, biogenic, termite structures as communication channel10.1016/j.csbj.2020.08.012 ↗
38. A hyper-heuristic methodology for coordinating swarms of robots in target search10.1016/j.compeleceng.2021.107420 ↗
39. Ant Colony Optimization-based distributed multilayer routing and restoration in IP/MPLS over optical networks10.1016/j.comnet.2020.107747 ↗
40. Upeksha, R.G.C., and Pemarathne, W.P.J. (2022). Ant Colony Optimization Algorithms for Routing in Wireless Sensor Networks: A Review. Lecture Notes in Electrical Engineering, Springer.10.1007/978-981-16-9781-4_6 ↗
41. Ant system: Optimization by a colony of cooperating agents10.1109/3477.484436 ↗
42. Continuous ant colony system and tabu search algorithms hybridized for global minimization of continuous multi-minima functions10.1007/s10589-008-9176-7 ↗
43. Differential evolution and differential ant-stigmergy on dynamic optimisation problems10.1080/00207721.2011.617899 ↗
44. Bilchev, G., and Parmee, I.C. (1995). The ant colony metaphor for searching continuous design spaces. Evolutionary Computing, Springer.10.1007/3-540-60469-3_22 ↗
45. Dréo, J., and Siarry, P. (2002). A New Ant Colony Algorithm Using the Heterarchical Concept Aimed at Optimization of Multiminima Continuous Functions. Ant Algorithms, Springer.10.1007/3-540-45724-0_18 ↗
46. Korošec, P., and Šilc, J. (2009). A Stigmergy-Based Algorithm for Continuous Optimization Tested on Real-Life-Like Environment. Lecture Notes in Computer Science, Springer.10.1007/978-3-642-01129-0_77 ↗
47. A stigmergic approach to teaching-learning-based optimization for continuous domains10.1016/j.swevo.2020.100826 ↗
48. Application of differential evolution algorithm in static and dynamic economic or emission dispatch problem: A review10.1016/j.rser.2017.03.097 ↗
49. Enhanced versions of differential evolution: State-of-the-art survey10.1504/IJCSM.2014.064064 ↗
50. Combining Multiobjective Optimization With Differential Evolution to Solve Constrained Optimization Problems10.1109/TEVC.2010.2093582 ↗
51. Stigmergy as a universal coordination mechanism I: Definition and components10.1016/j.cogsys.2015.12.002 ↗
52. Stigmergy as a universal coordination mechanism II: Varieties and evolution10.1016/j.cogsys.2015.12.007 ↗
53. Solution of Linear and Non-Linear Boundary Value Problems Using Population-Distributed Parallel Differential Evolution10.2478/jaiscr-2019-0004 ↗
54. Differential Evolution Implementation for Power Quality Disturbances Monitoring using OpenCL10.4316/AECE.2019.02002 ↗
55. Research of Dynamic Economic Emission Dispatch Based on Parallel Molecular Differential Evolution Algorithm10.1088/1755-1315/170/3/032003 ↗
56. A differential evolution algorithm parallel implementation in a GPU
57. Evaluating center-seeking and initialization bias: The case of particle swarm and gravitational search algorithms10.1016/j.ins.2014.03.094 ↗
58. Hollander, M., Wolfe, D.A., and Chicken, E. (2013). Nonparametric Statistical Methods, John Wiley & Sons.
59. Differential evolution: A recent review based on state-of-the-art works10.1016/j.aej.2021.09.013 ↗
60. Differential Evolution Algorithm for Job Shop Scheduling Problem
61. Algebraic Differential Evolution Algorithm for the Permutation Flowshop Scheduling Problem With Total Flowtime Criterion10.1109/TEVC.2015.2507785 ↗
62. Multilevel Image Thresholding Based on 2D Histogram and Maximum Tsallis Entropy—A Differential Evolution Approach10.1109/TIP.2013.2277832 ↗
63. A comparison of nature inspired algorithms for multi-threshold image segmentation10.1016/j.eswa.2012.08.017 ↗
64. Jain, S., Sharma, V.K., and Kumar, S. (2020). Robot Path Planning Using Differential Evolution. Advances in Computing and Intelligent Systems, Springer.10.1007/978-981-15-0222-4_50 ↗
65. An area coverage algorithm for wireless sensor networks based on differential evolution10.1177/1550147718796734 ↗
66. Measuring the curse of dimensionality and its effects on particle swarm optimization and differential evolution10.1007/s10489-014-0613-2 ↗