Introducció

L'optimització de colònia de formigues (ACO, per les seves sigles en anglès) és una tècnica d'optimització inspirada en el comportament de les formigues reals. Les formigues utilitzen feromones per comunicar-se i trobar el camí més curt entre el seu niu i una font d'aliment. Aquest comportament ha estat modelat per crear algorismes capaços de resoldre problemes d'optimització complexos.

Conceptes Bàsics

Comportament de les Formigues

Feromones: Les formigues deixen rastres de feromones a mesura que es mouen, que altres formigues poden seguir.
Evaporació de Feromones: Les feromones s'evaporen amb el temps, evitant que els camins antics siguin seguides indefinidament.
Exploració i Explotació: Les formigues exploren nous camins però també exploten els camins coneguts amb altes concentracions de feromones.

Modelatge Matemàtic

Grafo de Solucions: El problema es modela com un grafo on els nodes representen estats i les arestes representen possibles decisions.
Funció de Feromones: Cada aresta té un valor de feromona associat que indica la seva atractivitat.
Actualització de Feromones: Les feromones es reforcen en les arestes utilitzades per les formigues que han trobat solucions de qualitat.

Algorisme ACO

Pseudocodi

Inicialitzar feromones
Mentre no es compleixi el criteri de parada:
    Per cada formiga:
        Construir una solució
        Avaluar la solució
    Actualitzar feromones
Retornar la millor solució trobada

Explicació del Pseudocodi

Inicialització: Es comença amb una quantitat inicial de feromones en totes les arestes.
Construcció de Solucions: Cada formiga construeix una solució seguint les feromones i una funció heurística.
Avaluació: Les solucions construïdes per les formigues es valoren segons una funció objectiu.
Actualització de Feromones: Les feromones es reforcen en les arestes que formen part de les millors solucions, i s'evaporen en les altres.

Exemple Pràctic

Problema del Viatjant de Comerç (TSP)

El TSP és un problema clàssic d'optimització on es busca el camí més curt que visita un conjunt de ciutats exactament una vegada i torna a la ciutat d'origen.

Implementació en Python

import numpy as np

# Paràmetres de l'algorisme
num_formigues = 10
num_ciutats = 5
alpha = 1.0  # Importància de les feromones
beta = 2.0   # Importància de la heurística
rho = 0.5    # Taxa d'evaporació de feromones
Q = 100      # Quantitat de feromones dipositades

# Inicialització de les feromones
feromones = np.ones((num_ciutats, num_ciutats))

# Distàncies entre ciutats (exemple)
distancies = np.array([
    [0, 2, 2, 5, 7],
    [2, 0, 4, 8, 2],
    [2, 4, 0, 1, 3],
    [5, 8, 1, 0, 2],
    [7, 2, 3, 2, 0]
])

def calcular_probabilitats(ciutat_actual, ciutats_no_visitades):
    tau = feromones[ciutat_actual, ciutats_no_visitades]
    eta = 1 / distancies[ciutat_actual, ciutats_no_visitades]
    producte = (tau ** alpha) * (eta ** beta)
    return producte / producte.sum()

def construir_solucio():
    solucio = []
    ciutats_no_visitades = list(range(num_ciutats))
    ciutat_actual = np.random.choice(ciutats_no_visitades)
    solucio.append(ciutat_actual)
    ciutats_no_visitades.remove(ciutat_actual)
    
    while ciutats_no_visitades:
        probabilitats = calcular_probabilitats(ciutat_actual, ciutats_no_visitades)
        ciutat_actual = np.random.choice(ciutats_no_visitades, p=probabilitats)
        solucio.append(ciutat_actual)
        ciutats_no_visitades.remove(ciutat_actual)
    
    return solucio

def avaluar_solucio(solucio):
    cost = 0
    for i in range(len(solucio) - 1):
        cost += distancies[solucio[i], solucio[i + 1]]
    cost += distancies[solucio[-1], solucio[0]]  # Tornar a la ciutat d'origen
    return cost

def actualitzar_feromones(solucions, costos):
    global feromones
    feromones *= (1 - rho)
    for solucio, cost in zip(solucions, costos):
        per_feromona = Q / cost
        for i in range(len(solucio) - 1):
            feromones[solucio[i], solucio[i + 1]] += per_feromona
        feromones[solucio[-1], solucio[0]] += per_feromona

# Algorisme principal
millor_solucio = None
millor_cost = float('inf')

for iteracio in range(100):
    solucions = []
    costos = []
    for _ in range(num_formigues):
        solucio = construir_solucio()
        cost = avaluar_solucio(solucio)
        solucions.append(solucio)
        costos.append(cost)
        if cost < millor_cost:
            millor_solucio = solucio
            millor_cost = cost
    actualitzar_feromones(solucions, costos)

print(f'Millor solució: {millor_solucio}')
print(f'Cost de la millor solució: {millor_cost}')

Explicació del Codi

Inicialització: Es defineixen els paràmetres de l'algorisme i es crea la matriu de feromones.
Construcció de Solucions: Cada formiga construeix una solució basada en les probabilitats calculades a partir de les feromones i les distàncies.
Avaluació: Es calcula el cost de cada solució.
Actualització de Feromones: Les feromones es reforcen en les arestes utilitzades per les millors solucions.

Exercicis Pràctics

Exercici 1: Implementar l'algorisme ACO per un altre problema d'optimització

Descripció: Implementa l'algorisme ACO per resoldre el problema del camí mínim en un grafo.

Solució:

Modela el problema com un grafo.
Defineix les funcions de construcció de solucions, avaluació i actualització de feromones.
Executa l'algorisme i compara els resultats amb altres algorismes de camí mínim.

Exercici 2: Ajustar els Paràmetres de l'Algorisme

Descripció: Experimenta amb diferents valors per als paràmetres alpha, beta, rho i Q per veure com afecten el rendiment de l'algorisme.

Solució:

Crea un conjunt de proves amb diferents combinacions de paràmetres.
Mesura el rendiment de l'algorisme en termes de qualitat de la solució i temps de computació.
Analitza els resultats per determinar els millors paràmetres per al teu problema específic.

Conclusió

L'optimització de colònia de formigues és una tècnica poderosa per resoldre problemes d'optimització complexos. La seva inspiració biològica permet una exploració i explotació eficient de l'espai de solucions. Amb una comprensió adequada dels seus conceptes bàsics i una implementació acurada, es poden obtenir resultats excel·lents en una àmplia varietat de problemes.

Optimització de Colònia de Formigues

Introducció

Conceptes Bàsics

Comportament de les Formigues

Modelatge Matemàtic

Algorisme ACO

Pseudocodi

Explicació del Pseudocodi

Exemple Pràctic

Problema del Viatjant de Comerç (TSP)

Implementació en Python

Explicació del Codi

Exercicis Pràctics

Exercici 1: Implementar l'algorisme ACO per un altre problema d'optimització

Exercici 2: Ajustar els Paràmetres de l'Algorisme

Conclusió

Algoritmes Avançats

Mòdul 1: Introducció als Algoritmes Avançats

Mòdul 2: Algoritmes d'Optimització

Mòdul 3: Algoritmes en Grafs

Mòdul 4: Algoritmes de Cerca i Ordenació

Mòdul 5: Algoritmes d'Aprenentatge Automàtic

Mòdul 6: Casos d'Estudi i Aplicacions

Mòdul 7: Projecte Final