Una forma sencilla y rápida de aprender JAVA, observando y deduciendo cómo se comporta el lenguaje a través de ejemplos prácticos.

Archivo del blog

martes, 13 de agosto de 2024

Problema del viajante de Comercio TSP (VI). Método Colonia de Hormigas (ACO).

El algoritmo de Colonia de Hormigas (Ant Colony Optimization, siglas en inglés: ACO) es un método metaheurístico inspirado en el comportamiento de las hormigas reales para resolver problemas de optimización combinatoria, como el Problema del Viajante de Comercio (TSP).

Descripción del Algoritmo de Colonia de Hormigas:

Las hormigas reales son capaces de encontrar el camino más corto entre su colonia y una fuente de alimento mediante la deposición de feromonas en el suelo. Estas feromonas sirven como una señal química que guía a otras hormigas. Cuanto más corto sea el camino, más rápido regresan las hormigas, incrementando la cantidad de feromonas en ese trayecto y, por lo tanto, haciendo que sea más atractivo para otras hormigas. El algoritmo ACO* o
TSPCH simula este comportamiento.

Parámetros necesarios:

    distances: Matriz de distancias entre las ciudades.
    numAnts: Número de hormigas que participan en cada iteración.
    numIterations: Número de iteraciones para ejecutar el algoritmo.
    alpha, beta: Parámetros que controlan la influencia de la feromona y la visibilidad, respectivamente.
    evaporation: Tasa de evaporación de las feromonas.
    Q: Constante para la cantidad de feromona depositada.


Código Java (TSP_ColoniaHormigas):

package tsp_coloniahormigas;

import java.util.Arrays;

public class TSP_ColoniaHormigas {

    public static void main(String[] args) {

        // Matriz de distancias (16x16)
        double[][] distances = {
            {0, 6780, 6332, 5183, 3541, 6777, 9735, 7, 7297, 9569, 9649, 6776, 2841, 6953, 538, 4117},
            {6780, 0, 9200, 7166, 6987, 7864, 8168, 6569, 5755, 5199, 508, 2574, 8282, 5348, 106, 511},
            {6332, 9200, 0, 9806, 3578, 8764, 6077, 9847, 4451, 9042, 3870, 2817, 2318, 7693, 4202, 7622},
            {5183, 7166, 9806, 0, 3518, 4282, 255, 9261, 1766, 9321, 5317, 5747, 6177, 4520, 3900, 7828},
            {3541, 6987, 3578, 3518, 0, 9134, 4385, 8033, 3046, 7208, 3214, 2128, 19, 7763, 1796, 9843},
            {6777, 7864, 8764, 4282, 9134, 0, 4017, 7218, 2483, 5176, 3423, 9862, 6872, 5376, 7486, 4337},
            {9735, 8168, 6077, 255, 4385, 4017, 0, 4140, 2692, 409, 6729, 4045, 4354, 8323, 888, 3671},
            {7, 6569, 9847, 9261, 8033, 7218, 4140, 0, 1894, 9932, 4223, 2703, 932, 2015, 5867, 5244},
            {7297, 5755, 4451, 1766, 3046, 2483, 2692, 1894, 0, 2481, 171, 4352, 9602, 4497, 9916, 8946},
            {9569, 5199, 9042, 9321, 7208, 5176, 409, 9932, 2481, 0, 8364, 6474, 8869, 7058, 2869, 2216},
            {9649, 508, 3870, 5317, 3214, 3423, 6729, 4223, 171, 8364, 0, 109, 7461, 436, 4842, 3091},
            {6776, 2574, 2817, 5747, 2128, 9862, 4045, 2703, 4352, 6474, 109, 0, 2945, 8514, 7882, 2895},
            {2841, 8282, 2318, 6177, 19, 6872, 4354, 932, 9602, 8869, 7461, 2945, 0, 7904, 232, 6090},
            {6953, 5348, 7693, 4520, 7763, 5376, 8323, 2015, 4497, 7058, 436, 8514, 7904, 0, 4406, 103},
            {538, 106, 4202, 3900, 1796, 7486, 888, 5867, 9916, 2869, 4842, 7882, 232, 4406, 0, 3609},
            {4117, 511, 7622, 7828, 9843, 4337, 3671, 5244, 8946, 2216, 3091, 2895, 6090, 103, 3609, 0}
        };

        int numAnts = 10;           // Número de hormigas que participan en cada iteración.
        int numIterations = 1000;   // Número de iteraciones para ejecutar el algoritmo.
        float alpha = 1.0f;         // Parámetro que controlanla influencia de la feromona.
        float beta = 5.0f;          // Parámetro que controlanla influencia de la visibilidad.
        float evaporation = 0.5f;   // Tasa de evaporación de las feromonas.
        float Q = 100.0f;           // Constante para la cantidad de feromona depositada.

        TSPCH tsp = new TSPCH(
                distances,
                numAnts,
                numIterations,
                alpha,
                beta,
                evaporation,
                Q);

        System.out.println("> Mejor ruta encontrada:\n" + Arrays.toString(tsp.getBestRoute()));
        System.out.println("> La distancia total recorrida es: " + tsp.getBestDistance());

    }

}


Código Java (TSPCH.java):

package tsp_coloniahormigas;

import java.util.Arrays;
import java.util.Random;

public class TSPCH {

    private final int numCities;
    private final int numAnts;
    private final double[][] distances;
    private final double[][] pheromone;
    private final double alpha;
    private final double beta;
    private final double evaporation;
    private final double Q;
    private int[] bestRoute;
    private int bestDistance;
    private final Random random;

    public TSPCH(double[][] distances, int numAnts, int numIterations, double alpha, double beta, double evaporation, double Q) {
        this.numCities = distances.length;
        this.numAnts = numAnts;
        this.distances = distances;
        this.alpha = alpha;
        this.beta = beta;
        this.evaporation = evaporation;
        this.Q = Q;
        this.pheromone = new double[numCities][numCities];
        this.bestDistance = Integer.MAX_VALUE;
        this.random = new Random();

        // Inicializa la matriz de feromonas con un pequeño valor inicial
        for (int i = 0; i < numCities; i++) {
            Arrays.fill(pheromone[i], 1.0);
        }

        // Ejecuta el algoritmo de optimización
        for (int i = 0; i < numIterations; i++) {
            optimize();
        }
    }

    private void optimize() {
        int[][] antRoutes = new int[numAnts][numCities];
        int[] antDistances = new int[numAnts];

        for (int i = 0; i < numAnts; i++) {
            antRoutes[i] = constructSolution();
            antDistances[i] = calculateDistance(antRoutes[i]);

            if (antDistances[i] < bestDistance) {
                bestDistance = antDistances[i];
                bestRoute = antRoutes[i].clone();
            }
        }

        updatePheromones(antRoutes, antDistances);
    }

    private int[] constructSolution() {
        int[] route = new int[numCities];
        boolean[] visited = new boolean[numCities];
        int currentCity = random.nextInt(numCities);
        route[0] = currentCity;
        visited[currentCity] = true;

        for (int i = 1; i < numCities; i++) {
            int nextCity = selectNextCity(currentCity, visited);
            route[i] = nextCity;
            visited[nextCity] = true;
            currentCity = nextCity;
        }

        return route;
    }

    private int selectNextCity(int currentCity, boolean[] visited) {
        double[] probabilities = new double[numCities];
        double sum = 0.0;

        for (int i = 0; i < numCities; i++) {
            if (!visited[i]) {
                probabilities[i] = Math.pow(pheromone[currentCity][i], alpha) * Math.pow(1.0 / distances[currentCity][i], beta);
                sum += probabilities[i];
            }
        }

        double r = random.nextDouble() * sum;
        sum = 0.0;

        for (int i = 0; i < numCities; i++) {
            if (!visited[i]) {
                sum += probabilities[i];
                if (sum >= r) {
                    return i;
                }
            }
        }

        return -1;
    }

