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)
