Problema del viajante de Comercio TSP (XV). Método Dinámica de Enjambre de Partículas (PSO).

El Algoritmo de Dinámica de Enjambre de Partículas (PSO) aplicado al Problema del Viajante de Comercio (TSP) busca encontrar la ruta más corta posible que visita una serie de ciudades y regresa al punto de partida. Cada partícula en PSO representa una posible ruta a través de todas las ciudades. Estas partículas se mueven dentro del espacio de soluciones ajustando sus rutas basadas en la mejor solución personal que han encontrado y la mejor solución global conocida.

Características:

    . Representación de las Soluciones: Cada partícula es una permutación de las ciudades, representando una posible ruta en el TSP.

    . Movimiento de las Partículas: Las partículas ajustan su ruta actual usando:
        . Inercia (w): Mantienen parte de su ruta anterior.
        . Cognitivo (c1): Se acercan a la mejor ruta que han encontrado.
        . Social (c2): Se acercan a la mejor ruta conocida por todo el enjambre.

    . Exploración y Explotación:
        Inercia (w): Un valor moderado, como 0.7, ayuda a balancear entre explorar nuevas rutas y explotar rutas conocidas.
        Cognitivo y Social (c1 y c2): Valores iguales, como 1.5, equilibran la influencia de la experiencia personal y la influencia del grupo.

    . Actualización de las Rutas: Durante las iteraciones, las partículas intercambian segmentos de rutas para acercarse a las mejores soluciones, evitando quedarse atrapadas en soluciones subóptimas.

    . Criterio de Parada: El algoritmo ejecuta un número fijo de iteraciones (por ejemplo, 10000) para asegurar que se explore adecuadamente el espacio de soluciones.

Ventajas:

    . Flexibilidad: PSO puede adaptarse fácilmente a problemas con diferentes tamaños de ciudades.
    . Capacidad de Escapar de Mínimos Locales: La influencia combinada de la inercia, la mejor solución personal y la global permite que las partículas exploren diferentes áreas del espacio de soluciones.
    . Convergencia: PSO tiende a converger hacia una buena solución rápidamente, aunque no garantiza encontrar la solución óptima.



Código Java (TSP_DinamicaEnjambreParticulas.java):

package tsp_dinamicaenjambreparticulas;

import java.util.ArrayList;

public class TSP_DinamicaEnjambreParticulas {

    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}
        };

        int numParticles = 100;  // Número partículas
        double w = 0.5;          // Inercia reducida
        double c1 = 2.0;         // Coeficiente cognitivo (mayor peso en la mejor solución personal)
        double c2 = 2.0;         // Coeficiente social (mayor peso en la mejor solución global)

        TSPPSO tsp = new TSPPSO(distanceMatrix, numParticles, w, c1, c2);
        ArrayList<Integer> bestRoute = tsp.solve(10000); // 10000 iteraciones
        double bestDistance = tsp.calculateTotalDistance(bestRoute);

        System.out.println("Ruta óptima aproximada encontrada: " + bestRoute);
        System.out.println("Distancia mínima aproximada: " + bestDistance);
    }

}


Código Java (TSPPSO.java):

package tsp_dinamicaenjambreparticulas;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class TSPPSO {

    private final double[][] distanceMatrix;
    private final int numCities;
    private int numParticles = 50;  // Número partículas
    private double w = 0.7;         // Inercia
    private double c1 = 1.5;        // Coeficiente cognitivo
    private double c2 = 1.5;        // Coeficiente social
    private final Random random = new Random();

    public TSPPSO(double[][] distanceMatrix, int numParticles, double w, double c1, double c2) {
        this.distanceMatrix = distanceMatrix;
        this.numCities = distanceMatrix.length;
        this.numParticles = numParticles;
        this.w = w;
        this.c1 = c1;
        this.c2 = c2;
    }

    public TSPPSO(double[][] distanceMatrix) {
        this.distanceMatrix = distanceMatrix;
        this.numCities = distanceMatrix.length;
    }

    public ArrayList<Integer> solve(int maxIterations) {
        ArrayList<ArrayList<Integer>> particles = new ArrayList<>();
        ArrayList<ArrayList<Integer>> personalBestPositions = new ArrayList<>();
        ArrayList<Double> personalBestDistances = new ArrayList<>();
        ArrayList<Integer> globalBestPosition = null;
        double globalBestDistance = Double.MAX_VALUE;

        // Inicializar las partículas
        for (int i = 0; i < numParticles; i++) {
            ArrayList<Integer> route = generateRandomRoute();
            particles.add(route);
            personalBestPositions.add(new ArrayList<>(route));
            double routeDistance = calculateTotalDistance(route);
            personalBestDistances.add(routeDistance);

            // Actualizar mejor global
            if (routeDistance < globalBestDistance) {
                globalBestPosition = route;
                globalBestDistance = routeDistance;
            }
        }

        // Iterar hasta alcanzar el criterio de parada
        for (int iter = 0; iter < maxIterations; iter++) {
            for (int i = 0; i < numParticles; i++) {
                ArrayList<Integer> currentPosition = particles.get(i);
                ArrayList<Integer> newPosition = updatePosition(currentPosition, personalBestPositions.get(i), globalBestPosition);

                double newDistance = calculateTotalDistance(newPosition);
                double personalBestDistance = personalBestDistances.get(i);

                // Actualizar la mejor posición personal
                if (newDistance < personalBestDistance) {
                    personalBestPositions.set(i, newPosition);
                    personalBestDistances.set(i, newDistance);
                }

                // Actualizar la mejor posición global
                if (newDistance < globalBestDistance) {
                    globalBestPosition = newPosition;
                    globalBestDistance = newDistance;
                }

                particles.set(i, newPosition);
            }
        }

        return globalBestPosition;
    }

    private ArrayList<Integer> generateRandomRoute() {
        ArrayList<Integer> route = new ArrayList<>();
        for (int i = 0; i < numCities; i++) {
            route.add(i);
        }
        Collections.shuffle(route);
        return route;
    }

    private ArrayList<Integer> updatePosition(ArrayList<Integer> currentPosition, ArrayList<Integer> personalBest, ArrayList<Integer> globalBest) {
        ArrayList<Integer> newPosition = new ArrayList<>(currentPosition);

        // Aplicar intercambios para simular "velocidades"
        for (int i = 0; i < numCities; i++) {
            if (random.nextDouble() < w) {
                int swapIndex1 = random.nextInt(numCities);
                int swapIndex2 = random.nextInt(numCities);
                Collections.swap(newPosition, swapIndex1, swapIndex2);
            }

            if (random.nextDouble() < c1) {
                int swapIndex = personalBest.indexOf(newPosition.get(i));
                Collections.swap(newPosition, i, swapIndex);
            }

            if (random.nextDouble() < c2) {
                int swapIndex = globalBest.indexOf(newPosition.get(i));
                Collections.swap(newPosition, i, swapIndex);
            }
        }

        return newPosition;
    }

    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)]; // Retorno al inicio
        return totalDistance;
    }
}


Resultado:

run:
Ruta óptima aproximada encontrada: [15, 9, 5, 2, 7, 10, 3, 4, 0, 13, 8, 11, 12, 1, 6, 14]
Distancia mínima aproximada: 25093.0
BUILD SUCCESSFUL (total time: 1 second)