pymoo
Latest Version: pymoo==0.4.1

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.

brkga

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.