5.8 Particle swarm optimization (PSO) code

In the field of crystal and cluster structure prediction, several approaches proved to be successful for small systems. Particle Swarm Optimization (PSO), pioneered in this field by Boldyrev ²⁹, is a special class of evolutionary algorithms where a population (swarm) of candidate solutions (called “particles”) is moved in the search space according to a few simple formulae. The movements of the particles are guided by their own best known position in the search space as well as the entire swarm’s best known position. Initially, the coordinates $\chi$ and ’velocities’ $\upsilon$ of the particles are generated randomly. Then at every step, the positions and velocities are updated according to the formulae:

$\begin{equation} \label{eq:pso} \begin{aligned} \upsilon ’_{i} & = \omega \cdot \upsilon _{i} + \varphi _{p} \cdot r_{p} \cdot (p_{i} - \chi _{i}) + \varphi _{g} \cdot r_{g} \cdot (g - \chi _{i}),\\ \chi ’_{i} & = \chi _{i} + \upsilon ’_{i}. \end{aligned} \end{equation}$

(8)

Here $\omega$ , $\varphi _{p}$ and $\varphi _{g}$ are weight factors that control the behavior and efficiency of the PSO algorithm; $r_{p}$ and $r_{g}$ are random numbers in the [0; 1] range generated separately for every particle at every step; $p_{i}$ is the best known position of particle $i$ and $g$ is the best known position of the entire swarm.

Such an algorithm, despite its simplicity, can work ²⁹. Key points to improve with respect to previous implementations ^{29; 30} are (1) metric of the search space (it is not trivial to map crystal structures uniquely onto a coordinate system) and (2) ways to evolve structures in PSO, i.e. variation operators.

$\includegraphics[scale=0.3]{pic/PSO.png}$

Figure 14: Illustration of PSO-USPEX hybrid algorithm for the population of three individuals (marked by diamonds, squares and circles) after 10 generations. Best position for each particle is marked by an enlarged symbol. The best structure is the big square. The structure shown by circle can be either mutated, create a child with its historically best position (large circle) or the best position of entire population (large square) using heredity operator with probabilities $P_{m}$ , $P_{p}$ and $P_{g}$ , respectively.

Evolving the particles by determining the speed $\upsilon _{i}$ (8) directly from coordinates of the atoms and cell parameters of two structures (as in Ref. ³⁰) cannot be productive. Our solution is to use fingerprint distances ¹⁷ as the most natural metric for the energy landscape, and variation operators of USPEX for evolving the ’PSO particles’ (i.e. structures) as the most efficient unbiased ways to evolve a population of structures. Namely, the particle is either mutated (to imitate a random move), or participates in heredity with its best known position or in heredity with the best known population position (to imitate PSO moves in the direction of these positions). Instead of applying at each step all moves with some weights (see Eq. 8), we apply them one at a time with probabilities described by formulae:

$\begin{equation} \label{eq:pso2} \begin{aligned} P_{m} = \frac{\omega }{\Sigma };\qquad & P_{p} = \frac{\varphi _{p} \cdot r_{p} \cdot D_{p}}{\Sigma };\qquad P_{g} = \frac{\varphi _{g} \cdot r_{g} \cdot D_{g}}{\Sigma };\\ & \Sigma = \omega + \varphi _{p} \cdot r_{p} \cdot D_{p} + \varphi _{g} \cdot r_{g} \cdot D_{g}, \end{aligned} \end{equation}$

(11)

where $D_{p}$ is a fingerprint distance between current and best position of a particle, while $D_{g}$ is a fingerprint distance between the current position of the particle and best known position of the entire population. Our tests, performed on a few diverse systems, show that this approach (which we call “cor-PSO”, i.e. corrected PSO) is relatively successful and works better than previous versions of PSO, but still cannot compete with the USPEX algorithm ^{2; 31} for success rate or efficiency.

The following variables are unique for calculationMethod=PSO:

$\triangleright$ variable blue PSO_softMut

Meaning: Weight of softmutation ( $\omega$ in eq. 11).

Default: 1

Format:

1 : PSO_softMut

$\triangleright$ variable blue PSO_BestStruc

Meaning: Weight of heredity with the best position of the same PSO particle ( $\varphi _{p}$ in eq. 11).

Default: 1

Format:

1 : PSO_BestStruc

$\triangleright$ variable blue PSO_BestEver

Meaning: Weight of heredity with the globally best PSO particle ( $\varphi _{g}$ in eq. 11).

Default: 1

Format:

1 : PSO_BestEver