El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia

HOME

La Optimización de Colonia de Hormigas (ACO, por sus siglas en inglés) es una técnica de optimización inspirada en el comportamiento de las hormigas en la naturaleza. Las hormigas encuentran el camino más corto entre su colonia y una fuente de alimento mediante la deposición de feromonas, que guían a otras hormigas hacia la fuente de alimento. Este comportamiento colectivo y descentralizado se puede modelar para resolver problemas complejos de optimización.

Conceptos Básicos

Feromonas: Las hormigas depositan una sustancia química llamada feromona en su camino, que sirve como señal para otras hormigas.
Evaporación de Feromonas: Con el tiempo, la cantidad de feromona en un camino se evapora, lo que evita la convergencia prematura a soluciones subóptimas.
Heurística: Información adicional que puede guiar a las hormigas en su búsqueda, como la distancia entre nodos en un grafo.
Exploración y Explotación: Las hormigas deben equilibrar entre explorar nuevos caminos y explotar caminos conocidos con alta concentración de feromonas.

Algoritmo Básico de ACO

Inicialización:
- Inicializar las feromonas en todos los caminos.
- Definir parámetros como el número de hormigas, la tasa de evaporación de feromonas, y el número de iteraciones.
Construcción de Soluciones:
- Cada hormiga construye una solución moviéndose de nodo en nodo, guiada por la cantidad de feromonas y la heurística.
Actualización de Feromonas:
- Evaporar una fracción de las feromonas en todos los caminos.
- Añadir feromonas en los caminos utilizados por las hormigas, proporcionalmente a la calidad de la solución encontrada.
Iteración:
- Repetir los pasos de construcción de soluciones y actualización de feromonas hasta alcanzar el criterio de parada (número de iteraciones o convergencia).

Ejemplo Práctico: Problema del Viajante de Comercio (TSP)

Descripción del Problema

El Problema del Viajante de Comercio (TSP) consiste en encontrar el camino más corto que visita una serie de ciudades exactamente una vez y regresa a la ciudad de origen.

Implementación en Python

import numpy as np

# Parámetros del algoritmo
num_hormigas = 10
num_ciudades = 5
alpha = 1.0  # Importancia de las feromonas
beta = 2.0   # Importancia de la heurística (inverso de la distancia)
rho = 0.5    # Tasa de evaporación de feromonas
Q = 100      # Cantidad de feromonas depositadas

# Matriz de distancias entre ciudades (simétrica)
distancias = np.array([
    [0, 2, 9, 10, 7],
    [2, 0, 6, 4, 3],
    [9, 6, 0, 8, 5],
    [10, 4, 8, 0, 6],
    [7, 3, 5, 6, 0]
])

# Inicialización de feromonas
feromonas = np.ones((num_ciudades, num_ciudades))

def calcular_probabilidades(ciudad_actual, ciudades_no_visitadas):
    numerador = (feromonas[ciudad_actual, ciudades_no_visitadas] ** alpha) * \
                ((1 / distancias[ciudad_actual, ciudades_no_visitadas]) ** beta)
    denominador = np.sum(numerador)
    return numerador / denominador

def construir_solucion():
    solucion = []
    ciudades_no_visitadas = list(range(num_ciudades))
    ciudad_actual = np.random.choice(ciudades_no_visitadas)
    solucion.append(ciudad_actual)
    ciudades_no_visitadas.remove(ciudad_actual)
    
    while ciudades_no_visitadas:
        probabilidades = calcular_probabilidades(ciudad_actual, ciudades_no_visitadas)
        ciudad_siguiente = np.random.choice(ciudades_no_visitadas, p=probabilidades)
        solucion.append(ciudad_siguiente)
        ciudades_no_visitadas.remove(ciudad_siguiente)
        ciudad_actual = ciudad_siguiente
    
    return solucion

