BRKGA: Biased Random Key Genetic Algorithm

Contents

BRKGA: Biased Random Key Genetic Algorithm#

An excellent and very informative presentation about BRKGAs can be found here. BRKGAs are known to perform well on combinatorial problems.

5cb02718f29647db83c82f9063047a3e

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

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

[1]:

import numpy as np

from pymoo.core.problem import ElementwiseProblem


class MyProblem(ElementwiseProblem):

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

    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 an essential aspect for evolutionary algorithms, we have to make sure all duplicates with respect to the permutation (and not to the real values) are filtered out.

[2]:

from pymoo.core.duplicate import ElementwiseDuplicateElimination


class MyElementwiseDuplicateElimination(ElementwiseDuplicateElimination):

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

Then, we define a problem that 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 obtain the sorted list:

[4]:

from pymoo.algorithms.soo.nonconvex.brkga import BRKGA
from pymoo.optimize import minimize

algorithm = BRKGA(
    n_elites=100,
    n_offsprings=300,
    n_mutants=50,
    bias=0.7,
    eliminate_duplicates=MyElementwiseDuplicateElimination())

res = minimize(problem,
               algorithm,
               ("n_gen", 50),
               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.42160356 0.02091566 0.60968035 0.38796652 0.35142922 0.30605207
 0.12643968 0.76278233 0.26019122 0.25382495 0.86947414 0.5933793
 0.08418963 0.58686872 0.12110523 0.93693115 0.96602129 0.53807698
 0.94810887 0.05377791]
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.soo.nonconvex.brkga.BRKGA(self, n_elites=200, n_offsprings=700, n_mutants=100, bias=0.7, sampling=FloatRandomSampling(), survival=None, output=SingleObjectiveOutput(), eliminate_duplicates=False, **kwargs)[source]

Biased Random Key Genetic Algorithm.

Parameters:

  • n_elites – Number of elite individuals.

  • n_offsprings – Number of offsprings generated through mating.

  • n_mutants – Number of mutations introduced each generation.

  • bias – Bias of an offspring inheriting from its elite parent.

  • sampling – Sampling strategy for initial population.

  • survival – Survival selection strategy.

  • output – Output display configuration.

  • eliminate_duplicates – If True, duplicates are filtered by objective values. If a DuplicateElimination object, uses it for custom duplicate checking.

  • **kwargs – Additional keyword arguments.

Contents