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

[nirmalsnair]

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).