Cet article a fait l'objet d'une traduction automatique.
Série de tests
Optimisation par colonie de fourmis
Téléchargez l'exemple de Code
.jpg)
Dans la colonne de ce mois-ci je présente le code c# qui implémente un algorithme Ant Colony Optimization (ACO) pour résoudre le problème du voyageur (TSP). Un algorithme de l'ACO est une technique d'intelligence artificielle basée sur le comportement de ponte des phéromones des fourmis ; Il peut être utilisé pour trouver des solutions à des problèmes extrêmement complexes qui cherchent le chemin optimal grâce à un graphique. La meilleure façon de voir vers où je suis est de prendre un coup de œil à la capture d'écran Figure 1. Dans ce cas, la démo est à résoudre une instance de la c. à thé dans le but de trouver le chemin le plus court que chacun des 60 villes visites exactement une fois. Le programme de démonstration utilise quatre fourmis ; chaque fourmi représente une solution potentielle. ACO requiert la spécification de plusieurs paramètres tels que le facteur d'influence de phéromone (alpha) et le coefficient de l'évaporation de phéromone (rho), que j'expliquerai plus tard. Les quatre fourmis sont initialisées avec des pistes au hasard par les 60 villes ; après l'initialisation, le meilleur ant a une longueur de piste plus courte de 245.0 unités. L'idée principale de l'ACO est l'utilisation de phéromones simulées, qui attirent les fourmis de meilleures pistes à travers le graphique. La boucle de traitement principale alterne entre les sentiers de la fourmi basées sur les valeurs actuelles de la phéromone de mise à jour et mise à jour des phéromones basés sur les sentiers nouveaux de la fourmi. Après que le nombre maximal de fois (1 000) dans la boucle de traitement principale, le programme affiche la meilleure piste trouvé et sa longueur correspondante (61,0 unités).
Le graphe 60-ville est construit artificiellement afin que chaque ville est reliée à toutes les autres villes, et la distance entre les deux villes est une valeur aléatoire entre 1,0 et 8,0 unités arbitraires (miles, km et ainsi de suite). Il n'existe aucun moyen facile de résoudre le TSP. Avec 60 villes, en supposant que vous pouvez commencer à toute ville et aller vers l'avant ou vers l'arrière, et que toutes les villes sont reliés, il y a 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 solutions possibles. Même si vous pouvait évaluer les solutions possibles de 1 milliard de dollars par seconde, il faudrait environ 2,2 * 1063 ans pour vérifier tous les, qui est plusieurs fois plus longtemps que l'âge estimé de l'univers.
ACO est un meta-heuristic, ce qui signifie que c'est un cadre général qui peut être utilisé pour créer un algorithme pour résoudre un problème de chemin d'accès graphique spécifique. Bien que l'ACO a été proposée dans une thèse de doctorat de 1991 par M. Dorigo, la première description détaillée de l'algorithme est généralement attribué à un document de suivi de 1996 par M. Dorigo, V. Maniezzo et a. Colorni. Depuis lors, ACO a été largement étudiée et mise à jour, mais, assez curieusement, quelques implémentations complètes et correctes sont disponibles en ligne.
Cette rubrique suppose que vous avez des compétences en programmes intermédiaire à avancé. J'implémente le programme CoA à l'aide de c#, mais vous ne devraient pas avoir trop d'ennuis refactorisation mon code pour un langage différent, tel que JavaScript. J'ai décidé d'éviter toute utilisation de la programmation orientée objet (POO) pour garder les idées de l'algorithme aussi claire que possible. À cause des limitations de l'espace, je ne peux pas présenter tous le code s'exécutant dans Figure 1. J'irai sur les parties les plus délicats et vous pouvez télécharger le code complet de archive.msdn.microsoft.com/mag201202TestRun. Bien que vous ne pouvez jamais utiliser code de CoA directement, plusieurs de ses techniques, telles que la sélection de roue de la roulette, peuvent être intéressants et définir des ajouts utiles à vos compétences techniques.
.png)
Figure 1 Ant Colony Optimization en Action
Structure du programme
J'ai mis en œuvre le programme de démonstration ACO comme une simple application de console c#. La structure globale du programme, avec la plupart des déclarations de WriteLine enlevée, est montrée dans Figure 2. Bien que certaines parties sont difficiles, le programme n'est pas aussi compliqué que Figure2 suggère parce que la plupart des méthodes sont des méthodes d'assistance court.
Structure du programme figure 2 Ant Colony Optimization
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) { .
.
}
}
}
J'ai utilisé Visual Studio pour créer un programme d'application console nommé AntColony. Dans la fenêtre Explorateur de solutions j'ai renommé le fichier Program.cs par défaut de AntColonyProgram.cs, qui automatiquement renommé la classe unique dans le projet. J'ai supprimé tous les modèle généré utilisant des déclarations sauf pour l'espace de noms système — ACO n'a pas généralement besoin beaucoup de soutien Bibliothèque. Les deux principales méthodes sont UpdateAnts et UpdatePheromones. Méthode UpdateAnts appelle d'assistance BuildTrail, qui appelle NextCity, qui appelle MoveProbs. Méthode UpdatePheromones appelle d'assistance EdgeInTrail, qui appelle IndexOfTarget.
J'ai déclaré un objet aléatoire de classe-portée nommé aléatoire. Algorithmes de l'ACO sont probabilistes comme vous le verrez sous peu. Le champ classe variables alpha, beta, rhô et q contrôlent le comportement de l'algorithme de l'ACO. Utiliser les noms de ces variables parce qu'ils ont été utilisés dans la description originale de l'ACO.
Mise en place du problème
J'ai utilisé la méthode MakeGraphDistances pour mettre en place un graphique artificiel :
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;
}
Pour un problème graphique du monde réel, vous liriez probablement graph -contiguïté et la distance entre les nœuds de données dans un fichier texte dans une sorte de structure de données. Ici j'ai simulé un graphe en créant un tableau de tableaux où l'index de ligne je représente la ville d'et l'index de colonne j représente la ville de. Notez que toutes les villes sont reliées, les distances sont symétriques et la distance de la ville elle-même est 0.
Une fois que j'ai une structure de données de distances, je peux l'utiliser pour une méthode de la Distance :
static double Distance(int cityX, int cityY, int[][] dists)
{
return dists[cityX][cityY];
}
Afin de minimiser la quantité de code présenté, j'ai omis normal erreur vérification, comme par exemple en s'assurant que la City et cityY paramètres sont valides.
Les fourmis et les phéromones
Dans cette implémentation non-OOP, une fourmi est tout simplement un tableau de valeurs int qui représentent le sentier ou chemin d'accès, d'une ville initiale par le biais de toutes les autres villes. Une collection de fourmis est un tableau de tableaux dans lesquels le premier index indique la fourmi :
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;
}
La méthode d'initialisation alloue une ligne pour le sentier pour chaque fourmi, choisit une ville de départ aléatoire et puis appelle une méthode d'assistance 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;
}
L'assistance RandomTrail alloue un sentier et l'initialise à 0, 1, 2... numCities-1. Ensuite, la méthode utilise l'algorithme de shuffle de Fisher-Yates pour randomiser l'ordre des villes dans la piste. La ville de départ spécifié est alors située et échangée dans le sentier de la position [0].
Les phéromones sont des substances chimiques fourmis lieu sur leurs pistes ; elles attirent d'autres fourmis. Plus de fourmis seront rendra sur une piste plus courte à une source de nourriture — et déposer des phéromones plus — que sur les sentiers plus longtemps. Les phéromones s'évaporent lentement au fil du temps. Voici la méthode 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;
}
Information de la phéromone est stockée dans une matrice symétrique de style de tableau de tableaux où la ligne d'index i est de la ville et l'index de colonne j est à la ville. Toutes les valeurs sont initialement a une valeur arbitraire et petite (0,01) sauter commencer le cycle de UpdateAnts-UpdatePheromones.
Mise à jour des fourmis
La clé de l'algorithme de l'ACO est le processus qui met à jour chaque fourmi et trail en construisant un nouveau — nous espérons mieux — sentier basé sur les informations de distance et de phéromones. Regardez Figure 3. Supposons que nous avons un petit graphe avec seulement cinq villes. En Figure 3 le nouveau sentier pour une fourmi est en cours de construction. Le sentier commence en ville 1, puis va à la ville 3, et l'algorithme de mise à jour consiste à déterminer la prochaine ville. Supposons maintenant que la phéromone et la distance information est tel que montré dans l'image. La première étape dans la détermination de la prochaine ville fait construire un tableau j'ai appelé « taueta » (parce que le papier de recherche original utilisé le tau de lettres grecques et eta). La valeur de taueta est la valeur de la phéromone sur le bord élevé à la puissance alpha, temps un rapport à la valeur de distance, élevée à la puissance de la bêta. Rappelons qu'alpha et bêta sont des constantes globales qui doivent être spécifiés. Ici, je supposerai qu'alpha est 3 et beta 2. Les valeurs taueta de la ville 1 et 3 ne sont pas calculés parce qu'ils sont déjà dans la piste actuelle. Notez que les valeurs plus élevées de la phéromone augmentent taueta, mais taueta diminuent de plus grandes distances.
.png)
La figure 3 mise à jour informations Ant
Après que toutes les valeurs de taueta ont été calculées, la prochaine étape est de convertir ces valeurs de probabilités et les placer dans un tableau, j'ai marqué probs. L'algorithme résume les valeurs taueta, obtention de 82.26 dans cet exemple et puis divise chaque valeur de taueta de la somme. À ce stade, la ville 0 a une probabilité de 0,09 d'être sélectionné et ainsi de suite. Ensuite, l'algorithme doit choisir la prochaine ville basée sur les probabilités calculées. Tel que déjà mentionné, l'algorithme ACO que je présente dans cet article utilise une technique soignée appelée sélection de roue de la roulette. J'ai construit un tableau augmenté appelé cumulation, qui détient les probabilités cumulées. La taille du tableau augmentée est un plus grand que le tableau de probs et cellulaire [0] est ensemencé de 0,0. Chaque cellule de cumul est la somme cumulée des probabilités. Après que le tableau de cumul a été construit, un nombre aléatoire p entre 0,0 et 1,0 est généré. Supposons que p = 0,538 comme indiqué. Cette valeur de p se situe entre les valeurs [2] et [3] dans le tableau de cumulation, ce qui signifie que [2], ou la ville 2, est choisi comme la prochaine ville.
La méthode de niveau supérieur pour la mise à jour est nommée 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;
}
}
Notez que chaque fourmi est attribué à une ville nouvelle, au hasard de départ plutôt que de commencer à préservant l'ancienne ville. La plupart du travail est effectuée par la méthode d'assistance BuildTrail, comme le montre Figure 4.
Figure 4 la méthode 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 maintient un tableau de Boolean a visité, de sorte que le sentier créé ne contient pas les villes en double. La valeur au sentier [0] est ensemencée avec une ville de départ, puis chaque ville est ajouté à son tour par la méthode d'assistance NextCity, en Figure 5.
Figure 5 la méthode 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");
}
La méthode NextCity implémente l'algorithme de sélection de roue roulette.Notez que l'algorithme va échouer si la dernière valeur dans le tableau de cumul est supérieure à 1,00 (peut-être en raison d'erreurs d'arrondi), et donc vous pouvez ajouter une logique pour définir toujours cumul [cumulation.Longueur-1] à 1,00. NextCity nécessite un tableau de probabilités produite par la méthode d'assistance MoveProbs, en Figure 6.
Figure 6 de la méthode 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;
}
Les valeurs de taueta peuvent être très petites (si la valeur de la distance est très importante) ou très grand (si la valeur de la phéromone est grande), qui peut produire des difficultés pour l'algorithme. Pour faire face à cela, je vérifier les valeurs de taueta et imposer l'arbitraire min et max valeurs.
Mettre à jour les phéromones
Mise à jour des informations de la phéromone est beaucoup plus facile que de mettre à jour les informations de piste de fourmis. Les principales lignes de code dans la méthode UpdatePhermones sont :
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;
Chaque valeur de phéromone est diminuée, simulant l'évaporation et augmenté, simulant le dépôt de phéromones par des fourmis sur la piste. L'effet de la baisse est produite en multipliant la valeur actuelle de la phéromone par un facteur inférieur à 1.0 qui dépend de rho de paramètre global. La plus grande rho est, plue la diminution de valeur de phéromone. L'effet de l'augmentation est produite en ajoutant une proportion de longueur de piste total de la fourmi actuel, où la proportion est déterminée par le paramètre global Q. Plus grandes valeurs de q augmentent la quantité de phéromone ajouté. Appels de méthode UpdatePheromones helper EdgeInTrail, qui détermine si un segment entre deux villes est sur la piste actuelle de la fourmi. Vous pouvez vérifier sur le téléchargement de code de cet article pour plus de détails (archive.msdn.microsoft.com/mag201202TestRun).
Récapitulation
Permettez-moi de souligner qu'il y a beaucoup de variations de l'ACO ; la version que j'ai présenté ici est qu'une des nombreuses approches possibles. Défenseurs de l'ACO ont appliqué l'algorithme à un large éventail de problèmes d'optimisation combinatoire. Autre opti combinatoiremization algorithmes basés sur le comportement des systèmes naturels sont simulés recuit (SA), dont j'ai recouvert le mois dernier (msdn.microsoft.com/magazine/hh708758) et simulé Bee Colony (SBC), qui je couverts dans mon article d'avril 2011 (msdn.microsoft.com/magazine/gg983491). Chaque méthode a des forces et des faiblesses. À mon avis, l'ACO est mieux pour des problèmes qui ressemblent au problème du voyageur, tandis que SA et SBC sont mieux pour des problèmes d'optimisation combinatoire plus généraux, comme la planification.
ACO, en commun avec d'autres meta-heuristique basée sur les systèmes naturels, est très sensible à votre choix de paramètres globaux libres — alpha, bêta et ainsi de suite. Bien qu'il y a eu un peu de recherche sur les paramètres de l'ACO, le consensus général est que vous devez expérimenter un peu avec les paramètres libres pour obtenir la meilleure combinaison de qualité de performance et de la solution.
Dr. James McCaffrey travaille pour Volt Information Sciences Inc., où il gère la formation technique d'ingénieurs logiciels travaillant à la Microsoft Redmond, Wash., campus de. Il a travaillé sur plusieurs produits Microsoft, y compris Internet Explorer et MSN Search. McCaffrey est l'auteur de ".NET Test Automation Recipes » (Apress, 2006) et peut être atteint à jmccaffrey@volt.com ou jammc@microsoft.com.
Grâce à des experts techniques Microsoft suivants pour l'examen de cet article : Dan Liebling et Anne Loomis Thompson