Algorithms
List of implemented metaheuristics.
Evolutionary Centers Algorithm
ECA was proposed for solving global optimization problems. See J.-A. Mejía-de-Dios , E. Mezura-Montes (2019) for more information.
Metaheuristics.ECA
— TypeECA(;
η_max = 2.0,
K = 7,
N = 0,
N_init = N,
p_exploit = 0.95,
p_bin = 0.02,
p_cr = Float64[],
adaptive = false,
resize_population = false,
information = Information(),
options = Options()
)
Parameters for the metaheuristic ECA: step-size η_max
,K
is number of vectors to generate the center of mass, N
is the population size.
Example
julia> f(x) = sum(x.^2)
f (generic function with 1 method)
julia> optimize(f, [-1 -1 -1; 1 1 1.0], ECA())
+=========== RESULT ==========+
iteration: 1429
minimum: 3.3152400000000004e-223
minimizer: [4.213750597785841e-113, 5.290977430907081e-112, 2.231685329262638e-112]
f calls: 29989
total time: 0.1672 s
+============================+
julia> optimize(f, [-1 -1 -1; 1 1 1.0], ECA(N = 10, η_max = 1.0, K = 3))
+=========== RESULT ==========+
iteration: 3000
minimum: 0.000571319
minimizer: [-0.00017150889316537758, -0.007955828028420616, 0.022538733289139145]
f calls: 30000
total time: 0.1334 s
+============================+
Differential Evolution
DE is an evolutionary algorithm based on vector differences. See K. V. Price (2013) for more details.
Metaheuristics.DE
— TypeDE(;
N = 0,
F = 1.0,
CR = 0.9,
strategy = :rand1,
information = Information(),
options = Options()
)
Parameters for Differential Evolution (DE) algorithm: step-size F
,CR
controlls the binomial crossover, N
is the population size. The parameter trategy
is related to the variation operator (:rand1
, :rand2
, :best1
, :best2
, :randToBest1
).
Example
julia> f(x) = sum(x.^2)
f (generic function with 1 method)
julia> optimize(f, [-1 -1 -1; 1 1 1.0], DE())
+=========== RESULT ==========+
iteration: 1000
minimum: 0
minimizer: [0.0, 0.0, 0.0]
f calls: 30000
total time: 0.0437 s
+============================+
julia> optimize(f, [-1 -1 -1; 1 1 1.0], DE(N=50, F=1.5, CR=0.8))
+=========== RESULT ==========+
iteration: 600
minimum: 8.68798e-25
minimizer: [3.2777877981303293e-13, 3.7650459509488005e-13, -7.871487597385812e-13]
f calls: 30000
total time: 0.0319 s
+============================+
Particle Swarm Optimization
PSO is a population-based optimization technique inspired by the motion of bird flocks and schooling fish (J. Kennedy , R. Eberhart (1995)).
Metaheuristics.PSO
— TypePSO(;
N = 0,
C1 = 2.0,
C2 = 2.0,
ω = 0.8,
information = Information(),
options = Options()
)
Parameters for Particle Swarm Optimization (PSO) algorithm: learning rates C1
and C2
, N
is the population size and ω
controlls the inertia weight.
Example
julia> f(x) = sum(x.^2)
f (generic function with 1 method)
julia> optimize(f, [-1 -1 -1; 1 1 1.0], PSO())
+=========== RESULT ==========+
iteration: 1000
minimum: 1.40522e-49
minimizer: [3.0325415595139883e-25, 1.9862212295897505e-25, 9.543772256546461e-26]
f calls: 30000
total time: 0.1558 s
+============================+
julia> optimize(f, [-1 -1 -1; 1 1 1.0], PSO(N = 100, C1=1.5, C2=1.5, ω = 0.7))
+=========== RESULT ==========+
iteration: 300
minimum: 2.46164e-39
minimizer: [-3.055334698085433e-20, -8.666986835846171e-21, -3.8118413472544027e-20]
f calls: 30000
total time: 0.1365 s
+============================+
Artificial Bee Colony
A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm by D. Karaboga , B. Basturk (2007).
Metaheuristics.ABC
— TypeABC(;
N = 50,
Ne = div(N+1, 2),
No = div(N+1, 2),
limit=10,
information = Information(),
options = Options()
)
ABC implements the original parameters for the Artificial Bee Colony Algorithm. N
is the population size, Ne
is the number of employees, No
is the number of outlookers bees. limit
is related to the times that a solution is visited.
Example
julia> f(x) = sum(x.^2)
f (generic function with 1 method)
julia> optimize(f, [-1 -1 -1; 1 1 1.0], ABC())
+=========== RESULT ==========+
iteration: 595
minimum: 4.03152e-28
minimizer: [1.489845115451046e-14, 1.2207275971717747e-14, -5.671872444705246e-15]
f calls: 30020
total time: 0.0360 s
+============================+
julia> optimize(f, [-1 -1 -1; 1 1 1.0], ABC(N = 80, No = 20, Ne = 50, limit=5))
+=========== RESULT ==========+
iteration: 407
minimum: 8.94719e-08
minimizer: [8.257485723496422e-5, 0.0002852795196258074, -3.5620824723352315e-5]
f calls: 30039
total time: 0.0432 s
+============================+
MOEA/D-DE
Multiobjective optimization problems with complicated Pareto sets by H. Li , Q. Zhang (2008).
Metaheuristics.MOEAD_DE
— TypeMOEAD_DE(weights)
MOEAD_DE
implements the original version of MOEA/D-DE. It uses the contraint handling method based on the sum of violations (for constrained optimizaton): g(x, λ, z) = max(λ .* abs.(fx - z)) + sum(max.(0, gx)) + sum(abs.(hx))
To use MOEAD_DE, the output from the objective function should be a 3-touple (f::Vector, g::Vector, h::Vector)
, where f
contains the objective functions, g
and h
are the equality and inequality constraints respectively.
A feasible solution is such that g_i(x) ≤ 0 and h_j(x) = 0
.
Ref. Multiobjective Optimization Problems With Complicated Pareto Sets, MOEA/D and NSGA-II; Hui Li and Qingfu Zhang.
Example
Assume you want to solve the following optimizaton problem:
Minimize:
f(x) = (x_1, x_2)
subject to:
g(x) = x_1^2 + x_2^2 - 1 ≤ 0
x_1, x_2 ∈ [-1, 1]
A solution can be:
# Dimension
D = 2
# Objective function
f(x) = ( x, [sum(x.^2) - 1], [0.0] )
# bounds
bounds = [-1 -1;
1 1.0
]
nobjectives = 2
npartitions = 100
# reference points (Das and Dennis's method)
weights = gen_ref_dirs(nobjectives, npartitions)
# define the parameters
moead_de = MOEAD_DE(weights, options=Options(debug=false, iterations = 250))
# optimize
status_moead = optimize(f, bounds, moead_de)
# show results
display(status_moead)
Gravitational Search Algorithm
Chaotic gravitational constants for the gravitational search algorithm by S. Mirjalili , A. H. Gandomi (2017)
Metaheuristics.CGSA
— TypeCGSA(;
N::Int = 30,
chValueInitial::Real = 20,
chaosIndex::Real = 9,
ElitistCheck::Int = 1,
Rpower::Int = 1,
Rnorm::Int = 2,
wMax::Real = chValueInitial,
wMin::Real = 1e-10,
information = Information(),
options = Options()
)
CGSA is an extension of the GSA algorithm but with Chaotic gravitational constants for the gravitational search algorithm.
Ref. Chaotic gravitational constants for the gravitational search algorithm. Applied Soft Computing 53 (2017): 407-419.
Parameters:
- N: Population size
- chValueInitial: Initial value for the chaos value
- chaosIndex: Integer 1 ≤ chaosIndex ≤ 10 is the function that model the chaos
- Rpower: power related to the distance norm(x)^Rpower
- Rnorm: is the value as in norm(x, Rnorm)
Example
julia> f(x) = sum(x.^2)
f (generic function with 1 method)
julia> optimize(f, [-1 -1 -1; 1 1 1.0], CGSA())
+=========== RESULT ==========+
iteration: 500
minimum: 8.63808e-08
minimizer: [0.0002658098418993323, -1.140808975532608e-5, -0.00012488307670533095]
f calls: 15000
total time: 0.1556 s
+============================+
julia> optimize(f, [-1 -1 -1; 1 1 1.0], CGSA(N = 80, chaosIndex = 1))
+=========== RESULT ==========+
iteration: 500
minimum: 1.0153e-09
minimizer: [-8.8507563788141e-6, -1.3050111801923072e-5, 2.7688577445980026e-5]
f calls: 40000
total time: 1.0323 s
+============================+
Simulated Annealing
Physics inspired algorithm for optimization Peter J.M. Van L. , E.H.L. Aarts (1987).
Metaheuristics.SA
— Type SA(;
x_initial::Vector = zeros(0),
N::Int = 500,
tol_fun::Real= 1e-4,
information = Information(),
options = Options()
)
Parameters for the method of Simulated Annealing (Kirkpatrick et al., 1983).
Parameters:
- x_intial: Inital solution. If empty, then SA will generate a random one within the bounds.
- N: The number of test points per iteration.
- tol_fun: tolerance value for the Metropolis condition to accept or reject the test point as current point.
Example
julia> f(x) = sum(x.^2)
f (generic function with 1 method)
julia> optimize(f, [-1 -1 -1; 1 1 1.0], SA())
+=========== RESULT ==========+
iteration: 60
minimum: 5.0787e-68
minimizer: [-2.2522059499734615e-34, 3.816133503985569e-36, 6.934348004465088e-36]
f calls: 29002
total time: 0.0943 s
+============================+
julia> optimize(f, [-1 -1 -1; 1 1 1.0], SA(N = 100, x_initial = [1, 0.5, -1]))
+=========== RESULT ==========+
iteration: 300
minimum: 1.99651e-69
minimizer: [4.4638292404181215e-35, -1.738939846089388e-36, -9.542441152683457e-37]
f calls: 29802
total time: 0.0965 s
+============================+
Whale Optimization Algorithm
The Whale Optimization Algorithm inspired by humpback whales S. Mirjalili , A. Lewis (2016).
Metaheuristics.WOA
— TypeWOA(;N = 30, information = Information(), options = Options())
Parameters for the Whale Optimization Algorithm. N
is the population size (number of whales).
Example
julia> f(x) = sum(x.^2)
f (generic function with 1 method)
julia> optimize(f, [-1 -1 -1; 1 1 1.0], WOA())
+=========== RESULT ==========+
iteration: 500
minimum: 3.9154600000000003e-100
minimizer: [8.96670478694908e-52, -1.9291317455298046e-50, 4.3113080446722046e-51]
f calls: 15000
total time: 0.0134 s
+============================+
julia> optimize(f, [-1 -1 -1; 1 1 1.0], WOA(N = 100))
+=========== RESULT ==========+
iteration: 500
minimum: 1.41908e-145
minimizer: [9.236161414012512e-74, -3.634919950380001e-73, 3.536831799149254e-74]
f calls: 50000
total time: 0.0588 s
+============================+
NSGA-II
A fast and elitist multiobjective genetic algorithm: NSGA-IIK. Deb , A. Pratap , S. Agarwal , T. Meyarivan (2002).
Metaheuristics.NSGA2
— Typefunction NSGA2(;
N = 100,
η_cr = 20,
p_cr = 0.9,
η_m = 20,
p_m = 1.0 / D,
ε = eps(),
information = Information(),
options = Options(),
)
Parameters for the metaheuristic NSGA-II.
Parameters:
N
Population size.η_cr
η for the crossover.p_cr
Crossover probability.η_m
η for the mutation operator.p_m
Mutation probability (1/D for D-dimensional problem by default).
To use NSGA2, the output from the objective function should be a 3-touple (f::Vector, g::Vector, h::Vector)
, where f
contains the objective functions, g
and h
are inequality, equality constraints respectively.
A feasible solution is such that g_i(x) ≤ 0 and h_j(x) = 0
.
using Metaheuristics
# Dimension
D = 2
# Objective function
f(x) = ( x, [sum(x.^2) - 1], [0.0] )
# bounds
bounds = [-1 -1;
1 1.0
]
# define the parameters (use `NSGA2()` for using default parameters)
nsga2 = NSGA2(N = 100, p_cr = 0.85)
# optimize
status = optimize(f, bounds, nsga2)
# show results
display(status)
NSGA-III
An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints K. Deb , H. Jain (2014).
Metaheuristics.NSGA3
— Typefunction NSGA3(;
N = 100,
η_cr = 20,
p_cr = 0.9,
η_m = 20,
p_m = 1.0 / D,
ε = eps(),
information = Information(),
options = Options(),
)
Parameters for the metaheuristic NSGA-III.
Parameters:
N
Population size.η_cr
η for the crossover.p_cr
Crossover probability.η_m
η for the mutation operator.p_m
Mutation probability (1/D for D-dimensional problem by default).
To use NSGA3, the output from the objective function should be a 3-touple (f::Vector, g::Vector, h::Vector)
, where f
contains the objective functions, g
and h
are inequality, equality constraints respectively.
A feasible solution is such that g_i(x) ≤ 0 and h_j(x) = 0
.
using Metaheuristics
# Objective function, bounds, and the True Pareto front
f, bounds, pf = Metaheuristics.TestProblems.get_problem(:DTLZ2)
# define the parameters (use `NSGA3()` for using default parameters)
nsga3 = NSGA3(p_cr = 0.9)
# optimize
status = optimize(f, bounds, nsga3)
# show results
display(status)