Problema del viajante de Comercio TSP (XI). Método Búsqueda Local (LS).

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)

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)

Problema del viajante de Comercio TSP (IX). Método Genético (GA).

Un Algoritmo Genético (GA) es una técnica de optimización inspirada en el proceso de selección natural de la biología. Los GAs se utilizan para resolver problemas complejos de búsqueda y optimización cuando los métodos tradicionales son ineficaces o difíciles de aplicar.

Características del Algoritmo(GA) adaptado al TSP:

    Población Inicial: Se genera una población inicial de rutas aleatorias. Cada ruta es una permutación de las ciudades.
    Selección por Torneo: En cada generación, se seleccionan pares de rutas (padres) mediante un proceso de torneo. El tamaño del torneo puede ajustarse para equilibrar la exploración y explotación del espacio de soluciones.
    Crossover: Se realiza un crossover (cruce) para generar nuevas rutas (hijos) a partir de los padres seleccionados. Se utiliza un cruce de segmento (Partial Map Crossover), donde un segmento de la ruta del primer padre es copiado al hijo y se rellenan los huecos con la ruta del segundo padre.
    Mutación: Se introduce variación en la población mediante mutación. Aquí, se implementa una mutación de inversión, donde se invierte una subsección de la ruta con una probabilidad controlada por el mutationRate.
    Elitismo: Se mantiene la mejor ruta encontrada en cada generación, asegurando que no se pierda la mejor solución.


Código Java (TSP_Genetico.java):

package tsp_genetico;

import java.util.ArrayList;

public class TSP_Genetico {

    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 populationSize = 500;
        double mutationRate = 0.05;
        int numberOfGenerations = 5000;

        TSPGA tspGA = new TSPGA(distanceMatrix, populationSize, mutationRate, numberOfGenerations);
        ArrayList<Integer> bestRoute = tspGA.solve();

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


Código Java (TSPGA.java):

package tsp_genetico;

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

class TSPGA {

    private final double[][] distanceMatrix;
    private final int populationSize;
    private final double mutationRate;
    private final int numberOfGenerations;
    private ArrayList<Integer> bestRoute;
    private double bestDistance;

    public TSPGA(double[][] distanceMatrix, int populationSize, double mutationRate, int numberOfGenerations) {
        this.distanceMatrix = distanceMatrix;
        this.populationSize = populationSize;
        this.mutationRate = mutationRate;
        this.numberOfGenerations = numberOfGenerations;
    }

    public ArrayList<Integer> solve() {
        int numCities = distanceMatrix.length;
        ArrayList<ArrayList<Integer>> population = initializePopulation(numCities);
        ArrayList<Integer> bestSoFar = getBestRoute(population);

        for (int generation = 0; generation < numberOfGenerations; generation++) {
            ArrayList<ArrayList<Integer>> newPopulation = new ArrayList<>();

            // Mantener la mejor solución (élite)
            newPopulation.add(bestSoFar);

            // Tamaño del torneo, lo puedes ajustar como prefieras
            int tournamentSize = 5;

            for (int i = 1; i < populationSize; i++) {
                ArrayList<Integer> parent1 = selectParent(population, tournamentSize);
                ArrayList<Integer> parent2 = selectParent(population, tournamentSize);
                ArrayList<Integer> offspring = crossover(parent1, parent2);
                mutate(offspring);
                newPopulation.add(offspring);
            }

            population = newPopulation;
            bestSoFar = getBestRoute(population);
        }

        bestRoute = bestSoFar;
        bestDistance = calculateTotalDistance(bestRoute);

        return bestRoute;
    }

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

    private ArrayList<Integer> selectParent(ArrayList<ArrayList<Integer>> population, int tournamentSize) {
        Random rand = new Random();
        ArrayList<ArrayList<Integer>> tournament = new ArrayList<>();

        // Selecciona individuos al azar para el torneo
        for (int i = 0; i < tournamentSize; i++) {
            int randomIndex = rand.nextInt(population.size());
            tournament.add(population.get(randomIndex));
        }

        // Devuelve el mejor individuo del torneo
        return getBestRoute(tournament);
    }

    private ArrayList<Integer> crossover(ArrayList<Integer> parent1, ArrayList<Integer> parent2) {
        Random rand = new Random();
        int size = parent1.size();
        ArrayList<Integer> child = new ArrayList<>(Collections.nCopies(size, -1));

        int start = rand.nextInt(size);
        int end = start + rand.nextInt(size - start);

        for (int i = start; i <= end; i++) {
            child.set(i, parent1.get(i));
        }

        int currentIndex = (end + 1) % size;
        for (int i = 0; i < size; i++) {
            int parent2Value = parent2.get((end + 1 + i) % size);
            if (!child.contains(parent2Value)) {
                child.set(currentIndex, parent2Value);
                currentIndex = (currentIndex + 1) % size;
            }
        }

        return child;
    }

    private void mutate(ArrayList<Integer> route) {
        Random rand = new Random();
        if (rand.nextDouble() < mutationRate) {
            int start = rand.nextInt(route.size());
            int end = start + rand.nextInt(route.size() - start);
            Collections.reverse(route.subList(start, end));
        }

    }

    private ArrayList<Integer> getBestRoute(ArrayList<ArrayList<Integer>> population) {
        ArrayList<Integer> best = population.get(0);
        double bestDist = calculateTotalDistance(best);

        for (ArrayList<Integer> route : population) {
            double currentDist = calculateTotalDistance(route);
            if (currentDist < bestDist) {
                best = route;
                bestDist = currentDist;
            }
        }

        return best;
    }

    private double calculateTotalDistance(ArrayList<Integer> route) {
        double totalDistance = 0.0;

        for (int i = 0; i < route.size() - 1; i++) {
            int city1 = route.get(i);
            int city2 = route.get(i + 1);
            totalDistance += distanceMatrix[city1][city2];
        }

        totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Return to start city

        return totalDistance;
    }

    public double getBestDistance() {
        return bestDistance;
    }
}


Resultado:

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