def calcular_longitud(solucion):
    longitud = 0
    for i in range(len(solucion) - 1):
        longitud += distancias[solucion[i], solucion[i + 1]]
    longitud += distancias[solucion[-1], solucion[0]]  # Regreso a la ciudad de origen
    return longitud

def actualizar_feromonas(solutions, lengths):
    global feromonas
    feromonas *= (1 - rho)
    for solucion, longitud in zip(solutions, lengths):
        for i in range(len(solucion) - 1):
            feromonas[solucion[i], solucion[i + 1]] += Q / longitud
        feromonas[solucion[-1], solucion[0]] += Q / longitud

# Algoritmo principal
mejor_solucion = None
mejor_longitud = float('inf')

for iteracion in range(100):
    soluciones = []
    longitudes = []
    
    for _ in range(num_hormigas):
        solucion = construir_solucion()
        longitud = calcular_longitud(solucion)
        soluciones.append(solucion)
        longitudes.append(longitud)
        
        if longitud < mejor_longitud:
            mejor_solucion = solucion
            mejor_longitud = longitud
    
    actualizar_feromonas(soluciones, longitudes)
    print(f"Iteración {iteracion + 1}: Mejor longitud = {mejor_longitud}")

print("Mejor solución encontrada:", mejor_solucion)
print("Longitud de la mejor solución:", mejor_longitud)

Explicación del Código

Inicialización:
- Se definen los parámetros del algoritmo, como el número de hormigas, la importancia de las feromonas (alpha), la importancia de la heurística (beta), la tasa de evaporación de feromonas (rho), y la cantidad de feromonas depositadas (Q).
- Se crea una matriz de distancias entre las ciudades y se inicializan las feromonas.
Construcción de Soluciones:
- Cada hormiga construye una solución comenzando en una ciudad aleatoria y eligiendo la siguiente ciudad basada en las probabilidades calculadas a partir de las feromonas y la heurística (inverso de la distancia).
Cálculo de la Longitud de la Solución:
- Se calcula la longitud total del recorrido de cada hormiga.
Actualización de Feromonas:
- Se evapora una fracción de las feromonas en todos los caminos.
- Se añaden feromonas en los caminos utilizados por las hormigas, proporcionalmente a la calidad de la solución encontrada.
Iteración:
- Se repiten los pasos de construcción de soluciones y actualización de feromonas durante un número fijo de iteraciones.

Ejercicios Prácticos

Modificación de Parámetros:
- Modifica los parámetros alpha, beta, rho y Q y observa cómo afectan la convergencia del algoritmo y la calidad de las soluciones encontradas.
Aplicación a Otros Problemas:
- Implementa el algoritmo de ACO para resolver otro problema de optimización, como el problema de la mochila o el problema de asignación de tareas.
Visualización del Proceso:
- Añade visualizaciones para mostrar cómo las hormigas construyen sus soluciones y cómo evolucionan las feromonas en el grafo.

Conclusión

La Optimización de Colonia de Hormigas es una poderosa técnica de optimización inspirada en la naturaleza. Su capacidad para encontrar soluciones cercanas al óptimo en problemas complejos la hace especialmente útil en diversas aplicaciones. A través de la implementación práctica y los ejercicios propuestos, los estudiantes pueden profundizar en su comprensión y habilidades para aplicar ACO en diferentes contextos.

Optimización de Colonia de Hormigas

Conceptos Básicos

Algoritmo Básico de ACO

Ejemplo Práctico: Problema del Viajante de Comercio (TSP)

Descripción del Problema

Implementación en Python

Explicación del Código

Ejercicios Prácticos

Conclusión

Algoritmos Avanzados

Módulo 1: Introducción a los Algoritmos Avanzados

Módulo 2: Algoritmos de Optimización

Módulo 3: Algoritmos en Grafos

Módulo 4: Algoritmos de Búsqueda y Ordenación

Módulo 5: Algoritmos de Aprendizaje Automático

Módulo 6: Casos de Estudio y Aplicaciones

Módulo 7: Proyecto Final