Benchmarking solver implementations in EvoLP.jl v1.1
Comparing against old implementations (v1.0)
This post showcases how the new and old implementation of the algorithms compare in terms of runtime.
We perform a benchmark for 60 seconds on both versions of each algorithm and present the results. The old version of each algorithm is provided (which you can compare to by looking at previous commits in EvoLP.jl [1]), while the new version is loaded directly from EvoLP.jl 1.1 [2].
You can also read this entry as a Jupyter Notebook HTML [3], which presents nicer, coloured graphics provided by the BenchmarkTools.jl package [4]. The .ipynb
file is also available [5].
using Statistics
using EvoLP
using BenchmarkTools
GA
For this example we will use:
- Rosenbrock function with 1 ms sleep
- Random normal generator
- Rank based selection
- Interpolation crossover with $\lambda=0.5$
- Gaussian mutation with $\sigma = 0.05$
- No logbook
f(x) = begin
sleep(0.001)
return rosenbrock(x)
end
f (generic function with 1 method)
pop_size = 100
population = normal_rand_vector_pop(pop_size, [0, 0], [1 0; 0 1])
first(population, 3)
3-element Vector{Vector{Float64}}:
[1.0517614595972073, 1.8402213160040617]
[-0.36639692426819936, 0.8691721709188464]
[-2.403222766197478, 0.5402756188420645]
S = RankBasedSelectionGenerational()
C = InterpolationCrossover(0.5)
M = GaussianMutation(0.05)
GaussianMutation(0.05)
Original
function oldGA(
f::Function,
pop::AbstractVector,
k_max::Integer,
S::EvoLP.SelectionMethod,
C::EvoLP.CrossoverMethod,
M::EvoLP.MutationMethod
)
n = length(pop)
for _ in 1:k_max
parents = select(S, f.(pop)) # O(k_max * n)
offspring = [cross(C, pop[p[1]], pop[p[2]]) for p in parents]
pop .= mutate.(Ref(M), offspring) # whole population is replaced
end
# x, fx
best, best_i = findmin(f, pop) # O(n)
n_evals = k_max * n + n
result = Result(best, pop[best_i], pop, k_max, n_evals)
return result
end
oldGA (generic function with 1 method)
@benchmark oldGA(f, population, 10, S, C, M) seconds=60
BenchmarkTools.Trial: 25 samples with 1 evaluation.
Range (min … max): 2.375 s … 2.430 s ┊ GC (min … max): 0.00% … 0.00%
Time (median): 2.412 s ┊ GC (median): 0.00%
Time (mean ± σ): 2.407 s ± 14.472 ms ┊ GC (mean ± σ): 0.02% ± 0.06%
█
▅▁▁▁▁▁▁▅▁▁▅▁▁▁▅▁▅▁▁▁▁▁▁▅▁▁▅▁▁█▁▁▁▁▁▁▁▅▁██▁█▅▅▁▁▁▅▅▁▁▁▅▁▁▅ ▁
2.37 s Histogram: frequency by time 2.43 s <
Memory estimate: 4.20 MiB, allocs estimate: 17782.
Optimised
Here we perform the same benchmark, this time on the optimised GA in EvoLP 1.1:
@benchmark GA(f, population, 10, S, C, M) seconds=60
BenchmarkTools.Trial: 28 samples with 1 evaluation.
Range (min … max): 2.160 s … 2.200 s ┊ GC (min … max): 0.00% … 0.00%
Time (median): 2.185 s ┊ GC (median): 0.00%
Time (mean ± σ): 2.185 s ± 10.243 ms ┊ GC (mean ± σ): 0.02% ± 0.08%
▁ ▁█ ▁ ▁ ▁ ▁ ▁ ▁▁▁▁▁▁▁▁▁▁ ▁ ██ ▁▁ █
█▁▁▁▁▁▁▁▁▁▁▁▁██▁▁█▁█▁▁█▁▁█▁▁▁█▁██████████▁▁▁█▁▁██▁▁██▁▁▁█ ▁
2.16 s Histogram: frequency by time 2.2 s <
Memory estimate: 4.19 MiB, allocs estimate: 17264.
PSO
For this example we will use:
- Same function (Rosenbrock function with 1 ms sleep)
- Random normal Particle Generator
- The new generator should work for both new and old versions of the solver
- No logbook
population = normal_rand_particle_pop(pop_size, [0, 0], [1 0; 0 1])
first(population, 3)
3-element Vector{Particle}:
Particle([0.21505942279789356, -0.41108445112773156], [0.0, 0.0], Inf,
[0.21505942279789356, -0.41108445112773156], Inf)
Particle([-0.6592316786828291, 0.2805535941858653], [0.0, 0.0], Inf,
[-0.6592316786828291, 0.2805535941858653], Inf)
Particle([0.22781682502062509, 0.16678151290193638], [0.0, 0.0], Inf,
[0.22781682502062509, 0.16678151290193638], Inf)
Original
function OldPSO(
f::Function, population::Vector{EvoLP.Particle}, k_max::Integer;
w=1, c1=1, c2=1
)
d = length(population[1].x)
x_best, y_best = copy(population[1].x_best), Inf
# evaluation loop
for P in population
y = f(P.x) # O(pop)
if y < y_best
x_best[:] = P.x
y_best = y
end
end
for _ in 1:k_max
for P in population
r1, r2 = rand(d), rand(d)
P.x += P.v
P.v = w*P.v + c1*r1 .* (P.x_best - P.x) + c2*r2 .* (x_best - P.x)
y = f(P.x) # O(k_max * pop)
if y < y_best
x_best[:] = P.x
y_best = y
end
if y < f(P.x_best) # O(k_max * pop)
P.x_best[:] = P.x
end
end
end
best_i = argmin([f(P.x_best) for P in population])
best = population[best_i]
n_evals = 2 * length(population) + 2 * k_max * length(population) + 1
result = Result(f(best.x_best), best, population, k_max, n_evals)
return result
end
OldPSO (generic function with 1 method)
@benchmark OldPSO(f, population, 10) seconds=60
BenchmarkTools.Trial: 13 samples with 1 evaluation.
Range (min … max): 4.960 s … 4.989 s ┊ GC (min … max): 0.00% … 0.00%
Time (median): 4.970 s ┊ GC (median): 0.00%
Time (mean ± σ): 4.972 s ± 10.978 ms ┊ GC (mean ± σ): 0.00% ± 0.00%
█
█▇▁▁▁▁▇▁▁▇▁▁▁▁▁▁▁▁▁▁▇▁▁▁▁▁▁▁▁▇▁▁▁▇▁▁▁▁▁▁▁▁▁▁▁▁▇▇▁▁▁▇▁▁▁▁▇ ▁
4.96 s Histogram: frequency by time 4.99 s <
Memory estimate: 1.33 MiB, allocs estimate: 28419.
Optimised
Here is the new version, which takes half the time:
@benchmark PSO(f, population, 10) seconds=60
BenchmarkTools.Trial: 25 samples with 1 evaluation.
Range (min … max): 2.409 s … 2.465 s ┊ GC (min … max): 0.00% … 0.00%
Time (median): 2.436 s ┊ GC (median): 0.00%
Time (mean ± σ): 2.439 s ± 14.486 ms ┊ GC (mean ± σ): 0.00% ± 0.00%
▁ ▁ ▁▁▁ █▁ ▁▁█ ▁ ▁▁█ ▁ ▁ █▁▁ ▁▁
█▁▁▁▁▁▁▁▁▁▁▁█▁███▁▁██▁▁███▁█▁▁▁▁▁███▁█▁▁▁█▁▁▁▁███▁▁▁▁▁▁██ ▁
2.41 s Histogram: frequency by time 2.47 s <
Memory estimate: 1.14 MiB, allocs estimate: 21705.
1 + 1 EA
For this problem we will use:
- OneMax problem with a 1ms delay
- Random binary individual of length 100
- Bitwise mutation of 1%
- No logbook
sleep_onemax(x) = begin
sleep(0.001)
return -onemax(x)
end
sleep_onemax (generic function with 1 method)
population = binary_vector_pop(1, 100)[1]
M = BitwiseMutation(0.001)
BitwiseMutation(0.001)
Original
function oldoneplusone(
f::Function, ind::AbstractVector, k_max::Integer, M::EvoLP.MutationMethod
)
for _ in 1:k_max
c = mutate(M, ind)
if f(c) <= f(ind) # O(2 * k_max)
ind = c
end
end
f_ind = f(ind) # O(1)
n_evals = 2 * k_max + 1
result = Result(f_ind, ind, [ind], k_max, n_evals)
return result
end
oldoneplusone (generic function with 1 method)
@benchmark oldoneplusone(sleep_onemax, population, 10, M) seconds=60
BenchmarkTools.Trial: 1302 samples with 1 evaluation.
Range (min … max): 43.003 ms … 48.687 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 46.163 ms ┊ GC (median): 0.00%
Time (mean ± σ): 46.060 ms ± 888.528 μs ┊ GC (mean ± σ): 0.00% ± 0.00%
▂ ▃▄▁▂▅▅▂▄▆▄▇▇▇█▅▄▅▁▂▁▁
▂▁▂▃▂▃▂▂▁▃▃▃▃▃▄▃▄▅▅▄▆▅▇█▇▆████████████████████████▆▅▆▄▅▃▂▃▃▃ ▅
43 ms Histogram: frequency by time 48 ms <
Memory estimate: 20.25 KiB, allocs estimate: 1117.
Optimised
Here is the optimised version. Improvement is negligible since it’s just 1 fewer call. In very expensive computations, it could help a little bit.
@benchmark oneplusone(sleep_onemax, population, 10, M) seconds=60
BenchmarkTools.Trial: 1369 samples with 1 evaluation.
Range (min … max): 41.086 ms … 45.970 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 43.890 ms ┊ GC (median): 0.00%
Time (mean ± σ): 43.794 ms ± 803.492 μs ┊ GC (mean ± σ): 0.00% ± 0.00%
▁▁▁▂ ▂▃▃▃▄▃▆▂▄▆▅█▅██▄▆▂▃
▃▃▁▂▁▁▃▃▂▃▂▃▅▃▄▄▃▃▄▆▅▄▇██████████████████████████▆▆▅▆▅▄▄▄▄▂▃ ▅
41.1 ms Histogram: frequency by time 45.5 ms <
Memory estimate: 20.11 KiB, allocs estimate: 1112.
Conclusion
We benchmarked and compared the new implementation of the algorithms provided in EvoLP 1.1 against their previous version. There is a noticeable reduction in runtime for PSO. For the GA and 1+1 EA, the reduction is little but can still become significant if doing expensive computations in the objective function.
References
[1] Browse code of EvoLP.jl 1.0
[2] Browse code of EvoLP.jl 1.1
[3] See this notebook in HTML
[4] BenchmarkTools.jl
[5] Download the Jupyter Notebook of this post