El código implementa el algoritmo Ramificación y Poda (TSPBB) para resolver el Problema del Viajante de Comercio (TSP). Explora sistemáticamente todas las rutas posibles, comenzando desde una ciudad inicial. Utiliza recursión y un array para rastrear ciudades visitadas. Mantiene actualizada la mejor ruta encontrada, podando ramas subóptimas para mejorar la eficiencia. El proceso continúa hasta explorar todas las combinaciones viables, garantizando la solución óptima.
Características:
1. Efectividad: Garantiza encontrar la solución óptima, aunque puede ser lento para un gran número de ciudades debido a su naturaleza exhaustiva.
2. Poda: Descarta ramas subóptimas, mejorando la eficiencia.
3. Exhaustividad: Explora todo el espacio de soluciones viable.
4. Memoria eficiente: Usa backtracking, requiriendo menos memoria que métodos que almacenan todas las soluciones.
5. Determinismo: Siempre produce el mismo resultado para los mismos datos de entrada.
Código Java (TSP_BranchAndBound.java):
package tsp_branchandbound;
import java.util.Arrays;
public class TSP_BranchAndBound {
public static void main(String[] args) {
double[][] distances = {
{0, 4008, 9665, 4771, 1778, 7977, 6458, 4382, 6975, 5656, 1866, 5567, 9295, 6606, 5620, 660},
{4008, 0, 6944, 5136, 7793, 2325, 1371, 9034, 457, 4749, 8772, 2501, 7517, 9010, 2227, 6696},
{9665, 6944, 0, 1620, 4822, 5690, 2570, 4991, 5606, 5347, 789, 683, 5823, 3832, 5270, 2851},
{4771, 5136, 1620, 0, 1537, 2606, 4129, 4096, 924, 7534, 114, 270, 4023, 7169, 5630, 8939},
{1778, 7793, 4822, 1537, 0, 8463, 4904, 8184, 1695, 204, 4358, 1615, 5363, 2176, 9802, 5605},
{7977, 2325, 5690, 2606, 8463, 0, 8239, 4344, 6284, 7034, 5428, 373, 8147, 6935, 6579, 1988},
{6458, 1371, 2570, 4129, 4904, 8239, 0, 3809, 2582, 3048, 1609, 2428, 6958, 5622, 3067, 4746},
{4382, 9034, 4991, 4096, 8184, 4344, 3809, 0, 9133, 7408, 1592, 9464, 782, 9170, 2441, 8855},
{6975, 457, 5606, 924, 1695, 6284, 2582, 9133, 0, 971, 7738, 4865, 7364, 6892, 1542, 5583},
{5656, 4749, 5347, 7534, 204, 7034, 3048, 7408, 971, 0, 9410, 4268, 3898, 8930, 7749, 6348},
{1866, 8772, 789, 114, 4358, 5428, 1609, 1592, 7738, 9410, 0, 6926, 1324, 7214, 1873, 8162},
{5567, 2501, 683, 270, 1615, 373, 2428, 9464, 4865, 4268, 6926, 0, 271, 3262, 8201, 4239},
{9295, 7517, 5823, 4023, 5363, 8147, 6958, 782, 7364, 3898, 1324, 271, 0, 4325, 1593, 8763},
{6606, 9010, 3832, 7169, 2176, 6935, 5622, 9170, 6892, 8930, 7214, 3262, 4325, 0, 5532, 7356},
{5620, 2227, 5270, 5630, 9802, 6579, 3067, 2441, 1542, 7749, 1873, 8201, 1593, 5532, 0, 2441},
{660, 6696, 2851, 8939, 5605, 1988, 4746, 8855, 5583, 6348, 8162, 4239, 8763, 7356, 2441, 0}
};
TSPBB tsp = new TSPBB(distances);
System.out.println("Mejor Ruta: " + Arrays.toString(tsp.getBestRoute()));
System.out.println("Distancia mínima: " + tsp.getBestDistance());
}
}
Código Java (TSPBB.java):
package tsp_branchandbound;
public class TSPBB {
private final double[][] distanceMatrix;
private final int numCities;
private final boolean[] visited;
private final int[] bestRoute;
private double bestDistance;
public TSPBB(double[][] distanceMatrix) {
this.distanceMatrix = distanceMatrix;
this.numCities = distanceMatrix.length;
this.visited = new boolean[numCities];
this.bestRoute = new int[numCities]; // Sin el regreso al inicio
this.bestDistance = Double.MAX_VALUE;
// Iniciar el algoritmo de Ramificación y Poda
int[] currentRoute = new int[numCities];
currentRoute[0] = 0; // Comenzar desde la primera ciudad
visited[0] = true;
branchAndBound(0, 1, 0.0, currentRoute);
}
private void branchAndBound(int currentCity, int level, double currentDistance, int[] currentRoute) {
// Si hemos visitado todas las ciudades
if (level == numCities) {
// Sumar la distancia de regreso a la ciudad inicial
double totalDistance = currentDistance + distanceMatrix[currentCity][0];
if (totalDistance < bestDistance) {
bestDistance = totalDistance;
System.arraycopy(currentRoute, 0, bestRoute, 0, numCities);
}
return;
}
for (int i = 0; i < numCities; i++) {
if (!visited[i]) {
visited[i] = true;
currentRoute[level] = i;
double nextDistance = currentDistance + distanceMatrix[currentCity][i];
if (nextDistance < bestDistance) {
branchAndBound(i, level + 1, nextDistance, currentRoute);
}
visited[i] = false;
}
}
}
public int[] getBestRoute() {
return bestRoute;
}
public double getBestDistance() {
return bestDistance;
}
}
Resultado:
run:
Mejor Ruta: [0, 10, 3, 2, 13, 4, 9, 8, 1, 6, 14, 7, 12, 11, 5, 15]
Distancia mínima: 22193.0
BUILD SUCCESSFUL (total time: 2 seconds)
miércoles, 14 de agosto de 2024
Problema del viajante de Comercio TSP (VIII). Método Ramificación y Poda (Branch and Bound).
martes, 13 de agosto de 2024
Problema del viajante de Comercio TSP (VII). Método Held-Karp.
El algoritmo de Held-Karp es una mejora significativa sobre la fuerza bruta en términos de eficiencia, especialmente cuando el número de ciudades es grande. Sin embargo, al igual que la fuerza bruta, Held-Karp es exacto y garantiza encontrar la solución óptima (ruta mas corta posible).
Características:
1. Método: Utiliza programación dinámica para evitar recalcular subproblemas y, por lo tanto, reduce el número de cálculos necesarios.
2. Complejidad Computacional: O(n^2 * 2^n). Aunque sigue siendo exponencial, es mucho más eficiente que la fuerza bruta. El algoritmo almacena resultados intermedios en una tabla (memorización), lo que reduce drásticamente el número de cálculos.
3. Precisión: Siempre encuentra la solución óptima, igual que la fuerza bruta.
Código Java (TSP_HeldKarp.java):
package tsp_heldkarp;
import java.util.Arrays;
public class TSP_HeldKarp {
public static void main(String[] args) {
// Matriz de distancias de 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}
};
TSPHK tsp = new TSPHK distances);
System.out.println("Mejor Ruta: " + Arrays.toString(tsp.getBestRoute()));
System.out.println("Distancia mínima: " + tsp.getBestDistance());
}
}
Código Java (TSPHK.java):
package tsp_heldkarp;
import java.util.HashMap;
import java.util.Map;
public class TSPHK {
private final double[][] distanceMatrix;
private final int numCities;
private final Map<String, Double> memo; // Para almacenar los resultados de subproblemas
private int[] bestRoute;
private double bestDistance;
public TSPHK(double[][] distanceMatrix) {
this.distanceMatrix = distanceMatrix;
this.numCities = distanceMatrix.length;
this.memo = new HashMap<>();
this.bestRoute = new int[numCities];
this.bestDistance = Double.MAX_VALUE;
// Calcula la mejor ruta y la distancia mínima
calculateOptimalRoute();
}
private void calculateOptimalRoute() {
int fullSet = (1 << numCities) - 1; // Representación binaria de todos los nodos visitados
double optimalDistance = heldKarp(0, fullSet);
reconstructRoute();
this.bestDistance = optimalDistance;
}
private double heldKarp(int position, int set) {
// Caso base: si solo queda el nodo inicial
if (set == (1 << position)) {
return distanceMatrix[0][position];
}
String key = position + "," + set;
if (memo.containsKey(key)) {
return memo.get(key);
}
double minDistance = Double.MAX_VALUE;
// Excluimos el nodo actual del conjunto
int remainingSet = set & ~(1 << position);
// Evaluamos las posibles rutas
for (int i = 0; i < numCities; i++) {
if (i != position && (set & (1 << i)) != 0) {
double distance = heldKarp(i, remainingSet) + distanceMatrix[i][position];
if (distance < minDistance) {
minDistance = distance;
}
}
}
memo.put(key, minDistance);
return minDistance;
}
private void reconstructRoute() {
int[] route = new int[numCities];
int position = 0;
int set = (1 << numCities) - 1;
for (int i = 0; i < numCities; i++) {
int bestNextCity = -1;
double minDistance = Double.MAX_VALUE;
int remainingSet = set & ~(1 << position);
for (int j = 0; j < numCities; j++) {
if ((set & (1 << j)) != 0 && j != position) {
double currentDistance = heldKarp(j, remainingSet) + distanceMatrix[j][position];
if (currentDistance < minDistance) {
minDistance = currentDistance;
bestNextCity = j;
}
}
}
route[i] = position;
set = set & ~(1 << position);
position = bestNextCity;
}
this.bestRoute = route;
}
public int[] getBestRoute() {
return bestRoute;
}
public double getBestDistance() {
return bestDistance;
}
}
Resultado:
run:
Mejor Ruta: [0, 7, 8, 5, 9, 6, 3, 4, 12, 2, 11, 10, 13, 15, 1, 14]
Distancia mínima: 20699.0
BUILD SUCCESSFUL (total time: 0 seconds)
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)