Este artículo proviene de un motor de traducción automática.
Ejecución de prueba
Optimización por colonia de hormigas
Descargar el código de ejemplo
En la columna de este mes presento código C# que implementa un algoritmo de optimización de Colonia de hormigas (ACO) para resolver el problema del viajante (TSP). Un algoritmo ACO es una técnica de inteligencia artificial basada en el comportamiento de colocación de feromonas de hormigas; puede utilizarse para encontrar soluciones a problemas sumamente complejos que buscan la ruta óptima a través de un gráfico. Es la mejor manera para ver donde estoy enfilé echar un vistazo a la captura de pantalla en figura 1. En este caso, la demostración es resolver una instancia de la TSP con el objetivo de encontrar el camino más corto que visita cada una de 60 ciudades exactamente una vez. El programa de demostración utiliza cuatro hormigas; cada hormiga representa una posible solución. ACO requiere la especificación de varios parámetros, como el factor de influencia de feromonas (alfa) y el coeficiente de evaporación de feromonas (rho), algo que explicaré más tarde. Las cuatro hormigas se inicializan a pistas aleatorias a través de las 60 ciudades; Después de la inicialización, la hormiga mejor tiene una longitud de ruta más corta de 245.0 unidades. La idea clave de ACO es el uso de feromonas simuladas, que atraen a hormigas senderos mejores a través de la gráfica. El bucle de procesamiento principal alterna entre actualizar los senderos de hormiga basados en los valores actuales de la feromona y actualizar las feromonas basadas en los nuevos senderos de hormiga. Después de que el número máximo de veces (1.000) a través del bucle principal de procesamiento, el programa muestra el mejor sendero que se encuentra y su longitud correspondiente (61.0 unidades).
El gráfico de 60-ciudad está construido artificialmente para que cada ciudad está conectada a todas las otras ciudades, y la distancia entre las dos ciudades es un valor aleatorio entre 1.0 y 8.0 unidades arbitrarias (millas, kilómetros etc.). No hay ninguna manera fácil de resolver el TSP. Con 60 ciudades, suponiendo que puede iniciar en cualquier ciudad e ir hacia adelante o hacia atrás, y que se conectan todas las ciudades, hay un total de (60 - 1)! / 2 = 69,341,559,272,844,917,868,969,509,860,194,703,172,951,438,386,343,716,270,410,647,470,080,000,000,
000,000 posibles soluciones. Incluso si pudiera evaluar posibles soluciones mil millones por segundo, tardaría unos 2.2 * 1063 años comprobar todos ellos, que es muchas veces más largo que la edad estimada del universo.
ACO es un meta-heuristic, lo que significa que es un marco general que puede utilizarse para crear un algoritmo específico para resolver un problema de trazado del gráfico específico. Aunque ACO fue propuesto en una tesis doctoral de 1991 por M. Dorigo, la primera descripción detallada del algoritmo es generalmente atribuida a un documento de seguimiento de 1996 por M. Dorigo, V. Maniezzo y a. Colorni. Desde entonces, ACO ha sido ampliamente estudiado y modificado, pero, curiosamente algo, muy pocas implementaciones completas y correctas están disponibles en línea.
Esta columna asume que tiene conocimientos de programación intermedio a avanzado. Implemento el programa ACO utilizando C#, pero no deberían tener demasiados problemas refactorización mi código a un idioma diferente, como JavaScript. Decidí evitar todo uso de la programación orientada a objetos (OOP) para mantener las ideas del algoritmo más claro posible. Debido a limitaciones de espacio, no puedo presentar todo el código que se muestra que se ejecutan en figura 1. Va a ir sobre las partes más difíciles y se puede descargar el código completo de archive.msdn.microsoft.com/mag201202TestRun. Aunque nunca podría utilizar código ACO directamente, muchas de sus técnicas, tales como la selección de rueda de ruleta, pueden ser interesantes y útiles adiciones a su habilidad técnica establezca.
.png)
Figura 1 optimización de Colonia de hormigas en acción
Estructura del programa
Había implementado el programa de demostración ACO como una única aplicación de consola en C#. La estructura general del programa, con más declaraciones de WriteLine eliminado, se muestra en figura 2. Aunque algunas partes son difíciles, el programa no es tan complicado como figura2 sugiere porque muchos de los métodos son métodos auxiliares corto.
Estructura del programa de optimización de la figura 2 Ant Colonia
using System;
namespace AntColony
{
class AntColonyProgram
{
static Random random = new Random(0);
static int alpha = 3;
static int beta = 2;
static double rho = 0.01;
static double Q = 2.0;
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin Ant Colony Optimization demo\n");
int numCities = 60;
int numAnts = 4;
int maxTime = 1000;
int[][] dists = MakeGraphDistances(numCities);
int[][] ants = InitAnts(numAnts, numCities);
int[] bestTrail = BestTrail(ants, dists);
double bestLength = Length(bestTrail, dists);
double[][] pheromones = InitPheromones(numCities);
int time = 0;
while (time < maxTime)
{
UpdateAnts(ants, pheromones, dists);
UpdatePheromones(pheromones, ants, dists);
int[] currBestTrail = BestTrail(ants, dists);
double currBestLength = Length(currBestTrail, dists);
if (currBestLength < bestLength)
{
bestLength = currBestLength;
bestTrail = currBestTrail;
}
++time;
}
Console.WriteLine("\nBest trail found:");
Display(bestTrail);
Console.WriteLine("\nLength of best trail found: " +
bestLength.ToString("F1"));
Console.WriteLine("\nEnd Ant Colony Optimization demo\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
static int[][] InitAnts(int numAnts, int numCities) { .
.
}
static int[] RandomTrail(int start, int numCities) { .
.
}
static int IndexOfTarget(int[] trail, int target) { .
.
}
static double Length(int[] trail, int[][] dists) { .
.
}
static int[] BestTrail(int[][] ants, int[][] dists) { .
.
}
static double[][] InitPheromones(int numCities) { .
.
}
static void UpdateAnts(int[][] ants, double[][] pheromones,
int[][] dists) { .
.
}
static int[] BuildTrail(int k, int start, double[][] pheromones,
int[][] dists) { .
.
}
static int NextCity(int k, int cityX, bool[] visited, double[][] pheromones,
int[][] dists) { .
.
}
static double[] MoveProbs(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists) { .
.
}
static void UpdatePheromones(double[][] pheromones, int[][] ants,
int[][] dists) { .
.
}
static bool EdgeInTrail(int nodeX, int nodeY, int[] trail) { .
.
}
static int[][] MakeGraphDistances(int numCities) { .
.
}
static double Distance(int cityX, int cityY, int[][] dists) { .
.
}
static void Display(int[] trail) { .
.
}
static void ShowAnts(int[][] ants, int[][] dists) { .
.
}
static void Display(double[][] pheromones) { .
.
}
}
}
He utilizado Visual Studio para crear un programa de aplicación de consola denominado AntColony. En la ventana Explorador de soluciones renombrado el archivo Program.cs predeterminado a AntColonyProgram.cs, que automatically renombrado como la única clase en el proyecto. He eliminado toda la plantilla generada utilizando declaraciones excepto para el espacio de nombres System: ACO normalmente no necesita mucho apoyo de la biblioteca. Los dos métodos principales son UpdateAnts y UpdatePheromones. Auxiliar de llamadas de método UpdateAnts BuildTrail, que se llama NextCity, que se llama MoveProbs. Método UpdatePheromones llama auxiliar EdgeInTrail, que se llama IndexOfTarget.
Declaró un objeto aleatorio de ámbito de clase el nombre aleatorio. Algoritmos ACO son probabilísticos como verá poco. El alfa de variables de ámbito de clase, beta, rho y q controlan el comportamiento del algoritmo ACO. Usar estos nombres de variable porque fueron utilizados en la descripción original de ACO.
Configurar el problema
Utilicé el método MakeGraphDistances para configurar un gráfico artificial:
static int[][] MakeGraphDistances(int numCities)
{
int[][] dists = new int[numCities][];
for (int i = 0; i < dists.Length; ++i)
dists[i] = new int[numCities];
for (int i = 0; i < numCities; ++i)
for (int j = i + 1; j < numCities; ++j) {
int d = random.Next(1, 9); // [1,8]
dists[i][j] = d; dists[j][i] = d;
}
return dists;
}
Para un problema real-mundo gráfico, quedaría probablemente gráfico -adyacencia y distancia entre nodos de datos desde un archivo de texto en algún tipo de estructura de datos. Aquí simulado un gráfico mediante la creación de una matriz de matrices donde el índice de la fila representa de la ciudad y la columna índice j representa a la ciudad. Observe que todas las ciudades están conectadas, distancias son simétricos y la distancia de una ciudad a sí mismo es 0.
Una vez que tengo una estructura de datos de distancias puedo usarlo para un método de distancia:
static double Distance(int cityX, int cityY, int[][] dists)
{
return dists[cityX][cityY];
}
Para minimizar la cantidad de código presentado, he omitido normal error al comprobar, como asegurándose de que los parámetros cityY y cityX son válidos.
Iniciando las hormigas y las feromonas
En esta implementación no Poo, una hormiga es simplemente una matriz de valores int que representan el camino o la ruta, desde una ciudad inicial a través de todas las otras ciudades. Una colección de hormigas es una matriz de matrices en las que el primer índice indica la hormiga:
static int[][] InitAnts(int numAnts, int numCities)
{
int[][] ants = new int[numAnts][];
for (int k = 0; k < numAnts; ++k) {
int start = random.Next(0, numCities);
ants[k] = RandomTrail(start, numCities);
}
return ants;
}
El método de inicialización asigna una fila para el sendero para cada hormiga, recoge una ciudad Inicio aleatorio y, a continuación, llama a un método auxiliar RandomTrail:
static int[] RandomTrail(int start, int numCities)
{
int[] trail = new int[numCities];
for (int i = 0; i < numCities; ++i) { trail[i] = i; }
for (int i = 0; i < numCities; ++i) {
int r = random.Next(i, numCities);
int tmp = trail[r]; trail[r] = trail[i]; trail[i] = tmp;
}
int idx = IndexOfTarget(trail, start);
int temp = trail[0]; trail[0] = trail[idx]; trail[idx] = temp;
return trail;
}
El Ayudante de RandomTrail asigna un rastro e inicializa a 0, 1, 2... numCities-1. A continuación, el método utiliza el algoritmo de shuffle de Fisher-Yates para aleatorizar el orden de las ciudades en la ruta. La ciudad de inicio especificada luego ubica y intercambiada en pista de posición [0].
Las feromonas son sustancias químicas lugar de hormigas en sus senderos; atraen a otras hormigas. Más hormigas viajará en un camino más corto a una fuente de alimentos — y depositar las feromonas más — que en los senderos más largos. Las feromonas se evaporan lentamente con el tiempo. Éste es el método InitPheromones:
static double[][] InitPheromones(int numCities)
{
double[][] pheromones = new double[numCities][];
for (int i = 0; i < numCities; ++i)
pheromones[i] = new double[numCities];
for (int i = 0; i < pheromones.Length; ++i)
for (int j = 0; j < pheromones[i].Length; ++j)
pheromones[i][j] = 0.01;
return pheromones;
}
Feromona información se almacena en una matriz simétrica de matriz de matrices de estilo donde la fila de índice es de la ciudad y la columna índice j a la ciudad. Todos los valores son establecidos inicialmente a un valor pequeño arbitrario (0,01) saltar inicia el ciclo de UpdateAnts-UpdatePheromones.
Actualización de las hormigas
La clave del algoritmo de ACO es el proceso que actualiza cada hormiga y camino por construir un nuevo — esperamos mejor: sendero basado en la información de feromonas y distancia. Echa un vistazo a figura 3. Supongamos que tenemos un gráfico pequeño con sólo cinco ciudades. En figura 3 el nuevo camino de una hormiga está bajo construcción. La ruta comienza en la ciudad 1 y, a continuación, va a la ciudad 3, y el algoritmo de actualización consiste en determinar la próxima ciudad. Ahora suponga que la feromona y distancia información es como se muestra en la imagen. El primer paso para determinar la siguiente ciudad es construir una matriz que he llamado "taueta" (porque el trabajo de investigación original utiliza la tau de letras griegas y eta). El valor de taueta es el valor de la feromona en el borde elevado a la potencia alfa, a veces uno sobre el valor de distancia elevado a la potencia de la versión beta. Recordar que alfa y beta son constantes globales que deben especificarse. Aquí te supongo que alfa es 3 y beta 2. Los valores taueta de ciudad 1 y 3 no calculados debido a que ya están en el camino actual. Observe que los valores más grandes de la feromona aumentan taueta, pero más grandes distancias disminuyen taueta.
.png)
Figura 3 actualizar información de hormiga
Después de que se han calculado todos los valores de taueta, el siguiente paso es convertir esos valores a probabilidades y colocarlos en una matriz he etiquetado como probs. El algoritmo de suma los valores de taueta, obteniendo 82.26 en este ejemplo y luego divide cada valor taueta por la suma. En este punto, ciudad 0 tiene una probabilidad de 0,09 de ser seleccionados y así sucesivamente. A continuación, el algoritmo debe seleccionar la siguiente ciudad basada en las probabilidades calculadas. Como he mencionado anteriormente, el algoritmo ACO que presento en este artículo utiliza una técnica impecable llamada selección de rueda de ruleta. Construyó una matriz aumentada llamada de acumulación, que tiene probabilidades acumulativas. El tamaño de la matriz aumentada es mayor que la matriz probs y celda [0] es inseminado con 0,0. Cada celda de acumulación es la suma acumulada de las probabilidades. Después de que se ha construido la matriz de acumulación, se genera un p número aleatorio entre 0.0 y 1.0. Supongamos que p = 0.538 como se muestra. Ese valor p cae entre los valores de [2] y [3] de la matriz de acumulación, lo que significa que [2], o ciudad 2, es seleccionado como la próxima ciudad.
El método de nivel superior para actualizar el nombre de UpdateAnts:
static void UpdateAnts(int[][] ants, double[][] pheromones, int[][] dists)
{
int numCities = pheromones.Length;
for (int k = 0; k < ants.Length; ++k) {
int start = random.Next(0, numCities);
int[] newTrail = BuildTrail(k, start, pheromones, dists);
ants[k] = newTrail;
}
}
Observe que cada hormiga se asigna una nueva ciudad partida aleatoria en lugar de preservar al antiguo Inicio ciudad. La mayoría del trabajo real se realiza mediante el método auxiliar BuildTrail, como se muestra en figura 4.
Figura 4 el método de BuildTrail
static int[] BuildTrail(int k, int start, double[][] pheromones,
int[][] dists)
{
int numCities = pheromones.Length;
int[] trail = new int[numCities];
bool[] visited = new bool[numCities];
trail[0] = start;
visited[start] = true;
for (int i = 0; i < numCities - 1; ++i) {
int cityX = trail[i];
int next = NextCity(k, cityX, visited, pheromones, dists);
trail[i + 1] = next;
visited[next] = true;
}
return trail;
}
BuildTrail mantiene una matriz de Boolean visitó, para que el sendero creado no contiene ciudades duplicadas. El valor en pista [0] es inseminado con una ciudad de inicio y, a continuación, cada ciudad se agrega a su vez por el método auxiliar NextCity, se muestra en la figura 5.
Figura 5 el método de NextCity
static int NextCity(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists)
{
double[] probs = MoveProbs(k, cityX, visited, pheromones, dists);
double[] cumul = new double[probs.Length + 1];
for (int i = 0; i < probs.Length; ++i)
cumul[i + 1] = cumul[i] + probs[i];
double p = random.NextDouble();
for (int i = 0; i < cumul.Length - 1; ++i)
if (p >= cumul[i] && p < cumul[i + 1])
return i;
throw new Exception("Failure to return valid city in NextCity");
}
El método NextCity implementa el algoritmo de selección de rueda de ruleta.Tenga en cuenta que el algoritmo fallará si el último valor de la matriz de acumulación es mayor que 1.00 (posiblemente debido a errores de redondeo), y por lo que tal vez desee agregar lógica para establecer siempre cumul [acumulación.Longitud-1] a 1,00. NextCity requiere una matriz de probabilidades producidos por el método auxiliar MoveProbs, se muestra en la figura 6.
Figura 6 el método de MoveProbs
static double[] MoveProbs(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists)
{
int numCities = pheromones.Length;
double[] taueta = new double[numCities];
double sum = 0.0;
for (int i = 0; i < taueta.Length; ++i) {
if (i == cityX)
taueta[i] = 0.0; // Prob of moving to self is zero
else if (visited[i] == true)
taueta[i] = 0.0; // Prob of moving to a visited node is zero
else {
taueta[i] = Math.Pow(pheromones[cityX][i], alpha) *
Math.Pow((1.0 / Distance(cityX, i, dists)), beta);
if (taueta[i] < 0.0001)
taueta[i] = 0.0001;
else if (taueta[i] > (double.MaxValue / (numCities * 100)))
taueta[i] = double.MaxValue / (numCities * 100);
}
sum += taueta[i];
}
double[] probs = new double[numCities];
for (int i = 0; i < probs.Length; ++i)
probs[i] = taueta[i] / sum;
return probs;
}
Los valores de taueta pueden ser muy pequeños (si el valor de la distancia es muy grande) o muy grandes (si el valor de la feromona es grande), que puede producir dificultades para el algoritmo. Para hacer frente a esto, compruebe los valores de taueta e imponer valores max y min arbitraria.
Actualización de las feromonas
Actualizar información de feromonas es mucho más fácil que actualizar la información de ruta de hormiga. Las principales líneas de código en el método UpdatePhermones son:
double length = Length(ants[k], dists);
double decrease = (1.0 - rho) * pheromones[i][j];
double increase = 0.0;
if (EdgeInTrail(i, j, ants[k]) == true)
increase = (Q / length);
pheromones[i][j] = decrease + increase;
Cada valor de feromonas disminuye, simulando la evaporación y aumentado, simulando el depósito de las feromonas por hormigas en la pista. El efecto de la disminución se produce multiplicando el valor actual de la feromona por un factor menos de 1.0 que depende de rho parámetro global. Rho mayor es, mayor será la reducción del valor de feromonas. El efecto de aumento se produce mediante la adición de una proporción de longitud de ruta total de hormiga actual, donde la proporción se determina por parámetro global Q. Valores grandes de q aumentan la cantidad de feromona añadido. Auxiliar de llamadas de método UpdatePheromones EdgeInTrail, que determina si un segmento entre dos ciudades es el camino actual de las hormigas. Puede comprobar la descarga de código de este artículo para ver los detalles (archive.msdn.microsoft.com/mag201202TestRun).
Conclusión
Permítaseme recalcar que hay muchas variaciones de ACO; la versión que he presentado aquí es sólo uno de muchos enfoques posibles. ACO defensores han aplicado el algoritmo para una amplia gama de problemas de optimización combinatoria. Otro combinatoria optimization algoritmos basados en el comportamiento de los sistemas naturales incluyen simulado recocido (SA), que cubría el mes pasado (msdn.microsoft.com/magazine/hh708758) y simulado Bee Colonia (SBC), que tratan en mi columna de abril de 2011 (msdn.microsoft.com/magazine/gg983491). Cada enfoque tiene fortalezas y debilidades. En mi opinión, es más adecuada a los problemas que se asemejan al problema del viajante, mientras que SA y SBC son mejores para los problemas más generales de optimización combinatoria, tales como la programación de ACO.
ACO, en común con otra meta-heurística basada en sistemas naturales, es muy sensible a su elección de parámetros globales libres: alfa, beta y así sucesivamente. Aunque ha habido un poco de investigación sobre parámetros ACO, el consenso general es que debe experimentar un poco con parámetros libres para obtener la mejor combinación de rendimiento y solución de calidad.
Dr.James McCaffrey trabaja para Volt Information Sciences Inc., donde administra capacitación técnica para ingenieros de software que trabaja en el Microsoft Redmond, Washington, campus. Trabajó en varios productos de Microsoft Internet Explorer y MSN Search. McCaffrey es el autor de ".Recetas de automatización de prueba NET"(Apress, 2006) y puede ser contactado en jmccaffrey@volt.com o jammc@microsoft.com.
Gracias a los siguientes expertos técnicos de Microsoft para revisar este artículo: Dan Liebling y Anne Loomis Thompson