Algorithms

BCA

BilevelHeuristics.BCA — Type

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.QBCA — Type

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.QBCA2 — Type

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.SABO — Type

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_MOBO — Type

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