Algoritmos genéticos y sus casos de uso en Machine Learning

Este artículo fue publicado como parte del Blogatón de ciencia de datos

Los algoritmos genéticos son algoritmos de búsqueda inspirados en la teoría de la evolución de Darwin en la naturaleza.

• Al simular el proceso de selección natural, reproducción y mutación, los algoritmos genéticos pueden producir soluciones de alta calidad para diversos problemas, incluida la búsqueda y la optimización.

• Mediante el uso efectivo de la Teoría de la Evolución, los algoritmos genéticos pueden superar los problemas que enfrentan los algoritmos tradicionales.

Según la teoría de la evolución de Darwin, una evolución mantiene una población de individuos que varían entre sí (variación). Aquellos que están mejor adaptados a su entorno tienen más posibilidades de sobrevivir, reproducirse y transmitir sus rasgos a la siguiente generación (supervivencia del más apto).

‌¿Cómo funcionan los algoritmos genéticos?

‌Antes de entrar en el funcionamiento de un algoritmo genético, profundicemos en la terminología básica de los algoritmos genéticos.

Cromosoma / individuo

Un cromosoma es una colección de genes. Por ejemplo, un cromosoma se puede representar como una cadena binaria donde cada bit es un gen.

Fuente de la imagen: algoritmo genético práctico con Python, Eyal Wirsansky

población

Dado que un individuo se representa como un cromosoma, una población es una colección de tales cromosomas.

Fuente de la imagen: algoritmo genético práctico con Python, Eyal Wirsansky

Función de fitness

En cada iteración, los individuos se evalúan en función de sus puntuaciones de aptitud que se calculan mediante la función de aptitud.

Las personas que logran un mejor puntaje de aptitud física representan mejores soluciones y es más probable que sean elegidas para cruzar y pasar a la siguiente generación.

Por ejemplo, si se utilizan algoritmos genéticos para la selección de características, entonces la precisión del modelo con esas características seleccionadas sería la función de adecuación si se tratara de un problema de clasificación.

selección

Después de calcular la aptitud de cada individuo de la población, se utiliza un proceso de selección para determinar cuál de los individuos de la población podrá reproducirse y crear la descendencia que formará la próxima generación.

Tipos de métodos de selección disponibles,

Flujo de trabajo general de un algoritmo genético simple

Fuente de la imagen: algoritmos genéticos prácticos con Python, Eyal Wirsansky

¿En qué se diferencian los algoritmos genéticos de los algoritmos tradicionales?

• ‌Un espacio de búsqueda es un conjunto de todas las posibles soluciones al problema. Los algoritmos tradicionales mantienen solo un conjunto en un espacio de búsqueda, mientras que los algoritmos genéticos utilizan varios conjuntos en un espacio de búsqueda (selección de características mediante RFE frente a algoritmos genéticos).

• Los algoritmos tradicionales requieren más información para realizar una búsqueda, mientras que los algoritmos genéticos solo requieren una función objetivo para calcular la aptitud de un individuo.

• Los algoritmos tradicionales no pueden funcionar en paralelo, mientras que los algoritmos genéticos pueden funcionar en paralelo (el cálculo de la aptitud de los individuos es independiente).

• Una gran diferencia en los algoritmos genéticos es que en lugar de operar directamente en soluciones candidatas, los algoritmos genéticos operan en sus representaciones (o codificación), a menudo denominadas cromosomas.

• ‌Los algoritmos tradicionales solo pueden producir una solución al final, mientras que en los algoritmos genéticos se pueden obtener múltiples soluciones óptimas de diferentes generaciones.

• ‌Los algoritmos tradicionales no tienen más probabilidades de producir soluciones óptimas globales, no se garantiza que los algoritmos genéticos produzcan soluciones óptimas globales también, pero es más probable que produzcan soluciones óptimas globales debido a los operadores genéticos como el cruce y la mutación.

• Los algoritmos tradicionales son de naturaleza determinista, mientras que los algoritmos genéticos son de naturaleza probabilística y estocástica.

• Los problemas del mundo real son multimodales (contienen múltiples soluciones óptimas localmente), los algoritmos tradicionales no manejan bien estos problemas mientras que los algoritmos genéticos, con la configuración de parámetros correcta, pueden manejar estos problemas muy bien debido al gran espacio de solución.

Ventajas de los algoritmos genéticos

• Paralelismo

• Optimización global

• Un conjunto más grande de espacio para soluciones

• Requiere menos información

• Proporciona múltiples soluciones óptimas

• Probabilista en la naturaleza

• Representaciones genéticas usando cromosomas

Desventajas de los algoritmos genéticos

‌ Casos de uso de algoritmos genéticos en aprendizaje automático

TPOT(Optimización de canalización basada en árboles) es un marco de Auto-ML que utiliza algoritmos genéticos para optimizar las canalizaciones de aprendizaje automático utilizando el marco de algoritmo genético llamado DEAP (Algoritmos evolutivos distribuidos en Python).

Selección de características usando algoritmos genéticos

Usando algoritmos genéticos, realicemos la selección de características en un conjunto de datos de vino disponible en sklearn.

import random
import pandas as pd
from sklearn.base import clone
from deap.algorithms import eaSimple
from deap import base, creator, tools
from sklearn.datasets import load_wine
from sklearn.metrics import accuracy_score
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split

