Repulsive Particle Swarm (RPSO)

The Binary Particle Swarm Optimization algorithm (described in [1]) is an optimization metaheuristic based in population. A set of potential solutions evolves to approach a convenient solution (or set of solutions) for a problem. The search is guided by the value of a real-valued fitness function.

In the standard PSO algorithm, each particle represents a solution to the problem. However, to resolve the ECC problem, we use a different approach (Michigan approach), in which the whole swarm represents the solution, and the social attraction in the standard PSO becomes "social repulsion" in the Repulsive Swarm. This modified version of the Binary PSO will be referred to hereafter as Repulsion Particle Swarm (RPSO).

The RPSO for the ECC problem solving is configured so each particle in the swarm represents one of the code words that will become part of the solution; each of the particles tries to maximize the Hamming distance to the closest particle in the swarm by separating from that particle. That is:

The following equation rules the particle velocity in RPSO, replacing the standard PSO movement equation:


\begin{displaymath}
v^{t+1}_{id} = w \cdot v^{t}_{id} + c_1 \cdot \psi_1 \cdo...
... c_2 \cdot \psi_2 \cdot rf_{i} \cdot d(p^{t}_{rd},x^{t}_{id})
\end{displaymath} (1)

where,

$v^{t}_{id}$: Component in dimension d of the $i^{th}$ particle velocity in iteration $t$.
$x^{t}_{id}$: Component in dimension d of the $i^{th}$ particle position in iteration $t$.
$c_1$ ,$c_2$: Constant weight factors.
$p_i$: best position achieved so long by particle $i$.
$p_{rd}$: position of the closest neighbor of particle $i$.
$\psi_1$ ,$\psi_2$: random factors in the [0,1] interval.
$\psi_3$: random factor in the [0,1] interval.
$w$: inertia weight.
$rf_{ir}$: adaptive repulsion factor between the particle $i$ and the repulsion centre (closest neighbor).

The velocity equation introduces the function $d(p^{t}_{rd},x^{t}_{id})$ that takes two binary values as parameters. This function returns:

After velocity for the particle is determined, its position is calculated using the following equation:


\begin{displaymath}
x^{t+1}_{id} = \left\{
\begin{array}{ll}
1 & if \psi_3 <...
...{-v^{t+1}_{id}}} \\
0 & otherwise \\
\end{array}
\right.
\end{displaymath} (2)


The position equation implies that a binary PSO without individual and social influences ($c_1=c_2=0.0$) would still perform a random search on the space (the position in each dimension would have a chance of 0.5 of being either a zero or one).

The repulsion factor $rf_{ir}$ is required to weight the intensity of the repulsion force depending on the Hamming distance to the closest particle. Currently we use a linear expresion for this term, that takes negative values (which are interpreted as the force becoming attractive) in cases where distance to the closer particle is greater than the optimum.


\begin{displaymath}
rf_{ip} = \frac{1}{dim} \cdot \left( d_{opt} - H(i,r) \right)
\end{displaymath} (3)

$H(i,r)$: Hamming distance between the particle $i$ and the repulsion center $r$
$dim$: Particle dimension
$d_{opt}$: Optimum hamming distance between particles