Problema del viajante de Comercio TSP (VI). Método Colonia de Hormigas (ACO).

El algoritmo de Colonia de Hormigas (Ant Colony Optimization, siglas en inglés: ACO) es un método metaheurístico inspirado en el comportamiento de las hormigas reales para resolver problemas de optimización combinatoria, como el Problema del Viajante de Comercio (TSP).

Descripción del Algoritmo de Colonia de Hormigas:

Las hormigas reales son capaces de encontrar el camino más corto entre su colonia y una fuente de alimento mediante la deposición de feromonas en el suelo. Estas feromonas sirven como una señal química que guía a otras hormigas. Cuanto más corto sea el camino, más rápido regresan las hormigas, incrementando la cantidad de feromonas en ese trayecto y, por lo tanto, haciendo que sea más atractivo para otras hormigas. El algoritmo ACO* o TSPCH simula este comportamiento.

Parámetros necesarios:

    distances: Matriz de distancias entre las ciudades.
    numAnts: Número de hormigas que participan en cada iteración.
    numIterations: Número de iteraciones para ejecutar el algoritmo.
    alpha, beta: Parámetros que controlan la influencia de la feromona y la visibilidad, respectivamente.
    evaporation: Tasa de evaporación de las feromonas.
    Q: Constante para la cantidad de feromona depositada.


Código Java (TSP_ColoniaHormigas):

package tsp_coloniahormigas;

import java.util.Arrays;

public class TSP_ColoniaHormigas {

    public static void main(String[] args) {

        // Matriz de distancias (16x16)
        double[][] distances = {
            {0, 6780, 6332, 5183, 3541, 6777, 9735, 7, 7297, 9569, 9649, 6776, 2841, 6953, 538, 4117},
            {6780, 0, 9200, 7166, 6987, 7864, 8168, 6569, 5755, 5199, 508, 2574, 8282, 5348, 106, 511},
            {6332, 9200, 0, 9806, 3578, 8764, 6077, 9847, 4451, 9042, 3870, 2817, 2318, 7693, 4202, 7622},
            {5183, 7166, 9806, 0, 3518, 4282, 255, 9261, 1766, 9321, 5317, 5747, 6177, 4520, 3900, 7828},
            {3541, 6987, 3578, 3518, 0, 9134, 4385, 8033, 3046, 7208, 3214, 2128, 19, 7763, 1796, 9843},
            {6777, 7864, 8764, 4282, 9134, 0, 4017, 7218, 2483, 5176, 3423, 9862, 6872, 5376, 7486, 4337},
            {9735, 8168, 6077, 255, 4385, 4017, 0, 4140, 2692, 409, 6729, 4045, 4354, 8323, 888, 3671},
            {7, 6569, 9847, 9261, 8033, 7218, 4140, 0, 1894, 9932, 4223, 2703, 932, 2015, 5867, 5244},
            {7297, 5755, 4451, 1766, 3046, 2483, 2692, 1894, 0, 2481, 171, 4352, 9602, 4497, 9916, 8946},
            {9569, 5199, 9042, 9321, 7208, 5176, 409, 9932, 2481, 0, 8364, 6474, 8869, 7058, 2869, 2216},
            {9649, 508, 3870, 5317, 3214, 3423, 6729, 4223, 171, 8364, 0, 109, 7461, 436, 4842, 3091},
            {6776, 2574, 2817, 5747, 2128, 9862, 4045, 2703, 4352, 6474, 109, 0, 2945, 8514, 7882, 2895},
            {2841, 8282, 2318, 6177, 19, 6872, 4354, 932, 9602, 8869, 7461, 2945, 0, 7904, 232, 6090},
            {6953, 5348, 7693, 4520, 7763, 5376, 8323, 2015, 4497, 7058, 436, 8514, 7904, 0, 4406, 103},
            {538, 106, 4202, 3900, 1796, 7486, 888, 5867, 9916, 2869, 4842, 7882, 232, 4406, 0, 3609},
            {4117, 511, 7622, 7828, 9843, 4337, 3671, 5244, 8946, 2216, 3091, 2895, 6090, 103, 3609, 0}
        };

        int numAnts = 10;           // Número de hormigas que participan en cada iteración.
        int numIterations = 1000;   // Número de iteraciones para ejecutar el algoritmo.
        float alpha = 1.0f;         // Parámetro que controlanla influencia de la feromona.
        float beta = 5.0f;          // Parámetro que controlanla influencia de la visibilidad.
        float evaporation = 0.5f;   // Tasa de evaporación de las feromonas.
        float Q = 100.0f;           // Constante para la cantidad de feromona depositada.

        TSPCH tsp = new TSPCH(
                distances,
                numAnts,
                numIterations,
                alpha,
                beta,
                evaporation,
                Q);

        System.out.println("> Mejor ruta encontrada:\n" + Arrays.toString(tsp.getBestRoute()));
        System.out.println("> La distancia total recorrida es: " + tsp.getBestDistance());

    }

}