data = load_wine()
features = pd.DataFrame(
    data.data, columns=data.feature_names
)
target = pd.Series(data.target)

# split the data into train and test
x_train, x_test, y_train, y_test = train_test_split(
    features, target, test_size=0.2, stratify=target
)

model = RandomForestClassifier()

Divida los datos en características y destino y luego divida las características y el destino para entrenamiento y prueba.

def compute_fitness_score(individual):
    """
    Select the features from the individual, train
    and compute the accuracy_score.
    
    Example:
    individual = [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
    The 1 represents the presence of features and
    0 represents the absence of features
    
    """
    column_support = pd.Series(individual).astype(bool)
    global x_train, y_train, x_test, y_test, model
    
    x_train_ = x_train[x_train.columns[column_support]]
    x_test_ = x_test[x_test.columns[column_support]]

    model.fit(x_train_, y_train)
    y_pred = model.predict(x_test_)
    score = accuracy_score(y_test, y_pred)
    
    return score,

Defina la puntuación de fitness. compute_fitness_score toma a un individuo como entrada, por ejemplo, consideremos el siguiente individuo [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1], en esta lista, 1 representa la presencia de esa característica en particular y 0 representa la ausencia de esa característica. Las columnas se seleccionan según el individuo y luego se ajusta el modelo y se calcula la puntuación de precisión. Esta puntuación de precisión es la puntuación de aptitud física de un individuo.

n_genes = x_train.shape[1]
n_generations = 10
n_population = 10
crossover_probability = 0.6
mutation_probability = 0.2


def setup_toolbox():
    # container for individuals
    creator.create('FitnessMax', base.Fitness, weights=(1.0,))
    creator.create('Individual', list, fitness=creator.FitnessMax)

    toolbox = base.Toolbox()
    toolbox.register(
        'individual_generator_function',
        random.randint, 0, 1
    )
    # method to populate individual
    toolbox.register(
        'individual_generator',
        tools.initRepeat,
        creator.Individual,
        toolbox.individual_generator_function,
        n_genes
    )
    # method to create population
    toolbox.register(
        'population_generator',
        tools.initRepeat,
        list,
        toolbox.individual_generator
    )
    # fitness calculation
    toolbox.register(
        'evaluate', compute_fitness_score
    )
    # selection
    toolbox.register(
        'select', tools.selTournament, tournsize=3
    )
    # crossover
    toolbox.register('mate', tools.cxOnePoint)
    # mutation
    toolbox.register(
        'mutate',
        tools.mutFlipBit,
        indpb=mutation_probability
    )
    return toolbox

n_genes representan el número de genes en un individuo que es igual al número de características, n_generations representa el número de generaciones que es igual a 10 y también n_population que representa el número de población. La probabilidad de cruce se establece en 0,6 y la probabilidad de mutación se establece en 0,2.

Toolbox es una clase en un marco deap que nos proporciona las utilidades necesarias para definir individuos, poblaciones y mucho más.

Los pasos realizados en el método setup_toolbox son,

• Primero, definimos un individuo que tiene un puntaje de aptitud asociado a él
• A continuación, definimos una función que genera genes de un individuo, en nuestro caso 0 o 1 en un individuo
• Definimos una función que genera individuos de una población, por ejemplo, [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1] es un individuo en una población.
• A continuación, definimos una función que genera una población, por ejemplo, [[0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1],

  [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1]]es una población de tamaño 2.

• A continuación, definimos una función para evaluación, en nuestro caso usamos la función compute_fitness_score.

• Elegimos el método de selección de torneo para el proceso de selección, un punto de cruce para el proceso de cruce y una mutación de bit de cambio para el proceso de mutación.

# setup deap toolbox
toolbox = setup_toolbox()

# create a population
population = toolbox.population_generator(n_population)

# A simple evolutionary algorithm
final_population, logbook = eaSimple(
    population, 
    toolbox, 
    crossover_probability, 
    mutation_probability, 
    n_generations
)

Primero generamos una población de individuos de tamaño 10. Luego llamamos al método eaSimple en profundidad, que realiza un algoritmo genético simple.

Los argumentos de la función eaSimple,

• El primer argumento es la población
• toolbox es la instancia de la clase Toolbox de deap
• La probabilidad de cruce denota la probabilidad de que un par de individuos se cruce
• La probabilidad de mutación denota la probabilidad de que un individuo mute
• n_generations denota el número de generaciones a evolucionar.

El algoritmo eaSimple funciona de la siguiente manera,

1. Se calcula la aptitud de los individuos en una población
2. Seleccione al individuo más apto utilizando el método de selección del torneo.
3. Cruce de individuos utilizando el método de cruce de un punto
4. Mutar a los individuos usando la mutación flip bit
5. Calcule de nuevo la aptitud de los individuos.
6. Siga los pasos 2 a 5 hasta alcanzar el número deseado de generaciones.

De esta forma, puede realizar la selección de características mediante un algoritmo genético.

Referencias

[1] Algoritmos genéticos prácticos con Python, Eyal Wirsansky

¡Gracias!

Los medios que se muestran en este artículo no son propiedad de DataPeaker y se utilizan a discreción del autor.

Relacionado