    private void updatePheromones(int[][] antRoutes, int[] antDistances) {
        // Evaporación
        for (int i = 0; i < numCities; i++) {
            for (int j = 0; j < numCities; j++) {
                pheromone[i][j] *= (1 - evaporation);
            }
        }

        // Actualización basada en la calidad de la solución
        for (int i = 0; i < numAnts; i++) {
            for (int j = 0; j < numCities - 1; j++) {
                int city1 = antRoutes[i][j];
                int city2 = antRoutes[i][j + 1];
                pheromone[city1][city2] += Q / antDistances[i];
                pheromone[city2][city1] += Q / antDistances[i];
            }

            // Añadir feromona en la ruta de vuelta
            int lastCity = antRoutes[i][numCities - 1];
            int firstCity = antRoutes[i][0];
            pheromone[lastCity][firstCity] += Q / antDistances[i];
            pheromone[firstCity][lastCity] += Q / antDistances[i];
        }
    }

    private int calculateDistance(int[] route) {
        int totalDistance = 0;
        for (int i = 0; i < numCities - 1; i++) {
            totalDistance += distances[route[i]][route[i + 1]];
        }
        totalDistance += distances[route[numCities - 1]][route[0]]; // Volver a la ciudad inicial
        return totalDistance;
    }

    public int[] getBestRoute() {
        return bestRoute;
    }

    public int getBestDistance() {
        return bestDistance;
    }
}


Resultado:

run:
> Mejor ruta encontrada:
[14, 1, 15, 13, 10, 11, 2, 12, 4, 3, 6, 9, 5, 8, 7, 0]
> La distancia total recorrida es: 20699
BUILD SUCCESSFUL (total time: 0 seconds)

Matriz de conectividad circular.

Este código Java genera puntos aleatorios en la línea de la circunferencia de un círculo y crea una matriz de distancias entre ellos. Esta matriz de distancias generada, que representa un grafo completo con propiedades geométricas especiales, es el núcleo del programa. Es ideal para probar diversos algoritmos, especialmente variantes del Problema del Viajante de Comercio (TSP).
La disposición circular de los puntos ofrece una característica importante: la ruta óptima del TSP es conocida (seguir la circunferencia), y el algoritmo del del TSP Vecino Más Cercano la encuentra eficientemente. Esto proporciona un valioso punto de referencia para evaluar y comparar el rendimiento de diferentes algoritmos de optimización sobre la misma matriz de distancias.


Código Java (CircunferenciaDistancias.java):

package circunferenciadistancias;

import java.util.Random;

public class CircunferenciaDistancias {

    public static int N = 16;
    public static int diametro = 1024;

    public static void main(String[] args) {
        double radio = diametro / 2.0;
        double[][] puntos = new double[N][2];
        double[][] distancias = new double[N][N];
        Random random = new Random();

        // Generar N puntos aleatorios en la circunferencia
        for (int i = 0; i < N; i++) {
            double angulo = random.nextDouble() * 2 * Math.PI;
            double x = radio + radio * Math.cos(angulo);
            double y = radio + radio * Math.sin(angulo);
            puntos[i][0] = x;
            puntos[i][1] = y;
        }

        // Calcular la matriz de distancias entre los puntos y mostrarlas en pantalla
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i != j) {
                    distancias[i][j] = Math.sqrt(
                            Math.pow(puntos[i][0] - puntos[j][0], 2)
                            + Math.pow(puntos[i][1] - puntos[j][1], 2)
                    );
                } else {
                    distancias[i][j] = 0;
                }
                System.out.printf("%6d", Math.round(distancias[i][j]));
            }
            System.out.println();
        }
    }
}


Resultado:

run:
     0   264   299   950   996   894   199   901   673  1023   895   941   258   701  1024   812
   264     0   541   820   901   993    67   996   452   998   993   805   505   485   981   946
   299   541     0  1020  1022   710   483   720   869   968   711  1018    42   888   988   595
   950   820  1020     0   149   796   858   787   465   414   795    26  1016   432   352   881
   996   901  1022   149     0   693   930   684   593   274   693   174  1024   562   209   796
   894   993   710   796   693     0   974    13  1002   467     1   811   740   993   525   149
   199    67   483   858   930   974     0   978   511  1011   975   844   446   543   998   918
   901   996   720   787   684    13   978     0   999   455    12   803   749   990   514   162
   673   452   869   465   593  1002   511   999     0   795  1001   442   846    37   751  1022
  1023   998   968   414   274   467  1011   455   795     0   466   437   981   770    67   595
   895   993   711   795   693     1   975    12  1001   466     0   811   741   993   524   150
   941   805  1018    26   174   811   844   803   442   437   811     0  1012   409   376   894
   258   505    42  1016  1024   740   446   749   846   981   741  1012     0   867   998   629
   701   485   888   432   562   993   543   990    37   770   993   409   867     0   725  1019
  1024   981   988   352   209   525   998   514   751    67   524   376   998   725     0   648
   812   946   595   881   796   149   918   162  1022   595   150   894   629  1019   648     0
BUILD SUCCESSFUL (total time: 0 seconds)
 

Problema del Viajante de Comercio TSP (V.3.1). Análisis estadístico de eficiencia de N-Opt.

Este programa Java implementa una solución multihilo para el Problema del Viajante de Comercio (TSP) utilizando el algoritmo N-opt, con un enfoque especial en el análisis estadístico de eficiencia. El código está diseñado para evaluar sistemáticamente diferentes combinaciones de parámetros del algoritmo N-opt, permitiendo un estudio exhaustivo de su rendimiento bajo diversas condiciones.

Características principales:

1. Análisis estadístico de eficiencia: El programa realiza un análisis exhaustivo combinando varios parámetros clave del algoritmo N-opt:
   - Utiliza diferentes valores de N (2, 3, 4, 5) para el N-opt.
   - Varía el número de iteraciones (50, 100, 200, 400, 800, 1600, 3200, 6400, 12800).
   - Ejecuta cada combinación de parámetros múltiples veces (64 ejecuciones) para obtener resultados estadísticamente significativos.

   Nota: Estas arrays permiten un análisis sistemático y exhaustivo del rendimiento del algoritmo N-opt bajo diferentes configuraciones. Al combinar cada valor de N con cada número de iteraciones, el programa puede evaluar un total de 36 configuraciones diferentes (4 valores de N × 9 valores de iteraciones), proporcionando una visión completa del comportamiento del algoritmo en diversas condiciones.

2. Uso de ExecutorService: Emplea un pool de hilos fijo (8 hilos) para ejecutar tareas en paralelo, maximizando la utilización de los recursos de la CPU.
3. Paralelización de experimentos: Cada combinación de N y número de iteraciones se ejecuta como una tarea independiente, permitiendo la evaluación simultánea de múltiples configuraciones.
4. Recopilación y agregación de resultados: Los resultados de cada tarea se agregan de forma segura, calculando promedios de tiempo de ejecución y calidad de la solución (distancia) para cada configuración.
5. Análisis comparativo: Al final, se presentan los 100 mejores resultados, ordenados por distancia media y tiempo de ejecución, facilitando la comparación entre diferentes configuraciones del algoritmo.

Este enfoque multihilo no solo acelera la ejecución del gran número de experimentos necesarios para el análisis estadístico, sino que también permite una evaluación más completa del rendimiento del algoritmo N-opt bajo diferentes parámetros. Esto es crucial para determinar las configuraciones óptimas del algoritmo para diferentes tamaños de problema y restricciones de tiempo de ejecución.

