API documentation

@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}$

@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.

@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.

@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.

@enum Sense

Tells the algorithm either to MINIMIZE or MAXIMIZE the objective function.

@enum ShakingType

Specifies the type of shaking to be performed.

• CHANGE: applies the following perturbations:

  1. Inverts the value of a random chosen, i.e., from value to 1 - value;
  2. Assigns a random value to a random key.

• SWAP: applies two swap perturbations:

  1. Swaps the values of a randomly chosen key i and its neighbor i + 1;
  2. Swaps values of two randomly chosen keys.

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.

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.

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.

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].

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].

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.

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.

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.

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.

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

Throws

• ErrorException: if bias_function is not defined previously.

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.

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.

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.

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.

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.

Throws

• ErrorException: if initialize! has not been called before.

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.

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.

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.

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.

get_current_population(brkga_data::BrkgaData,
                       population_index::Int64)::Population

Return a reference for population population_index.

Throws

• ErrorException: if initialize! has not been called before.
• ArgumentError: when population_index < 1 or population_index > num_independent_populations.

evolve!(brkga_data::BrkgaData, num_generations::Int64 = 1)

Evolve the current populations following the guidelines of Multi-parent BRKGAs for num_generations generations.

Throws

• ErrorException: if initialize!() was not called before.
• ArgumentError: when num_generations < 1.

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.

Arguments

• block1::SubArray{Float64, 1}: the first vector.
• block2::SubArray{Float64, 1}: the second vector.
• threshold::Float64 = 0.5: the threshold for binarization.

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.

Arguments

• block1::SubArray{Float64, 1}: the first vector.
• block2::SubArray{Float64, 1}: the second vector.

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.

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.

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.

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.

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.

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.

mutable struct DecodeStruct

Hold the data structures used to build a candidate chromosome for parallel decoding on permutation-based path relink.

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.

mutable struct Triple

Hold the data structures used to build a candidate chromosome for parallel decoding on direct path relink.

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

const empty_function() = nothing

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

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.

swap!(x::Array{Any, 1}, pos1::Int64, pos2::Int64)

Swap the value in position pos1 with the value in position pos2 in vector x.

evolve_population!(brkga_data::BrkgaData, population_index::Int64)

Evolve the population population_index to the next generation.

Throws

• ErrorException: if initialize!() was not called before.
• ArgumentError: when population_index < 1 or population_index > num_independent_populations.

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.

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.

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.

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.