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

jueves, 15 de agosto de 2024

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)

Con la tecnología de Blogger.