El uso de arrays predefinidos para N y el número de iteraciones (Ns y iterationsArray) permite una fácil modificación y expansión del espacio de parámetros a evaluar, facilitando futuros análisis más detallados o enfocados en rangos específicos de estos parámetros.


Código Java (TSP_Optimization.java):

package tsp_optimization;

import java.util.Optional;
import java.util.stream.Collectors;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;

public class TSP_Optimization {

    private static final List<Result> aggregatedResults = new ArrayList<>();

    public static void main(String[] args) throws Exception {

        // Matriz de distancias de 32x32
        double[][] distances = {
            {0, 8718, 6530, 4970, 9334, 8982, 3156, 1176, 2851, 6647, 3224, 7585, 1188, 674, 2976, 6462, 9859, 4383, 413, 8051, 2599, 4309, 6907, 6617, 5877, 40, 9527, 599, 5186, 2204, 958, 6352},
            {8718, 0, 5578, 6583, 3220, 373, 8710, 9125, 7310, 5435, 6190, 5, 172, 8327, 9867, 7121, 8150, 7334, 5975, 6283, 3346, 4778, 4260, 2658, 1343, 2078, 5685, 7380, 4178, 4378, 9261, 2925},
            {6530, 5578, 0, 3962, 9826, 7362, 2942, 9474, 8696, 702, 4025, 2482, 2835, 2242, 4553, 3010, 8983, 3542, 9294, 2125, 9571, 9825, 2661, 1486, 8266, 1282, 1351, 8665, 4985, 8601, 2280, 9848},
            {4970, 6583, 3962, 0, 8376, 7925, 367, 5408, 5804, 1419, 8230, 1472, 6616, 5679, 8119, 3974, 3555, 6723, 8150, 3918, 8549, 697, 6750, 1783, 4507, 5238, 6531, 1172, 3210, 5349, 3911, 4668},
            {9334, 3220, 9826, 8376, 0, 9280, 3764, 4344, 9310, 5045, 7951, 6054, 7108, 9809, 2248, 5730, 947, 4696, 1152, 1922, 1549, 3312, 117, 162, 4051, 3235, 4711, 6196, 7258, 9712, 3544, 5608},
            {8982, 373, 7362, 7925, 9280, 0, 1416, 9483, 2944, 9414, 7099, 9253, 3002, 6088, 6071, 6438, 6671, 9525, 938, 8854, 7549, 696, 1710, 6428, 4259, 6255, 634, 5646, 8444, 9392, 4613, 1831},
            {3156, 8710, 2942, 367, 3764, 1416, 0, 3941, 2741, 760, 134, 1421, 8024, 8239, 4515, 5480, 2234, 5244, 2988, 2736, 4316, 7303, 9550, 9208, 9937, 1990, 4288, 3886, 1627, 8133, 7496, 8701},
            {1176, 9125, 9474, 5408, 4344, 9483, 3941, 0, 6482, 2291, 209, 1564, 6115, 7033, 388, 7159, 949, 1206, 819, 7063, 8407, 7276, 8549, 2065, 692, 6609, 3787, 4200, 7321, 4083, 273, 1167},
            {2851, 7310, 8696, 5804, 9310, 2944, 2741, 6482, 0, 5805, 1260, 2545, 4431, 7551, 109, 9793, 3329, 7518, 6346, 7244, 970, 9089, 4194, 4286, 9696, 4135, 6841, 8441, 9612, 1688, 2835, 981},
            {6647, 5435, 702, 1419, 5045, 9414, 760, 2291, 5805, 0, 1198, 7659, 4863, 3156, 9607, 8913, 766, 9156, 104, 3774, 9823, 3869, 8037, 7464, 4425, 3770, 1525, 5335, 3428, 4548, 1464, 173},
            {3224, 6190, 4025, 8230, 7951, 7099, 134, 209, 1260, 1198, 0, 4420, 5162, 8597, 9135, 3779, 781, 7727, 1873, 3465, 9720, 7812, 8289, 2987, 4365, 2162, 6521, 45, 3882, 8806, 2951, 3621},
            {7585, 5, 2482, 1472, 6054, 9253, 1421, 1564, 2545, 7659, 4420, 0, 7994, 2146, 6586, 8030, 3783, 8586, 2883, 981, 2254, 1388, 7707, 2868, 7915, 4826, 3, 2297, 5955, 9653, 3941, 194},
            {1188, 172, 2835, 6616, 7108, 3002, 8024, 6115, 4431, 4863, 5162, 7994, 0, 6081, 1943, 6874, 5095, 6744, 8236, 581, 659, 39, 7486, 8141, 5008, 5082, 3388, 313, 5951, 8125, 8967, 483},
            {674, 8327, 2242, 5679, 9809, 6088, 8239, 7033, 7551, 3156, 8597, 2146, 6081, 0, 7233, 5627, 377, 8318, 6613, 7989, 8130, 2708, 8351, 8639, 3376, 5304, 464, 6356, 5450, 5435, 6056, 2441},
            {2976, 9867, 4553, 8119, 2248, 6071, 4515, 388, 109, 9607, 9135, 6586, 1943, 7233, 0, 8937, 7994, 9845, 9423, 5764, 404, 9510, 2690, 8358, 1337, 8400, 7455, 702, 7261, 6572, 8530, 1075},
            {6462, 7121, 3010, 3974, 5730, 6438, 5480, 7159, 9793, 8913, 3779, 8030, 6874, 5627, 8937, 0, 2076, 3500, 8861, 4498, 7016, 4600, 6052, 853, 7694, 9338, 6213, 9554, 6007, 7202, 150, 189},
            {9859, 8150, 8983, 3555, 947, 6671, 2234, 949, 3329, 766, 781, 3783, 5095, 377, 7994, 2076, 0, 650, 3974, 2983, 4635, 4879, 8521, 9878, 324, 7166, 1590, 6161, 2388, 565, 8154, 1109},
            {4383, 7334, 3542, 6723, 4696, 9525, 5244, 1206, 7518, 9156, 7727, 8586, 6744, 8318, 9845, 3500, 650, 0, 8510, 6072, 9148, 8725, 4253, 179, 7482, 1879, 4345, 2123, 2609, 7177, 9474, 5491},
            {413, 5975, 9294, 8150, 1152, 938, 2988, 819, 6346, 104, 1873, 2883, 8236, 6613, 9423, 8861, 3974, 8510, 0, 2408, 9521, 1261, 3307, 2986, 4130, 6344, 8514, 7086, 9097, 2474, 812, 5845},
            {8051, 6283, 2125, 3918, 1922, 8854, 2736, 7063, 7244, 3774, 3465, 981, 581, 7989, 5764, 4498, 2983, 6072, 2408, 0, 5767, 7228, 8174, 4159, 5450, 5999, 9462, 7850, 7524, 4761, 3336, 3912},
            {2599, 3346, 9571, 8549, 1549, 7549, 4316, 8407, 970, 9823, 9720, 2254, 659, 8130, 404, 7016, 4635, 9148, 9521, 5767, 0, 8060, 2095, 755, 7323, 7827, 9760, 3379, 5808, 4447, 3691, 2063},
            {4309, 4778, 9825, 697, 3312, 696, 7303, 7276, 9089, 3869, 7812, 1388, 39, 2708, 9510, 4600, 4879, 8725, 1261, 7228, 8060, 0, 310, 1156, 6942, 2354, 9513, 7937, 7901, 2823, 8495, 9382},
            {6907, 4260, 2661, 6750, 117, 1710, 9550, 8549, 4194, 8037, 8289, 7707, 7486, 8351, 2690, 6052, 8521, 4253, 3307, 8174, 2095, 310, 0, 699, 2285, 463, 7347, 7896, 3418, 7033, 8571, 1879},
            {6617, 2658, 1486, 1783, 162, 6428, 9208, 2065, 4286, 7464, 2987, 2868, 8141, 8639, 8358, 853, 9878, 179, 2986, 4159, 755, 1156, 699, 0, 1500, 5797, 3703, 9899, 8202, 5020, 2487, 1438},
            {5877, 1343, 8266, 4507, 4051, 4259, 9937, 692, 9696, 4425, 4365, 7915, 5008, 3376, 1337, 7694, 324, 7482, 4130, 5450, 7323, 6942, 2285, 1500, 0, 7450, 813, 3252, 4077, 5836, 5629, 6369},
            {40, 2078, 1282, 5238, 3235, 6255, 1990, 6609, 4135, 3770, 2162, 4826, 5082, 5304, 8400, 9338, 7166, 1879, 6344, 5999, 7827, 2354, 463, 5797, 7450, 0, 5938, 9266, 5470, 7824, 6255, 5539},
            {9527, 5685, 1351, 6531, 4711, 634, 4288, 3787, 6841, 1525, 6521, 3, 3388, 464, 7455, 6213, 1590, 4345, 8514, 9462, 9760, 9513, 7347, 3703, 813, 5938, 0, 4890, 8193, 7989, 4389, 477},
            {599, 7380, 8665, 1172, 6196, 5646, 3886, 4200, 8441, 5335, 45, 2297, 313, 6356, 702, 9554, 6161, 2123, 7086, 7850, 3379, 7937, 7896, 9899, 3252, 9266, 4890, 0, 6852, 6175, 3352, 2781},
            {5186, 4178, 4985, 3210, 7258, 8444, 1627, 7321, 9612, 3428, 3882, 5955, 5951, 5450, 7261, 6007, 2388, 2609, 9097, 7524, 5808, 7901, 3418, 8202, 4077, 5470, 8193, 6852, 0, 3231, 7790, 2594},
            {2204, 4378, 8601, 5349, 9712, 9392, 8133, 4083, 1688, 4548, 8806, 9653, 8125, 5435, 6572, 7202, 565, 7177, 2474, 4761, 4447, 2823, 7033, 5020, 5836, 7824, 7989, 6175, 3231, 0, 7831, 6332},
            {958, 9261, 2280, 3911, 3544, 4613, 7496, 273, 2835, 1464, 2951, 3941, 8967, 6056, 8530, 150, 8154, 9474, 812, 3336, 3691, 8495, 8571, 2487, 5629, 6255, 4389, 3352, 7790, 7831, 0, 3777},
            {6352, 2925, 9848, 4668, 5608, 1831, 8701, 1167, 981, 173, 3621, 194, 483, 2441, 1075, 189, 1109, 5491, 5845, 3912, 2063, 9382, 1879, 1438, 6369, 5539, 477, 2781, 2594, 6332, 3777, 0}
        };


        /* Define los diferentes valores de Ns para el algoritmo N-opt.
    N representa el número de ciudades que se intentarán optimizar simultáneamente en cada iteración.
    Se evalúan 2-opt, 3-opt, 4-opt y 5-opt, permitiendo comparar la eficacia de diferentes grados de optimización local.
         */
        
       
int[] Ns = {2, 3, 4, 5};

        /* Especifica el número de iteraciones que se ejecutarán para cada configuración de N.
    Utiliza una secuencia que se duplica en cada paso, abarcando un amplio rango desde 50 hasta 12800 iteraciones.
    Permite evaluar cómo el aumento del número de iteraciones afecta la calidad de la solución y el tiempo de ejecución.
         */
        
       
int[] iterationsArray = {50, 100, 200, 400, 800, 1600, 3200, 6400, 12800};

        // Crear un pool de hilos con un número fijo de hilos (8 hilos)
        ExecutorService executor = Executors.newFixedThreadPool(8);

        for (int i = 0; i < 64; i++) {
            System.out.println("Ejecución número " + (i + 1));
            List<Future<Result>> futures = new ArrayList<>();
            for (int N : Ns) {
                for (int iterations : iterationsArray) {
                    // Crear una tarea para cada experimento y enviarla al executor
                    futures.add(executor.submit(new ExperimentTask(distances, N, iterations)));
                }
            }

            // Esperar a que todas las tareas terminen y recoger los resultados
            List<Result> executionResults = new ArrayList<>();
            for (Future<Result> future : futures) {
                executionResults.add(future.get());
            }

            aggregateResults(executionResults);
        }

        executor.shutdown();
        executor.awaitTermination(1, TimeUnit.HOURS);

        printFinalTop100Results();
    }

