# Algorithms

## BCA

BilevelHeuristics.BCAType
BCA(;N, n, K, η_max, resize_population)

Bilevel Centers Algorithm uses two nested ECA.

Parameters

• N Upper level population size
• n Lower level population size.
• K Num. of solutions to generate centers.
• η_max Step size.

Usage

Upper level problem: F(x,y) with x as the upper-level vector.

julia> F(x, y) = sum(x.^2) + sum(y.^2)
F (generic function with 1 method)

julia> bounds_ul = [-ones(5) ones(5)];


Lower level problem: f(x, y) with y as the lower-level vector.

julia> f(x, y) = sum((x - y).^2) + y[1]^2
f (generic function with 1 method)

julia> bounds_ll = [-ones(5) ones(5)];


Approximate solution.

julia> res = optimize(F, f, bounds_ul, bounds_ll, BCA())
+=========== RESULT ==========+
iteration: 108
minimum:
F: 2.7438e-09
f: 3.94874e-11
minimizer:
x: [-8.80414308649828e-6, 2.1574853199308744e-5, -1.5550602817418899e-6, 1.9314104453973864e-5, 2.1709393089480435e-5]
y: [-4.907639660543081e-6, 2.173986368018122e-5, -1.8133242873785074e-6, 1.9658451600356374e-5, 2.1624363965042988e-5]
F calls: 2503
f calls: 6272518
Message: Stopped due UL function evaluations limitations.
total time: 14.8592 s
+============================+

julia> x, y = minimizer(res);

julia> x
5-element Vector{Float64}:
-8.80414308649828e-6
2.1574853199308744e-5
-1.5550602817418899e-6
1.9314104453973864e-5
2.1709393089480435e-5

julia> y
5-element Vector{Float64}:
-4.907639660543081e-6
2.173986368018122e-5
-1.8133242873785074e-6
1.9658451600356374e-5
2.1624363965042988e-5

julia> Fmin, fmin = minimum(res)
(2.7438003987697017e-9, 3.9487399650845625e-11)

Citation

Mejía-de-Dios, J. A., & Mezura-Montes, E. (2018, November). A physics-inspired algorithm for bilevel optimization. In 2018 IEEE International Autumn Meeting on Power, Electronics and Computing (ROPEC) (pp. 1-6). IEEE.

source

## QBCA

BilevelHeuristics.QBCAType
QBCA(;N, K, η_ul_max, η_ll_max, α, β, autodiff)

Quasi-newton BCA uses ECA (upper-level) and BFGS (lower-level).

Parameters

• N Upper level population size
• K Num. of solutions to generate centers.
• η_ul_max UL step size.
• η_ll_max LL step size.
• α, β Parameters for the Tikhnonov regularization.
• autodiff=:finite Used to approximate LL derivates.

Usage

Upper level problem: F(x,y) with x as the upper-level vector.

julia> F(x, y) = sum(x.^2) + sum(y.^2)
F (generic function with 1 method)

julia> bounds_ul = [-ones(5) ones(5)];


Lower level problem: f(x, y) with y as the lower-level vector.

julia> f(x, y) = sum((x - y).^2) + y[1]^2
f (generic function with 1 method)

julia> bounds_ll = [-ones(5) ones(5)];


Approximate solution.

julia> res = optimize(F, f, bounds_ul, bounds_ll, QBCA())
+=========== RESULT ==========+
iteration: 71
minimum:
F: 1.20277e-06
f: 1.8618e-08
minimizer:
x: [-0.00019296602928680934, -0.00031720504506331244, 0.00047217689470620765, 0.00014459596611862214, 0.00048345619641040644]
y: [-9.647494056567316e-5, -0.0003171519406858993, 0.00047209784939209284, 0.00014457176048263256, 0.0004833752613377002]
F calls: 2130
f calls: 366743
Message: Stopped due UL small fitness variance.
total time: 7.7909 s
+============================+

julia> x, y = minimizer(res);

julia> x
5-element Vector{Float64}:
-0.00019296602928680934
-0.00031720504506331244
0.00047217689470620765
0.00014459596611862214
0.00048345619641040644

julia> y
5-element Vector{Float64}:
-9.647494056567316e-5
-0.0003171519406858993
0.00047209784939209284
0.00014457176048263256
0.0004833752613377002

