Abstract
In this paper, we study Particle Swarm Optimization (PSO) as a collective search mechanism for individuals (such as aerial micro-robots) which are supposed to search in environments with unknown external dynamics. In order to deal with the unknown disturbance, we present new PSO equations which are evolved using Genetic Programming (GP) with a semantically diverse starting population, seeded by the Evolutionary Demes Despeciation Algorithm (EDDA), that generalizes better than standard GP in the presence of unknown dynamics. The analysis of the evolved equations shows that with only small modifications in the velocity equation, PSO can achieve collective search behavior while being unaware of the dynamic external environment, mimicking the zigzag upwind flights of birds towards the food source.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bartashevich, P., Bakurov, I., Mostaghim, S., Vanneschi, L.: Evolving PSO algorithm design in vector fields using geometric semantic GP. In: Proceedings of the ACM Genetic and Evolutionary Computation Conference (GECCO 2018), Kyoto, July 2018, 2 p. (To appear)
Bartashevich, P., Grimaldi, L., Mostaghim, S.: PSO-based search mechanism in dynamic environments: swarms in vector fields. In: 2017 IEEE Congress on Evolutionary Computation, pp. 1263–1270 (2017)
Clerc, M.: Stagnation analysis in particle swarm optimization or what happens when nothing happens. Technical report (2006)
Di Chio, C., Di Chio, P.: Group-foraging with particle swarms and genetic programming. In: Ebner, M., O’Neill, M., Ekárt, A., Vanneschi, L., Esparcia-Alcázar, A.I. (eds.) EuroGP 2007. LNCS, vol. 4445, pp. 331–340. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71605-1_31
Di Chio, C., Poli, R., Langdon, W.B.: Evolution of force-generating equations for PSO using GP. In: Proceedings of the 2005 AI*IA Workshop on Evolutionary Computation (2005)
Dioşan, L., Oltean, M.: Evolving the structure of the particle swarm optimization algorithms. In: Gottlieb, J., Raidl, G.R. (eds.) EvoCOP 2006. LNCS, vol. 3906, pp. 25–36. Springer, Heidelberg (2006). https://doi.org/10.1007/11730095_3
Diosan, L., Oltean, M.: What else is the evolution of PSO telling us? J. Artif. Evol. Appl. 1, 1–12 (2008)
Dorigo, M., Birattari, M., Stutzle, T.: Ant colony optimization. IEEE Comput. Intell. Mag. 1, 28–39 (2006)
Erskine, A., Herrmann, J.M.: Critical Dynamics in Particle Swarm Optimization. CoRR (2014)
Kennedy, J., Eberhart, R.C.: Swarm Intelligence. Morgan Kaufmann Publishers Inc., San Francisco (2001)
Langdon, W.B., Poli, R.: Evolving problems to learn about particle swarm optimisers and other search algorithms. IEEE Trans. Evol. Comput. 11(5), 561–578 (2007)
Lyle, N.L., Howard, W.: The velocity dependence of aerodynamic drag: a primer for mathematicians. Math. Assoc. Am. 106, 127–135 (1999)
Moraglio, A., Krawiec, K.: Semantic genetic programming. In: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 603–627. ACM (2015)
Pawlak, T.P., Wieloch, B., Krawiec, K.: Review and comparative analysis of geometric semantic crossovers. Genet. Program. Evolvable Mach. 16, 351–386 (2015)
Poli, R., Di Chio, C., Langdon, W.B.: Exploring extended particle swarms: a genetic programming approach. In: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation, New York, USA, pp. 169–176 (2005)
Poli, R., Langdon, W.B., Holland, O.: Extending particle swarm optimisation via genetic programming. In: Keijzer, M., Tettamanzi, A., Collet, P., van Hemert, J., Tomassini, M. (eds.) EuroGP 2005. LNCS, vol. 3447, pp. 291–300. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31989-4_26
Runka, A.: Evolving an edge selection formula for ant colony optimization. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, pp. 1075–1082. ACM (2009)
Tavares, J., Pereira, F.B.: Evolving strategies for updating pheromone trails: a case study with the TSP. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6239, pp. 523–532. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15871-1_53
Vanneschi, L.: An introduction to geometric semantic genetic programming. In: Schütze, O., Trujillo, L., Legrand, P., Maldonado, Y. (eds.) NEO 2015. SCI, vol. 663, pp. 3–42. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-44003-3_1
Vanneschi, L., Bakurov, I., Castelli, M.: An initialization technique for geometric semantic GP based on demes evolution and despeciation. In: 2017 IEEE Congress on Evolutionary Computation, pp. 113–120 (2017)
Vanneschi, L., Silva, S., Castelli, M., Manzoni, L.: Geometric semantic genetic programming for real life applications. In: Riolo, R., Moore, J.H., Kotanchek, M. (eds.) Genetic Programming Theory and Practice XI. GEC, pp. 191–209. Springer, New York (2014). https://doi.org/10.1007/978-1-4939-0375-7_11
Wilke, D.N., Kok, S., Groenwold, A.A.: Comparison of linear and classical velocity update rules in particle swarm optimization: notes on scale and frame invariance. Int. J. Numer. Methods Eng. 70(8), 985–1008 (2007)
Wyatt, T.: Pheromones and Animal Behavior: Chemical Signals and Signatures. Cambridge University Press, Cambridge (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Bartashevich, P., Bakurov, I., Mostaghim, S., Vanneschi, L. (2018). PSO-Based Search Rules for Aerial Swarms Against Unexplored Vector Fields via Genetic Programming. In: Auger, A., Fonseca, C., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds) Parallel Problem Solving from Nature – PPSN XV. PPSN 2018. Lecture Notes in Computer Science(), vol 11101. Springer, Cham. https://doi.org/10.1007/978-3-319-99253-2_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-99253-2_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99252-5
Online ISBN: 978-3-319-99253-2
eBook Packages: Computer ScienceComputer Science (R0)