Particle Swarm Optimization with Moving Particles on Scale-Free Networks (MP-PSO)

What is PSO?

Particle swarm optimization (PSO), presented by Kennedy and Eberhart, is a widespread optimization algorithm dealing with complex practical matters in many fields.

In PSO, a flock of particles fly in the searching space during the optimization process and try to find out the optimal solution cooperatively. Each particle has its certain position in the space, which is evaluated by fitness value. During iterations, the velocity and position of a particle are updated according to the best position discovered before by both itself and other interacted particles. PSO has attracted many researchers since its appearance, and many variants of PSO have been proposed to better balance exploration and exploitation.

What is MP-PSO?

In most of the variants, particles are with fixed interaction patterns during the optimization process. Particles can only learn from the neighbors on the static topology structure, which limits the information interaction in the swarm.

However, in PSO with moving particles on scale-free networks (MP-PSO), there are two networks, base network and swarm network. The base network is a static scale-free network, and the swarm network is consists of particles and edges between them. Figures below show their relationship.

Red points are particles and bold edges are edges in the swarm network.

During iterations, particles in MP-PSO are consistently restricted in a static scale-free base network, but are partly free to adaptively change the swarm network with the moving strategy during iterations, which is the key point of MP-PSO.

Firstly, we define a time counter for each particle, which denotes the number of iterations that the best position of this particle ceases improving. If the time counter reaches a preset threshold, the particle is called qualified. A qualified particle can move to a vacant neighbor node if there is at least one vacant position in its base network neighbors, carrying its position and velocity information as well as history information. Consequently, the structure of swarm network is changed. The figure below briefly shows how the moving strategy works.

The particle changes its topology position based on the base network, according to the arrow. While the base network is static, the information source of interaction changes after this iteration.

How MP-PSO performs?

In experiments, MP-PSO is compared with other 5 PSO variants on 16 unimoadal and (rotated) multimodal benchmark functions. MP-PSO can obtain best results on 6 of 11 multimodal and rotated multimodal problems (including 3 multimodal functions and 3 rotated multimodal functions), remarkably outperforming other algorithms.

Experiments on other aspects, including convergence speed and success rate, also show its outstanding performance.

Why MP-PSO performs well?

One of the most important reasons is MP-PSO balance exporation and exploitation. Our experiments show thatduring iterarions, the average degree in swarm network grows, the number of connect components drops and the number of moving particles increases at the end of the optimization process, which indicates it does not concentrate blindly, which may induce premature. Actually, this increasing number of moving particles presents some possibilities of exploration.

The change of average degree in swarm network, the number of connect components and the number of moving particles with iterations.

Microscopically, the swarm network converges rapidly to one single component once the particle moving is first permitted. And during the later period of optimization process, the giant component still exists, but more particles occasionally separate from the giant component and explore by themselves, making the swarm explore the searching space and may find more promising regions. Therefore, particles located on hub nodes are always within the giant component, while particles separating from the giant component are mainly located on non-hub nodes.

Snapshots during an optimization process. The size of the colored nodes is positively correlated to the degree in swarm network, and the different colors represent distinct components in the swarm network (red components denote the giant components).

Further we investigate the effects of the node degree on particle moving behaviors. We find out that nodes with larger node degree, the hub nodes, are more possibly to be occupied, which is reasonable. Besides, the move desire decreases with the increase of the node degree, showing that particles on hub nodes are more inert to move. Conversely, the move frequency shows a just opposite trend.

The change of occupied frequency, move desire and move frequency during optimization.

We can conclude that moving behaviors of particles on hub and non-hub nodes are quite different. For a hub particle, the move desire and the move frequency are almost the same, indicating that it can move once it wants to move. However, particles on non-hub nodes present strong move desires but much lower move frequency. For a non-hub particle, although the move desire can be very strong, it cannot move if there does not exist a vacant node in its neighbor set. Furthermore, even if a non-hub particle is allowed to move, since the neighboring hub nodes are always occupied, it will possibly leave the giant component to explore by itself.

As a result, the particles on hub nodes take on the main responsibility of the optimization, while particles on non-hub nodes guarantee an appropriate exploration ability of the swarm during the eolution. The cooperation between particles on hub and non-hub nodes achieves an overall better performance.

How can MP-PSO solve real problems?

We use MP-PSO to solve the arrival sequencing and scheduling (ASS) problem, and also get relative good results. The detail of the experiment can be found in the paper.

Resources:

Original paper on IEEE Transactions on Network Science and Engineering