# Biased Random Key Genetic Algorithm (BRKGA)¶

A great and very informative presentation about BRKGAs can be found here. BRKGAs are known to perform well-known on combinatorial problems.

Instead of customizing evolutionary operators a decoding has to be defined. Therefore, the evolution takes place simply on real-valued variables.

Let us define a permutation problem which derives an order by sorting a real-valued variables:

[1]:

import numpy as np
from pymoo.model.problem import Problem

class MyProblem(Problem):

def __init__(self, my_list):
self.correct = np.argsort(my_list)
super().__init__(n_var=len(my_list), n_obj=1, n_constr=0, xl=0, xu=1, elementwise_evaluation=True)

def _evaluate(self, x, out, *args, **kwargs):
pheno = np.argsort(x)
out["F"] = - float((self.correct == pheno).sum())
out["pheno"] = pheno
out["hash"] = hash(str(pheno))


Since duplicate eliminates is a very import aspect for evolutionary algorithm, we have to make sure all duplicates with respect to the permutation (and not to the real values) are filtered out.

[2]:

from pymoo.model.duplicate import ElementwiseDuplicateElimination

class MyElementwiseDuplicateElimination(ElementwiseDuplicateElimination):

def is_equal(self, a, b):
return a.get("hash")[0] == b.get("hash")[0]


Then, we define a problem which has to sort a list by their values.

[3]:

np.random.seed(2)
list_to_sort = np.random.random(20)
problem = MyProblem(list_to_sort)
print("Sorted by", np.argsort(list_to_sort))

Sorted by [ 1 19 12 14  6  9  8  5  4  3  0 17 13 11  2  7 10 15 18 16]


Finally, we use BRKGA to obtained the sorted list:

[4]:

from pymoo.algorithms.so_brkga import BRKGA
from pymoo.optimize import minimize

algorithm = BRKGA(
n_elites=200,
n_offsprings=700,
n_mutants=100,
bias=0.7,
eliminate_duplicates=MyElementwiseDuplicateElimination())

res = minimize(problem,
algorithm,
("n_gen", 75),
seed=1,
verbose=False)

print("Best solution found: \nX = %s\nF = %s" % (res.X, res.F))
print("Solution", res.opt.get("pheno")[0])
print("Optimum ", np.argsort(list_to_sort))

Best solution found:
X = [0.62512107 0.00210869 0.73537788 0.60261201 0.43045971 0.38763854
0.19209895 0.80429496 0.35157945 0.25393386 0.80567794 0.73484463
0.10660141 0.66239025 0.1506689  0.92465587 0.98896201 0.63240497
0.94057641 0.07739991]
F = [-20.]
Solution [ 1 19 12 14  6  9  8  5  4  3  0 17 13 11  2  7 10 15 18 16]
Optimum  [ 1 19 12 14  6  9  8  5  4  3  0 17 13 11  2  7 10 15 18 16]


## API¶

class pymoo.algorithms.so_brkga.BRKGA(self, n_elites=200, n_offsprings=700, n_mutants=100, bias=0.7, sampling=FloatRandomSampling(), survival=None, display=SingleObjectiveDisplay(), eliminate_duplicates=False, **kwargs)
Parameters
n_elitesint

Number of elite individuals

n_offspringsint

Number of offsprings to be generated through mating of an elite and a non-elite individual

n_mutantsint

Number of mutations to be introduced each generation

biasfloat

Bias of an offspring inheriting the allele of its elite parent

eliminate_duplicatesbool or class

The duplicate elimination is more important if a decoding is used. The duplicate check has to be performed on the decoded variable and not on the real values. Therefore, we recommend passing a DuplicateElimination object. If eliminate_duplicates is simply set to True, then duplicates are filtered out whenever the objective values are equal.