If you try to search for “PSO” abbreviation in wiki you may find Pacific Symphony Orchestra or Phase-shift oscillator. However, my project at HZB is about neither music nor electricity, but mathematics. For almost a month here I have been working on an algorithm called Particle Swarm Optimization method and I would like you to have some impression of it.

**Optimization**

Actually, the definition of optimization problem is quite simple. One has a function of n-variables f(x1, …, xn) and seeks to find such values of variables that give minimum to the function. However, the solution is not that simple, because in general you cannot use calculus, since the function might be not smooth. That is why we have to look for another approach and here we come to so called Swarm Intelligence (SI) that was originally inspired by social behavior of animals.

**PSO method**

Imagine how a swarm of bees, for example, would like to solve our optimization problem. Let us assume it is flying in 3-D space and the function represents the density of lilacs in the field. The one who is familiar with biology would say that every honeybee flies around the field remembering its own best position and communicating or sharing it with its sisters through odor cues and dancing. Finally, the optimal location is defined through all these collective work, and everyone flies there. More or less the same technique is applied in Particle swarm method. The basic algorithm works by having a population (swarm) of candidate solutions or particles. Each of them moves around the search space guided by two factors. The first is its personal best position during the previous search. The second is the best known position throughout the swarm. Thereby at some moment there appears a general tendency towards the optimum and the swarm converges on solution.

**Why BESSY?**

You might wonder what all this has to do with accelerator physics and BESSY II. Actually, a synchrotron also needs some optimization and my work here is not only limited with theoretical research of Swarm Intelligence. During the internship I am also implementing the algorithm on python for our colleagues working at BESSY II. Besides, this SI techniques can be extended to multi-objective cases, which means that we can optimize several objectives at once. In particular, it might be applied in accelerators like BESSY II to increase both current and lifetime of the beam.

In conclusion, I would like to add that SI methods may also have applications in other fields like crowd control and robotics. Meantime, it is not a big leap of imagination to picture artificial bees searching for pollen in a field to supply you with pure honey. And you can be sure that they will not bite you.

Very interesting and well explained!

Thank you for a nice workshop, Antonia! I am really grateful for your quick feedback and help)

Thank you, Ilyas! I find your explanation very neat and informative. I wonder how quickly does PS method converge and how hard are the compuations. I meant here what can you say about computational complexity of PS.

Thank you, Dima! That is a tough question, because it really depends on version of the algorithm, but for the basic one we can say that it is O(swarmsize*n + swarmsize*F_cost) for every iteration, where n – is dimension of the problem, F_cost – is computation cost of function. Seems quite fast, but one should take into account that in applications F_cost may play a key role and we have to reduce the number of function computations by any means.

What may be really interesting for you in Swarm Intelligence is the way how particles interact with each other, forming so called different topologies. For example, a particle may receive an information from all particles, but may compare its global best only with its closest neighbours. Changing the topologies you significantly affect the behavior of the swarm and the convergence rate.

thanks for that simple explanation, I always find “animal” algorithms interesting to study. Can you explain that contour graph on the right?

Thank you for your question, Alaa. On this contour graph yellow crosses represent the particles (or “bees”) and the vectors – their current velocities. A color bar on the right helps to determine a value of each contour line.

It is only the beginning of the algorithm and particles are quite evenly distributed in space, but you can see a general tendency towards the global minimum in the center.