Skip to content

BRKGA: Biased Random-Key Genetic Algorithm

El algoritmo BRKGA (Algoritmo Genético con Claves Aleatorias y Tendencia), es una variante de los algoritmos genéticos diseñada para resolver problemas combinatorios mediante una representación basada en vectores de números reales llamados "random keys". Es especialmente útil cuando se requiere mantener una codificación continua que luego se decodifica a una solución entera o estructurada.

¿Qué son las Random Keys?

Una random key es un número real en el intervalo \([0, 1]\). En BRKGA, cada individuo se representa como un vector de claves aleatorias:

\[ \mathbf{r} = [r_1, r_2, \dots, r_n] \quad \text{con } r_i \in [0,1] \]

Este vector es luego traducido (decodificado) a una solución factible usando una función determinista conocida como decodificador.

Aplicación al Clustering

Para clustering con restricciones, la interpretación de las random keys puede realizarse, por ejemplo, asignando:

  • Clusters según el orden de las claves (e.g., ordenarlas y asignar los primeros \(K\) valores como centroides).
  • Clases o grupos según intervalos del valor de cada clave.
  • Operadores personalizados para respetar restricciones ML/CL.

Funcionamiento del BRKGA

El BRKGA modifica el esquema de los algoritmos genéticos clásicos de la siguiente manera:

1. Representación

  • Los individuos son vectores de claves aleatorias.
  • Se requiere una función de decodificación específica del problema.

2. Población Inicial

  • Se generan \(P\) individuos con claves aleatorias en \([0,1]\).

3. Evaluación

  • Cada individuo se decodifica a una solución del problema.
  • Se evalúa su calidad mediante una función objetivo (fitness).

4. Selección

  • Se selecciona un subconjunto de élite \(E \subset P\) con los mejores individuos.

5. Cruce Sesgado (Biased Crossover)

  • Se generan nuevos individuos combinando claves de:
  • Un padre de la élite.
  • Un padre aleatorio (no élite).
  • Con probabilidad \(p\) se toma la clave del padre élite, y con \(1 - p\) del padre no élite.
\[ r_i^\text{hijo} = \begin{cases} r_i^\text{élite} & \text{con probabilidad } p \\ r_i^\text{no élite} & \text{con probabilidad } 1-p \end{cases} \]

6. Mutación

  • Algunos individuos nuevos se generan completamente al azar (mutantes).

7. Reemplazo

  • La población siguiente se construye con:
  • Todos los individuos élite.
  • Individuos generados por cruce sesgado.
  • Mutantes aleatorios.

8. Criterio de Parada

  • Número máximo de generaciones, convergencia o tiempo límite.

BRKGA en Clustering con Restricciones

En problemas de clustering con restricciones, BRKGA se puede adaptar de la siguiente forma:

  • Cada clave aleatoria define un orden o peso relativo de asignación de puntos a clusters.
  • El decodificador debe respetar o penalizar las restricciones must-link y cannot-link.
  • La función de fitness incluye:
  • Cohesión intra-cluster.
  • Penalización por restricciones violadas.

Parámetros Típicos

  • Tamaño de población \(P = 100\)–200.
  • Porcentaje de élite: 15%–25%.
  • Porcentaje de mutantes: 10%–20%.
  • Probabilidad de herencia del élite: \(p \in [0.6, 0.8]\).

Referencia

Gonçalves, J.F., Resende, M.G.C. (2011). "Biased Random-Key Genetic Algorithms for Combinatorial Optimization". Journal of Heuristics, 17(5), 487–525.

API

Bases: GeneticClustering

BRKGA (Biased Random-Key Genetic Algorithm).

BRKGA is a genetic algorithm adapted for clustering with constraints. It uses a random-key encoding to represent solutions and biased genetic operators to generate new populations that optimize data partitioning.

This algorithm inherits from the base class GeneticClustering.

Attributes:

Name Type Description
n_clusters int

Number of target clusters.
init str

Method for initializing centroids.
max_iter int

Maximum number of iterations.
tol float

Tolerance for the convergence criterion.
constraints Sequence[Sequence]

Must-link and cannot-link constraints.
population_size int

Size of the genetic population.
percentage_elite float

Percentage of individuals considered elite.
probability_mutation float

Percentage of mutants in each generation.
pbt_inherit float

