Large variation in performances between PSO variants for high-dimensional problems

For problems with large number of variables (>1000), there is a significant variation in the performance of PSO variants in terms of run-time and solution quality. The code given below calculates the time taken by a PSO variant on a toy problem excluding the time taken for all fitness evaluations.

```
import time
import timeit
import numpy as np
import pygmo as pg

# PSO parameters
n_pop = 10
n_gen = 10000
n_dim = 5000
pso_variant = 1

lb = list(np.zeros(n_dim))
ub = list(np.ones(n_dim))

class sphere_function:
def fitness(self, x):
return [np.sum(x*x)]
def get_bounds(self):
return (lb, ub)

if __name__ == '__main__':
# Calculate time taken for whole optimisation
start_time = time.time()
prob = pg.problem(sphere_function())
algo = pg.algorithm(pg.pso(gen = n_gen, variant = pso_variant))
pop = pg.population(prob, n_pop)
pop = algo.evolve(pop)
total_time = time.time() - start_time

# Calculate time taken for a single fitness evaluation
x = np.random.randn(n_dim)
fitness_time = timeit.timeit(stmt='np.sum(x*x)', globals=globals())
fitness_time = fitness_time / 1000000 # convert microseconds to seconds

# Calculate time taken by all fitness evaluations
fevals_time = fitness_time * n_pop * n_gen
fevals_percent = fevals_time / total_time * 100

# Calculate time taken by PSO excluding the fitness evaluations
pso_time = total_time - fevals_time
pso_percent = pso_time / total_time * 100

print('Best fitness = {:.2f}'.format(pop.champion_f[0]))
print('fevals time = {:.2f} s'.format(fevals_time))
print('PSO time = {:.2f} s'.format(pso_time))
print('Total time = {:.2f} s'.format(total_time))
print('fevals percent = {:.2f} %'.format(fevals_percent))
print('PSO percent = {:.2f} %'.format(pso_percent))
```

Using different values for `n_pop`, `n_gen`, `n_dim`, and `pso_variant`, I got the following results:
n_pop | n_gen | n_dim | pso_ vrnt | Best fitness | fevals time (percent) | PSO time (percent) | Total time
-|-|-|-|-:|-|-|-:
10 | 10000 | 5000 | 1 | 1463.88 | 0.60 s
(2.17 %) | 27.15 s (97.83 %) | 27.75 s
10 | 10000 | 5000 | 2 | 1540.88 | 0.60 s
(3.90 %) | 15.01 s (96.10 %) | 15.62 s
10 | 10000 | 5000 | 3 | 1072.19 | 0.60 s
(24.09 %) | 1.89 s
(75.91 %) | 2.50 s
10 | 10000 | 5000 | 4 | 1090.89 | 0.60 s
(20.57 %) | 2.33 s
(79.43 %) | 2.94 s
10 | 10000 | 5000 | 5 | 311.00 | 0.60 s
(2.23 %) | 26.66 s (97.77 %) | 27.26 s
10 | 10000 | 5000 | 6 | 139.62 | 0.60 s
(1.15 %) | 54.03 s (98.85 %) | 54.65 s

n_pop | n_gen | n_dim | pso_ vrnt | Best fitness | fevals time (percent) | PSO time (percent) | Total time
-|-|-|-|-:|-|-|-:
1000 | 100 | 5000 | 1 | 1440.17 | 0.60 s
(2.14 %) | 28.08 s (97.86 %) | 28.69 s
1000 | 100 | 5000 | 2 | 1470.63 | 0.60 s
(3.67 %) | 15.79 s (96.33 %) | 16.40 s
1000 | 100 | 5000 | 3 | 1242.72 | 0.60 s
(17.02 %) | 2.94 s
(82.98 %) | 3.54 s
1000 | 100 | 5000 | 4 | 1244.08 | 0.60 s
(15.69 %) | 3.32 s
(84.31 %) | 3.94 s
1000 | 100 | 5000 | 5 | 1327.64 | 0.60 s
(2.22 %) | 27.77 s (97.78 %) | 28.40 s
1000 | 100 | 5000 | 6 | 1249.19 | 0.60 s
(1.08 %) | 55.25 s (98.92 %) | 55.85 s

n_pop | n_gen | n_dim | pso_ vrnt | Best fitness | fevals time (percent) | PSO time (percent) | Total time
-|-|-|-|-:|-|-|-:
10 | 10000 | 100 | 1 | 1.00 | 0.30 s
(26.20 %) | 0.85 s
73.80 % | 1.15 s
10 | 10000 | 100 | 2 | 2.00 | 0.30 s
(32.34 %) | 0.63 s
67.66 % | 0.93 s
10 | 10000 | 100 | 3 | 0.00 | 0.30 s
(46.68 %) | 0.35 s
53.32 % | 0.65 s
10 | 10000 | 100 | 4 | 0.00 | 0.30 s
(46.93 %) | 0.34 s
53.07 % | 0.65 s
10 | 10000 | 100 | 5 | 0.00 | 0.30 s
(26.03 %) | 0.86 s
73.97 % | 1.16 s
10 | 10000 | 100 | 6 | 0.00 | 0.30 s
(17.94 %) | 1.39 s
82.06 % | 1.70 s

As you can see, the time taken by PSO variants 1,2,5, and 6 are significantly higher than variants 3 and 4 when number of optimization variables is high (Tables 1 and 2). For low-dimensional problems, the overhead is negligible (Table 3).

In addition, the solution quality of variant 6 in Table 1 is significantly better than the rest but has the worst run-time (20 times than the fastest variant).