An introduction to the BRKGA-MP-IPR Algorithm

I recently performed a study on a brand new evolutionary algorithm called BRKGA-MP-IPR_[1]_. This article aims to explain a little about what the algorithm consists of and its main features and novelties.

What does this longs name even means?

Let’s break it into three pieces, so we can get it more easily.

Firstly, BRKGA stands for Biased random key genetic algorithm, this is a branch of the classical genetic algorithm (GA for short). Secondly, MP stands for Multi parenting which is just a technique for individuals selection (we’ll explain this later on) and finally, IPR stands for Implicit Path Relink, a novel version of the Path relink local search method, commonly used to enhance solutions found by heuristics by combining them.

Understanding the core concepts

To see the big picture of BRKGA-MP-IPR_[1]_ more clearly, we need to understand the core concepts the algorithm relies on, and these are:

• Genetic Algorithm;
• Biased Random Keys;
• Multi Parenting;
• Path Relink;

1. Genetic Algorithm

Genetic algorithms (GAs) are a family of metaheuristics deeply inspired by the theory of natural evolution. GAs are implemented so they reflect various processes of natural selection such as the survival of the fittest individuals, breeding, mutation and of course the evolution of individuals. Common usages of GAs include global optimization and scheduling problems, even though since its initial development numerous variations of GAs were crafted to fit a very wide field of real-world problems (see the list here).

In terms of code, the simplest versions of GAs are simple to understand. I’m linking here the most relevant implementations listed by Github if you want to explore how it looks in real code.

2. Biased Random Keys

To represent a candidate solution for a problem, a GA encodes a solution in the form of an individual. The simplest example of this might be a population of individuals that can be decoded to solutions for a TSP (Traveling Salesperson Problem) instance. Below there’s an exampĺe of such a representation:

2.1. Simple encoding

# a possible solution as a list of numbers
print(population[individual_index])
# output: [1,2,3,4,5]

In this example, the variable individual stores the order in which cities are visited on the salesperson tour, and like this, each number is a graph edge.

2.2. Random Key encoding

Generally, a random key is a float in the interval [0,1]. Random keys will represent the information similarly seen in the example above but with some additional perks: We now won’t have to worry about possibly generating invalid new individuals while breeding or mutating (say a mutated gene points to an inexistent city on the TSP instance) and we’ll represent individuals in a problem independent manner (permutation problems, in general, are simply represented by random keys). Here’s the same example code from above, now using a random key scheme:

# a possible solution as a list of random keys print(population[some_individual_index])
# output: [0.54,0.89,0.32,0.11,0.73]

# decode the individual to a real solution
print(decode(population[some_individual_index]))
# output: [3,2,0,4,1]

We can notice that independently of what genes were generated during breeding and mutation all solutions are valid (given that decoding will be performed on the individual).

Now one last thing about random keys is how a decoder method will translate a list of random keys to a feasible solution. It can be quite simple actually, in the decoding scheme above we just sorted the alleles in ascending order (the ordered array is [0.11,0.32,0.54,0.73,0.89] ) and mapped the ordered keys with their original index in the list (so we get solution [3,2,0,4,1] ). There are other methods of decoding solutions, this is just the simplest one.

If you’re looking for more information, please refer to the original publication_[2]_.

2.3. Biased Random Key

This variation of random keys encoding is proposed as two changes in the breeding method:

• One of the parents chosen for mating is biased to be of higher fitness than the other parent. A strategy to always have a biased couple of individuals is to select one of them from the elite group (a smaller portion of the population that contains the individuals with the current best fitnesses).
• The probability that an offspring inherits the allele of its elite parent is higher than from its non-elite parent. The empirical intuition of this algorithmic choice is that an elite-biased offspring will elevate the overall quality of the population and consequently leading to a better performance of the evolutional process.
  Figure: Flowchart of a BRKGA
  Source: J.F. Gonçalves, M.G.C. Resende

3.Multi-parent

The first of the two major novelties in the BRKGA-MP-IPR algorithm is the multi-parent scheme. Instead of choosing one parent from the elite and one from the non-elite now n individuals will be selected for breeding a new individual and of those, e are individuals from the elite and n-e are not. In addition to this, each of n parents will have a bias of selection that is proportional to its fitness. Just as biased random keys, multi-parent is an attempt to elevate the quality of solutions without leaving behind the possibility of diversification of the population.

Path-relinking intends to find a better solution that’s somewhere in between two already known solutions from the elite population, hoping that such an intermediate solution will improve the quality and diversity of the elite population.

Figure: Visual example of path-relinking
Source: Conci A., Brazil A.[3]

From the image above we see that through some iterative steps the algorithm replace parts of a base solution with parts of a guide solution and if in any of these part replacements step the fitness associated with this intermediate individual is better than what we currently have, we can consider the search successful and append this new individual to the population.

4.2. What’s implicit about this?