    private static class ExperimentTask implements Callable<Result> {

        private final double[][] distances;
        private final int N;
        private final int iterations;

        ExperimentTask(double[][] distances, int N, int iterations) {
            this.distances = distances;
            this.N = N;
            this.iterations = iterations;
        }

        @Override
        public Result call() {
            long startTime = System.nanoTime();

            TSPNOpt tspN = new TSPNOpt(distances, N);
            List<Integer> bestRoute = tspN.findBestRoute(iterations);
            double bestDistance = tspN.calculateTotalDistance(bestRoute);

            long endTime = System.nanoTime();
            long duration = (endTime - startTime) / 1_000_000;

            return new Result(distances.length, N, iterations, duration, bestDistance, bestRoute);
        }
    }

    private static void aggregateResults(List<Result> executionResults) {
        executionResults.forEach(result -> {
            Optional<Result> existingResult = aggregatedResults.stream()
                    .filter(r -> r.nOpt == result.nOpt && r.iterations == result.iterations)
                    .findFirst();

            if (existingResult.isPresent()) {
                Result aggResult = existingResult.get();
                aggResult.addExecution(result);
            } else {
                aggregatedResults.add(new Result(result));
            }
        });
    }

    private static void printFinalTop100Results() {
        // Ordenar por la distancia media y luego por tiempo medio
        aggregatedResults.sort(Comparator
                .comparingDouble((Result r) -> r.averageBestDistance())
                .thenComparingDouble(Result::averageDuration));

        System.out.println("| Nodos | N-opt | Iteraciones | Tiempo medio (ms) | Distancia media | Mejor ruta promedio ·>>");
        System.out.println("|-------|-------|-------------|-------------------|-----------------|---------------------···");

        // Limitar a top 100
        aggregatedResults.stream().limit(100).forEach(result -> {
            System.out.printf("| %5d | %5d | %11d | %17.2f | %15.2f | %s |%n",
                    result.numCities, result.nOpt, result.iterations,
                    result.averageDuration(), result.averageBestDistance(),
                    routeToString(result.bestRoute));
        });
    }

    private static String routeToString(List<Integer> route) {
        return route.stream()
                .map(i -> String.valueOf((char) ('A' + i)))
                .collect(Collectors.joining(""));
    }

    private static class Result {

        int numCities, nOpt, iterations;
        long totalDuration;
        double totalBestDistance;
        List<Integer> bestRoute;
        int count;

        Result(int numCities, int nOpt, int iterations, long duration, double bestDistance, List<Integer> bestRoute) {
            this.numCities = numCities;
            this.nOpt = nOpt;
            this.iterations = iterations;
            this.totalDuration = duration;
            this.totalBestDistance = bestDistance;
            this.bestRoute = new ArrayList<>(bestRoute);
            this.count = 1;
        }

        // Constructor para crear un nuevo Result a partir de otro
        Result(Result other) {
            this.numCities = other.numCities;
            this.nOpt = other.nOpt;
            this.iterations = other.iterations;
            this.totalDuration = other.totalDuration;
            this.totalBestDistance = other.totalBestDistance;
            this.bestRoute = new ArrayList<>(other.bestRoute);
            this.count = other.count;
        }

        void addExecution(Result other) {
            this.totalDuration += other.totalDuration;
            this.totalBestDistance += other.totalBestDistance;
            this.count++;
        }

        double averageDuration() {
            return (double) this.totalDuration / this.count;
        }

        double averageBestDistance() {
            return this.totalBestDistance / this.count;
        }
    }

}


Código Java (TSPNOpt.java):

package tsp_optimization;

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

public class TSPNOpt {

    private final double[][] distances;
    private final int numCities;
    private final int N;

    public TSPNOpt(double[][] distances, int N) {
        this.distances = distances;
        this.numCities = distances.length;
        this.N = N;
    }

    public List<Integer> findBestRoute(int numRuns) {
        List<Integer> bestRoute = null;
        double bestDistance = Double.MAX_VALUE;

        for (int run = 0; run < numRuns; run++) {
            List<Integer> route = generateRandomRoute();
            route = optimizeRoute(route);

            double distance = calculateTotalDistance(route);
            if (distance < bestDistance) {
                bestDistance = distance;
                bestRoute = new ArrayList<>(route);
            }
        }

        return bestRoute;
    }

    private List<Integer> generateRandomRoute() {
        List<Integer> route = new ArrayList<>();
        for (int i = 0; i < numCities; i++) {
            route.add(i);
        }
        Collections.shuffle(route);
        return route;
    }

    private List<Integer> optimizeRoute(List<Integer> route) {
        boolean improved = true;
        while (improved) {
            improved = false;
            for (int i = 0; i < numCities - N + 1; i++) {
                for (int j = i + 1; j < numCities - N + 2; j++) {
                    List<Integer> newRoute = nOptSwap(route, i, j);
                    if (calculateTotalDistance(newRoute) < calculateTotalDistance(route)) {
                        route = newRoute;
                        improved = true;
                    }
                }
            }
        }
        return route;
    }

    private List<Integer> nOptSwap(List<Integer> route, int i, int j) {
        List<Integer> newRoute = new ArrayList<>(route.subList(0, i));
        List<Integer> subRoute = new ArrayList<>(route.subList(i, j + 1));
        Collections.reverse(subRoute);
        newRoute.addAll(subRoute);
        newRoute.addAll(route.subList(j + 1, route.size()));
        return newRoute;
    }

    public double calculateTotalDistance(List<Integer> route) {
        double totalDistance = 0;
        for (int i = 0; i < route.size(); i++) {
            totalDistance += distances[route.get(i)][route.get((i + 1) % route.size())];
        }
        return totalDistance;
    }
}


Resultado:

run:
Ejecución número 1
Ejecución número 2
...
...
...

Ejecución número 63
Ejecución número 64

| Nodos | N-opt | Iteraciones | Tiempo medio (ms) | Distancia media | Mejor ruta promedio ·>>
|-------|-------|-------------|-------------------|-----------------|---------------------···
|    32 |     3 |       12800 |          21358,67 |        18835,03 | CJSFBL`P_HK\OUI^QY[NAZWEXR]GDVMT
|    32 |     2 |       12800 |          22551,59 |        18852,16 | \KHY[NQ^IOUMTCJS_P`LBFVDG]RXEWZA
|    32 |     2 |        6400 |          12418,63 |        18907,08 | AN[LBFVD\KG]RXEWZCTMUOI^QYH_P`JS
|    32 |     3 |        6400 |          11719,80 |        18932,08 | ^QN[YH_P`LBFVD\KG]RXEWZASJCTMUOI
|    32 |     3 |        3200 |           5967,63 |        19003,86 | SJCZWETM\KH_P`LBFVDG]RXUOI^QY[NA
|    32 |     2 |        3200 |           6311,00 |        19011,36 | TLBFSJCZA\KGDVWEXR]^QN[YH_P`IOUM
|    32 |     2 |        1600 |           3226,63 |        19076,80 | LBFVDG]RXEWZCJS_P`[NA\KHYQ^IOUMT
|    32 |     3 |        1600 |           3019,42 |        19108,42 | QY[NAZWEXR]GDVMTCJSFBL`P_HK\OUI^
|    32 |     4 |       12800 |          18555,02 |        19287,33 | L`P_HK\OUI^QY[NASJCZWEXR]GDVFBMT
|    32 |     2 |         800 |           1643,80 |        19331,39 | G]RQ^IOUXEWZAN[YHK\MTCJS_P`LBFVD
|    32 |     4 |        6400 |          10526,55 |        19362,56 | WVDG]RXUOI^QY[NAZCJSFBL`P_HK\MTE
|    32 |     3 |         800 |           1512,89 |        19406,67 | VM\KH_P`JCZWETLBFSAN[YQ^IOUXR]GD
|    32 |     3 |         400 |            772,70 |        19550,09 | MTCZWEXR]GK\DVFBL[NASJ`P_HYQ^IOU
|    32 |     2 |         400 |            867,86 |        19578,63 | \MTEWZCJSAN[YQ^IOUXR]GDVFBL`P_HK
|    32 |     4 |        3200 |           5431,09 |        19668,63 | OUMTCZWEXR]GDVFBL[YQNA\KH_P`JS^I
|    32 |     3 |         200 |            387,34 |        19926,53 | IOH_P`LBFSJCTMUEXR]GK\DVWZAN[YQ^
|    32 |     2 |         200 |            447,53 |        19938,53 | OI^QY[NAZCTLBFSJ`P_HK\DG]RXEWVMU
|    32 |     4 |        1600 |           2729,55 |        19944,30 | CZAN[LBFVDG]RXUOI^QYWESJ`P_HK\MT
|    32 |     5 |       12800 |          15715,53 |        20226,56 | FSJ`P_HK\OUI^QYWEXR]GDVMTCZAN[LB
|    32 |     2 |         100 |            228,02 |        20314,23 | ]RXEWZCJ`P_STMUOI^QYHK\AN[LBFVDG
|    32 |     3 |         100 |            203,81 |        20318,09 | _P`L[NA\KHYQ^IOUXR]GDVFBMTEWZCJS
|    32 |     4 |         800 |           1365,69 |        20390,78 | BLTCZWEUOI^QYXR]GDVM\KH_P`JSAN[F
|    32 |     2 |          50 |            113,28 |        20553,84 | AN[YQ^IUO\KH_P`LDVFBMTCZWEXR]GJS
|    32 |     3 |          50 |            104,23 |        20606,63 | GDVWZAN[LBFS_P`JCTM\KHYQ^IOUEXR]
|    32 |     5 |        6400 |           8862,86 |        20664,75 | XEWZCJSAN[YQ^IUOH_P`LTM\KGDVFB]R
|    32 |     4 |         400 |            684,28 |        20685,34 | OI`P_HK\AN[YBLTCZWEXRQ^]GDJSFVMU
|    32 |     5 |        3200 |           4832,70 |        20953,80 | UI^QN[YH_P`JSA\KGD]RXEWZCTLBFVMO
|    32 |     4 |         200 |            341,08 |        21262,47 | ZWEUOI^QN[YH_P`LBFVMTCXR]GK\DJSA
|    32 |     5 |        1600 |           2470,16 |        21434,16 | JCZA_P`HYWETMVD\KG]RXUOI^QN[LBFS
|    32 |     4 |         100 |            171,50 |        21762,75 | G]RXEWVFBMTL`P_SJCZA\KHOUI^QN[YD
|    32 |     5 |         800 |           1232,75 |        21828,98 | SFBLTMVDG]RXEWZANQ^IUO\KHY[`P_CJ
|    32 |     4 |          50 |             85,17 |        22325,89 | WZK\OUI`P_SJCTMAN[LBFVDG]^QYHRXE
|    32 |     5 |         400 |            616,48 |        22443,19 | P_SJCTMBF[NAZR]GDVWEXUOI^QYHK\L`
|    32 |     5 |         200 |            306,70 |        23201,78 | LBFS_HYQ^IOUXR]GK\MVDJCP`[NAZWET
|    32 |     5 |         100 |            152,92 |        24017,14 | BFVM\AN[YHKIOUXRQ^]GDJ`P_SEWZCTL
|    32 |     5 |          50 |             75,78 |        24890,53 | WZASJCTM\KIOUXRH_P`L[NQ^]GDVFBYE
BUILD SUCCESSFUL (total time: 30 minutes 1 second)

lunes, 12 de agosto de 2024

Problema del viajante de Comercio TSP (IV.2). Método Vecino Cercano mejorado.

Se intenta mejorar el algoritmo del TSP Vecino Cercano (TSP VC). Básicamente la mejora consiste en elegir todos los nodos como punto de origen y a partir de ahi calcular las rutas (una ruta para cada nodo de origen) y de todas las rutas realizadas se elige la de menor costo. Se puede resumir de la siguiente manera:

1. El algoritmo comienza seleccionando el primer nodo como punto de origen.
2. A partir de este origen, construye una ruta completa utilizando la heurística del vecino más cercano, es decir, siempre elige el nodo no visitado más cercano como siguiente destino.
3. Una vez completada la ruta, calcula y registra su longitud total.
4. Luego, pasa al siguiente nodo de la lista y lo convierte en el nuevo punto de origen.
5. Repite los pasos 2 y 3 con este nuevo origen, construyendo una nueva ruta completa y registrando su longitud.
6. Este proceso se repite para todos los nodos del grafo, de modo que cada nodo sirve como punto de partida una vez.
7. Finalmente, compara todas las rutas generadas y selecciona la más corta como la solución óptima.

Esta técnica mejora la calidad de la solución al no depender de un único punto de partida arbitrario. Al probar con todos los nodos como puntos de inicio, aumenta la probabilidad de encontrar una solución de mejor calidad para el problema del TSP.


Código (TSP_VecinoCercano.java):

package tsp_vecinocercano;

import java.util.ArrayList;
import java.util.List;

public class TSP_VecinoCercano {

    public static void main(String[] args) {

        double[][] distances = {
            {0, 8718, 6530, 4970, 9334, 8982, 3156, 1176, 2851, 6647, 3224, 7585, 1188, 674, 2976, 6462, 9859, 4383, 413, 8051, 2599, 4309, 6907, 6617, 5877, 40, 9527, 599, 5186, 2204, 958, 6352},
            {8718, 0, 5578, 6583, 3220, 373, 8710, 9125, 7310, 5435, 6190, 5, 172, 8327, 9867, 7121, 8150, 7334, 5975, 6283, 3346, 4778, 4260, 2658, 1343, 2078, 5685, 7380, 4178, 4378, 9261, 2925},
            {6530, 5578, 0, 3962, 9826, 7362, 2942, 9474, 8696, 702, 4025, 2482, 2835, 2242, 4553, 3010, 8983, 3542, 9294, 2125, 9571, 9825, 2661, 1486, 8266, 1282, 1351, 8665, 4985, 8601, 2280, 9848},
            {4970, 6583, 3962, 0, 8376, 7925, 367, 5408, 5804, 1419, 8230, 1472, 6616, 5679, 8119, 3974, 3555, 6723, 8150, 3918, 8549, 697, 6750, 1783, 4507, 5238, 6531, 1172, 3210, 5349, 3911, 4668},
            {9334, 3220, 9826, 8376, 0, 9280, 3764, 4344, 9310, 5045, 7951, 6054, 7108, 9809, 2248, 5730, 947, 4696, 1152, 1922, 1549, 3312, 117, 162, 4051, 3235, 4711, 6196, 7258, 9712, 3544, 5608},
            {8982, 373, 7362, 7925, 9280, 0, 1416, 9483, 2944, 9414, 7099, 9253, 3002, 6088, 6071, 6438, 6671, 9525, 938, 8854, 7549, 696, 1710, 6428, 4259, 6255, 634, 5646, 8444, 9392, 4613, 1831},
            {3156, 8710, 2942, 367, 3764, 1416, 0, 3941, 2741, 760, 134, 1421, 8024, 8239, 4515, 5480, 2234, 5244, 2988, 2736, 4316, 7303, 9550, 9208, 9937, 1990, 4288, 3886, 1627, 8133, 7496, 8701},
            {1176, 9125, 9474, 5408, 4344, 9483, 3941, 0, 6482, 2291, 209, 1564, 6115, 7033, 388, 7159, 949, 1206, 819, 7063, 8407, 7276, 8549, 2065, 692, 6609, 3787, 4200, 7321, 4083, 273, 1167},
            {2851, 7310, 8696, 5804, 9310, 2944, 2741, 6482, 0, 5805, 1260, 2545, 4431, 7551, 109, 9793, 3329, 7518, 6346, 7244, 970, 9089, 4194, 4286, 9696, 4135, 6841, 8441, 9612, 1688, 2835, 981},
            {6647, 5435, 702, 1419, 5045, 9414, 760, 2291, 5805, 0, 1198, 7659, 4863, 3156, 9607, 8913, 766, 9156, 104, 3774, 9823, 3869, 8037, 7464, 4425, 3770, 1525, 5335, 3428, 4548, 1464, 173},
            {3224, 6190, 4025, 8230, 7951, 7099, 134, 209, 1260, 1198, 0, 4420, 5162, 8597, 9135, 3779, 781, 7727, 1873, 3465, 9720, 7812, 8289, 2987, 4365, 2162, 6521, 45, 3882, 8806, 2951, 3621},
            {7585, 5, 2482, 1472, 6054, 9253, 1421, 1564, 2545, 7659, 4420, 0, 7994, 2146, 6586, 8030, 3783, 8586, 2883, 981, 2254, 1388, 7707, 2868, 7915, 4826, 3, 2297, 5955, 9653, 3941, 194},
            {1188, 172, 2835, 6616, 7108, 3002, 8024, 6115, 4431, 4863, 5162, 7994, 0, 6081, 1943, 6874, 5095, 6744, 8236, 581, 659, 39, 7486, 8141, 5008, 5082, 3388, 313, 5951, 8125, 8967, 483},
            {674, 8327, 2242, 5679, 9809, 6088, 8239, 7033, 7551, 3156, 8597, 2146, 6081, 0, 7233, 5627, 377, 8318, 6613, 7989, 8130, 2708, 8351, 8639, 3376, 5304, 464, 6356, 5450, 5435, 6056, 2441},
            {2976, 9867, 4553, 8119, 2248, 6071, 4515, 388, 109, 9607, 9135, 6586, 1943, 7233, 0, 8937, 7994, 9845, 9423, 5764, 404, 9510, 2690, 8358, 1337, 8400, 7455, 702, 7261, 6572, 8530, 1075},
            {6462, 7121, 3010, 3974, 5730, 6438, 5480, 7159, 9793, 8913, 3779, 8030, 6874, 5627, 8937, 0, 2076, 3500, 8861, 4498, 7016, 4600, 6052, 853, 7694, 9338, 6213, 9554, 6007, 7202, 150, 189},
            {9859, 8150, 8983, 3555, 947, 6671, 2234, 949, 3329, 766, 781, 3783, 5095, 377, 7994, 2076, 0, 650, 3974, 2983, 4635, 4879, 8521, 9878, 324, 7166, 1590, 6161, 2388, 565, 8154, 1109},
            {4383, 7334, 3542, 6723, 4696, 9525, 5244, 1206, 7518, 9156, 7727, 8586, 6744, 8318, 9845, 3500, 650, 0, 8510, 6072, 9148, 8725, 4253, 179, 7482, 1879, 4345, 2123, 2609, 7177, 9474, 5491},
            {413, 5975, 9294, 8150, 1152, 938, 2988, 819, 6346, 104, 1873, 2883, 8236, 6613, 9423, 8861, 3974, 8510, 0, 2408, 9521, 1261, 3307, 2986, 4130, 6344, 8514, 7086, 9097, 2474, 812, 5845},
            {8051, 6283, 2125, 3918, 1922, 8854, 2736, 7063, 7244, 3774, 3465, 981, 581, 7989, 5764, 4498, 2983, 6072, 2408, 0, 5767, 7228, 8174, 4159, 5450, 5999, 9462, 7850, 7524, 4761, 3336, 3912},
            {2599, 3346, 9571, 8549, 1549, 7549, 4316, 8407, 970, 9823, 9720, 2254, 659, 8130, 404, 7016, 4635, 9148, 9521, 5767, 0, 8060, 2095, 755, 7323, 7827, 9760, 3379, 5808, 4447, 3691, 2063},
            {4309, 4778, 9825, 697, 3312, 696, 7303, 7276, 9089, 3869, 7812, 1388, 39, 2708, 9510, 4600, 4879, 8725, 1261, 7228, 8060, 0, 310, 1156, 6942, 2354, 9513, 7937, 7901, 2823, 8495, 9382},
            {6907, 4260, 2661, 6750, 117, 1710, 9550, 8549, 4194, 8037, 8289, 7707, 7486, 8351, 2690, 6052, 8521, 4253, 3307, 8174, 2095, 310, 0, 699, 2285, 463, 7347, 7896, 3418, 7033, 8571, 1879},
            {6617, 2658, 1486, 1783, 162, 6428, 9208, 2065, 4286, 7464, 2987, 2868, 8141, 8639, 8358, 853, 9878, 179, 2986, 4159, 755, 1156, 699, 0, 1500, 5797, 3703, 9899, 8202, 5020, 2487, 1438},
            {5877, 1343, 8266, 4507, 4051, 4259, 9937, 692, 9696, 4425, 4365, 7915, 5008, 3376, 1337, 7694, 324, 7482, 4130, 5450, 7323, 6942, 2285, 1500, 0, 7450, 813, 3252, 4077, 5836, 5629, 6369},
            {40, 2078, 1282, 5238, 3235, 6255, 1990, 6609, 4135, 3770, 2162, 4826, 5082, 5304, 8400, 9338, 7166, 1879, 6344, 5999, 7827, 2354, 463, 5797, 7450, 0, 5938, 9266, 5470, 7824, 6255, 5539},
            {9527, 5685, 1351, 6531, 4711, 634, 4288, 3787, 6841, 1525, 6521, 3, 3388, 464, 7455, 6213, 1590, 4345, 8514, 9462, 9760, 9513, 7347, 3703, 813, 5938, 0, 4890, 8193, 7989, 4389, 477},
            {599, 7380, 8665, 1172, 6196, 5646, 3886, 4200, 8441, 5335, 45, 2297, 313, 6356, 702, 9554, 6161, 2123, 7086, 7850, 3379, 7937, 7896, 9899, 3252, 9266, 4890, 0, 6852, 6175, 3352, 2781},
            {5186, 4178, 4985, 3210, 7258, 8444, 1627, 7321, 9612, 3428, 3882, 5955, 5951, 5450, 7261, 6007, 2388, 2609, 9097, 7524, 5808, 7901, 3418, 8202, 4077, 5470, 8193, 6852, 0, 3231, 7790, 2594},
            {2204, 4378, 8601, 5349, 9712, 9392, 8133, 4083, 1688, 4548, 8806, 9653, 8125, 5435, 6572, 7202, 565, 7177, 2474, 4761, 4447, 2823, 7033, 5020, 5836, 7824, 7989, 6175, 3231, 0, 7831, 6332},
            {958, 9261, 2280, 3911, 3544, 4613, 7496, 273, 2835, 1464, 2951, 3941, 8967, 6056, 8530, 150, 8154, 9474, 812, 3336, 3691, 8495, 8571, 2487, 5629, 6255, 4389, 3352, 7790, 7831, 0, 3777},
            {6352, 2925, 9848, 4668, 5608, 1831, 8701, 1167, 981, 173, 3621, 194, 483, 2441, 1075, 189, 1109, 5491, 5845, 3912, 2063, 9382, 1879, 1438, 6369, 5539, 477, 2781, 2594, 6332, 3777, 0}
        };


        TSPVC tsp = new TSPVC(distances);
        List<Integer> path = tsp.findBestRoute();

        // Poner nombre a los nodos siguiendo la secuencia del abecedario
        List<String> nodeNames = new ArrayList<>();
        for (int i = 0; i < distances.length; i++) {
            char letter = (char) ('A' + i);
            nodeNames.add(String.valueOf(letter));
        }

        // Imprimir ruta y distancia recorrida
        System.out.println("> Mejor ruta encontrada:");
        double totalDistance = 0;
        for (int i = 0; i < path.size() - 1; i++) {
            int node1 = path.get(i);
            int node2 = path.get(i + 1);
            double distance = distances[node1][node2];
            totalDistance += distance;
            System.out.printf("%s ", nodeNames.get(node1), distance);
        }
        // Imprimir el nodo final y la vuelta al nodo inicial
        System.out.println(nodeNames.get(path.get(path.size() - 1)));
        System.out.printf("> La distancia total recorrida es: %.0f\n", totalDistance);
    }
}


Código 2 (TSPVC.java):

package tsp_vecinocercano;

import java.util.ArrayList;
import java.util.List;

public class TSPVC {

    private final double[][] distances;

    public TSPVC(double[][] distances) {
        this.distances = distances;
    }

    public List<Integer> findBestRoute() {
        List<Integer> bestPath = null;
        double shortestDistance = Double.MAX_VALUE;

        // Probar con cada nodo como punto de inicio
        for (int startNode = 0; startNode < distances.length; startNode++) {
            List<Integer> path = findPathStartingFrom(startNode);
            double totalDistance = calculateTotalDistance(path);

            if (totalDistance < shortestDistance) {
                shortestDistance = totalDistance;
                bestPath = path;
            }
        }

        return bestPath;
    }

    private List<Integer> findPathStartingFrom(int startNode) {
        List<Integer> path = new ArrayList<>();
        path.add(startNode);

        int currentNode = startNode;
        for (int i = 0; i < distances.length - 1; i++) {
            double minDistance = Double.MAX_VALUE;
            int nextNode = -1;
            for (int j = 0; j < distances.length; j++) {
                if (distances[currentNode][j] < minDistance && !path.contains(j)) {
                    minDistance = distances[currentNode][j];
                    nextNode = j;
                }
            }
            path.add(nextNode);
            currentNode = nextNode;
        }

        // Volvemos al nodo de origen
        path.add(startNode);

        return path;
    }

    private double calculateTotalDistance(List<Integer> path) {
        double totalDistance = 0;
        for (int i = 0; i < path.size() - 1; i++) {
            int node1 = path.get(i);
            int node2 = path.get(i + 1);
            totalDistance += distances[node1][node2];
        }
        return totalDistance;
    }
}


Resultado:

run:
> Ruta:
_ P ` J S A Z W E X R Q Y H K \ M V F B L [ N C T G D ] ^ I O U _
> La distancia total recorrida es: 25606
BUILD SUCCESSFUL (total time: 0 seconds)

sábado, 10 de agosto de 2024

Problema del Viajante de Comercio TSP (V.3). Método Optimization N-Opt.

El algoritmo TSP Optimization (N-opt) es una técnica heurística generalizada utilizada para mejorar la solución del Problema del Viajante de Comercio (TSP). Este enfoque permite seleccionar y modificar un número arbitrario de aristas (N) en la ruta actual, donde N representa el número de segmentos que se consideran para ser reordenados. Al igual que con las variantes más simples, como el 2-opt o el 3-opt, el N-opt busca encontrar una ruta más corta, pero con una mayor flexibilidad y un espacio de búsqueda más amplio, lo que potencialmente conduce a mejores soluciones. Sin embargo, al aumentar N, también se incrementa la complejidad computacional, y como en las otras variantes, no garantiza encontrar el óptimo global.



Código Java 1 (TSP_Optimization.java):

package tsp_optimization;

import java.util.ArrayList;
import java.util.List;

public class TSP_Optimization {

    public static void main(String[] args) {

        double[][] distances = {
            {0, 1190, 1255, 7549, 7009, 4245, 7539, 314, 993, 5236, 3676, 2508, 8987, 5886, 1835},
            {1190, 0, 7723, 3900, 7082, 8972, 8360, 5127, 6002, 8613, 5598, 7216, 7303, 1013, 2294},
            {1255, 7723, 0, 7843, 6636, 9905, 3190, 5337, 8012, 6704, 9300, 6966, 328, 2112, 1028},
            {7549, 3900, 7843, 0, 2657, 5301, 9294, 1987, 8633, 6415, 2611, 8728, 3895, 7705, 7429},
            {7009, 7082, 6636, 2657, 0, 8304, 2569, 9744, 7886, 9015, 8502, 4337, 5159, 32, 8341},
            {4245, 8972, 9905, 5301, 8304, 0, 9945, 4113, 3297, 8881, 9562, 9211, 4182, 7529, 4457},
            {7539, 8360, 3190, 9294, 2569, 9945, 0, 1714, 2308, 7467, 1861, 7895, 7867, 240, 2956},
            {314, 5127, 5337, 1987, 9744, 4113, 1714, 0, 7642, 2461, 9780, 9201, 640, 9583, 8358},
            {993, 6002, 8012, 8633, 7886, 3297, 2308, 7642, 0, 8584, 6593, 3903, 3533, 5105, 5461},
            {5236, 8613, 6704, 6415, 9015, 8881, 7467, 2461, 8584, 0, 94, 9758, 2375, 5656, 3203},
            {3676, 5598, 9300, 2611, 8502, 9562, 1861, 9780, 6593, 94, 0, 6284, 3894, 948, 633},
            {2508, 7216, 6966, 8728, 4337, 9211, 7895, 9201, 3903, 9758, 6284, 0, 4675, 4214, 9524},
            {8987, 7303, 328, 3895, 5159, 4182, 7867, 640, 3533, 2375, 3894, 4675, 0, 7004, 3146},
            {5886, 1013, 2112, 7705, 32, 7529, 240, 9583, 5105, 5656, 948, 4214, 7004, 0, 1020},
            {1835, 2294, 1028, 7429, 8341, 4457, 2956, 8358, 5461, 3203, 633, 9524, 3146, 1020, 0}
        };

        int n = distances.length;
        List<String> cityNames = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char letter = (char) ('A' + i);
            cityNames.add(String.valueOf(letter));
        }

        int N = 4; // Puedes cambiar el valor de N según lo necesites
        TSPNOpt tspN = new TSPNOpt(distances, N);
        bestRoute = tspN.findBestRoute(100);
        bestDistance = tspN.calculateTotalDistance(bestRoute);

        System.out.println("Matriz de distancias :");
        for (double[] distance : distances) {
            for (int j = 0; j < distance.length; j++) {
                System.out.printf("%7d", Math.round(distance[j]));
            }
            System.out.println();
        }
        System.out.println();

        System.out.println("> Mejor ruta encontrada:");
        bestRoute.forEach(city -> {
            System.out.print(cityNames.get(city) + " ");
        });
        System.out.println(cityNames.get(bestRoute.get(0)));
        System.out.println("> La distancia total recorrida es: " + bestDistance);

    }

}


Código Java 2 (TSPNOpt.java):

package tsp_optimization;

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

public class TSPNOpt {

    private final double[][] distances;
    private final int numCities;
    private final int N;

    public TSPNOpt(double[][] distances, int N) {
        this.distances = distances;
        this.numCities = distances.length;
        this.N = N;
    }

    public List<Integer> findBestRoute(int numRuns) {
        List<Integer> bestRoute = null;
        double bestDistance = Double.MAX_VALUE;

        for (int run = 0; run < numRuns; run++) {
            List<Integer> route = generateRandomRoute();
            route = optimizeRoute(route);

            double distance = calculateTotalDistance(route);
            if (distance < bestDistance) {
                bestDistance = distance;
                bestRoute = new ArrayList<>(route);
            }
        }

        return bestRoute;
    }

    private List<Integer> generateRandomRoute() {
        List<Integer> route = new ArrayList<>();
        for (int i = 0; i < numCities; i++) {
            route.add(i);
        }
        Collections.shuffle(route);
        return route;
    }

    private List<Integer> optimizeRoute(List<Integer> route) {
        boolean improved = true;
        while (improved) {
            improved = false;
            for (int i = 0; i < numCities - N + 1; i++) {
                for (int j = i + 1; j < numCities - N + 2; j++) {
                    List<Integer> newRoute = nOptSwap(route, i, j);
                    if (calculateTotalDistance(newRoute) < calculateTotalDistance(route)) {
                        route = newRoute;
                        improved = true;
                    }
                }
            }
        }
        return route;
    }

    private List<Integer> nOptSwap(List<Integer> route, int i, int j) {
        List<Integer> newRoute = new ArrayList<>(route.subList(0, i));
        List<Integer> subRoute = new ArrayList<>(route.subList(i, j + 1));
        Collections.reverse(subRoute);
        newRoute.addAll(subRoute);
        newRoute.addAll(route.subList(j + 1, route.size()));
        return newRoute;
    }

    public double calculateTotalDistance(List<Integer> route) {
        double totalDistance = 0;
        for (int i = 0; i < route.size(); i++) {
            totalDistance += distances[route.get(i)][route.get((i + 1) % route.size())];
        }
        return totalDistance;
    }
}


Resultado:

run:
Matriz de distancias:
      0   1190   1255   7549   7009   4245   7539    314    993   5236   3676   2508   8987   5886   1835
   1190      0   7723   3900   7082   8972   8360   5127   6002   8613   5598   7216   7303   1013   2294
   1255   7723      0   7843   6636   9905   3190   5337   8012   6704   9300   6966    328   2112   1028
   7549   3900   7843      0   2657   5301   9294   1987   8633   6415   2611   8728   3895   7705   7429
   7009   7082   6636   2657      0   8304   2569   9744   7886   9015   8502   4337   5159     32   8341
   4245   8972   9905   5301   8304      0   9945   4113   3297   8881   9562   9211   4182   7529   4457
   7539   8360   3190   9294   2569   9945      0   1714   2308   7467   1861   7895   7867    240   2956
    314   5127   5337   1987   9744   4113   1714      0   7642   2461   9780   9201    640   9583   8358
    993   6002   8012   8633   7886   3297   2308   7642      0   8584   6593   3903   3533   5105   5461
   5236   8613   6704   6415   9015   8881   7467   2461   8584      0     94   9758   2375   5656   3203
   3676   5598   9300   2611   8502   9562   1861   9780   6593     94      0   6284   3894    948    633
   2508   7216   6966   8728   4337   9211   7895   9201   3903   9758   6284      0   4675   4214   9524
   8987   7303    328   3895   5159   4182   7867    640   3533   2375   3894   4675      0   7004   3146
   5886   1013   2112   7705     32   7529    240   9583   5105   5656    948   4214   7004      0   1020
   1835   2294   1028   7429   8341   4457   2956   8358   5461   3203    633   9524   3146   1020      0

> Mejor ruta encontrada:
F D E N G K J H M C O B A L I F
> La distancia total recorrida es: 27834.0
BUILD SUCCESSFUL (total time: 0 seconds)

Con la tecnología de Blogger.