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)
