Optimización del Problema del Viajante mediante Enfriamiento Simulado en Python

Implementación de la Clase Viajante_BL

A continuación se presenta la definición de la clase para resolver el Problema del Viajante (TSP) utilizando técnicas de Búsqueda Local.

class Viajante_BL(Problema_Busqueda_Local):
    def __init__(self, ciudades, distancia):
        super().__init__()
        self.ciudades = ciudades
        self.distancia = distancia

    def genera_estado_inicial(self):
        estado = self.ciudades[:]  # Copia para no modificar self.ciudades
        random.shuffle(estado)
        return estado

    def genera_sucesor(self, estado):
        n = len(estado)
        i = random.choice(range(n))
        j = random.choice(range(n))
        while j == i:  # Nos aseguramos de que sean distintas
            j = random.choice(range(n))
        if i > j:
            i, j = j, i  # Para que i sea siempre el menor
        return estado[:i] + estado[i:j+1][::-1] + estado[j+1:]

    def valoracion(self, estado):
        n = len(estado)
        total = 0
        for k in range(n):
            total += self.distancia(estado[k], estado[(k+1) % n])
        return total

Ejercicios y Casos de Prueba

Ejercicios de Configuración y Sorteo

Ej2: Configuración del viajante para la región de Andalucía:

viajante_andalucia = Viajante_BL(list(andalucia.keys()), lambda c1, c2: distancia_euc2D(c1, c2, andalucia))

Ej3: Función para determinar el éxito de un evento basado en una probabilidad p:

def sorteo(p):
    return random.random() < p

Algoritmo de Enfriamiento Simulado

Ej5: Implementación del algoritmo de Enfriamiento Simulado (Simulated Annealing) para optimización combinatoria:

def enfriamiento_simulado(problema, t_inicial, factor_descenso, n_enfriamientos, n_iteraciones):
    actual = problema.genera_estado_inicial()
    valor_actual = problema.valoracion(actual)
    mejor = actual
    valor_mejor = valor_actual
    T = t_inicial
    for _ in range(n_enfriamientos):
        for _ in range(n_iteraciones):
            candidata = problema.genera_sucesor(actual)
            valor_candidata = problema.valoracion(candidata)
            if aceptar_e_s(valor_candidata, valor_actual, T, problema.mejor):
                actual = candidata
                valor_actual = valor_candidata
                if problema.mejor(valor_actual, valor_mejor):
                    mejor = actual
                    valor_mejor = valor_actual
        T *= factor_descenso
    return (mejor, valor_mejor)

Ej4: Función de aceptación para el criterio de Enfriamiento Simulado:

def aceptar_e_s(valor_candidata, valor_actual, T, mejor):
    if mejor(valor_candidata, valor_actual):
        return True
    else:
        incremento = abs(valor_candidata - valor_actual)
        p = math.exp(-incremento / T)
        return sorteo(p)

Ej6: Ejecución del algoritmo con parámetros específicos:

enfriamiento_simulado(viajante_andalucia, 100, 0.95, 100, 100)

Generación de Puntos y Estructuras Geométricas

Ej7: Funciones para crear instancias del problema basadas en coordenadas de puntos:

def crea_viajante_puntos(puntos):
    coords = {p: p for p in puntos}
    return Viajante_BL(puntos, lambda c1, c2: distancia_euc2D(c1, c2, coords))

def cuadrado_puntos_bl(n):
    puntos = []
    for x in range(n):  # Lado inferior: (0,0) .. (n-1,0)
        puntos.append((x, 0))
    for y in range(n):  # Lado derecho: (n,0) .. (n,n-1)
        puntos.append((n, y))
    for x in range(n, 0, -1):  # Lado superior: (n,n) .. (1,n)
        puntos.append((x, n))
    for y in range(n, 0, -1):  # Lado izquierdo: (0,n) .. (0,1)
        puntos.append((0, y))
    return crea_viajante_puntos(puntos)