Optimización de colonia de hormigas con un ejemplo de Java

1. Introducción

El objetivo de esta serie es explicar la idea de algoritmos genéticos y mostrar las implementaciones más conocidas .

En este tutorial, describiremos el concepto de optimización de colonias de hormigas (ACO), seguido del ejemplo de código.

2. Cómo funciona ACO

ACO es un algoritmo genético inspirado en el comportamiento natural de una hormiga. Para comprender completamente el algoritmo ACO, debemos familiarizarnos con sus conceptos básicos:

  • Las hormigas usan feromonas para encontrar el camino más corto entre el hogar y la fuente de alimento.
  • las feromonas se evaporan rápidamente
  • Las hormigas prefieren usar caminos más cortos con feromonas más densas.

Muestremos un ejemplo simple de ACO utilizado en el Problema del vendedor ambulante. En el siguiente caso, necesitamos encontrar la ruta más corta entre todos los nodos del gráfico:

Siguiendo los comportamientos naturales, las hormigas comenzarán a explorar nuevos caminos durante la exploración. El color azul más fuerte indica las rutas que se utilizan con más frecuencia que los demás, mientras que el color verde indica la ruta más corta actual que se encuentra:

Como resultado, lograremos la ruta más corta entre todos los nodos:

La buena herramienta basada en GUI para pruebas ACO se puede encontrar aquí.

3. Implementación de Java

3.1. Parámetros ACO

Analicemos los principales parámetros para el algoritmo ACO, declarado en la clase AntColonyOptimization :

private double c = 1.0; private double alpha = 1; private double beta = 5; private double evaporation = 0.5; private double Q = 500; private double antFactor = 0.8; private double randomFactor = 0.01;

El parámetro c indica el número original de senderos, al inicio de la simulación. Además, alfa controla la importancia de las feromonas, mientras que beta controla la prioridad de distancia. En general, el parámetro beta debe ser mayor que alfa para obtener los mejores resultados.

A continuación, la variable de evaporación muestra el porcentaje de cuánto se evapora la feromona en cada iteración, mientras que Q proporciona información sobre la cantidad total de feromona dejada en el camino por cada hormiga , y antFactor nos dice cuántas hormigas usaremos por ciudad.

Finalmente, necesitamos tener un poco de aleatoriedad en nuestras simulaciones, y esto está cubierto por randomFactor .

3.2. Crear hormigas

Cada hormiga podrá visitar una ciudad específica, recordar todas las ciudades visitadas y realizar un seguimiento de la longitud del sendero:

public void visitCity(int currentIndex, int city) { trail[currentIndex + 1] = city; visited[city] = true; } public boolean visited(int i) { return visited[i]; } public double trailLength(double graph[][]) { double length = graph[trail[trailSize - 1]][trail[0]]; for (int i = 0; i < trailSize - 1; i++) { length += graph[trail[i]][trail[i + 1]]; } return length; } 

3.3. Configurar hormigas

Al principio, necesitamos inicializar nuestra implementación de código ACO proporcionando rutas y matrices de hormigas:

graph = generateRandomMatrix(noOfCities); numberOfCities = graph.length; numberOfAnts = (int) (numberOfCities * antFactor); trails = new double[numberOfCities][numberOfCities]; probabilities = new double[numberOfCities]; ants = new Ant[numberOfAnts]; IntStream.range(0, numberOfAnts).forEach(i -> ants.add(new Ant(numberOfCities)));

A continuación, necesitamos configurar la matriz de hormigas para comenzar con una ciudad aleatoria:

public void setupAnts() { IntStream.range(0, numberOfAnts) .forEach(i -> { ants.forEach(ant -> { ant.clear(); ant.visitCity(-1, random.nextInt(numberOfCities)); }); }); currentIndex = 0; }

Para cada iteración del ciclo, realizaremos las siguientes operaciones:

