El algoritmo formula el TSP como un problema de optimización matemática donde las variables de decisión son enteras (generalmente binarias). Busca minimizar la distancia total del recorrido sujeto a restricciones que aseguran que cada ciudad se visite exactamente una vez y que el tour sea continuo.
Características:
. Exactitud: Garantiza encontrar la solución óptima global, si existe y si el algoritmo se ejecuta hasta su finalización.
. Formulación matemática: Utiliza variables binarias para representar las decisiones de viaje entre ciudades.
. Función objetivo: Minimiza la suma de las distancias entre las ciudades visitadas consecutivamente.
. Complejidad: Es un problema NP-duro, lo que significa que el tiempo de ejecución puede crecer exponencialmente con el tamaño del problema.
. Métodos de resolución: Suele utilizar técnicas como ramificación y acotación (branch and bound) o planos de corte (cutting planes).
. Escalabilidad: Eficiente para instancias pequeñas a medianas, pero puede volverse computacionalmente intensivo para problemas grandes.
. Flexibilidad: Permite incorporar fácilmente restricciones adicionales al problema base.
. Precisión: No se ve afectado por errores de redondeo como algunos métodos heurísticos.
. Uso de software especializado: A menudo se implementa utilizando solucionadores de programación lineal entera como CPLEX, Gurobi o CBC.
Código Java (TSP_IntegerProgramming):
package tsp_programacionlinealentera;
import java.util.ArrayList;
public class TSP_ProgramacionLinealEntera {
public static void main(String[] args) {
double[][] distanceMatrix = {
{0, 8128, 823, 8767, 1253, 8827, 5106, 5501, 7097, 8026, 7162, 2260, 4441, 510, 7138, 6509},
{8128, 0, 6653, 9241, 4344, 7231, 1503, 7145, 6571, 6217, 9412, 9051, 1931, 5817, 8633, 8513},
{823, 6653, 0, 7900, 1178, 1820, 1262, 678, 9930, 6739, 9965, 908, 9481, 7708, 1874, 9303},
{8767, 9241, 7900, 0, 589, 9827, 520, 6671, 9859, 4489, 1642, 1045, 1760, 5607, 5053, 7776},
{1253, 4344, 1178, 589, 0, 5829, 5823, 3482, 9090, 9537, 8507, 3802, 3302, 2944, 8613, 7257},
{8827, 7231, 1820, 9827, 5829, 0, 9288, 6497, 5442, 4381, 9297, 2086, 1372, 5616, 1981, 3412},
{5106, 1503, 1262, 520, 5823, 9288, 0, 3242, 5625, 4715, 7754, 2366, 8314, 1360, 623, 3915},
{5501, 7145, 678, 6671, 3482, 6497, 3242, 0, 1522, 6648, 324, 8704, 7602, 8091, 1608, 1286},
{7097, 6571, 9930, 9859, 9090, 5442, 5625, 1522, 0, 7740, 7480, 2266, 9346, 967, 9585, 9113},
{8026, 6217, 6739, 4489, 9537, 4381, 4715, 6648, 7740, 0, 9509, 7830, 5276, 7174, 8535, 2604},
{7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 9509, 0, 1847, 8948, 9498, 9456, 4716},
{2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 7830, 1847, 0, 1620, 6634, 7744, 9744},
{4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 5276, 8948, 1620, 0, 2261, 3892, 7722},
{510, 5817, 7708, 5607, 2944, 5616, 1360, 8091, 967, 7174, 9498, 6634, 2261, 0, 6734, 6447},
{7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 8535, 9456, 7744, 3892, 6734, 0, 2382},
{6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 2604, 4716, 9744, 7722, 6447, 2382, 0}
};
TSPIP tsp = new TSPIP(distanceMatrix);
ArrayList<Integer> bestRoute = tsp.solve();
double bestDistance = tsp.calculateTotalDistance(bestRoute);
System.out.println("Ruta óptima aproximada encontrada: " + bestRoute);
System.out.println("Distancia mínima aproximada: " + bestDistance);
}
}
Código Java (TSPIP.java):
package tsp_programacionlinealentera;
import java.util.ArrayList;
public class TSPIP {
private final double[][] distanceMatrix;
private final int numCities;
public TSPIP(double[][] distanceMatrix) {
this.distanceMatrix = distanceMatrix;
this.numCities = distanceMatrix.length;
}
public ArrayList<Integer> solve() {
ArrayList<Integer> currentRoute = new ArrayList<>();
for (int i = 0; i < numCities; i++) {
currentRoute.add(i);
}
double currentDistance = calculateTotalDistance(currentRoute);
boolean improved = true;
while (improved) {
improved = false;
for (int i = 1; i < numCities - 1; i++) {
for (int j = i + 1; j < numCities; j++) {
ArrayList<Integer> newRoute = new ArrayList<>(currentRoute);
reverse(newRoute, i, j);
double newDistance = calculateTotalDistance(newRoute);
if (newDistance < currentDistance) {
currentRoute = newRoute;
currentDistance = newDistance;
improved = true;
}
}
}
}
return currentRoute;
}
private void reverse(ArrayList<Integer> route, int start, int end) {
while (start < end) {
int temp = route.get(start);
route.set(start, route.get(end));
route.set(end, temp);
start++;
end--;
}
}
public double calculateTotalDistance(ArrayList<Integer> route) {
double totalDistance = 0.0;
for (int i = 0; i < route.size() - 1; i++) {
totalDistance += distanceMatrix[route.get(i)][route.get(i + 1)];
}
totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Return to start
return totalDistance;
}
}
Resultado:
run:
Ruta óptima aproximada encontrada: [0, 4, 3, 10, 7, 8, 11, 2, 14, 5, 12, 1, 9, 15, 6, 13]
Distancia mínima aproximada: 30268.0
BUILD SUCCESSFUL (total time: 0 seconds)
jueves, 15 de agosto de 2024
Problema del viajante de Comercio TSP (XIV). Método Programación Lineal Entera (PLE).
Problema del viajante de Comercio TSP (XIII). Método Aproximación de Christofides.
El Algoritmo de Aproximación de Christofides es un método para resolver el Problema del Viajante de Comercio (TSP).
Características:
Garantía de aproximación: Proporciona una solución que es, como máximo, 3/2 veces el óptimo para instancias que cumplen la desigualdad triangular.
Complejidad: Tiene una complejidad temporal de O(n^3), donde n es el número de ciudades.
Pasos principales:
1.Construye un árbol de expansión mínima (MST)
2.Encuentra vértices de grado impar en el MST
3.Crea un emparejamiento perfecto de mínimo peso para estos vértices
4.Combina el MST y el emparejamiento para formar un circuito euleriano
5.Convierte el circuito euleriano en un tour hamiltoniano
Aplicabilidad: Es especialmente útil para instancias del TSP que cumplen la desigualdad triangular.
Eficiencia: Ofrece un buen equilibrio entre calidad de la solución y tiempo de ejecución.
Limitaciones: No garantiza el óptimo global y su rendimiento puede degradarse en instancias que no cumplen la desigualdad triangular.
Código Java (TSP_Christofides.java):
package tsp_christofides;
import java.util.ArrayList;
public class TSP_Christofides {
public static void main(String[] args) {
double[][] distanceMatrix = {
{0, 8128, 823, 8767, 1253, 8827, 5106, 5501, 7097, 8026, 7162, 2260, 4441, 510, 7138, 6509},
{8128, 0, 6653, 9241, 4344, 7231, 1503, 7145, 6571, 6217, 9412, 9051, 1931, 5817, 8633, 8513},
{823, 6653, 0, 7900, 1178, 1820, 1262, 678, 9930, 6739, 9965, 908, 9481, 7708, 1874, 9303},
{8767, 9241, 7900, 0, 589, 9827, 520, 6671, 9859, 4489, 1642, 1045, 1760, 5607, 5053, 7776},
{1253, 4344, 1178, 589, 0, 5829, 5823, 3482, 9090, 9537, 8507, 3802, 3302, 2944, 8613, 7257},
{8827, 7231, 1820, 9827, 5829, 0, 9288, 6497, 5442, 4381, 9297, 2086, 1372, 5616, 1981, 3412},
{5106, 1503, 1262, 520, 5823, 9288, 0, 3242, 5625, 4715, 7754, 2366, 8314, 1360, 623, 3915},
{5501, 7145, 678, 6671, 3482, 6497, 3242, 0, 1522, 6648, 324, 8704, 7602, 8091, 1608, 1286},
{7097, 6571, 9930, 9859, 9090, 5442, 5625, 1522, 0, 7740, 7480, 2266, 9346, 967, 9585, 9113},
{8026, 6217, 6739, 4489, 9537, 4381, 4715, 6648, 7740, 0, 9509, 7830, 5276, 7174, 8535, 2604},
{7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 9509, 0, 1847, 8948, 9498, 9456, 4716},
{2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 7830, 1847, 0, 1620, 6634, 7744, 9744},
{4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 5276, 8948, 1620, 0, 2261, 3892, 7722},
{510, 5817, 7708, 5607, 2944, 5616, 1360, 8091, 967, 7174, 9498, 6634, 2261, 0, 6734, 6447},
{7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 8535, 9456, 7744, 3892, 6734, 0, 2382},
{6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 2604, 4716, 9744, 7722, 6447, 2382, 0}
};
TSPCh tsp = new TSPCh(distanceMatrix);
ArrayList<Integer> bestRoute = tsp.solve();
double bestDistance = tsp.calculateTotalDistance(bestRoute);
// Verificar la desigualdad triangular
if (!tsp.checkTriangleInequality()) {
System.out.println("ADVERTENCIA: La matriz de distancias no cumple con la desigualdad triangular.");
System.out.println("El resultado puede no ser óptimo o estar alejado del óptimo esperado.\n");
}
System.out.println("Ruta óptima aproximada encontrada: " + bestRoute);
System.out.println("Distancia mínima aproximada: " + bestDistance);
}
}
Código Java (TSPCh.java):
package tsp_christofides;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Stack;
public class TSPCh {
private final double[][] distanceMatrix;
private final int numCities;
public TSPCh(double[][] distanceMatrix) {
this.distanceMatrix = distanceMatrix;
this.numCities = distanceMatrix.length;
}
public ArrayList<Integer> solve() {
ArrayList<int[]> mstEdges = generateMST();
ArrayList<Integer> oddDegreeNodes = findOddDegreeNodes(mstEdges);
ArrayList<int[]> perfectMatching = generatePerfectMatching(oddDegreeNodes);
ArrayList<int[]> eulerianCircuit = combineMSTAndMatching(mstEdges, perfectMatching);
return findHamiltonianCircuit(eulerianCircuit);
}
private ArrayList<int[]> generateMST() {
boolean[] inMST = new boolean[numCities];
double[] key = new double[numCities];
int[] parent = new int[numCities];
Arrays.fill(key, Double.MAX_VALUE);
key[0] = 0;
parent[0] = -1;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingDouble(o -> key[o[0]]));
pq.add(new int[]{0, -1});
ArrayList<int[]> mstEdges = new ArrayList<>();
while (!pq.isEmpty()) {
int u = pq.poll()[0];
inMST[u] = true;
for (int v = 0; v < numCities; v++) {
if (!inMST[v] && distanceMatrix[u][v] < key[v]) {
key[v] = distanceMatrix[u][v];
pq.add(new int[]{v, u});
parent[v] = u;
}
}
}
for (int i = 1; i < numCities; i++) {
mstEdges.add(new int[]{i, parent[i]});
}
return mstEdges;
}
private ArrayList<Integer> findOddDegreeNodes(ArrayList<int[]> mstEdges) {
int[] degree = new int[numCities];
for (int[] edge : mstEdges) {
degree[edge[0]]++;
degree[edge[1]]++;
}
ArrayList<Integer> oddDegreeNodes = new ArrayList<>();
for (int i = 0; i < numCities; i++) {
if (degree[i] % 2 != 0) {
oddDegreeNodes.add(i);
}
}
return oddDegreeNodes;
}
private ArrayList<int[]> generatePerfectMatching(ArrayList<Integer> oddDegreeNodes) {
ArrayList<int[]> perfectMatching = new ArrayList<>();
boolean[] matched = new boolean[numCities];
for (int i = 0; i < oddDegreeNodes.size(); i++) {
if (matched[oddDegreeNodes.get(i)]) {
continue;
}
int minJ = -1;
double minDistance = Double.MAX_VALUE;
for (int j = i + 1; j < oddDegreeNodes.size(); j++) {
if (!matched[oddDegreeNodes.get(j)] && distanceMatrix[oddDegreeNodes.get(i)][oddDegreeNodes.get(j)] < minDistance) {
minDistance = distanceMatrix[oddDegreeNodes.get(i)][oddDegreeNodes.get(j)];
minJ = j;
}
}
matched[oddDegreeNodes.get(i)] = true;
matched[oddDegreeNodes.get(minJ)] = true;
perfectMatching.add(new int[]{oddDegreeNodes.get(i), oddDegreeNodes.get(minJ)});
}
return perfectMatching;
}
private ArrayList<int[]> combineMSTAndMatching(ArrayList<int[]> mstEdges, ArrayList<int[]> perfectMatching) {
ArrayList<int[]> combinedGraph = new ArrayList<>(mstEdges);
combinedGraph.addAll(perfectMatching);
return combinedGraph;
}
private ArrayList<Integer> findHamiltonianCircuit(ArrayList<int[]> eulerianCircuit) {
LinkedHashSet<Integer> visited = new LinkedHashSet<>();
Stack<Integer> stack = new Stack<>();
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : eulerianCircuit) {
graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
}
stack.push(0);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited.contains(node)) {
visited.add(node);
if (graph.containsKey(node)) {
for (int neighbor : graph.get(node)) {
stack.push(neighbor);
}
}
}
}
return new ArrayList<>(visited);
}
public double calculateTotalDistance(ArrayList<Integer> route) {
double totalDistance = 0.0;
for (int i = 0; i < route.size() - 1; i++) {
int city1 = route.get(i);
int city2 = route.get(i + 1);
totalDistance += distanceMatrix[city1][city2];
}
totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Return to start city
return totalDistance;
}
public boolean checkTriangleInequality() {
for (int i = 0; i < numCities; i++) {
for (int j = 0; j < numCities; j++) {
for (int k = 0; k < numCities; k++) {
if (distanceMatrix[i][j] > distanceMatrix[i][k] + distanceMatrix[k][j]) {
return false;
}
}
}
}
return true;
}
}
Resultado:
run:
ADVERTENCIA: La matriz de distancias no cumple con la desigualdad triangular.
El resultado puede no ser óptimo o estar alejado del óptimo esperado.
Ruta óptima aproximada encontrada: [0, 13, 8, 11, 12, 5, 14, 6, 1, 3, 4, 2, 7, 15, 9, 10]
Distancia mínima aproximada: 43089.0
BUILD SUCCESSFUL (total time: 0 seconds)
Problema del viajante de Comercio TSP (XII). Método de Recocido Simulado (Simulated Annealing).
El Algoritmo de Recocido Simulado (Simulated Annealing) es una técnica metaheurística inspirada en el proceso de enfriamiento de metales, donde se trata de encontrar una solución cercana al óptimo global para problemas de optimización, como el Problema del Viajero (TSP). El algoritmo funciona de la siguiente manera:
Inicialización: Comienza con una solución inicial (ruta en el caso del TSP) y una temperatura inicial alta.
Vecindario: En cada iteración, se genera una nueva solución en el vecindario de la solución actual, por ejemplo, intercambiando dos ciudades en la ruta.
Aceptación de Soluciones: La nueva solución se acepta automáticamente si es mejor que la solución actual. Si es peor, se acepta con una probabilidad que disminuye a medida que la temperatura baja, permitiendo así escapar de óptimos locales.
Enfriamiento: La temperatura se reduce gradualmente según una política de enfriamiento, hasta que se alcanza un umbral mínimo, momento en el que se detiene la búsqueda.
Criterio de Terminación: El algoritmo termina cuando la temperatura es muy baja o después de un número fijo de iteraciones sin mejora significativa.
Código Java (TSP_RecocidoSimulado.java):
package tsp_recocidosimulado;
import java.util.ArrayList;
import java.util.Collections;
public class TSP_RecocidoSimulado {
public static void main(String[] args) {
double[][] distanceMatrix = {
{0, 8128, 823, 8767, 1253, 8827, 5106, 5501, 7097, 8026, 7162, 2260, 4441, 510, 7138, 6509},
{8128, 0, 6653, 9241, 4344, 7231, 1503, 7145, 6571, 6217, 9412, 9051, 1931, 5817, 8633, 8513},
{823, 6653, 0, 7900, 1178, 1820, 1262, 678, 9930, 6739, 9965, 908, 9481, 7708, 1874, 9303},
{8767, 9241, 7900, 0, 589, 9827, 520, 6671, 9859, 4489, 1642, 1045, 1760, 5607, 5053, 7776},
{1253, 4344, 1178, 589, 0, 5829, 5823, 3482, 9090, 9537, 8507, 3802, 3302, 2944, 8613, 7257},
{8827, 7231, 1820, 9827, 5829, 0, 9288, 6497, 5442, 4381, 9297, 2086, 1372, 5616, 1981, 3412},
{5106, 1503, 1262, 520, 5823, 9288, 0, 3242, 5625, 4715, 7754, 2366, 8314, 1360, 623, 3915},
{5501, 7145, 678, 6671, 3482, 6497, 3242, 0, 1522, 6648, 324, 8704, 7602, 8091, 1608, 1286},
{7097, 6571, 9930, 9859, 9090, 5442, 5625, 1522, 0, 7740, 7480, 2266, 9346, 967, 9585, 9113},
{8026, 6217, 6739, 4489, 9537, 4381, 4715, 6648, 7740, 0, 1527, 4847, 4770, 5032, 3387, 3706},
{7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 1527, 0, 2399, 9453, 7380, 8661, 1177},
{2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 4847, 2399, 0, 3224, 4943, 8957, 8156},
{4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 4770, 9453, 3224, 0, 4289, 5709, 2858},
{510, 5817, 7708, 5607, 2944, 5616, 1360, 5176, 967, 3706, 6509, 7380, 1942, 0, 6631, 1397},
{7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 3387, 8661, 8957, 5709, 6631, 0, 2345},
{6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 3706, 1177, 8156, 2858, 1397, 2345, 0}
};
// Parametros de entrada:
double TemperaturaInicial = 10000;
double TasaEnfriamiento = 0.9999;
int NumeroIteraciones = 1000000;
TSPRS tsp = new TSPRS(distanceMatrix, TemperaturaInicial, TasaEnfriamiento, NumeroIteraciones);
// Generar una solución inicial (ruta aleatoria)
ArrayList<Integer> initialRoute = new ArrayList<>();
for (int i = 0; i < distanceMatrix.length; i++) {
initialRoute.add(i);
}
Collections.shuffle(initialRoute);
// Resolver el TSP usando Recocido Simulado
ArrayList<Integer> bestRoute = tsp.solve(initialRoute);
double bestDistance = tsp.calculateTotalDistance(bestRoute);
// Imprimir los resultados
System.out.println("Ruta óptima encontrada: " + bestRoute);
System.out.println("Distancia mínima: " + bestDistance);
}
}
Código Java (TSPRS.java):
package tsp_recocidosimulado;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
public class TSPRS {
private final double[][] distanceMatrix;
private final double initialTemperature;
private final double coolingRate;
private final int maxIterations;
private final Random random;
public TSPRS(double[][] distanceMatrix, double initialTemperature, double coolingRate, int maxIterations) {
this.distanceMatrix = distanceMatrix;
this.initialTemperature = initialTemperature;
this.coolingRate = coolingRate;
this.maxIterations = maxIterations;
this.random = new Random();
}
public ArrayList<Integer> solve(ArrayList<Integer> initialRoute) {
ArrayList<Integer> currentRoute = new ArrayList<>(initialRoute);
ArrayList<Integer> bestRoute = new ArrayList<>(initialRoute);
double bestDistance = calculateTotalDistance(bestRoute);
double temperature = initialTemperature;
int iteration = 0;
while (temperature > 1 && iteration < maxIterations) {
ArrayList<Integer> newRoute = generateNeighbor(new ArrayList<>(currentRoute));
double currentDistance = calculateTotalDistance(currentRoute);
double newDistance = calculateTotalDistance(newRoute);
if (acceptanceProbability(currentDistance, newDistance, temperature) > random.nextDouble()) {
currentRoute = new ArrayList<>(newRoute);
}
if (calculateTotalDistance(currentRoute) < bestDistance) {
bestRoute = new ArrayList<>(currentRoute);
bestDistance = calculateTotalDistance(bestRoute);
}
temperature *= coolingRate;
iteration++;
}
return bestRoute;
}
private ArrayList<Integer> generateNeighbor(ArrayList<Integer> route) {
int pos1 = random.nextInt(route.size());
int pos2 = random.nextInt(route.size());
Collections.swap(route, pos1, pos2);
return route;
}
private double acceptanceProbability(double currentDistance, double newDistance, double temperature) {
if (newDistance < currentDistance) {
return 1.0;
}
return Math.exp((currentDistance - newDistance) / temperature);
}
double calculateTotalDistance(ArrayList<Integer> route) {
double totalDistance = 0.0;
for (int i = 0; i < route.size() - 1; i++) {
totalDistance += distanceMatrix[route.get(i)][route.get(i + 1)];
}
totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Regreso a la ciudad de inicio
return totalDistance;
}
}
Resultado:
run:
Ruta óptima encontrada: [7, 8, 11, 2, 5, 14, 6, 1, 12, 3, 4, 0, 13, 15, 9, 10]
Distancia mínima: 23620.0
BUILD SUCCESSFUL (total time: 0 seconds)
Problema del viajante de Comercio TSP (XI). Método Búsqueda Local (LS).
El Algoritmo de Búsqueda Local (LS) es una técnica de optimización heurística que busca mejorar una solución inicial explorando el espacio de soluciones vecinas. Es especialmente útil para problemas de optimización combinatoria, como el Problema del Viajante de Comercio (TSP).
Características:
Solución Inicial: Comienza con una solución factible, que puede generarse de manera aleatoria o utilizando heurísticas simples.
Vecinos: En cada iteración, el algoritmo genera una lista de soluciones vecinas a partir de la solución actual. Estos vecinos se obtienen mediante movimientos locales, que son pequeñas modificaciones a la solución (por ejemplo, intercambiar dos elementos en el TSP).
Criterio de Evaluación: La búsqueda local evalúa cada solución vecina y selecciona la que tenga el mejor valor según la función objetivo (en el TSP, la distancia total).
Actualización de la Solución: La solución actual se actualiza con la mejor solución vecina encontrada. Si la mejor solución vecina es peor que la solución actual, el algoritmo puede detenerse o seguir buscando.
Criterios de Parada: El algoritmo puede detenerse si no se encuentra una mejor solución después de un número predefinido de iteraciones (1 millon) o si se alcanza un criterio de convergencia.
Ventajas:
Simplicidad: Es fácil de implementar y entender.
Rapidez: A menudo converge rápidamente a una solución, especialmente para problemas de menor dimensión.
Desventajas:
Óptimos Locales: Puede quedarse atrapado en soluciones subóptimas, conocidas como óptimos locales, ya que solo explora soluciones cercanas a la actual.
Dependencia de la Solución Inicial: La calidad de la solución final puede depender significativamente de la solución inicial elegida.
Código Java (TSP_BusquedaLocal.java):
package tsp_busquedalocal;
import java.util.Arrays;
import java.util.Random;
public class TSP_BusquedaLocal {
public static void main(String[] args) {
double[][] distanceMatrix = {
{0, 8128, 823, 8767, 1253, 8827, 5106, 5501, 7097, 8026, 7162, 2260, 4441, 510, 7138, 6509},
{8128, 0, 6653, 9241, 4344, 7231, 1503, 7145, 6571, 6217, 9412, 9051, 1931, 5817, 8633, 8513},
{823, 6653, 0, 7900, 1178, 1820, 1262, 678, 9930, 6739, 9965, 908, 9481, 7708, 1874, 9303},
{8767, 9241, 7900, 0, 589, 9827, 520, 6671, 9859, 4489, 1642, 1045, 1760, 5607, 5053, 7776},
{1253, 4344, 1178, 589, 0, 5829, 5823, 3482, 9090, 9537, 8507, 3802, 3302, 2944, 8613, 7257},
{8827, 7231, 1820, 9827, 5829, 0, 9288, 6497, 5442, 4381, 9297, 2086, 1372, 5616, 1981, 3412},
{5106, 1503, 1262, 520, 5823, 9288, 0, 3242, 5625, 4715, 7754, 2366, 8314, 1360, 623, 3915},
{5501, 7145, 678, 6671, 3482, 6497, 3242, 0, 1522, 6648, 324, 8704, 7602, 8091, 1608, 1286},
{7097, 6571, 9930, 9859, 9090, 5442, 5625, 1522, 0, 7740, 7480, 2266, 9346, 967, 9585, 9113},
{8026, 6217, 6739, 4489, 9537, 4381, 4715, 6648, 7740, 0, 1527, 4847, 4770, 5032, 3387, 3706},
{7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 1527, 0, 2399, 9453, 7380, 8661, 1177},
{2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 4847, 2399, 0, 3224, 4943, 8957, 8156},
{4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 4770, 9453, 3224, 0, 4289, 5709, 2858},
{510, 5817, 7708, 5607, 2944, 5616, 1360, 8091, 967, 5032, 7380, 4943, 4289, 0, 984, 9450},
{7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 3387, 8661, 8957, 5709, 984, 0, 5211},
{6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 3706, 1177, 8156, 2858, 9450, 5211, 0}
};
TSPLS tsp = new TSPLS(distanceMatrix);
int[] bestRoute = tsp.solve();
double bestDistance = tsp.calculateTotalDistance(bestRoute);
System.out.println("> Ruta óptima encontrada: " + Arrays.toString(bestRoute));
System.out.println("> Distancia mínima: " + bestDistance);
}
}
Código Java (TSPLS.java):
package tsp_busquedalocal;
import java.util.Random;
class TSPLS {
private final double[][] distanceMatrix;
private final int n;
private final Random random = new Random();
public TSPLS(double[][] distanceMatrix) {
this.distanceMatrix = distanceMatrix;
this.n = distanceMatrix.length;
}
public int[] solve() {
int[] bestRoute = null;
double bestDistance = Double.MAX_VALUE;
for (int i = 0; i < 100000; i++) {
int[] currentRoute = generateInitialRoute();
currentRoute = localSearch(currentRoute);
double currentDistance = calculateTotalDistance(currentRoute);
if (currentDistance < bestDistance) {
bestDistance = currentDistance;
bestRoute = currentRoute.clone();
}
}
return bestRoute;
}
private int[] generateInitialRoute() {
int[] route = new int[n];
for (int i = 0; i < n; i++) {
route[i] = i;
}
for (int i = n - 1; i > 0; i--) {
int j = random.nextInt(i + 1);
int temp = route[i];
route[i] = route[j];
route[j] = temp;
}
return route;
}
private int[] localSearch(int[] route) {
boolean improved;
int iterations = 0;
do {
improved = false;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (trySwap(route, i, j)) {
improved = true;
}
}
}
iterations++;
} while (improved && iterations < 100); // Limitado a 100 iteraciones
return route;
}
private boolean trySwap(int[] route, int i, int j) {
double change = calculateSwapChange(route, i, j);
if (change < 0) {
int temp = route[i];
route[i] = route[j];
route[j] = temp;
return true;
}
return false;
}
private double calculateSwapChange(int[] route, int i, int j) {
double change = 0;
int prev_i = (i > 0) ? route[i - 1] : route[n - 1];
int next_j = (j < n - 1) ? route[j + 1] : route[0];
change -= distanceMatrix[prev_i][route[i]];
change -= distanceMatrix[route[j]][next_j];
change += distanceMatrix[prev_i][route[j]];
change += distanceMatrix[route[i]][next_j];
if (j == i + 1) {
change -= distanceMatrix[route[i]][route[j]];
change += distanceMatrix[route[j]][route[i]];
} else {
int next_i = route[i + 1];
int prev_j = route[j - 1];
change -= distanceMatrix[route[i]][next_i];
change -= distanceMatrix[prev_j][route[j]];
change += distanceMatrix[route[j]][next_i];
change += distanceMatrix[prev_j][route[i]];
}
return change;
}
double calculateTotalDistance(int[] route) {
double totalDistance = 0;
for (int i = 0; i < n - 1; i++) {
totalDistance += distanceMatrix[route[i]][route[i + 1]];
}
totalDistance += distanceMatrix[route[n - 1]][route[0]];
return totalDistance;
}
}
Resultado:
run:
> Ruta óptima encontrada: [4, 3, 11, 2, 5, 12, 1, 6, 14, 9, 10, 15, 7, 8, 13, 0]
> Distancia mínima: 21420.0
BUILD SUCCESSFUL (total time: 2 seconds)
Problema del viajante de Comercio TSP (X). Método Tabu Search (TS).
El algoritmo Tabú es un enfoque de optimización heurística utilizado para resolver problemas combinatorios complejos, como el TSP. Este algoritmo se basa en la búsqueda local, pero incorpora un mecanismo de memoria para evitar ciclos y mejorar la exploración de soluciones.
Características:
Búsqueda Local: El algoritmo comienza con una solución inicial y mejora iterativamente a partir de esta mediante movimientos locales. Un movimiento local implica realizar pequeños cambios en la solución actual (por ejemplo, intercambiar dos ciudades en el TSP).
Lista Tabú: Para evitar que el algoritmo se quede atrapado en óptimos locales, utiliza una lista tabú que almacena soluciones recientemente exploradas. Cualquier movimiento que produzca una solución que esté en esta lista es prohibido temporalmente, lo que obliga al algoritmo a explorar nuevas áreas del espacio de soluciones.
Criterios de Evaluación: Durante cada iteración, el algoritmo evalúa los vecinos de la solución actual (todas las soluciones generadas mediante movimientos locales) y selecciona el mejor vecino que no esté en la lista tabú. Esto garantiza que el algoritmo explore soluciones prometedoras sin regresar a las soluciones prohibidas.
Actualización de la Lista Tabú: La lista tabú tiene un tamaño fijo y, a medida que se agregan nuevas soluciones, las más antiguas se eliminan. Esto permite que el algoritmo mantenga una memoria de las soluciones prohibidas sin consumir demasiada memoria.
Iteraciones y Criterios de Parada: El algoritmo se ejecuta durante un número predefinido de iteraciones o hasta que se alcanza un criterio de convergencia, como la estabilización de la mejor solución encontrada.
*Ventajas:
Eficiencia: A menudo encuentra soluciones de alta calidad en un tiempo razonable, incluso para problemas grandes.
Evita Mínimos Locales: La lista tabú permite escapar de óptimos locales, aumentando las posibilidades de encontrar la solución global óptima.
*Desventajas:
Parámetros Dependientes: La efectividad del algoritmo puede depender en gran medida de la elección de parámetros como el tamaño de la lista tabú y el número de iteraciones.
Complejidad: La implementación puede ser más compleja que otros métodos de búsqueda local debido al manejo de la lista tabú.
Código Java (TSP_TabuSearch.java):
package tsp_tabusearch;
public class TSP_TabuSearch {
public static void main(String[] args) {
double[][] distanceMatrix = {
{0, 8128, 823, 8767, 1253, 8827, 5106, 5501, 7097, 8026, 7162, 2260, 4441, 510, 7138, 6509},
{8128, 0, 6653, 9241, 4344, 7231, 1503, 7145, 6571, 6217, 9412, 9051, 1931, 5817, 8633, 8513},
{823, 6653, 0, 7900, 1178, 1820, 1262, 678, 9930, 6739, 9965, 908, 9481, 7708, 1874, 9303},
{8767, 9241, 7900, 0, 589, 9827, 520, 6671, 9859, 4489, 1642, 1045, 1760, 5607, 5053, 7776},
{1253, 4344, 1178, 589, 0, 5829, 5823, 3482, 9090, 9537, 8507, 3802, 3302, 2944, 8613, 7257},
{8827, 7231, 1820, 9827, 5829, 0, 9288, 6497, 5442, 4381, 9297, 2086, 1372, 5616, 1981, 3412},
{5106, 1503, 1262, 520, 5823, 9288, 0, 3242, 5625, 4715, 7754, 2366, 8314, 1360, 623, 3915},
{5501, 7145, 678, 6671, 3482, 6497, 3242, 0, 1522, 6648, 324, 8704, 7602, 8091, 1608, 1286},
{7097, 6571, 9930, 9859, 9090, 5442, 5625, 1522, 0, 7740, 7480, 2266, 9346, 967, 9585, 9113},
{8026, 6217, 6739, 4489, 9537, 4381, 4715, 6648, 7740, 0, 1527, 4847, 4770, 5032, 3387, 3706},
{7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 1527, 0, 2399, 9453, 7380, 8661, 1177},
{2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 4847, 2399, 0, 3224, 4943, 8957, 8156},
{4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 4770, 9453, 3224, 0, 4289, 5709, 2858},
{510, 5817, 7708, 5607, 2944, 5616, 1360, 8091, 967, 5032, 7380, 4943, 4289, 0, 984, 9450},
{7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 3387, 8661, 8957, 5709, 984, 0, 5211},
{6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 3706, 1177, 8156, 2858, 9450, 5211, 0}
};
int maxIterations = 1000; // Ajusta según sea necesario
int tabuListSize = 100; // Ajusta según sea necesario
TSPTS tsp = new TSPTS(distanceMatrix, maxIterations, tabuListSize);
tsp.solve();
System.out.println("> Mejor ruta encontrada: " + tsp.getBestRoute());
System.out.println("> Distancia mínima: " + tsp.getBestDistance());
}
}
Código Java (TSP_TabuSearch.java):
package tsp_tabusearch;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Random;
class TSPTS {
private final double[][] distanceMatrix;
private final int maxIterations;
private final int tabuListSize;
private ArrayList<Integer> bestRoute;
private double bestDistance;
public TSPTS(double[][] distanceMatrix, int maxIterations, int tabuListSize) {
this.distanceMatrix = distanceMatrix;
this.maxIterations = maxIterations;
this.tabuListSize = tabuListSize;
this.bestRoute = new ArrayList<>();
this.bestDistance = Double.MAX_VALUE;
}
public void solve() {
int numCities = distanceMatrix.length;
ArrayList<Integer> currentRoute = initializeRoute(numCities);
double currentDistance = calculateTotalDistance(currentRoute);
HashSet<String> tabuList = new HashSet<>();
for (int iteration = 0; iteration < maxIterations; iteration++) {
ArrayList<Integer> bestNeighbor = null;
double bestNeighborDistance = Double.MAX_VALUE;
// Generar y evaluar vecinos
for (int i = 0; i < numCities - 1; i++) {
for (int j = i + 1; j < numCities; j++) {
ArrayList<Integer> neighbor = new ArrayList<>(currentRoute);
Collections.swap(neighbor, i, j); // Realiza un movimiento
String neighborKey = neighbor.toString(); // Clave para la lista tabú
// Evaluar si el vecino no está en la lista tabú
if (!tabuList.contains(neighborKey)) {
double neighborDistance = calculateTotalDistance(neighbor);
if (neighborDistance < bestNeighborDistance) {
bestNeighborDistance = neighborDistance;
bestNeighbor = neighbor;
}
}
}
}
// Actualizar la ruta actual
if (bestNeighbor != null) {
currentRoute = bestNeighbor;
currentDistance = bestNeighborDistance;
// Actualizar mejor ruta global
if (currentDistance < bestDistance) {
bestDistance = currentDistance;
bestRoute = new ArrayList<>(currentRoute);
}
// Agregar a la lista tabú
tabuList.add(currentRoute.toString());
if (tabuList.size() > tabuListSize) {
// Eliminar el elemento más antiguo si se supera el tamaño
tabuList.remove(tabuList.iterator().next());
}
}
}
}
private ArrayList<Integer> initializeRoute(int numCities) {
ArrayList<Integer> route = new ArrayList<>();
for (int i = 0; i < numCities; i++) {
route.add(i);
}
Collections.shuffle(route); // Ruta inicial aleatoria
return route;
}
private double calculateTotalDistance(ArrayList<Integer> route) {
double totalDistance = 0.0;
for (int i = 0; i < route.size() - 1; i++) {
totalDistance += distanceMatrix[route.get(i)][route.get(i + 1)];
}
totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Regresar a la ciudad de inicio
return totalDistance;
}
public ArrayList<Integer> getBestRoute() {
return bestRoute;
}
public double getBestDistance() {
return bestDistance;
}
}
Resultado:
run:
> Mejor ruta encontrada: [6, 1, 12, 5, 14, 9, 10, 15, 7, 8, 13, 0, 4, 2, 11, 3]
> Distancia mínima: 22067.0
BUILD SUCCESSFUL (total time: 0 seconds)
Problema del viajante de Comercio TSP (IX). Método Genético (GA).
Un Algoritmo Genético (GA) es una técnica de optimización inspirada en el proceso de selección natural de la biología. Los GAs se utilizan para resolver problemas complejos de búsqueda y optimización cuando los métodos tradicionales son ineficaces o difíciles de aplicar.
Características del Algoritmo(GA) adaptado al TSP:
Población Inicial: Se genera una población inicial de rutas aleatorias. Cada ruta es una permutación de las ciudades.
Selección por Torneo: En cada generación, se seleccionan pares de rutas (padres) mediante un proceso de torneo. El tamaño del torneo puede ajustarse para equilibrar la exploración y explotación del espacio de soluciones.
Crossover: Se realiza un crossover (cruce) para generar nuevas rutas (hijos) a partir de los padres seleccionados. Se utiliza un cruce de segmento (Partial Map Crossover), donde un segmento de la ruta del primer padre es copiado al hijo y se rellenan los huecos con la ruta del segundo padre.
Mutación: Se introduce variación en la población mediante mutación. Aquí, se implementa una mutación de inversión, donde se invierte una subsección de la ruta con una probabilidad controlada por el mutationRate.
Elitismo: Se mantiene la mejor ruta encontrada en cada generación, asegurando que no se pierda la mejor solución.
Código Java (TSP_Genetico.java):
package tsp_genetico;
import java.util.ArrayList;
public class TSP_Genetico {
public static void main(String[] args) {
double[][] distanceMatrix = {
{0, 8128, 823, 8767, 1253, 8827, 5106, 5501, 7097, 8026, 7162, 2260, 4441, 510, 7138, 6509},
{8128, 0, 6653, 9241, 4344, 7231, 1503, 7145, 6571, 6217, 9412, 9051, 1931, 5817, 8633, 8513},
{823, 6653, 0, 7900, 1178, 1820, 1262, 678, 9930, 6739, 9965, 908, 9481, 7708, 1874, 9303},
{8767, 9241, 7900, 0, 589, 9827, 520, 6671, 9859, 4489, 1642, 1045, 1760, 5607, 5053, 7776},
{1253, 4344, 1178, 589, 0, 5829, 5823, 3482, 9090, 9537, 8507, 3802, 3302, 2944, 8613, 7257},
{8827, 7231, 1820, 9827, 5829, 0, 9288, 6497, 5442, 4381, 9297, 2086, 1372, 5616, 1981, 3412},
{5106, 1503, 1262, 520, 5823, 9288, 0, 3242, 5625, 4715, 7754, 2366, 8314, 1360, 623, 3915},
{5501, 7145, 678, 6671, 3482, 6497, 3242, 0, 1522, 6648, 324, 8704, 7602, 8091, 1608, 1286},
{7097, 6571, 9930, 9859, 9090, 5442, 5625, 1522, 0, 7740, 7480, 2266, 9346, 967, 9585, 9113},
{8026, 6217, 6739, 4489, 9537, 4381, 4715, 6648, 7740, 0, 1527, 4847, 4770, 5032, 3387, 3706},
{7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 1527, 0, 2399, 9453, 7380, 8661, 1177},
{2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 4847, 2399, 0, 3224, 4943, 8957, 8156},
{4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 4770, 9453, 3224, 0, 4289, 5709, 2858},
{510, 5817, 7708, 5607, 2944, 5616, 1360, 8091, 967, 5032, 7380, 4943, 4289, 0, 984, 9450},
{7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 3387, 8661, 8957, 5709, 984, 0, 5211},
{6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 3706, 1177, 8156, 2858, 9450, 5211, 0}
};
int populationSize = 500;
double mutationRate = 0.05;
int numberOfGenerations = 5000;
TSPGA tspGA = new TSPGA(distanceMatrix, populationSize, mutationRate, numberOfGenerations);
ArrayList<Integer> bestRoute = tspGA.solve();
System.out.println("> Ruta óptima encontrada: " + bestRoute);
System.out.println("> Distancia mínima: " + tspGA.getBestDistance());
}
}
Código Java (TSPGA.java):
package tsp_genetico;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
class TSPGA {
private final double[][] distanceMatrix;
private final int populationSize;
private final double mutationRate;
private final int numberOfGenerations;
private ArrayList<Integer> bestRoute;
private double bestDistance;
public TSPGA(double[][] distanceMatrix, int populationSize, double mutationRate, int numberOfGenerations) {
this.distanceMatrix = distanceMatrix;
this.populationSize = populationSize;
this.mutationRate = mutationRate;
this.numberOfGenerations = numberOfGenerations;
}
public ArrayList<Integer> solve() {
int numCities = distanceMatrix.length;
ArrayList<ArrayList<Integer>> population = initializePopulation(numCities);
ArrayList<Integer> bestSoFar = getBestRoute(population);
for (int generation = 0; generation < numberOfGenerations; generation++) {
ArrayList<ArrayList<Integer>> newPopulation = new ArrayList<>();
// Mantener la mejor solución (élite)
newPopulation.add(bestSoFar);
// Tamaño del torneo, lo puedes ajustar como prefieras
int tournamentSize = 5;
for (int i = 1; i < populationSize; i++) {
ArrayList<Integer> parent1 = selectParent(population, tournamentSize);
ArrayList<Integer> parent2 = selectParent(population, tournamentSize);
ArrayList<Integer> offspring = crossover(parent1, parent2);
mutate(offspring);
newPopulation.add(offspring);
}
population = newPopulation;
bestSoFar = getBestRoute(population);
}
bestRoute = bestSoFar;
bestDistance = calculateTotalDistance(bestRoute);
return bestRoute;
}
private ArrayList<ArrayList<Integer>> initializePopulation(int numCities) {
ArrayList<ArrayList<Integer>> population = new ArrayList<>();
for (int i = 0; i < populationSize; i++) {
ArrayList<Integer> route = new ArrayList<>();
for (int j = 0; j < numCities; j++) {
route.add(j);
}
Collections.shuffle(route);
population.add(route);
}
return population;
}
private ArrayList<Integer> selectParent(ArrayList<ArrayList<Integer>> population, int tournamentSize) {
Random rand = new Random();
ArrayList<ArrayList<Integer>> tournament = new ArrayList<>();
// Selecciona individuos al azar para el torneo
for (int i = 0; i < tournamentSize; i++) {
int randomIndex = rand.nextInt(population.size());
tournament.add(population.get(randomIndex));
}
// Devuelve el mejor individuo del torneo
return getBestRoute(tournament);
}
private ArrayList<Integer> crossover(ArrayList<Integer> parent1, ArrayList<Integer> parent2) {
Random rand = new Random();
int size = parent1.size();
ArrayList<Integer> child = new ArrayList<>(Collections.nCopies(size, -1));
int start = rand.nextInt(size);
int end = start + rand.nextInt(size - start);
for (int i = start; i <= end; i++) {
child.set(i, parent1.get(i));
}
int currentIndex = (end + 1) % size;
for (int i = 0; i < size; i++) {
int parent2Value = parent2.get((end + 1 + i) % size);
if (!child.contains(parent2Value)) {
child.set(currentIndex, parent2Value);
currentIndex = (currentIndex + 1) % size;
}
}
return child;
}
private void mutate(ArrayList<Integer> route) {
Random rand = new Random();
if (rand.nextDouble() < mutationRate) {
int start = rand.nextInt(route.size());
int end = start + rand.nextInt(route.size() - start);
Collections.reverse(route.subList(start, end));
}
}
private ArrayList<Integer> getBestRoute(ArrayList<ArrayList<Integer>> population) {
ArrayList<Integer> best = population.get(0);
double bestDist = calculateTotalDistance(best);
for (ArrayList<Integer> route : population) {
double currentDist = calculateTotalDistance(route);
if (currentDist < bestDist) {
best = route;
bestDist = currentDist;
}
}
return best;
}
private double calculateTotalDistance(ArrayList<Integer> route) {
double totalDistance = 0.0;
for (int i = 0; i < route.size() - 1; i++) {
int city1 = route.get(i);
int city2 = route.get(i + 1);
totalDistance += distanceMatrix[city1][city2];
}
totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Return to start city
return totalDistance;
}
public double getBestDistance() {
return bestDistance;
}
}
Resultado:
run:
> Ruta óptima encontrada: [3, 10, 9, 15, 7, 8, 13, 14, 6, 1, 12, 5, 11, 2, 0, 4]
> Distancia mínima: 22722.0
BUILD SUCCESSFUL (total time: 3 seconds)
miércoles, 14 de agosto de 2024
Problema del viajante de Comercio TSP (VIII). Método Ramificación y Poda (Branch and Bound).
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)
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)