Algorithms

The following algorithms are implemented:

Particle Swarm Optimization

This implementation is the modified Particle Swarm Optimization ^[1] where it employs an inertia weight $\omega$ that controls convergence. This implementation uses linear decay for the inertia weight, which lowers the value of $\omega$ iteratively until it reaches the default minimum of $\omega = 0.4$.

The update rules for the particles are the following:

where $\beta_1$ and $\beta_2$ are uniformly distributed random numbers; $\varphi_1$ and $\varphi_2$ are the momentum coefficients; $p_i$ is the previous individual best position and $p_g$ is the privious global best position of the population; finally $\eta$ is the weight decay, currently implemented as

where $0.9$ is the original default value for $\omega$, $0.4$ is the default minimum as explained before and $n$ is the total number of iterations the algorithm is run. This guarantees that the weight decays linearly.

Simulated Annealing

Classic version

This implementation ^[2] uses the following logarithmic cooling schedule

to obtain a new temperature each iteration, starting from an initial temperature $T_0$.

This implementation searches possible candidate solutions by sampling from an approximate Boltzmann distribution, drawn as a normal distribution like so

where $g_{sol}(x)$ is an array filled with random values sampled from an approximate normal standard distribution with standard deviation $\sigma = \sqrt{T_{new}(t)}$ which corresponds to the previously found temperature. With this array, the new solution is computed as the previous (best) solution, $x_{sol}$, and adding the sampled array.

Finally, the Metropolis-Hastings algorithm is defined as

where $\Delta = f(x_{old}) - f(x_{sol})$.

Generalized version

This is the implementation developed by Tsallis & Stariolo ^[2] following Tsallis' theory on the generalization of the extensive entropy developed in Statistical Mechanics. This implementation has as special cases the classic version described above and the fast version developed by Szu & Hartley ^[3].

This implementation is quite interesting as it uses the Tsallis entropy defined ^[4] as

where $q$ is the so-called Tsallis parameter. By developing fundamental Statistical Mechanics theory and combining it with Gibbs' ensemble theory (I'm skipping all the development, it's quite extensive, pun intended), we arrive at a Metropolis-Hastings-like acceptance probability

there is a lot to unpack here, so we will go step by step.

Firstly, the cooling schedule is now defined as

where $T_0$ is the initial temperature.

Then we have the neighbor sampling distribution defined as

where $\Delta x = x_{sol} - x_{old}$, and $\Gamma$ denotes the Gamma function. As you can see, this distribution is very complicated, but in the original paper ^[2] Tsallis & Stariolo provide an algorithm where they approximate this distribution as a Lévy distribution. This algorithm is provided in the paper and it's the one used in this implementation.

With this, we update the neighbor solution as before $x_{sol} = x_{old} + g_{q_v}(\Delta x)$ and then we employ the Metropolis-Hastings algorithm.

Lastly, an important case is when $q_A < 0$ because the update rule is now undetermined, so we employ the following update rule

which means that we always reject the solution $x_{sol}$ whenever the proposition $[1+(q_a-1)\Delta / T_{new}(t)] < 0$ is true.

References