Mariana Macedo
Ronaldo Menezes
ABSTRACT
Computational swarm intelligence has been demonstrably shown to efficiently solve high-dimensional optimization problems due to its flexibility, robustness, and (low) computational cost. Despite these features, swarm-based algorithms are black boxes whose dynamics may be hard to understand. In this paper, we delve into the Fish School Search (FSS) algorithm by looking at how fish interact within the fish school. We find that the network emerging from these interactions is structurally invariant to the optimization of three benchmark functions: Rastrigin, Rosenbrock and Schwefel. However, at the same time, our results also reveal that the level of social interactions among the fish depends on the problem. We show that the absence of highly-influential fish leads to a slow-paced convergence in FSS and that the changes in the intensity of social interactions enable good performance on both unimodal and multimodal problems. Finally, we examine two other swarm-based algorithms---the Artificial Bee Colony (ABC) and Particle Swarm Optimization (PSO) algorithms---and find that for the same three benchmark functions, the structural invariance characteristic only occurs in the FSS algorithm. We argue that FSS, ABC, and PSO have distinctive signatures of interaction structure and flow.
Supplemental Material
Available for Download
p40-macedo_suppl.pdf
- James P Bagrow and Erik M Bollt. 2019. An information-theoretic, all-scales approach to comparing networks. Applied Network Science 4, 1 (2019), 45.Google Scholar
Cross Ref
- James P Bagrow, Erik M Bollt, Joseph D Skufca, and Daniel Ben-Avraham. 2008. Portraits of complex networks. EPL (Europhysics Letters) 81, 6 (2008), 68004.Google ScholarCross Ref
- C. J. A. Bastos Filho, F. B. de Lima Neto, A. J. C. C. Lins, A. I. S. Nascimento, and M. P. Lima. 2008. A novel search algorithm based on fish school behavior, In 2008 IEEE International Conference on Systems, Man and Cybernetics. 2008 IEEE International Conference on Systems, Man and Cybernetics, 2646--2651. Google ScholarCross Ref
- Dmitry I Belov and Ronald D Armstrong. 2011. Distributions of the Kullback-Leibler divergence with applications. Brit. J. Math. Statist. Psych. 64, 2 (2011), 291--309.Google ScholarCross Ref
- Daniel Bratton and Tim Blackwell. 2007. Understanding particle swarms through simplification: a study of recombinant PSO. In Proceedings of the 9th annual conference companion on Genetic and evolutionary computation. ACM, 2621--2628.Google ScholarDigital Library
- Amrita Chakraborty and Arpan Kumar Kar. 2017. Swarm intelligence: A review of algorithms. Nature-Inspired Computing and Optimization (2017), 475--494.Google Scholar
- C. J. A. B. Filho, F. B. L. Neto, M. F. C. Sousa, M. R. Pontes, and S. S. Madeiro. 2009. On the influence of the swimming operators in the Fish School Search algorithm, In 2009 IEEE International Conference on Systems, Man and Cybernetics. 2009 IEEE International Conference on Systems, Man and Cybernetics, 5012--5017. Google ScholarCross Ref
- Nishant Gurrapadi, Lydia Taw, Mariana Macedo, Marcos Oliveira, Diego Pinheiro, Carmelo Bastos-Filho, and Ronaldo Menezes. 2019. Modelling the Social Interactions in Ant Colony Optimization. In International Conference on Intelligent Data Engineering and Automated Learning. Springer, 216--224.Google Scholar
- J. R. Hershey and P. A. Olsen. 2007. Approximating the Kullb6ack Leibler Divergence Between Gaussian Mixture Models. In 2007 IEEE International Conference on Acoustics, Speech and Signal Processing, Vol. 4. USA, IV-317--IV-320. Google ScholarCross Ref
- Michalis Mavrovouniotis, Changhe Li, and Shengxiang Yang. 2017. A survey of swarm intelligence for dynamic optimization: Algorithms and applications. Swarm and Evolutionary Computation 33 (2017), 1--17.Google ScholarCross Ref
- Marcos Oliveira, Carmelo JA Bastos-Filho, and Ronaldo Menezes. 2014. Towards a network-based approach to analyze particle swarm optimizers. In Swarm Intelligence (SIS), 2014 IEEE Symposium on. IEEE, 1--8.Google ScholarCross Ref
- Marcos Oliveira, Diego Pinheiro, Mariana Macedo, Carmelo Bastos-Filho, and Ronaldo Menezes. 2017. Better exploration-exploitation pace, better swarm: Examining the social interactions. In Computational Intelligence (LA-CCI), 2017 IEEE Latin American Conference on. IEEE, 1--6.Google ScholarCross Ref
- Marcos Oliveira, Diego Pinheiro, Mariana Macedo, Carmelo Bastos-Filho, and Ronaldo Menezes. 2020. Uncovering the social interaction network in swarm intelligence algorithms. Applied Network Science 5, 1 (dec 2020), 24. arXiv:1811.03539 Google ScholarCross Ref
- Clodomir Santana, Edward Keedwell, and Ronaldo Menezes. 2020. An approach to assess swarm intelligence algorithms based on complex networks. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference. 31--39.Google ScholarDigital Library
- Kenneth Sörensen. 2015. Metaheuristics---the metaphor exposed. International Transactions in Operational Research 22, 1 (2015), 3--18.Google ScholarCross Ref
- P. N. Suganthan, N. Hansen, J. J. Liang, K. Deb, Y. P. Chen, A. Auger, and S. Tiwari. 2005. Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on Real-Parameter Optimization. Technical Report. Nanyang Technological University, Singapore.Google Scholar
- Lydia Taw, Nishant Gurrapadi, Mariana Macedo, Marcos Oliveira, Diego Pinheiro, Carmelo Bastos-Filho, and Ronaldo Menezes. 2019. Characterizing the Social Interactions in the Artificial Bee Colony Algorithm. In 2019 IEEE Congress on Evolutionary Computation (CEC). IEEE, 1243--1250.Google Scholar
- Yudong Zhang, Shuihua Wang, and Genlin Ji. 2015. A comprehensive survey on particle swarm optimization algorithm and its applications. Mathematical Problems in Engineering 2015 (2015).Google Scholar
Recommendations
Modelling the Social Interactions in Ant Colony Optimization
Intelligent Data Engineering and Automated Learning – IDEAL 2019AbstractAnt Colony Optimization (ACO) is a swarm-based algorithm inspired by the foraging behavior of ants. Despite its success, the efficiency of ACO has depended on the appropriate choice of parameters, requiring deep knowledge of the algorithm. A true ...
CAPSO: Centripetal accelerated particle swarm optimization
Meta-heuristic search algorithms are developed to solve optimization problems. Such algorithms are appropriate for global searches because of their global exploration and local exploitation abilities. Swarm intelligence (SI) algorithms comprise a branch ...
A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm
Swarm intelligence is a research branch that models the population of interacting agents or swarms that are able to self-organize. An ant colony, a flock of birds or an immune system is a typical example of a swarm system. Bees' swarming around their ...
Comments