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

Algoritmos de Optimización

Siguiente ►
►

Introducción

Los algoritmos de optimización son fundamentales en la inteligencia artificial (IA) y el aprendizaje automático. Estos algoritmos se utilizan para encontrar la mejor solución (o una solución suficientemente buena) a un problema dado, minimizando o maximizando una función objetivo. En esta sección, exploraremos los conceptos básicos de los algoritmos de optimización, sus tipos y algunos ejemplos prácticos.

Conceptos Clave

  1. Función Objetivo: La función que se desea minimizar o maximizar.
  2. Espacio de Búsqueda: El conjunto de todas las posibles soluciones.
  3. Variables de Decisión: Las variables que se ajustan para optimizar la función objetivo.
  4. Restricciones: Condiciones que deben cumplirse para que una solución sea válida.
  5. Óptimo Global: La mejor solución en todo el espacio de búsqueda.
  6. Óptimo Local: La mejor solución en una región específica del espacio de búsqueda.

Tipos de Algoritmos de Optimización

  1. Optimización Exacta

Estos algoritmos garantizan encontrar la solución óptima. Son adecuados para problemas pequeños o medianos debido a su alta complejidad computacional.

  • Programación Lineal (PL): Utilizada para problemas donde la función objetivo y las restricciones son lineales.
  • Programación Entera (PE): Similar a la PL, pero las variables de decisión deben ser enteras.
  • Programación Dinámica: Descompone un problema en subproblemas más pequeños y los resuelve de manera recursiva.

  1. Optimización Heurística

Estos algoritmos no garantizan encontrar la solución óptima, pero pueden encontrar soluciones suficientemente buenas en un tiempo razonable.

  • Algoritmos Genéticos (AG): Basados en la evolución natural, utilizan operadores como selección, cruce y mutación.
  • Recocido Simulado (Simulated Annealing): Inspirado en el proceso de enfriamiento de metales, permite escapar de óptimos locales.
  • Optimización por Enjambre de Partículas (PSO): Basado en el comportamiento social de los animales, como bandadas de aves.

  1. Optimización Metaheurística

Combina varias heurísticas para mejorar la búsqueda de soluciones.

  • Algoritmos de Colonia de Hormigas (ACO): Basados en el comportamiento de las hormigas en la búsqueda de alimento.
  • Algoritmos de Búsqueda Tabú: Utilizan una memoria para evitar ciclos y mejorar la exploración del espacio de búsqueda.

Ejemplo Práctico: Algoritmo Genético

Descripción del Problema

Supongamos que queremos maximizar la función \( f(x) = x^2 \) en el intervalo \([0, 31]\).

Pasos del Algoritmo Genético

  1. Inicialización: Crear una población inicial de soluciones aleatorias.
  2. Evaluación: Calcular la aptitud de cada solución utilizando la función objetivo.
  3. Selección: Seleccionar las mejores soluciones para reproducirse.
  4. Cruce: Combinar pares de soluciones para crear nuevas soluciones.
  5. Mutación: Introducir pequeñas modificaciones aleatorias en las soluciones.
  6. Reemplazo: Reemplazar las soluciones antiguas con las nuevas.
  7. Iteración: Repetir los pasos 2-6 hasta que se cumpla un criterio de parada.

Implementación en Python

import random

# Parámetros del algoritmo
population_size = 10
generations = 20
mutation_rate = 0.01

# Función objetivo
def fitness(x):
    return x ** 2

# Crear una población inicial
def create_population(size):
    return [random.randint(0, 31) for _ in range(size)]

# Selección por torneo
def selection(population):
    return max(random.sample(population, 2), key=fitness)

# Cruce de un punto
def crossover(parent1, parent2):
    point = random.randint(1, 4)
    mask = (1 << point) - 1
    child1 = (parent1 & mask) | (parent2 & ~mask)
    child2 = (parent2 & mask) | (parent1 & ~mask)
    return child1, child2

# Mutación
def mutate(individual):
    if random.random() < mutation_rate:
        point = random.randint(0, 4)
        individual ^= 1 << point
    return individual

# Algoritmo Genético
def genetic_algorithm():
    population = create_population(population_size)
    for _ in range(generations):
        new_population = []
        for _ in range(population_size // 2):
            parent1 = selection(population)
            parent2 = selection(population)
            child1, child2 = crossover(parent1, parent2)
            new_population.extend([mutate(child1), mutate(child2)])
        population = new_population
    return max(population, key=fitness)

# Ejecutar el algoritmo
best_solution = genetic_algorithm()
print(f"Mejor solución: {best_solution}, Aptitud: {fitness(best_solution)}")

Explicación del Código

  1. Inicialización: Se crea una población inicial de soluciones aleatorias.
  2. Evaluación: La función fitness calcula la aptitud de cada solución.
  3. Selección: Se utiliza la selección por torneo para elegir los padres.
  4. Cruce: Se realiza un cruce de un punto para generar nuevos individuos.
  5. Mutación: Se aplica una mutación aleatoria a los individuos.
  6. Iteración: Se repiten los pasos anteriores durante un número fijo de generaciones.

Ejercicio Práctico

Problema

Implementa un algoritmo de recocido simulado para encontrar el mínimo de la función \( f(x) = (x - 3)^2 \) en el intervalo \([-10, 10]\).

Pistas

  1. Inicializa una solución aleatoria en el intervalo \([-10, 10]\).
  2. Define una función de temperatura que disminuya con el tiempo.
  3. En cada iteración, genera una nueva solución cercana a la actual.
  4. Acepta la nueva solución con una probabilidad que depende de la diferencia de aptitud y la temperatura.

Solución

import math

# Parámetros del algoritmo
initial_temp = 100
cooling_rate = 0.99
iterations = 1000

# Función objetivo
def fitness(x):
    return (x - 3) ** 2

# Generar una nueva solución cercana
def neighbor(x):
    return x + random.uniform(-1, 1)

# Algoritmo de Recocido Simulado
def simulated_annealing():
    current_solution = random.uniform(-10, 10)
    current_fitness = fitness(current_solution)
    temp = initial_temp
    
    for _ in range(iterations):
        new_solution = neighbor(current_solution)
        new_fitness = fitness(new_solution)
        
        if new_fitness < current_fitness or random.random() < math.exp((current_fitness - new_fitness) / temp):
            current_solution = new_solution
            current_fitness = new_fitness
        
        temp *= cooling_rate
    
    return current_solution, current_fitness

# Ejecutar el algoritmo
best_solution, best_fitness = simulated_annealing()
print(f"Mejor solución: {best_solution}, Aptitud: {best_fitness}")

Explicación del Código

  1. Inicialización: Se inicia con una solución aleatoria y una temperatura alta.
  2. Generación de Vecinos: Se genera una nueva solución cercana a la actual.
  3. Aceptación de Soluciones: Se acepta la nueva solución si es mejor o con una probabilidad que depende de la temperatura.
  4. Enfriamiento: La temperatura disminuye en cada iteración.

Conclusión

En esta sección, hemos explorado los conceptos básicos de los algoritmos de optimización, sus tipos y algunos ejemplos prácticos. Los algoritmos de optimización son herramientas poderosas en la IA y el aprendizaje automático, permitiendo encontrar soluciones eficientes a problemas complejos. En la siguiente sección, profundizaremos en los conceptos básicos del aprendizaje automático.

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