julia> Fmin, fmin = minimum(res)
(1.2027656204730873e-6, 1.8617960564375732e-8)

Citation

Mejía-de-Dios, J. A., & Mezura-Montes, E. (2019, June). A metaheuristic for bilevel optimization using tykhonov regularization and the quasi-newton method. In 2019 IEEE Congress on Evolutionary Computation (CEC) (pp. 3134-3141). IEEE.

source

## QBCA2

BilevelHeuristics.QBCA2Type
QBCA2(;N, K, η_max, δ1, δ2, ε1, ε2, λ, t_reevaluate)

Quasi-newton BCA uses ECA (upper-level) and BFGS (lower-level).

Parameters

• N Upper level population size
• K Num. of solutions to generate centers.
• η_max Step size
• δ1, δ2, ε1 ε2 Parameters for conditions to avoid pseudo-feasible solutions.

Usage

Upper level problem: F(x,y) with x as the upper-level vector.

julia> F(x, y) = sum(x.^2) + sum(y.^2)
F (generic function with 1 method)

julia> bounds_ul = [-ones(5) ones(5)];


Lower level problem: f(x, y) with y as the lower-level vector.

julia> f(x, y) = sum((x - y).^2) + y[1]^2
f (generic function with 1 method)

julia> bounds_ll = [-ones(5) ones(5)];


Approximate solution.

julia> res = optimize(F, f, bounds_ul, bounds_ll, QBCA2())
+=========== RESULT ==========+
iteration: 59
minimum:
F: 3.95536e-07
f: 9.2123e-11
minimizer:
x: [-1.3573722472608445e-5, -0.00012074600446520904, -0.00035025471067487137, -0.0002315301345354928, -8.239473503719106e-5]
y: [-6.786860530140986e-6, -0.00012074599672993571, -0.00035025467380887673, -0.00023153010993486042, -8.239472729799499e-5]
F calls: 1775
f calls: 299157
Message: Stopped due UL small fitness variance.
total time: 5.6968 s
+============================+

julia> x, y = minimizer(res);

julia> x
5-element Vector{Float64}:
-1.3573722472608445e-5
-0.00012074600446520904
-0.00035025471067487137
-0.0002315301345354928
-8.239473503719106e-5

julia> y
5-element Vector{Float64}:
-6.786860530140986e-6
-0.00012074599672993571
-0.00035025467380887673
-0.00023153010993486042
-8.239472729799499e-5

julia> Fmin, fmin = minimum(res)
(3.9553637806596925e-7, 9.212297088378278e-11)

Citation

Mejía-de-Dios, J. A., Mezura-Montes, E., & Toledo-Hernández, P. (2022). Pseudo-feasible solutions in evolutionary bilevel optimization: Test problems and performance assessment. Applied Mathematics and Computation, 412, 126577.

source

## SABO

BilevelHeuristics.SABOType
SABO(;N, K, η_max, δ1, δ2, ε1, ε2, λ, t_reevaluate)

Surrogate Algorithm for Bilevel Optimization.

Parameters

• N Upper level population size
• K Num. of solutions to generate centers.
• η_max Step size
• δ1, δ2, ε1 ε2 Parameters for conditions to avoid pseudo-feasible solutions.
• λ Parameter for the surrogate model.
• t_reevaluate Indicates how many iterations is reevaluated the lower level.

Usage

Upper level problem: F(x,y) with x as the upper-level vector.

julia> F(x, y) = sum(x.^2) + sum(y.^2)
F (generic function with 1 method)

julia> bounds_ul = [-ones(5) ones(5)];


Lower level problem: f(x, y) with y as the lower-level vector.

julia> f(x, y) = sum((x - y).^2) + y[1]^2
f (generic function with 1 method)

julia> bounds_ll = [-ones(5) ones(5)];


Approximate solution.

julia> using Metaheuristics

julia> res = optimize(F, f, bounds_ul, bounds_ll, SABO(options_ul=Options(iterations=12)))
+=========== RESULT ==========+
iteration: 12
minimum:
F: 0.00472028
f: 0.000641749
minimizer:
x: [-0.03582594991950816, 0.018051141584692676, -0.030154879329873152, -0.017337812299467736, 0.004710839249040477]
y: [-0.017912974972476316, 0.018051141514328663, -0.030154879385452187, -0.017337812317661405, 0.004710839272021738]
F calls: 372
f calls: 513936
Message: Stopped due completed iterations.
total time: 19.0654 s
+============================+

julia> x, y = minimizer(res);

julia> x
5-element Vector{Float64}:
-0.03582594991950816
0.018051141584692676
-0.030154879329873152
-0.017337812299467736
0.004710839249040477

julia> y
5-element Vector{Float64}:
-0.017912974972476316
0.018051141514328663
-0.030154879385452187
-0.017337812317661405
0.004710839272021738

julia> Fmin, fmin = minimum(res)
(0.004720277765002139, 0.0006417493438175533)

Citation

Mejía-de-Dios, J. A., & Mezura-Montes, E. (2020, June). A surrogate-assisted metaheuristic for bilevel optimization. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference (pp. 629-635).

source

## SMS_MOBO

BilevelHeuristics.SMS_MOBOType
SMS_MOBO(;
ul = Metaheuristics.SMS_EMOA(;N = 100), # upper level optimizer
ll = Metaheuristics.NSGA2(;N = 50), # lower level optimizer
ul_offsprings = 10,
options_ul = Options(iterations = 100, f_calls_limit=Inf),
options_ll = Options(iterations = 50, f_calls_limit=Inf)
)

Parameters

• ul is the upper level optimizer: SMS_EMOA is the unique valid optimizer.
• ll can be NSGA2, SPEA2, or SMS_EMOA.
• ul_offsprings is the number of new solutions generated for each generation

Optimal solutions can obtained from res.population when res = optimize(...). or via method.parameters.archive.

julia> using BilevelHeuristics

julia> function F(x, y) # upper level
[y[1] - x[1], y[2]], [-1.0 - sum(y)], [0.0]
end
F (generic function with 1 method)

julia> function f(x, y) # lower level
y, [-x[1]^2 + sum(y .^ 2)], [0.0]
end
f (generic function with 1 method)

julia> bounds_ul = Array([0.0 1]') # upper level bounds for x
2×1 Matrix{Float64}:
0.0
1.0

julia> bounds_ll = [-1 -1; 1 1.0] # lower level bounds for y
2×2 Matrix{Float64}:
-1.0  -1.0
1.0   1.0

julia> method = SMS_MOBO()
SMS_MOBO{NSGA2}(SMS_EMOA(N=100, η_cr=20.0, p_cr=0.9, η_m=20.0, p_m=-1.0, n_samples=10000), NSGA2(N=50, η_cr=20.0, p_cr=0.9, η_m=20.0, p_m=-1.0), 10, Any[])

julia> res = optimize(F, f, bounds_ul, bounds_ll, method)
+=========== RESULT ==========+
iteration: 100
population:
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀F space⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
┌────────────────────────────────────────┐
1 │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
f₂    │⠦⢤⣤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤│
│⠀⠀⠈⠙⠒⠄⢄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠈⠙⠲⢄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠑⠦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⢆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⠢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
-1 │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
└────────────────────────────────────────┘
⠀-2⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀0⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀f₁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
non-dominated solution(s):
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀F space⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
┌────────────────────────────────────────┐
1 │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
f₂    │⠦⢤⣤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤⠤│
│⠀⠀⠈⠙⠒⠄⢄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠈⠙⠲⢄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠑⠦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⢆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
│⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⠢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
-1 │⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀│
└────────────────────────────────────────┘
⠀-2⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀0⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀f₁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
F calls: 54500
f calls: 2725000
Message: Stopped due completed iterations.
total time: 22.1997 s
+============================+

julia> final_archive = method.parameters.archive;

julia> final_archive[1][1] # upper level (solution #1)
(f = [-1.7312900738859534, -0.1378039391413857], g = [-0.003743764044991882], h = [0.0], x = [0.872837777072331])

julia> final_archive[1][2] # lower level (solution #1)
(f = [-0.8584522968136225, -0.1378039391413857], g = [-0.005915513537101735], h = [0.0], x = [-0.8584522968136225, -0.1378039391413857])
source