IntStream.range(0, maxIterations).forEach(i -> { moveAnts(); updateTrails(); updateBest(); });

3.4. Mover hormigas

Comencemos con el método moveAnts () . Necesitamos elegir la siguiente ciudad para todas las hormigas, recordando que cada hormiga intenta seguir los rastros de otras hormigas:

public void moveAnts() { IntStream.range(currentIndex, numberOfCities - 1).forEach(i -> { ants.forEach(ant -> { ant.visitCity(currentIndex, selectNextCity(ant)); }); currentIndex++; }); }

La parte más importante es seleccionar correctamente la próxima ciudad para visitar. Debemos seleccionar la siguiente ciudad según la lógica de probabilidad. Primero, podemos verificar si Ant debería visitar una ciudad aleatoria:

int t = random.nextInt(numberOfCities - currentIndex); if (random.nextDouble()  i == t && !ant.visited(i)) .findFirst(); if (cityIndex.isPresent()) { return cityIndex.getAsInt(); } }

Si no seleccionamos ninguna ciudad al azar, necesitamos calcular las probabilidades para seleccionar la siguiente ciudad, recordando que las hormigas prefieren seguir senderos más fuertes y más cortos. Podemos hacer esto almacenando la probabilidad de mudarnos a cada ciudad en la matriz:

public void calculateProbabilities(Ant ant) { int i = ant.trail[currentIndex]; double pheromone = 0.0; for (int l = 0; l < numberOfCities; l++) { if (!ant.visited(l)){ pheromone += Math.pow(trails[i][l], alpha) * Math.pow(1.0 / graph[i][l], beta); } } for (int j = 0; j < numberOfCities; j++) { if (ant.visited(j)) { probabilities[j] = 0.0; } else { double numerator = Math.pow(trails[i][j], alpha) * Math.pow(1.0 / graph[i][j], beta); probabilities[j] = numerator / pheromone; } } } 

Después de calcular las probabilidades, podemos decidir a qué ciudad ir usando:

double r = random.nextDouble(); double total = 0; for (int i = 0; i = r) { return i; } }

3.5. Actualizar senderos

En este paso, debemos actualizar los rastros y la feromona izquierda:

public void updateTrails() { for (int i = 0; i < numberOfCities; i++) { for (int j = 0; j < numberOfCities; j++) { trails[i][j] *= evaporation; } } for (Ant a : ants) { double contribution = Q / a.trailLength(graph); for (int i = 0; i < numberOfCities - 1; i++) { trails[a.trail[i]][a.trail[i + 1]] += contribution; } trails[a.trail[numberOfCities - 1]][a.trail[0]] += contribution; } }

3.6. Actualice la mejor solución

Este es el último paso de cada iteración. Necesitamos actualizar la mejor solución para mantener la referencia a ella:

private void updateBest() { if (bestTourOrder == null) { bestTourOrder = ants[0].trail; bestTourLength = ants[0].trailLength(graph); } for (Ant a : ants) { if (a.trailLength(graph) < bestTourLength) { bestTourLength = a.trailLength(graph); bestTourOrder = a.trail.clone(); } } }

Después de todas las iteraciones, el resultado final indicará la mejor ruta encontrada por ACO. Tenga en cuenta que al aumentar el número de ciudades, la probabilidad de encontrar el camino más corto disminuye.

4. Conclusión

Este tutorial presenta el algoritmo de optimización de colonia de hormigas . Puede aprender sobre algoritmos genéticos sin ningún conocimiento previo de esta área, teniendo solo habilidades básicas de programación informática.

El código fuente completo de los fragmentos de código de este tutorial está disponible en el proyecto GitHub.

Para todos los artículos de la serie, incluidos otros ejemplos de algoritmos genéticos, consulte los siguientes enlaces:

  • Cómo diseñar un algoritmo genético en Java
  • El problema del vendedor ambulante en Java
  • Optimización de colonia de hormigas (esto)