# 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`

to`1 - 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 neighbor`i + 1`

; - Swaps values of two randomly chosen keys.

- Swaps the values of a randomly chosen key

## Types

`BrkgaMpIpr.AbstractInstance`

— Type`abstract 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`

— Type`mutable 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. Since`decode!`

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 change`chromosome`

. IPR routines requires`decode!`

to not change`�chromosome`

�.

`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`

— Type`mutable 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`

— Type`mutable 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`

— Function`parse(::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`

— Function```
load_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`

— Function```
function 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`

— Function```
build_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 modify`chromosome`

.`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 modify`chromosome`

.`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!`

— Function`initialize!(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`

: if`bias_function`

is not defined previously.

`BrkgaMpIpr.set_bias_custom_function!`

— Function`set_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!`

— Function```
set_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!`

— Function`exchange_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`

: if`initialize!`

has not been called before.`ArgumentError`

: when`num_immigrants < 1`

.`ArgumentError`

:`num_immigrants ≥ ⌈population_size/num_independent_populations⌉ - 1`

.

`BrkgaMpIpr.inject_chromosome!`

— Function```
function 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`

: if`initialize!`

has not been called before.`ArgumentError`

: when`population_index < 1`

or`population_index > num_independent_populations`

.`ArgumentError`

: when`position < 1`

or`position > population_size`

.`ArgumentError`

: when`lenght(chromosome) != chromosome_size`

.

`BrkgaMpIpr.reset!`

— Function`reset!(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`

: if`initialize!`

has not been called before.

`BrkgaMpIpr.shake!`

— Function```
function 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`

: either`CHANGE`

or`SWAP`

moves;`population_index::Int64`

: the index of the population to be shaken. If`population_index > num_independent_populations`

, all populations are shaken.

**Throws**

`ErrorException`

: if`initialize!`

has not been called before.`ArgumentError`

: when`population_index < 1`

or`intensity < 1`

.

## Retrival functions

`BrkgaMpIpr.get_best_chromosome`

— Function`get_best_chromosome(brkga_data::BrkgaData)::Array{Float64, 1}`

Return a copy of the best individual found so far among all populations.

**Throws**

`ErrorException`

: if`initialize!`

has not been called before.

`BrkgaMpIpr.get_best_fitness`

— Function`get_best_fitness!(brkga_data::BrkgaData)::Float64`

Return the fitness/value of the best individual found so far among all populations.

**Throws**

`ErrorException`

: if`initialize!`

has not been called before.

`BrkgaMpIpr.get_chromosome`

— Function```
get_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`

: if`initialize!`

has not been called before.`ArgumentError`

: when`population_index < 1`

or`population_index > num_independent_populations`

.`ArgumentError`

: when`position < 1`

or`position > population_size`

.

`BrkgaMpIpr.get_current_population`

— Function```
get_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`

: if`initialize!`

has not been called before.`ArgumentError`

: when`population_index < 1`

or`population_index > num_independent_populations`

.

## Evolution functions

`BrkgaMpIpr.evolve!`

— Function`evolve!(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`

: if`initialize!()`

was not called before.`ArgumentError`

: when`num_generations < 1`

.

## Path relink functions

`BrkgaMpIpr.affect_solution_hamming_distance`

— Function```
affect_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`

— Function```
affect_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`

— Function```
hamming_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`

: if`vector1`

and`vector2`

have different sizes.

`BrkgaMpIpr.kendall_tau_distance`

— Function```
kendall_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`

: if`true`

, stop the computation immediately after find a difference.

**Throws**

`ArgumentError`

: if`vector1`

and`vector2`

have different sizes.

`BrkgaMpIpr.path_relink!`

— Function```
function 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. Either`DIRECT`

or`PERMUTATION`

-based.`pr_selection::PathRelinkingSelection`

: selection of which individuals use to path relinking. Either`BESTSOLUTION`

or`RANDOMELITE`

.`compute_distance::Function`

: the function used to compute the distance between two chromosomes. The function**MUST HAVE**the following signature`compute_distance(vector1::Array{Float64, 1}, vector2::Array{Float64, 1})::Float64`

`affect_solution::Function`

: function that takes two partial chromosomes / block of genes`block1`

and`block2`

and checks whether changing the keys from`block1`

to`block2`

affects the solution. For instance, suppose that the alleles/keys are used as threshold such that values > 0.5 activate a feature. Suppose we have`block1 = [0.3, 0.4, 0.1]`

and`block2 = [0.4, 0.1, 0.2]`

. Since all values are below 0.5, changing the keys from`block1`

to`block2`

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 signature`affect_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. If`number_pairs < 1`

, all pairs are tested.`minimum_distance::Float64`

: minimum distance between two chromosomes computed by`compute_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 reach`max_time`

. If`max_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`

: if`initialize!()`

was not called before.`ArgumentError`

: when`percentage < 1e-6 || percentage > 1.0`

and`block_size < 1`

.

## Internals

These types and functions are used internally in the framework. They are not meant to be used directly.

### Types

`BrkgaMpIpr.DecodeStruct`

— Type`mutable 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`

— Type`mutable 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`

— Type`mutable 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.:|`

— Function```
Base.:|(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`

— Function`const empty_function() = nothing`

Represent an empty function to be used as flag during data and bias function setups.

`BrkgaMpIpr.find_block_range`

— Function```
find_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!`

— Function`swap!(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!`

— Function`evolve_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`

: if`initialize!()`

was not called before.`ArgumentError`

: when`population_index < 1`

or`population_index > num_independent_populations`

.

`BrkgaMpIpr.direct_path_relink!`

— Function```
function 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}`

and`chromosome2::Array{Float64, 1}`

: the chromosomes to be used to build the path.`affect_solution::Function`

: function that takes two partial chromosomes / block of genes`block1`

and`block2`

and checks whether changing the keys from`block1`

to`block2`

affects the solution. For instance, suppose that the alleles/keys are used as threshold such that values > 0.5 activate a feature. Suppose we have`block1 = [0.3, 0.4, 0.1]`

and`block2 = [0.4, 0.1, 0.2]`

. Since all values are below 0.5, changing the keys from`block1`

to`block2`

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 signature`affect_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. If`block_size == 1`

, the traditional path relinking is performed.`max_time::Float64`

: abort path-relinking when reach`max_time`

. If`max_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, and`Inf`

in case of minimization.

`BrkgaMpIpr.permutation_based_path_relink!`

— Function```
function 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}`

and`chromosome2::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 reach`max_time`

. If`max_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, and`Inf`

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`