Algoritmos genéticos

9.1 Introducción a los algoritmos genéticos.

Los algoritmos genéticos (GA) son un método de optimización y búsqueda, inspirado en el proceso de selección natural, que imita procesos evolutivos biológicos.

Se utilizan para resolver problemas complejos donde los métodos tradicionales pueden ser ineficaces. Estos algoritmos utilizan mecanismos de selección, cruzamiento (crossover) y mutaciones para evolucionar soluciones.

Principios de funcionamiento:

1. Inicialización:

Se crea una población inicial de posibles soluciones (cromosomas). Cada solución se codifica como una cadena (cadena de bits, cadena de caracteres u otras estructuras).

2 Función de aptitud (fitness function):

Evalúa la calidad de cada solución en la población.

3. Evaluación:

Cada solución (individuo) se evalúa utilizando la función de aptitud (fitness function), que determina qué tan bien la solución resuelve el problema.

4. Selección:

Las soluciones con mejor aptitud tienen más probabilidades de ser seleccionadas para reproducción. A menudo se utilizan métodos como la selección de ruleta (roulette wheel selection), selección por torneo (tournament selection) y selección por rango (rank selection).

5. Cruzamiento:

Las soluciones seleccionadas (padres) se combinan para crear nuevas soluciones (hijos). El crossover puede ser de un punto, de dos puntos o de múltiples puntos.

6. Mutación:

Se aplican cambios aleatorios en las nuevas soluciones (mutaciones) para introducir diversidad. Esto ayuda al algoritmo a evitar mínimos locales.

7. Reemplazo:

La nueva población reemplaza a la antigua, y el proceso se repite hasta que se cumpla la condición de parada (por ejemplo, alcanzar un número determinado de generaciones o alcanzar una aptitud determinada).

Ventajas y desventajas

Ventajas:

• Amplia gama de aplicaciones: Se pueden aplicar para resolver diversos problemas, incluidos aquellos donde los métodos analíticos no funcionan.
• Optimización global: Son capaces de encontrar óptimos globales en espacios multidimensionales y complejos.
• Flexibilidad: Se pueden usar con cualquier función de aptitud.

Desventajas:

• Altos costos computacionales: Requieren recursos computacionales significativos, especialmente para poblaciones grandes y problemas complejos.
• Dificultades en la configuración de parámetros: Ajustar los parámetros (tamaño de la población, probabilidad de mutación y crossover) puede ser complicado y afectar significativamente el rendimiento.
• Falta de garantía de solución óptima: No hay garantía de que la solución encontrada sea globalmente óptima.

De hecho, el algoritmo genético es una heurística muy eficaz. No garantiza que se encuentre la mejor solución, aunque tenga acceso a todos los datos. Pero para situaciones complejas y enormes volúmenes de datos, ofrece rápidamente una solución cercana a la ideal.

9.2 Ejemplo de aplicación

Consideremos un ejemplo de aplicación de un algoritmo genético para optimizar una función.

import random

# Parámetros del algoritmo genético
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# Definición de la función de aptitud
def fitness_function(x):
    return -x**2 + 10*x
            
# Inicialización de la población
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# Selección (selección por torneo)
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# Cruzamiento (un punto)
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# Mutación
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# Ciclo principal del algoritmo genético
population = initialize_population(POPULATION_SIZE)
            
for generation in range(GENERATIONS):
    new_population = []
    for _ in range(POPULATION_SIZE):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        offspring = crossover(parent1, parent2)
        offspring = mutate(offspring)
        new_population.append(offspring)
    population = new_population
            
# Salida de la mejor solución
best_individual = max(population, key=fitness_function)
print("La mejor solución:", best_individual)
print("Valor de la función:", fitness_function(best_individual))
            
        

Ventajas y desventajas

9.3 Optimización de una función multidimensional

Tarea:

Encontrar el valor mínimo de una función multidimensional.

Solución:

Usamos la plantilla anterior

import numpy as np

def fitness_function(x):
    return np.sum(x ** 2)
            
def create_individual(dim):
    return np.random.uniform(-10, 10, dim)
            
def create_population(pop_size, dim):
return np.array([create_individual(dim) for _ in range(pop_size)])
            
def select_individuals(population, fitness, num_parents):
    parents = np.empty((num_parents, population.shape[1]))
    for parent_num in range(num_parents):
        min_fitness_idx = np.where(fitness == np.min(fitness))
        min_fitness_idx = min_fitness_idx[0][0]
        parents[parent_num, :] = population[min_fitness_idx, :]
        fitness[min_fitness_idx] = float('inf')
    return parents
            
def crossover(parents, offspring_size):
    offspring = np.empty(offspring_size)
    crossover_point = np.uint8(offspring_size[1] / 2)
    for k in range(offspring_size[0]):
        parent1_idx = k % parents.shape[0]
        parent2_idx = (k + 1) % parents.shape[0]
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
    return offspring
            
def mutate(offspring, mutation_rate):
    for idx in range(offspring.shape[0]):
        if np.random.rand() < mutation_rate:
            random_value = np.random.uniform(-1.0, 1.0, 1)
            offspring[idx, 4] = offspring[idx, 4] + random_value
    return offspring
            
def genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations):
    population = create_population(pop_size, dim)
    for generation in range(num_generations):
        fitness = np.array([fitness_function(ind) for ind in population])
        parents = select_individuals(population, fitness, num_parents)
        offspring_crossover = crossover(parents, (pop_size - parents.shape[0], dim))
        offspring_mutation = mutate(offspring_crossover, mutation_rate)
        population[0:parents.shape[0], :] = parents
        population[parents.shape[0]:, :] = offspring_mutation
    best_solution = population[np.argmin(fitness)]
    return best_solution
# Ejemplo de uso:
dim = 10
pop_size = 100
num_parents = 20
mutation_rate = 0.01
num_generations = 1000
best_solution = genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations)
print(f"La mejor solución: {best_solution}")