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)