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.