API documentation
Enumerations
BrkgaMpIpr.BiasFunction
— Type@enum BiasFunction
Specifies a bias function when choosing parents to mating. This function substitutes the $\rho$ (rho) parameter from the original BRKGA. For a given rank $r$, we have the following functions:
CONSTANT
: 1 / number of parents for mating (all individuals have the same probability)CUBIC
: $r^{-3}$EXPONENTIAL
: $ϵ^{-r}$LINEAR
: $1 / r$LOGINVERSE
: $1 / \log(r + 1)$QUADRATIC
: $r^{-2}$
BrkgaMpIpr.PathRelinkingResult
— Type@enum PathRelinkingResult
Specifies the result type/status of path relink procedure:
TOO_HOMOGENEOUS
: the chromosomes among the populations are too homogeneous and the path relink will not generate improveded solutions.NO_IMPROVEMENT
: path relink was done but no improveded solution was found.ELITE_IMPROVEMENT
: an improved solution among the elite set was found, but the best solution was not improved.BEST_IMPROVEMENT
: the best solution was improved.
BrkgaMpIpr.PathRelinkingSelection
— Type@enum PathRelinkingSelection
Specifies which individuals used to build the path:
BESTSOLUTION
: selects, in the order, the best solution of each population.RANDOMELITE
: chooses uniformly random solutions from the elite sets.
BrkgaMpIpr.PathRelinkingType
— Type@enum PathRelinkingType
Specifies type of path relinking:
DIRECT
: changes each key for the correspondent in the other chromosome.PERMUTATION
: switches the order of a key for that in the other chromosome.
BrkgaMpIpr.Sense
— Type@enum Sense
Tells the algorithm either to MINIMIZE
or MAXIMIZE
the objective function.
BrkgaMpIpr.ShakingType
— Type@enum ShakingType
Specifies the type of shaking to be performed.
CHANGE
: applies the following perturbations:- Inverts the value of a random chosen, i.e., from
value
to1 - value
; - Assigns a random value to a random key.
- Inverts the value of a random chosen, i.e., from
SWAP
: applies two swap perturbations:- Swaps the values of a randomly chosen key
i
and its neighbori + 1
; - Swaps values of two randomly chosen keys.
- Swaps the values of a randomly chosen key
Types
BrkgaMpIpr.AbstractInstance
— Typeabstract type AbstractInstance
The required interface for external data to be provided to the decoder. The problem definitions and data must be a subtype of AbstractInstance. For example,
mutable struct TSPInstance <: AbstractInstance
num_cities::Int64
distances::Array{Float64}
end
represents an instance type for the Traveling Salesman problem which defines the number fo cities and a matrix of distances between them.
BrkgaMpIpr.BrkgaData
— Typemutable struct BrkgaData
Represents the internal state of the BRKGA-MP-IPR algorithm.
This structure has no direct constructor and must be built using build_brkga
functions. You can create multiple BrkgaData
representing different states of the algorithm, and use them independently.
This structure is NOT INTENDED to be used outside BRKGA functions. Ad hoc changes may lead to inadvertent results.
Fields
opt_sense
Optimization sense (minimization = 0, maximization = 1).
chromosome_size
Number of genes in the chromosome [> 0].
params
BRKGA parameters for evolution.
elite_size
Number of elite items in the population [> 0].
num_mutants
Number of mutants introduced at each generation into the population [> 0].
evolutionary_mechanism_on
If false, no evolution is performed but only chromosome decoding. Very useful to emulate a multi-start algorithm.
problem_instance
(Internal data) The problem instance used by the
decode!
function to map a chromosome to a problem solution. Sincedecode!
should not change this data, this attribute can be considered constant.
decode!
(Internal data) This is the main decode function called during the evolutionary process and in the path relink. It must have the following signature:
decode!(chromosome::Array{Float64, 1}, problem_instance::AbstractInstance, rewrite::Bool = true)::Float64
Note that if
rewrite == false
,decode!
must not changechromosome
. IPR routines requiresdecode!
to not changechromosome
.
rng
(Internal data) The internal random generator number. DON'T USE FOR ANYTHING OUTSIDE. If you need a RNG, create a new generator.
previous
(Internal data) Previous population.
current
(Internal data) Current population.
bias_function
(Internal data) A unary non-increasing function such that
bias_function(::Int64 > 0)::Float64
total_bias_weight
(Internal data) Holds the sum of the results of each raking given a bias function. This value is needed to normalization.
shuffled_individuals
(Internal data) Used to shuffled individual/chromosome indices during the mate.
parents_ordered
(Internal data) Defines the order of parents during the mating.
initialized
(Internal data) Indicates if the algorithm was proper initialized.
reset_phase
(Internal data) Indicates if the algorithm have been reset.
BrkgaMpIpr.BrkgaParams
— Typemutable struct BrkgaParams
Represents the BRKGA and IPR hyper-parameters. You can load these parameters from a configuration file using load_configuration
and build_brkga
, and write them using write_configuration
.
Fields
population_size
Number of elements in the population [> 0].
elite_percentage
Percentage of individuals to become the elite set (0, 1].
mutants_percentage
Percentage of mutants to be inserted in the population
num_elite_parents
Number of elite parents for mating [> 0].
total_parents
Number of total parents for mating [> 0].
bias_type
Type of bias that will be used.
num_independent_populations
Number of independent parallel populations.
pr_number_pairs
Number of pairs of chromosomes to be tested to path relinking.
pr_minimum_distance
Mininum distance between chromosomes selected to path-relinking.
pr_type
Path relinking type.
pr_selection
Individual selection to path-relinking.
alpha_block_size
Defines the block size based on the size of the population.
pr_percentage
Percentage / path size to be computed. Value in (0, 1].
BrkgaMpIpr.ExternalControlParams
— Typemutable struct ExternalControlParams
Represents additional control parameters that can be used outside this framework. You can load these parameters from a configuration file using load_configuration
and build_brkga
, and write them using write_configuration
.
Fields
exchange_interval
Interval at which elite chromosomes are exchanged (0 means no exchange) [> 0].
num_exchange_indivuduals
Number of elite chromosomes exchanged from each population [> 0].
reset_interval
Interval at which the populations are reset (0 means no reset) [> 0].
I/O functions
Base.parse
— Functionparse(::Type{BiasFunction}, value::String)::BiasFunction
Parse value
returning a valid BiasFunction
enumeration.
Throws
ArgumentError
: in case the bias description does not match.
parse(::Type{PathRelinkingType}, value::String)::PathRelinkingType
Parse value
returning a valid PathRelinkingType
enumeration.
Throws
ArgumentError
: in case the type description does not match.
parse(::Type{PathRelinkingSelection}, value::String)::PathRelinkingSelection
Parse value
returning a valid PathRelinkingSelection
enumeration.
Throws
ArgumentError
: in case the selection description does not match.
BrkgaMpIpr.load_configuration
— Functionload_configuration(configuration_file::String)::
Tuple{BrkgaParams, ExternalControlParams}
Load the parameters from configuration_file
returning them as a tuple.
Throws
LoadError
: in cases of the file is an invalid configuration file, parameters are missing, or parameters are ill-formatted.
BrkgaMpIpr.write_configuration
— Functionfunction write_configuration(filename::String, brkga_params::BrkgaParams,
external_params::ExternalControlParams)
Write brkga_params
and external_params
into filename
.
Throws
SystemError
: in case the configuration files cannot be openned.
function write_configuration(filename::String, brkga_data::BrkgaData,
external_params::ExternalControlParams =
ExternalControlParams())
Write the parameters from brkga_data.params
and external_params
into filename
.
Throws
SystemError
: in case the configuration files cannot be openned.
Building functions
BrkgaMpIpr.build_brkga
— Functionbuild_brkga(problem_instance::AbstractInstance, decode_function!::Function,
opt_sense::Sense, seed::Int64, chromosome_size::Int64,
brkga_params::BrkgaParams, evolutionary_mechanism_on::Bool = true,
)::BrkgaData
Build a BrkgaData
object to be used in the evolutionary and path relink procedures. Such data structure should not be changed outside the BrkgaMpIpr
functions. This version accepts all control arguments, and it is handy for tuning purposes.
Arguments
problem_instance::AbstractInstance
: an instance to the problem to be solved.decode_function!::Function
: the decode funtion used to map chromosomes to solutions. It must have the following signature:decode!(chromosome::Array{Float64, 1}, problem_instance::AbstractInstance, rewrite::Bool)::Float64
Note that if
rewrite == false
,decode!
cannot modifychromosome
.opt_sense::Sense
: the optimization sense ( maximization or minimization).seed::Int64
: seed for the random number generator.chromosome_size::Int64
: number of genes in each chromosome.brkga_params::BrkgaParams
: BRKGA and IPR parameters object loaded from a configuration file or manually created. All the data is deep-copied.evolutionary_mechanism_on::Bool = true
: if false, no evolution is performed but only chromosome decoding. On each generation, all population is replaced excluding the best chromosome. Very useful to emulate a multi-start algorithm.
Throws
ArgumentError
: in several cases where the arguments or a combination of them are invalid.
build_brkga(problem_instance, decode_function!, opt_sense, seed,
chromosome_size, configuration_file,
evolutionary_mechanism_on)::Tuple{BrkgaData, ExternalControlParams}
Build a BrkgaData
object to be used in the evolutionary and path relink procedures, and a ExternalControlParams
that holds additional control parameters. Note that BrkgaData
should not be changed outside the BrkgaMpIpr
functions. This version reads most of the parameters from a configuration file.
Arguments
problem_instance::AbstractInstance
: an instance to the problem to be solved.decode_function!::Function
: the decode funtion used to map chromosomes to solutions. It must have the following signature:decode!(chromosome::Array{Float64, 1}, problem_instance::AbstractInstance, rewrite::Bool = true)::Float64
Note that if
rewrite == false
,decode!
cannot modifychromosome
.opt_sense::Sense
: the optimization sense ( maximization or minimization).seed::Int64
: seed for the random number generator.chromosome_size::Int64
: number of genes in each chromosome..configuration_file::String
: text file with the BRKGA parameters. An example can be found at <a href="example.conf">example.conf</a>. Note that the content after "#" is considered comments and it is ignored.evolutionary_mechanism_on::Bool = true
: if false, no evolution is performed but only chromosome decoding. On each generation, all population is replaced excluding the best chromosome. Very useful to emulate a multi-start algorithm.
Throws
LoadError
: in cases of the file is an invalid configuration file, parameters are missing, or parameters are ill-formatted.SystemError
: in case the configuration files cannot be openned.
BrkgaMpIpr.initialize!
— Functioninitialize!(brkga_data::BrkgaData)
Initialize the populations and others data structures of the BRKGA. If an initial population is supplied, this method completes the remaining individuals, if they do not exist.
THIS METHOD MUST BE CALLED BEFORE ANY OPTIMIZATION METHODS.
This method also performs the initial decoding of the chromosomes. Therefore, depending on the decoder implementation, this can take a while, and the user may want to time such procedure in his/her experiments.
As it is in evolve!
, the decoding is done in parallel using threads, and the user must guarantee that the decoder is THREAD-SAFE. If such property cannot be held, we suggest using a single thread by setting the environmental variable JULIA_NUM_THREADS = 1
(see Julia Parallel Computing).
Throws
ErrorException
: ifbias_function
is not defined previously.
BrkgaMpIpr.set_bias_custom_function!
— Functionset_bias_custom_function!(brkga_data::BrkgaData, bias_function::Function)
Set a new bias function to be used to rank the chromosomes during the mating. It must be a positive non-increasing function returning a Float64, i.e., f(::Int64)::Float64
such that f(i) ≥ 0
and f(i) ≥ f(i+1)
for i ∈ [1..total_parents]
. For instance, the following sets an inverse quadratic function:
set_bias_custom_function!(brkga_data, x -> 1.0 / (x * x))
Throws
ArgumentError
: in case the function is not a non-increasing positive function.
BrkgaMpIpr.set_initial_population!
— Functionset_initial_population!(brkga_data::BrkgaData,
chromosomes::Array{Array{Float64, 1}, 1})
Set initial individuals into the poulation to work as warm-starters. Such individuals can be obtained from solutions of external procedures such as fast heuristics, other methaheuristics, or even relaxations from a mixed integer programming model that models the problem.
All given solutions are assigned to one population only. Therefore, the maximum number of solutions is the size of the populations.
Throws
ArgumentError
: if the number of given chromosomes is larger than the population size; if the sizes of the given chromosomes do not match with the required chromosome size.
Population manipulation functions
BrkgaMpIpr.exchange_elite!
— Functionexchange_elite!(brkga_data::BrkgaData, num_immigrants::Int64)
Exchange elite-solutions between the populations. Given a population, the num_immigrants
best solutions are copied to the neighbor populations, replacing their worth solutions. If there is only one population, nothing is done.
Throws
ErrorException
: ifinitialize!
has not been called before.ArgumentError
: whennum_immigrants < 1
.ArgumentError
:num_immigrants ≥ ⌈population_size/num_independent_populations⌉ - 1
.
BrkgaMpIpr.inject_chromosome!
— Functionfunction inject_chromosome!(brkga_data::BrkgaData,
chromosome::Array{Float64, 1},
population_index::Int64,
position::Int64,
fitness::Float64 = Inf)
Inject chromosome
and its fitness
into population population_index
in the position
place. If fitness is not provided (fitness = Inf
), the decoding is performed over chromosome
. Once the chromosome is injected, the population is re-sorted according to the chromosomes' fitness.
Throws
ErrorException
: ifinitialize!
has not been called before.ArgumentError
: whenpopulation_index < 1
orpopulation_index > num_independent_populations
.ArgumentError
: whenposition < 1
orposition > population_size
.ArgumentError
: whenlenght(chromosome) != chromosome_size
.
BrkgaMpIpr.reset!
— Functionreset!(brkga_data::BrkgaData)
Reset all populations with brand new keys. All warm-start solutions provided by set_initial_population!
are discarded. You may use inject_chromosome!
to insert those solutions again.
As it is in evolve!()
, the decoding is done in parallel using threads, and the user must guarantee that the decoder is THREAD-SAFE. If such property cannot be held, we suggest using single thread by setting the environmental variable JULIA_NUM_THREADS = 1
(see Julia Parallel Computing)
Throws
ErrorException
: ifinitialize!
has not been called before.
BrkgaMpIpr.shake!
— Functionfunction shake!(brkga_data::BrkgaData, intensity::Int64,
shaking_type::ShakingType, population_index::Int64 = Inf64)
Perform a shaking in the chosen population. The procedure applies changes (shaking) on elite chromosomes and fully reset the remaining population.
Arguments
intensity::Int64
: the intensity of the shaking (> 0);shaking_type::ShakingType
: eitherCHANGE
orSWAP
moves;population_index::Int64
: the index of the population to be shaken. Ifpopulation_index > num_independent_populations
, all populations are shaken.
Throws
ErrorException
: ifinitialize!
has not been called before.ArgumentError
: whenpopulation_index < 1
orintensity < 1
.
Retrival functions
BrkgaMpIpr.get_best_chromosome
— Functionget_best_chromosome(brkga_data::BrkgaData)::Array{Float64, 1}
Return a copy of the best individual found so far among all populations.
Throws
ErrorException
: ifinitialize!
has not been called before.
BrkgaMpIpr.get_best_fitness
— Functionget_best_fitness!(brkga_data::BrkgaData)::Float64
Return the fitness/value of the best individual found so far among all populations.
Throws
ErrorException
: ifinitialize!
has not been called before.
BrkgaMpIpr.get_chromosome
— Functionget_chromosome(brkga_data::BrkgaData, population_index::Int64,
position::Int64)::Array{Float64, 1}
Return a copy of the chromosome ranked at position
in the population population_index
. Note that the chromosomes are rakend by fitness and the best chromosome is located in position 1.
Throws
ErrorException
: ifinitialize!
has not been called before.ArgumentError
: whenpopulation_index < 1
orpopulation_index > num_independent_populations
.ArgumentError
: whenposition < 1
orposition > population_size
.
BrkgaMpIpr.get_current_population
— Functionget_current_population(brkga_data::BrkgaData,
population_index::Int64)::Population
Return a reference for population population_index
.
This function is implemented for complaince with the C++ API. The user can access the population directly using brkga_data.current[population_index]
.
IT IS NOT ADIVISED TO CHANGE THE POPULATION DIRECTLY, since such changes can result in undefined behavior.
Throws
ErrorException
: ifinitialize!
has not been called before.ArgumentError
: whenpopulation_index < 1
orpopulation_index > num_independent_populations
.
Evolution functions
BrkgaMpIpr.evolve!
— Functionevolve!(brkga_data::BrkgaData, num_generations::Int64 = 1)
Evolve the current populations following the guidelines of Multi-parent BRKGAs for num_generations
generations.
The decoding is done in parallel using threads, and the user must guarantee that the decoder is THREAD-SAFE. If such property cannot be held, we suggest using single thread by setting the environmental variable JULIA_NUM_THREADS = 1
(see Julia Parallel Computing).
Throws
ErrorException
: ifinitialize!()
was not called before.ArgumentError
: whennum_generations < 1
.
Path relink functions
BrkgaMpIpr.affect_solution_hamming_distance
— Functionaffect_solution_hamming_distance(block1::SubArray{Float64, 1},
block2::SubArray{Float64, 1},
threshold::Float64 = 0.5)::Bool
Return true
the the changing of the blocks of keys block1
by the blocks of keys block2
affects the solution, based on the Hamming distance.
This function may be more appropriated to threshold/direct chromosome representations.
block1
and block2
must have the same size. No bounds checking is done due to performance reasons.
This function is annotated with @inline
due to performance reasons too.
Arguments
block1::SubArray{Float64, 1}
: the first vector.block2::SubArray{Float64, 1}
: the second vector.threshold::Float64 = 0.5
: the threshold for binarization.
BrkgaMpIpr.affect_solution_kendall_tau
— Functionaffect_solution_kendall_tau(block1::SubArray{Float64, 1},
block2::SubArray{Float64, 1})::Bool
Return true
the the changing of the blocks of keys block1
by the blocks of keys block2
affects the solution, based on the Kendall Tau distance.
block1
and block2
must have the same size. No bounds checking is done due to performance reasons.
Arguments
block1::SubArray{Float64, 1}
: the first vector.block2::SubArray{Float64, 1}
: the second vector.
BrkgaMpIpr.hamming_distance
— Functionhamming_distance(vector1::Array{Float64, 1}, vector2::Array{Float64, 1},
threshold::Float64 = 0.5)::Float64
Compute the Hamming distance between two vectors. It takes a threshold
parameter to "binarize" the vectors. For instance, if threshold = 0.7
, all values larger than or equal to 0.7 will be considerd 1.0
, otherwise 0.0
.
This function may be more appropriated to threshold/direct chromosome representations.
Arguments
vector1::Array{Float64, 1}
: the first vector.vector2::Array{Float64, 1}
: the second vector.threshold::Float64 = 0.5
: the threshold for binarization.
Throws
ArgumentError
: ifvector1
andvector2
have different sizes.
BrkgaMpIpr.kendall_tau_distance
— Functionkendall_tau_distance(vector1::Array{Float64, 1},
vector2::Array{Float64, 1};
stop_immediately::Bool = false)::Float64
kendall_tau_distance(vector1::SubArray{Float64, 1},
vector2::SubArray{Float64, 1};
stop_immediately::Bool = false)::Float64
Compute the Kendall Tau distance between two vectors.
This function may be more appropriated to permutation chromosome representations.
Arguments
vector1::Array{Float64, 1}
: the first vector.vector2::Array{Float64, 1}
: the second vector.stop_immediately::Bool = false
: iftrue
, stop the computation immediately after find a difference.
Throws
ArgumentError
: ifvector1
andvector2
have different sizes.
BrkgaMpIpr.path_relink!
— Functionfunction path_relink!(brkga_data::BrkgaData,
pr_type::PathRelinkingType,
pr_selection::PathRelinkingSelection,
compute_distance::Function,
affect_solution::Function,
number_pairs::Int64,
minimum_distance::Float64,
block_size::Int64,
max_time::Float64,
percentage::Float64
)::PathRelinkingResult
Perform path relinking between elite solutions that are, at least, a given minimum distance between themselves.
In the presence of multiple populations, the path relinking is performed between elite chromosomes from different populations, in a circular fashion. For example, suppose we have 3 populations. The framework performs 3 path relinkings: the first between individuals from populations 1 and 2, the second between populations 2 and 3, and the third between populations 3 and 1. In the case of just one population, both base and guiding individuals are sampled from the elite set of that population.
Note that the algorithm tries to find a pair of base and guiding solutions with a minimum distance given by the distance function. If this is not possible, a new pair of solutions are sampled (without replacement) and tested against the distance. In case it is not possible to find such pairs for the given populations, the algorithm skips to the next pair of populations (in a circular fashion, as described above). Yet, if such pairs are not found in any case, the algorithm declares failure. This indicates that the populations are very homogeneous.
If the found solution is the best solution found so far, IPR replaces the worst solution by it. Otherwise, IPR computes the distance between the found solution and all other solutions in the elite set, and replaces the worst solution by it if and only if the found solution is, at least, minimum_distance
from all them.
The API will call decode!()
function always with writeback = false
. The reason is that if the decoder rewrites the chromosome, the path between solutions is lost and inadvertent results may come up. Note that at the end of the path relinking, the method calls the decoder with writeback = true
in the best chromosome found to guarantee that this chromosome is re-written to reflect the best solution found.
This method is a multi-thread implementation. Instead of to build and decode each chromosome one at a time, the method builds a list of candidates, altering the alleles/keys according to the guide solution, and then decode all candidates in parallel. Note that O(chromosome_size^2 / block_size)
additional memory is necessary to build the candidates, which can be costly if the chromosome_size
is very large.
As it is in evolve!()
, the decoding is done in parallel using threads, and the user must guarantee that the decoder is THREAD-SAFE. If such property cannot be held, we suggest using single thread by setting the environmental variable JULIA_NUM_THREADS = 1
(see Julia Parallel Computing).
Arguments
brkga_data::BrkgaData
: the BRKGA data.pr_type::PathRelinkingType
: type of path relinking to be performed. EitherDIRECT
orPERMUTATION
-based.pr_selection::PathRelinkingSelection
: selection of which individuals use to path relinking. EitherBESTSOLUTION
orRANDOMELITE
.compute_distance::Function
: the function used to compute the distance between two chromosomes. The function MUST HAVE the following signaturecompute_distance(vector1::Array{Float64, 1}, vector2::Array{Float64, 1})::Float64
affect_solution::Function
: function that takes two partial chromosomes / block of genesblock1
andblock2
and checks whether changing the keys fromblock1
toblock2
affects the solution. For instance, suppose that the alleles/keys are used as threshold such that values > 0.5 activate a feature. Suppose we haveblock1 = [0.3, 0.4, 0.1]
andblock2 = [0.4, 0.1, 0.2]
. Since all values are below 0.5, changing the keys fromblock1
toblock2
do not change the solution, and therefore, we can drop such change (and subsequentely decoding). The blocks can hold only one key/allele, sequential key blocks, or even the whole chromosome.affect_solution
takes two views/subarrays. The function MUST HAVE the following signatureaffect_solution(block1::SubArray{Float64, 1}, block2::SubArray{Float64, 1})::Bool
Note This function depends on the problem structure and how the keys/alleles are used
number_pairs::Int64
: number of chromosome pairs to be tested. Ifnumber_pairs < 1
, all pairs are tested.minimum_distance::Float64
: minimum distance between two chromosomes computed bycompute_distance
.block_size::Int64 = 1
: number of alleles to be exchanged at once in each iteration. If one, the traditional path relinking is performed. It must be ≥ 1.max_time::Float64 = 0
: abort path-relinking when reachmax_time
. Ifmax_time ≤ 0
, no limit is imposed. Given in seconds.percentage::Float64 = 1.0
: define the size, in percentage, of the path to build. Range [0, 1].
Returns
- Returns
PathRelinkingResult
depending on the relink status.
Throws
ErrorException
: ifinitialize!()
was not called before.ArgumentError
: whenpercentage < 1e-6 || percentage > 1.0
andblock_size < 1
.
Internals
These types and functions are used internally in the framework. They are not meant to be used directly.
Types
BrkgaMpIpr.DecodeStruct
— Typemutable struct DecodeStruct
Hold the data structures used to build a candidate chromosome for parallel decoding on permutation-based path relink.
THIS IS AN INTERNAL DATA STRUCTURE AND IT IS NOT MEANT TO BE USED DIRECTLY.
BrkgaMpIpr.Population
— Typemutable struct Population (internal BRKGA data struct)
Encapsulates a population of chromosomes. Note that this struct is NOT meant to be used externally of this unit.
Fields
chromosomes
Population of chromosomes.
fitness
Fitness of a each chromosome. Each pair represents the fitness and the chromosome index.
BrkgaMpIpr.Triple
— Typemutable struct Triple
Hold the data structures used to build a candidate chromosome for parallel decoding on direct path relink.
THIS IS AN INTERNAL DATA STRUCTURE AND IT IS NOT MEANT TO BE USED DIRECTLY.
Minor helper functions
Base.:|
— FunctionBase.:|(x::PathRelinkingResult,
y::PathRelinkingResult)::PathRelinkingResult
Perform bitwise OR
between two PathRelinkingResult
returning the highest rank PathRelinkingResult
.
Examples
julia> TOO_HOMOGENEOUS | NO_IMPROVEMENT
NO_IMPROVEMENT::PathRelinkingResult = 1
julia> NO_IMPROVEMENT | ELITE_IMPROVEMENT
ELITE_IMPROVEMENT::PathRelinkingResult = 3
julia> ELITE_IMPROVEMENT | BEST_IMPROVEMENT
BEST_IMPROVEMENT::PathRelinkingResult = 7
BrkgaMpIpr.empty_function
— Functionconst empty_function() = nothing
Represent an empty function to be used as flag during data and bias function setups.
BrkgaMpIpr.find_block_range
— Functionfind_block_range(block_number::Int64, block_size::Int64,
max_end::Int64)::UnitRange{Int64}
Return a positive range for the given block_number
with length block_size
, limited to the max_end
.
This function only accept positive numbers, and all sanity check is disregarded due to performance reasons.
THIS IS AN INTERNAL DATA STRUCTURE AND IT IS NOT MEANT TO BE USED DIRECTLY.
BrkgaMpIpr.swap!
— Functionswap!(x::Array{Any, 1}, pos1::Int64, pos2::Int64)
Swap the value in position pos1
with the value in position pos2
in vector x
.
This function only accept positive numbers, and all sanity and bounds check is disregarded due to performance reasons.
THIS IS AN INTERNAL DATA STRUCTURE AND IT IS NOT MEANT TO BE USED DIRECTLY.
Major helper functions
BrkgaMpIpr.evolve_population!
— Functionevolve_population!(brkga_data::BrkgaData, population_index::Int64)
Evolve the population population_index
to the next generation.
Although this method allows us to evolve populations independently, and therefore, provide nice flexibility, the generation of each population can be unsyched. We must proceed with care when using this function instead of evolve!()
.
The decoding is done in parallel using threads, and the user must guarantee that the decoder is THREAD-SAFE. If such property cannot be held, we suggest using single thread by setting the environmental variable JULIA_NUM_THREADS = 1
(see Julia Parallel Computing).
Throws
ErrorException
: ifinitialize!()
was not called before.ArgumentError
: whenpopulation_index < 1
orpopulation_index > num_independent_populations
.
BrkgaMpIpr.direct_path_relink!
— Functionfunction direct_path_relink!(brkga_data::BrkgaData,
chromosome1::Array{Float64, 1},
chromosome2::Array{Float64, 1},
affect_solution::Function,
block_size::Int64,
max_time::Float64,
percentage::Float64
)::Tuple{Float64, Array{Float64, 1}}
Perform the direct path relinking, changing each allele or block of alleles of base chromosome for the correspondent one in the guide chromosome.
The API will call decode!()
function always with writeback = false
. The reason is that if the decoder rewrites the chromosome, the path between solutions is lost and inadvertent results may come up. Note that at the end of the path relinking, the method calls the decoder with writeback = true
in the best chromosome found to guarantee that this chromosome is re-written to reflect the best solution found.
This method is a multi-thread implementation. Instead of to build and decode each chromosome one at a time, the method builds a list of candidates, altering the alleles/keys according to the guide solution, and then decode all candidates in parallel. Note that O(chromosome_size^2 / block_size)
additional memory is necessary to build the candidates, which can be costly if the chromosome_size
is very large.
As it is in evolve!()
, the decoding is done in parallel using threads, and the user must guarantee that the decoder is THREAD-SAFE. If such property cannot be held, we suggest using single thread by setting the environmental variable JULIA_NUM_THREADS = 1
(see Julia Parallel Computing).
THIS IS AN INTERNAL METHOD AND IT IS NOT MEANT TO BE USED DIRECTLY. IT IS CALLED FROM THE path_relink!()
FUNCTION. Due to this reason, this method DOES NOT perform health checks on the arguments.
Arguments
brkga_data::BrkgaData
: the BRKGA data.chromosome1::Array{Float64, 1}
andchromosome2::Array{Float64, 1}
: the chromosomes to be used to build the path.affect_solution::Function
: function that takes two partial chromosomes / block of genesblock1
andblock2
and checks whether changing the keys fromblock1
toblock2
affects the solution. For instance, suppose that the alleles/keys are used as threshold such that values > 0.5 activate a feature. Suppose we haveblock1 = [0.3, 0.4, 0.1]
andblock2 = [0.4, 0.1, 0.2]
. Since all values are below 0.5, changing the keys fromblock1
toblock2
does not chage the solution, and therefore, we can drop such change (and subsequentely decoding). The blocks can hold only one key/allele, sequential key blocks, of even the whole chromosome.affect_solution
takes two views/subarrays. The function MUST HAVE the following signatureaffect_solution(block1::SubArray{Float64, 1}, block2::SubArray{Float64, 1})::Bool
Note This function depends on the problem structure and how the keys/alleles are used.
block_size::Int64
: (posite) number of alleles to be exchanged at once in each iteration. Ifblock_size == 1
, the traditional path relinking is performed.max_time::Float64
: abort path-relinking when reachmax_time
. Ifmax_time <= 0
, no limit is imposed. Given in seconds.percentage::Float64
: define the size, in percentage, of the path to build. Range [0, 1].
Returns
Array{Any, 1}
: the best pair [fitness, chromosome] found during the relinking. If the relink is not possible due to homogeneity,-Inf
returns in case of maximization, andInf
in case of minimization.
BrkgaMpIpr.permutation_based_path_relink!
— Functionfunction permutation_based_path_relink!(brkga_data::BrkgaData,
chromosome1::Array{Float64, 1},
chromosome2::Array{Float64, 1},
affect_solution::Function,
block_size::Int64,
max_time::Float64,
percentage::Float64
)::Tuple{Float64, Array{Float64, 1}}
Perform the permutation-based path relinking. In this method, the permutation induced by the keys in the guide solution is used to change the order of the keys in the permutation induced by the base solution.
The API will call decode!()
function always with writeback = false
. The reason is that if the decoder rewrites the chromosome, the path between solutions is lost and inadvertent results may come up. Note that at the end of the path relinking, the method calls the decoder with writeback = true
in the best chromosome found to guarantee that this chromosome is re-written to reflect the best solution found.
This method is a multi-thread implementation. Instead of to build and decode each chromosome one at a time, the method builds a list of candidates, altering the alleles/keys according to the guide solution, and then decode all candidates in parallel. Note that O(chromosome_size^2 / block_size)
additional memory is necessary to build the candidates, which can be costly if the chromosome_size
is very large.
As it is in evolve!()
, the decoding is done in parallel using threads, and the user must guarantee that the decoder is THREAD-SAFE. If such property cannot be held, we suggest using single thread by setting the environmental variable JULIA_NUM_THREADS = 1
(see Julia Parallel Computing).
THIS IS AN INTERNAL METHOD AND IT IS NOT MEANT TO BE USED DIRECTLY. IT IS CALLED FROM THE path_relink!()
FUNCTION. Due to this reason, this method DOES NOT perform health checks on the arguments.
Arguments
brkga_data::BrkgaData
: the BRKGA data.chromosome1::Array{Float64, 1}
andchromosome2::Array{Float64, 1}
: the chromosomes to be used to build the path.affect_solution::Function
: not used in this function but kept to API compatibility.block_size::Int64
: not used in this function but kept to API compatibility.max_time::Float64
: abort path-relinking when reachmax_time
. Ifmax_time <= 0
, no limit is imposed. Given in seconds.percentage::Float64
: define the size, in percentage, of the path to build. Range [0, 1].
Returns
Array{Any, 1}
: the best pair [fitness, chromosome] found during the relinking. If the relink is not possible due to homogeneity,-Inf
returns in case of maximization, andInf
in case of minimization.
Index
BrkgaMpIpr.AbstractInstance
BrkgaMpIpr.BiasFunction
BrkgaMpIpr.BrkgaData
BrkgaMpIpr.BrkgaParams
BrkgaMpIpr.DecodeStruct
BrkgaMpIpr.ExternalControlParams
BrkgaMpIpr.PathRelinkingResult
BrkgaMpIpr.PathRelinkingSelection
BrkgaMpIpr.PathRelinkingType
BrkgaMpIpr.Population
BrkgaMpIpr.Sense
BrkgaMpIpr.ShakingType
BrkgaMpIpr.Triple
Base.:|
Base.parse
BrkgaMpIpr.affect_solution_hamming_distance
BrkgaMpIpr.affect_solution_kendall_tau
BrkgaMpIpr.build_brkga
BrkgaMpIpr.direct_path_relink!
BrkgaMpIpr.empty_function
BrkgaMpIpr.evolve!
BrkgaMpIpr.evolve_population!
BrkgaMpIpr.exchange_elite!
BrkgaMpIpr.find_block_range
BrkgaMpIpr.get_best_chromosome
BrkgaMpIpr.get_best_fitness
BrkgaMpIpr.get_chromosome
BrkgaMpIpr.get_current_population
BrkgaMpIpr.hamming_distance
BrkgaMpIpr.initialize!
BrkgaMpIpr.inject_chromosome!
BrkgaMpIpr.kendall_tau_distance
BrkgaMpIpr.load_configuration
BrkgaMpIpr.path_relink!
BrkgaMpIpr.permutation_based_path_relink!
BrkgaMpIpr.reset!
BrkgaMpIpr.set_bias_custom_function!
BrkgaMpIpr.set_initial_population!
BrkgaMpIpr.shake!
BrkgaMpIpr.swap!
BrkgaMpIpr.write_configuration