Just like random key encoding, path-relinking does not want to be problem-dependent or implementation-dependent. These methods intend to be general approaches to a wide variety of problems, and like this, the path-relinking algorithm implicitly tries to find intermediate solutions without knowing about the structure of the problem you’re trying to solve. What will, in the end, lead you to use BRKGA-MP-IPR faster and easier.

Lastly, I’d like to say that there are two variations of this algorithm, a direct version, and a permutation-based version. They’re quite similar in implementation but differ slightly in some details. If you want for more details on this I recommend you looking into the original paper [1].

With these new concepts in mind we have all what’s necessary to start using the algorithm and start mastering it.

5. Implementation by C. E. Andrade

For clarification, I highly recommend that you go check the incredible python implementation of BRKGA-MP-IPR developed by Carlos Andrade. It contains excellent code, documentation, and walkthroughs. Alongside a python implementation you can also find C++ and Julia versions. In this section we’re executing an example of the algorithm being used to optmize routes on a instance of the traveling salesperson problem.

5.1. Simple execution example

The implementation is available as a python package, so assuming you have at least version 3.7 of Python you can execute:

pip install brkga-mp-ipr docopt

(We also need the docopt package for command-line arguments parsing)

Get a copy of the repository so we can access the examples folder where we have the script containing a very good and simple example solving a TSP instance:

git clone https://github.com/ceandrade/brkga_mp_ipr_python.git cd brkga_mp_ipr_python/examples/tsp

Before executing the script I recommend that you take a good read at it. Read it carrefully and you will get a better undestaing of the tool.

Now to see this evolutionary algorithm working, you can use this command:

python3.7 main_complete.py -c config.conf -s 2700001 -r Generations -a 100 -t 60 -i instances/brazil58.dat

Where -c specify the file containing all the optmization parameters, -s for the random seed, -r for the stop rule, -t for maximum execution time and -i specify the file containing the traveling salesperson instance graph representation.

After executing it, you will get an output similar to this:

------------------------------------------------------ > 
Experiment started at 2020-03-05 12:45:18.612186 
> Instance: instances/brazil58.dat 
> Configuration: config.conf 
> Algorithm Parameters: 
> -population_size 2000 
> -elite_percentage 0.3 
> -mutants_percentage 0.15 
> -num_elite_parents 2 
> -total_parents 3 
> -bias_type LOGINVERSE 
> -num_independent_populations 3 
> -pr_number_pairs 0 
> -pr_minimum_distance 0.15 
> -pr_type PERMUTATION 
> -pr_selection BESTSOLUTION 
> -alpha_block_size 1.0 
> -pr_percentage 1.0 
> -exchange_interval 200 
> -num_exchange_indivuduals 2 
> -reset_interval 600 
> Seed: 2700001 
> Stop rule: GENERATIONS 
> Stop argument: 100 
> Maximum time (s): 60.0 
------------------------------------------------------ 
[2020-03-05 12:45:18.627376] Reading TSP data... Number of nodes: 58 
[2020-03-05 12:45:18.651178] Generating initial tour... Initial cost: 30774.0 [2020-03-05 12:45:18.652157] Building BRKGA data... New population size: 580 [2020-03-05 12:45:18.652539] Initializing BRKGA data... [2020-03-05 12:45:18.858128] Warming up... 
[2020-03-05 12:45:20.052183] Evolving... * Iteration | Cost | CurrentTime * 1 | 30774 | 0.51 * 74 | 30759 | 43.13 * 78 | 30721 | 45.42 * 79 | 30371 | 46.12 * 81 | 30350 | 47.19 
[2020-03-05 12:46:17.117151] End of optimization 
Total number of iterations: 100 
Last update iteration: 81 
Total optimization time: 57.06
Last update time: 47.19
Large number of iterations between improvements: 73
% Best tour cost: 30350.00
% Best tour: 41 0 29 12 39 24 8 31 19 52 49 3 17 43 23 57 4 26 42 11 56 22 53 54 1 40 34 9 51 50 46 48 2 47 28 35 16 25 18 5 27 32 13 36 33 45 55 44 14 20 38 10 15 21 7 37 30 6 
   Instance,Seed,NumNodes,TotalIterations,TotalTime,LargeOffset,LastUpdateIteration,LastUpdateTime,Cost
   brazil58.dat,2700001,58,100,57.06,73,81,47.19,30350

6. Conclusion

Now we have a good initial understanding of the algorithm including its core concepts. We can also execute the algorithm following steps from the implementation docs. Next steps would be to find a problem of your choice and use this algorithm to solve it. Reading the original paper is also a good option for in-depth details.

References

[1] - The Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking and its real-world applications. Carlos E. Andrade, Rodrigo F. Toso, José F. Gonçalves, Mauricio G.C. Resende

[2] - Genetic Algorithms and Random Keys for Sequencing and Optimization. James C. Bean

[3] - Comparing LSB Color Image Steganography by using Performance Measurement Concept. Aura Conci, André Luiz Brazil.