Biased Random-Key Genetic Algorithm

By | May 18, 2012

I have been writing the report on the BRKGA meta-heuristic so I will quote a short description I wrote about this genetic algorithm 🙂

We have chosen the Biased Random-Key Genetic Algorithm (BRKGA) meta-heuristic in order to effectively solve this complex optimization problem. Typically, genetic algorithms evolve a population applying the principle of the survival of the fittest. An evolved population results in a new generation. Individuals of the same generation are combined to produce the offspring that makes up the next generation.

Let the population consist of a group of individuals (chromossomes), each being composed by a set of random keys (alleles) that represent a solution and a fitness level. These random keys are real-valued numbers in the interval [0,1]. The combination (mating) between two individuals is done by a parametric uniform crossover technique that consists of randomly choosing which parent passes an allele to the child. Let a decoder consist of a deterministic algorithm that takes as input a random-key vector and returns a feasible solution of the optimization problem and its cost (fitness). This decoder is the only problem-dependent part of the BRKGA algorithm, and hence, it needs to be specifically defined for this RPD problem.
In BRKGA, the generation individuals are created by means of a (1) mating process, a (2) set of high quality chromossomes from the previous generation (called elite), and a (3) set of randomly generated chromossomes(called mutants).

The main difference between Random-Key Genetic Algorithms and BRKGA is that from each generation, it chooses an elite set (2) that is copied unchanged into the following generation (survival of the fittest). Also, in BRKGA, mating is done only between elite individuals and non-elite individuals. The probability of next generation inheriting from the elite parents is therefore bigger. In the creation method (3), mutants are generated in each generation in order to help the algorithm escape from local optima. This means that there is no mutation done during crossover.

In order to map this genetic algorithm into a RPD problem, lets assume that each chromossome is given as many alleles as the number of nodes in our network. Each chromossome will represent a solution to our problem and the decoder function (g) will be used in order to calculate the fitness value of that solution. This fitness value should be directly proportional to the number of needed regenerators needed by the solution in order for it to be compliant with a certain OSNR level. So, depending on the number of computed generations, the evolution of populations should produce a chromossome which solution would need a minimal number of regenerators close to the optimal ILP solution.

Et voila!

Leave a Reply