Problema del viajante de Comercio TSP (XII). Método de Recocido Simulado (Simulated Annealing).

El Algoritmo de Recocido Simulado (Simulated Annealing) es una técnica metaheurística inspirada en el proceso de enfriamiento de metales, donde se trata de encontrar una solución cercana al óptimo global para problemas de optimización, como el Problema del Viajero (TSP). El algoritmo funciona de la siguiente manera:

    Inicialización: Comienza con una solución inicial (ruta en el caso del TSP) y una temperatura inicial alta.

    Vecindario: En cada iteración, se genera una nueva solución en el vecindario de la solución actual, por ejemplo, intercambiando dos ciudades en la ruta.

    Aceptación de Soluciones: La nueva solución se acepta automáticamente si es mejor que la solución actual. Si es peor, se acepta con una probabilidad que disminuye a medida que la temperatura baja, permitiendo así escapar de óptimos locales.

    Enfriamiento: La temperatura se reduce gradualmente según una política de enfriamiento, hasta que se alcanza un umbral mínimo, momento en el que se detiene la búsqueda.

    Criterio de Terminación: El algoritmo termina cuando la temperatura es muy baja o después de un número fijo de iteraciones sin mejora significativa.



Código Java (TSP_RecocidoSimulado.java):

package tsp_recocidosimulado;

import java.util.ArrayList;
import java.util.Collections;

public class TSP_RecocidoSimulado {

    public static void main(String[] args) {
        double[][] distanceMatrix = {
            {0, 8128, 823, 8767, 1253, 8827, 5106, 5501, 7097, 8026, 7162, 2260, 4441, 510, 7138, 6509},
            {8128, 0, 6653, 9241, 4344, 7231, 1503, 7145, 6571, 6217, 9412, 9051, 1931, 5817, 8633, 8513},
            {823, 6653, 0, 7900, 1178, 1820, 1262, 678, 9930, 6739, 9965, 908, 9481, 7708, 1874, 9303},
            {8767, 9241, 7900, 0, 589, 9827, 520, 6671, 9859, 4489, 1642, 1045, 1760, 5607, 5053, 7776},
            {1253, 4344, 1178, 589, 0, 5829, 5823, 3482, 9090, 9537, 8507, 3802, 3302, 2944, 8613, 7257},
            {8827, 7231, 1820, 9827, 5829, 0, 9288, 6497, 5442, 4381, 9297, 2086, 1372, 5616, 1981, 3412},
            {5106, 1503, 1262, 520, 5823, 9288, 0, 3242, 5625, 4715, 7754, 2366, 8314, 1360, 623, 3915},
            {5501, 7145, 678, 6671, 3482, 6497, 3242, 0, 1522, 6648, 324, 8704, 7602, 8091, 1608, 1286},
            {7097, 6571, 9930, 9859, 9090, 5442, 5625, 1522, 0, 7740, 7480, 2266, 9346, 967, 9585, 9113},
            {8026, 6217, 6739, 4489, 9537, 4381, 4715, 6648, 7740, 0, 1527, 4847, 4770, 5032, 3387, 3706},
            {7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 1527, 0, 2399, 9453, 7380, 8661, 1177},
            {2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 4847, 2399, 0, 3224, 4943, 8957, 8156},
            {4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 4770, 9453, 3224, 0, 4289, 5709, 2858},
            {510, 5817, 7708, 5607, 2944, 5616, 1360, 5176, 967, 3706, 6509, 7380, 1942, 0, 6631, 1397},
            {7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 3387, 8661, 8957, 5709, 6631, 0, 2345},
            {6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 3706, 1177, 8156, 2858, 1397, 2345, 0}
        };

        // Parametros de entrada:        
        double TemperaturaInicial = 10000;
        double TasaEnfriamiento = 0.9999;
        int NumeroIteraciones = 1000000;

        TSPRS tsp = new TSPRS(distanceMatrix, TemperaturaInicial, TasaEnfriamiento, NumeroIteraciones);

        // Generar una solución inicial (ruta aleatoria)
        ArrayList<Integer> initialRoute = new ArrayList<>();
        for (int i = 0; i < distanceMatrix.length; i++) {
            initialRoute.add(i);
        }
        Collections.shuffle(initialRoute);

        // Resolver el TSP usando Recocido Simulado
        ArrayList<Integer> bestRoute = tsp.solve(initialRoute);
        double bestDistance = tsp.calculateTotalDistance(bestRoute);

        // Imprimir los resultados
        System.out.println("Ruta óptima encontrada: " + bestRoute);
        System.out.println("Distancia mínima: " + bestDistance);
    }
}


Código Java (TSPRS.java):

package tsp_recocidosimulado;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class TSPRS {

    private final double[][] distanceMatrix;
    private final double initialTemperature;
    private final double coolingRate;
    private final int maxIterations;
    private final Random random;

    public TSPRS(double[][] distanceMatrix, double initialTemperature, double coolingRate, int maxIterations) {
        this.distanceMatrix = distanceMatrix;
        this.initialTemperature = initialTemperature;
        this.coolingRate = coolingRate;
        this.maxIterations = maxIterations;
        this.random = new Random();
    }

    public ArrayList<Integer> solve(ArrayList<Integer> initialRoute) {
        ArrayList<Integer> currentRoute = new ArrayList<>(initialRoute);
        ArrayList<Integer> bestRoute = new ArrayList<>(initialRoute);
        double bestDistance = calculateTotalDistance(bestRoute);

        double temperature = initialTemperature;
        int iteration = 0;

        while (temperature > 1 && iteration < maxIterations) {
            ArrayList<Integer> newRoute = generateNeighbor(new ArrayList<>(currentRoute));

            double currentDistance = calculateTotalDistance(currentRoute);
            double newDistance = calculateTotalDistance(newRoute);

            if (acceptanceProbability(currentDistance, newDistance, temperature) > random.nextDouble()) {
                currentRoute = new ArrayList<>(newRoute);
            }

            if (calculateTotalDistance(currentRoute) < bestDistance) {
                bestRoute = new ArrayList<>(currentRoute);
                bestDistance = calculateTotalDistance(bestRoute);
            }

            temperature *= coolingRate;
            iteration++;
        }

        return bestRoute;
    }

    private ArrayList<Integer> generateNeighbor(ArrayList<Integer> route) {
        int pos1 = random.nextInt(route.size());
        int pos2 = random.nextInt(route.size());
        Collections.swap(route, pos1, pos2);
        return route;
    }

    private double acceptanceProbability(double currentDistance, double newDistance, double temperature) {
        if (newDistance < currentDistance) {
            return 1.0;
        }
        return Math.exp((currentDistance - newDistance) / temperature);
    }

    double calculateTotalDistance(ArrayList<Integer> route) {
        double totalDistance = 0.0;

        for (int i = 0; i < route.size() - 1; i++) {
            totalDistance += distanceMatrix[route.get(i)][route.get(i + 1)];
        }
        totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Regreso a la ciudad de inicio

        return totalDistance;
    }
}


Resultado:

run:
Ruta óptima encontrada: [7, 8, 11, 2, 5, 14, 6, 1, 12, 3, 4, 0, 13, 15, 9, 10]
Distancia mínima: 23620.0
BUILD SUCCESSFUL (total time: 0 seconds)