Código Java (TSPCH.java):

package tsp_coloniahormigas;

import java.util.Arrays;
import java.util.Random;

public class TSPCH {

    private final int numCities;
    private final int numAnts;
    private final double[][] distances;
    private final double[][] pheromone;
    private final double alpha;
    private final double beta;
    private final double evaporation;
    private final double Q;
    private int[] bestRoute;
    private int bestDistance;
    private final Random random;

    public TSPCH(double[][] distances, int numAnts, int numIterations, double alpha, double beta, double evaporation, double Q) {
        this.numCities = distances.length;
        this.numAnts = numAnts;
        this.distances = distances;
        this.alpha = alpha;
        this.beta = beta;
        this.evaporation = evaporation;
        this.Q = Q;
        this.pheromone = new double[numCities][numCities];
        this.bestDistance = Integer.MAX_VALUE;
        this.random = new Random();

        // Inicializa la matriz de feromonas con un pequeño valor inicial
        for (int i = 0; i < numCities; i++) {
            Arrays.fill(pheromone[i], 1.0);
        }

        // Ejecuta el algoritmo de optimización
        for (int i = 0; i < numIterations; i++) {
            optimize();
        }
    }

    private void optimize() {
        int[][] antRoutes = new int[numAnts][numCities];
        int[] antDistances = new int[numAnts];

        for (int i = 0; i < numAnts; i++) {
            antRoutes[i] = constructSolution();
            antDistances[i] = calculateDistance(antRoutes[i]);

            if (antDistances[i] < bestDistance) {
                bestDistance = antDistances[i];
                bestRoute = antRoutes[i].clone();
            }
        }

        updatePheromones(antRoutes, antDistances);
    }

    private int[] constructSolution() {
        int[] route = new int[numCities];
        boolean[] visited = new boolean[numCities];
        int currentCity = random.nextInt(numCities);
        route[0] = currentCity;
        visited[currentCity] = true;

        for (int i = 1; i < numCities; i++) {
            int nextCity = selectNextCity(currentCity, visited);
            route[i] = nextCity;
            visited[nextCity] = true;
            currentCity = nextCity;
        }

        return route;
    }

    private int selectNextCity(int currentCity, boolean[] visited) {
        double[] probabilities = new double[numCities];
        double sum = 0.0;

        for (int i = 0; i < numCities; i++) {
            if (!visited[i]) {
                probabilities[i] = Math.pow(pheromone[currentCity][i], alpha) * Math.pow(1.0 / distances[currentCity][i], beta);
                sum += probabilities[i];
            }
        }

        double r = random.nextDouble() * sum;
        sum = 0.0;

        for (int i = 0; i < numCities; i++) {
            if (!visited[i]) {
                sum += probabilities[i];
                if (sum >= r) {
                    return i;
                }
            }
        }

        return -1;
    }

    private void updatePheromones(int[][] antRoutes, int[] antDistances) {
        // Evaporación
        for (int i = 0; i < numCities; i++) {
            for (int j = 0; j < numCities; j++) {
                pheromone[i][j] *= (1 - evaporation);
            }
        }

        // Actualización basada en la calidad de la solución
        for (int i = 0; i < numAnts; i++) {
            for (int j = 0; j < numCities - 1; j++) {
                int city1 = antRoutes[i][j];
                int city2 = antRoutes[i][j + 1];
                pheromone[city1][city2] += Q / antDistances[i];
                pheromone[city2][city1] += Q / antDistances[i];
            }

            // Añadir feromona en la ruta de vuelta
            int lastCity = antRoutes[i][numCities - 1];
            int firstCity = antRoutes[i][0];
            pheromone[lastCity][firstCity] += Q / antDistances[i];
            pheromone[firstCity][lastCity] += Q / antDistances[i];
        }
    }

    private int calculateDistance(int[] route) {
        int totalDistance = 0;
        for (int i = 0; i < numCities - 1; i++) {
            totalDistance += distances[route[i]][route[i + 1]];
        }
        totalDistance += distances[route[numCities - 1]][route[0]]; // Volver a la ciudad inicial
        return totalDistance;
    }

    public int[] getBestRoute() {
        return bestRoute;
    }

    public int getBestDistance() {
        return bestDistance;
    }
}


Resultado:

run:
> Mejor ruta encontrada:
[14, 1, 15, 13, 10, 11, 2, 12, 4, 3, 6, 9, 5, 8, 7, 0]
> La distancia total recorrida es: 20699
BUILD SUCCESSFUL (total time: 0 seconds)