El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Algoritmos Genéticos

Siguiente ►
►

Introducción

Los algoritmos genéticos (AG) son una clase de algoritmos de optimización inspirados en el proceso de selección natural de la biología. Utilizan técnicas como la herencia, mutación, selección y cruce para generar soluciones a problemas de optimización.

Conceptos Clave

  1. Población: Un conjunto de posibles soluciones al problema.
  2. Cromosoma: Representación de una solución.
  3. Gen: Parte de un cromosoma que representa una característica de la solución.
  4. Fitness: Una función que evalúa qué tan buena es una solución.
  5. Selección: Proceso de elegir los mejores cromosomas para reproducirse.
  6. Cruce (Crossover): Combinar dos cromosomas para producir una nueva solución.
  7. Mutación: Alterar un gen en un cromosoma para introducir variabilidad.

Pasos de un Algoritmo Genético

  1. Inicialización: Crear una población inicial de cromosomas.
  2. Evaluación: Calcular el fitness de cada cromosoma.
  3. Selección: Seleccionar los cromosomas más aptos para reproducirse.
  4. Cruce: Combinar pares de cromosomas para producir descendencia.
  5. Mutación: Aplicar mutaciones aleatorias a algunos genes.
  6. Reemplazo: Formar una nueva población con los descendientes.
  7. Terminación: Repetir los pasos 2-6 hasta que se cumpla un criterio de parada (por ejemplo, un número fijo de generaciones o una solución suficientemente buena).

Ejemplo Práctico

Vamos a implementar un algoritmo genético simple para maximizar la función \( f(x) = x^2 \) en el intervalo [0, 31].

Representación del Cromosoma

Usaremos una cadena binaria de 5 bits para representar los valores de \( x \).

Función de Fitness

La función de fitness será simplemente \( f(x) = x^2 \).

Código en Python

import random

# Parámetros del algoritmo
POPULATION_SIZE = 10
GENES = 5
GENERATIONS = 20
MUTATION_RATE = 0.01

# Función de fitness
def fitness(chromosome):
    x = int(chromosome, 2)
    return x ** 2

# Crear un cromosoma aleatorio
def create_chromosome():
    return ''.join(random.choice('01') for _ in range(GENES))

# Crear una población inicial
def create_population():
    return [create_chromosome() for _ in range(POPULATION_SIZE)]

# Selección por torneo
def selection(population):
    tournament = random.sample(population, 3)
    tournament.sort(key=fitness, reverse=True)
    return tournament[0]

# Cruce de un punto
def crossover(parent1, parent2):
    point = random.randint(1, GENES - 1)
    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]
    return child1, child2

# Mutación
def mutate(chromosome):
    chromosome = list(chromosome)
    for i in range(GENES):
        if random.random() < MUTATION_RATE:
            chromosome[i] = '1' if chromosome[i] == '0' else '0'
    return ''.join(chromosome)

# Algoritmo Genético
def genetic_algorithm():
    population = create_population()
    for generation in range(GENERATIONS):
        new_population = []
        for _ in range(POPULATION_SIZE // 2):
            parent1 = selection(population)
            parent2 = selection(population)
            child1, child2 = crossover(parent1, parent2)
            new_population.append(mutate(child1))
            new_population.append(mutate(child2))
        population = new_population
        best_chromosome = max(population, key=fitness)
        print(f"Generation {generation}: Best Fitness = {fitness(best_chromosome)}")
    return best_chromosome

# Ejecutar el algoritmo
best_solution = genetic_algorithm()
print(f"Best solution: {best_solution} with fitness {fitness(best_solution)}")

Explicación del Código

  1. Parámetros del Algoritmo: Definimos el tamaño de la población, el número de genes por cromosoma, el número de generaciones y la tasa de mutación.
  2. Función de Fitness: Calcula el valor de \( x^2 \) para un cromosoma dado.
  3. Crear Cromosoma y Población: Genera cromosomas aleatorios y una población inicial.
  4. Selección por Torneo: Selecciona el mejor cromosoma de un subconjunto aleatorio de la población.
  5. Cruce de un Punto: Combina dos cromosomas en un punto aleatorio.
  6. Mutación: Cambia aleatoriamente bits en un cromosoma con una probabilidad definida.
  7. Algoritmo Genético: Ejecuta el ciclo de evaluación, selección, cruce y mutación durante un número fijo de generaciones.

Ejercicio Práctico

Ejercicio 1

Implementa un algoritmo genético para maximizar la función \( f(x, y) = x^2 + y^2 \) en el intervalo [0, 31] para \( x \) y [0, 31] para \( y \). Usa una cadena binaria de 10 bits (5 bits para \( x \) y 5 bits para \( y \)).

Solución

# Función de fitness para dos variables
def fitness(chromosome):
    x = int(chromosome[:5], 2)
    y = int(chromosome[5:], 2)
    return x ** 2 + y ** 2

# Crear un cromosoma aleatorio de 10 bits
def create_chromosome():
    return ''.join(random.choice('01') for _ in range(10))

# Algoritmo Genético
def genetic_algorithm():
    population = create_population()
    for generation in range(GENERATIONS):
        new_population = []
        for _ in range(POPULATION_SIZE // 2):
            parent1 = selection(population)
            parent2 = selection(population)
            child1, child2 = crossover(parent1, parent2)
            new_population.append(mutate(child1))
            new_population.append(mutate(child2))
        population = new_population
        best_chromosome = max(population, key=fitness)
        print(f"Generation {generation}: Best Fitness = {fitness(best_chromosome)}")
    return best_chromosome

# Ejecutar el algoritmo
best_solution = genetic_algorithm()
x = int(best_solution[:5], 2)
y = int(best_solution[5:], 2)
print(f"Best solution: x = {x}, y = {y} with fitness {fitness(best_solution)}")

Retroalimentación y Consejos

  1. Errores Comunes:

    • No ajustar correctamente los parámetros del algoritmo (tamaño de la población, tasa de mutación, etc.).
    • No implementar correctamente la función de fitness.
    • No manejar adecuadamente los límites de los valores representados por los cromosomas.

  2. Consejos:

    • Experimenta con diferentes tasas de mutación y tamaños de población para encontrar la configuración óptima.
    • Asegúrate de que la función de fitness esté correctamente definida y probada.
    • Utiliza técnicas de selección más avanzadas como la selección por ruleta o la selección por ranking para mejorar el rendimiento del algoritmo.

Conclusión

En esta sección, hemos aprendido sobre los algoritmos genéticos, sus componentes clave y cómo implementarlos para resolver problemas de optimización. Hemos visto un ejemplo práctico y un ejercicio para reforzar los conceptos aprendidos. En la siguiente sección, exploraremos otros algoritmos de optimización combinatoria.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados