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)
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).
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)