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)
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
-
►
2012
(38)
- ► septiembre (3)
-
►
2020
(12)
- ► septiembre (1)
-
▼
2024
(29)
-
▼
agosto
(17)
- Problema del Viajante de Comercio TSP (V.1). Métod...
- Problema del Viajante de Comercio TSP (V.2). Métod...
- Problema del Viajante de Comercio TSP (V.3). Métod...
- Problema del viajante de Comercio TSP (IV.2). Méto...
- Problema del Viajante de Comercio TSP (V.3.1). Aná...
- Matriz de conectividad circular.
- Problema del viajante de Comercio TSP (VI). Método...
- Problema del viajante de Comercio TSP (VII). Métod...
- Problema del viajante de Comercio TSP (VIII). Méto...
- Problema del viajante de Comercio TSP (IX). Método...
- Problema del viajante de Comercio TSP (X). Método ...
- Problema del viajante de Comercio TSP (XI). Método...
- Problema del viajante de Comercio TSP (XII). Métod...
- Problema del viajante de Comercio TSP (XIII). Méto...
- Problema del viajante de Comercio TSP (XIV). Métod...
- Problema del viajante de Comercio TSP (XV). Método...
- Juegos VII. La Mansión Misteriosa: Un juego de tex...
-
▼
agosto
(17)
viernes, 16 de agosto de 2024
Problema del viajante de Comercio TSP (XV). Método Dinámica de Enjambre de Partículas (PSO).
Suscribirse a:
Entradas (Atom)
Con la tecnología de Blogger.