Probability of inheritance in the crossover operator.
Source code in clustlib/gac/brkga.py 
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
class BRKGA(GeneticClustering):
    """BRKGA (Biased Random-Key Genetic Algorithm).

    BRKGA is a genetic algorithm adapted for clustering with constraints.
    It uses a random-key encoding to represent solutions and biased genetic operators
    to generate new populations that optimize data partitioning.

    This algorithm inherits from the base class GeneticClustering.

    Attributes:
        n_clusters (int): Number of target clusters.
        init (str): Method for initializing centroids.
        max_iter (int): Maximum number of iterations.
        tol (float): Tolerance for the convergence criterion.
        constraints (Sequence[Sequence]): Must-link and cannot-link constraints.
        population_size (int): Size of the genetic population.
        percentage_elite (float): Percentage of individuals considered elite.
        probability_mutation (float): Percentage of mutants in each generation.
        pbt_inherit (float): Probability of inheritance in the crossover operator.

    """

    def __init__(
        self,
        constraints: Sequence[Sequence],
        n_clusters=8,
        init="random",
        max_iter=300,
        tol=1e-4,
        population_size=20,
        percentage_elite=0.3,
        probability_mutation=0.2,
        pbt_inherit=0.1,
    ):
        self.n_clusters = n_clusters
        self.init = init
        self.max_iter = max_iter
        self.tol = tol
        self.centroids = None
        self.constraints = constraints
        self._population_size = population_size
        self._dim = constraints.shape[0]

        self._num_elite = math.ceil(self._population_size * percentage_elite)
        self._num_mutants = math.ceil(self._population_size * probability_mutation)

        self._pbt_inherit = pbt_inherit

    def _update(self):
        mutants = self.mutation()

        normal_population = (
            self.population.shape[0] - self._num_elite - self._num_mutants
        )
        normal_population = max(normal_population, 0)
        if normal_population > 0:
            offspring = self.offspring(normal_population)
            self.population[self._num_elite :, :] = np.vstack((offspring, mutants))
        else:
            self.population[self._num_elite :, :] = mutants

        self.calculate_fitness()
        self._labels = self.decode_solution(self.population[0, :])
        self.centroids = self.get_centroids(self._labels)

    def _convergence(self):
        if self._delta is None:
            logger.debug("Delta is None, convergence cannot be checked.")
            return False

        return np.linalg.norm(self._delta) < self.tol

    def _fit(self):
        """Fits the BRKGA model to the given data.

        Args:
            X (ndarray): Input data matrix.
            y (ndarray, optional): True labels if available (not used).
            logger (Logger, optional): Logging object for process tracking.

        Returns:
            self: Fitted object.

        """
        self.create_population()

        iteration = 0
        while not self.stop_criteria(iteration):
            self.update()
            iteration += 1

        return self

    def crossover(self, parent1, parent2):
        """Realiza cruce entre dos padres para generar un nuevo cromosoma.

        Args:
            parent1 (ndarray): Cromosoma del padre elitista.
            parent2 (ndarray): Cromosoma del padre no elitista.

        Returns:
            ndarray: Nuevo cromosoma generado.

        """
        v = np.where(np.random.rand(self._dim) > self._pbt_inherit)[0]
        new_cromosome = parent1
        new_cromosome[v] = parent2[v]
        return new_cromosome

    def offspring(self, offspring_size):
        """Genera descendencia cruzando padres elite con no-elite.

        Args:
            offspring_size (int): Número de descendientes a generar.

        Returns:
            ndarray: Matriz con la descendencia generada.

        """
        elite_idx = np.random.randint(self._num_elite, size=offspring_size)
        non_elite_idx = np.random.randint(
            low=self._num_elite, high=self._population_size, size=offspring_size
        )
        offspring = np.empty((offspring_size, self._dim))

        elites = self.population[elite_idx]
        non_elites = self.population[non_elite_idx]

        i = 0
        for elite, non_elite in zip(elites, non_elites):
            offspring[i, :] = self.crossover(elite, non_elite)
            i += 1

        return offspring

    def mutation(self):
        """Crea una nueva generación de individuos mutantes.

        Returns:
            ndarray: Matriz de cromosomas mutantes.

        """
        return np.random.rand(self._num_mutants, self._dim)

crossover(parent1, parent2)

Realiza cruce entre dos padres para generar un nuevo cromosoma.

Parameters:

Name Type Description Default
parent1 ndarray

Cromosoma del padre elitista.

 required
parent2 ndarray

Cromosoma del padre no elitista.

 required

Returns:

Name Type Description
ndarray

Nuevo cromosoma generado.
Source code in clustlib/gac/brkga.py 
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
def crossover(self, parent1, parent2):
    """Realiza cruce entre dos padres para generar un nuevo cromosoma.

    Args:
        parent1 (ndarray): Cromosoma del padre elitista.
        parent2 (ndarray): Cromosoma del padre no elitista.

    Returns:
        ndarray: Nuevo cromosoma generado.

    """
    v = np.where(np.random.rand(self._dim) > self._pbt_inherit)[0]
    new_cromosome = parent1
    new_cromosome[v] = parent2[v]
    return new_cromosome

mutation()

Crea una nueva generación de individuos mutantes.

Returns:

Name Type Description
ndarray

Matriz de cromosomas mutantes.
Source code in clustlib/gac/brkga.py 
147
148
149
150
151
152
153
154
def mutation(self):
    """Crea una nueva generación de individuos mutantes.

    Returns:
        ndarray: Matriz de cromosomas mutantes.

    """
    return np.random.rand(self._num_mutants, self._dim)

offspring(offspring_size)

Genera descendencia cruzando padres elite con no-elite.

Parameters:

Name Type Description Default
offspring_size int

Número de descendientes a generar.

 required

Returns:

Name Type Description
ndarray

Matriz con la descendencia generada.
Source code in clustlib/gac/brkga.py 
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
def offspring(self, offspring_size):
    """Genera descendencia cruzando padres elite con no-elite.

    Args:
        offspring_size (int): Número de descendientes a generar.

    Returns:
        ndarray: Matriz con la descendencia generada.

    """
    elite_idx = np.random.randint(self._num_elite, size=offspring_size)
    non_elite_idx = np.random.randint(
        low=self._num_elite, high=self._population_size, size=offspring_size
    )
    offspring = np.empty((offspring_size, self._dim))

    elites = self.population[elite_idx]
    non_elites = self.population[non_elite_idx]

    i = 0
    for elite, non_elite in zip(elites, non_elites):
        offspring[i, :] = self.crossover(elite, non_elite)
        i += 1

    return offspring