Cet article a fait l'objet d'une traduction automatique.
Série de tests
Algorithmes Tabu et plus grande clique
Téléchargez l'exemple de Code
.jpg "James McCaffrey")
Dans la colonne de ce mois-ci, je vais présente une solution avancée au problème graphique clique maximale. La solution utilise ce qu'on appelle un algorithme tabu, et j'aborderai comment concevoir et tester ces algorithmes. L'idée du problème clique maximale est de trouver le plus grand groupe de nœuds dans un graphique qui sont tous reliés les uns aux autres. Regardez le graphique simple à la Figure 1. Le graphe possède neuf nœuds et 13 arêtes. Le graphe est non pondéré (il n'y a aucune priorité associée à des bords) et non dirigée (toutes les arêtes sont bidirectionnelles). Nœuds de 2, 4 et 5 forment une clique de taille trois. La clique maximale est que le nœud défini 0, 1, 3 et 4, qui forme une clique de taille quatre.
.png)
Figure 1 graphique pour un algorithme de Tabu Maximum Clique
Le problème de la clique maximale est intéressant pour plusieurs raisons. Bien qu'il n'est pas apparent dans le graphique simple dans Figure 1, le problème de la clique maximale est l'un des plus difficiles en informatique. Elle se pose de nombreux problèmes pratiques importantes, comme l'analyse de communication réseau social, où les nœuds représentent les gens et bords représentent des messages ou des relations. Et le problème utilise des techniques telles que des algorithmes cupides et algorithmes tabu, qui sont importantes avancées techniques de programmation. Avoir une solution au problème de la clique maximale dans votre bibliothèque personnelle peut être un outil pratique utile et comprendre l'algorithme utilisé peut ajouter de nouvelles techniques pour l'ensemble de vos compétences.
Il s'agit de la troisième colonne dans une série qu'utilise le problème de la clique maximale pour illustrer les avancées de codage et de tests techniques, mais cette colonne peut être lu sans référence directe aux deux précédentes. Dans ma colonne octobre, « Graphe Structures et Maximum Clique » (msdn.microsoft.com/magazine/hh456397), j'ai décrit comment coder une structure de données efficace pour maintenir une structure de données de graphe en mémoire. Dans ma colonne de novembre, « Algorithmes cupides et Clique Maximum » (msdn.microsoft.com/magazine/hh547104), j'ai décrit comment un algorithme relativement simple peut être utilisé pour trouver une solution au problème difficile clique maximale.
En termes informels, un algorithme glouton est un algorithme qui démarre avec une solution simple et incomplète d'un problème difficile et de manière itérative cherche ensuite pour la meilleure façon d'améliorer la solution. Le processus se répète jusqu'à ce que certaines conditions de freinage sont atteint. Commentjamais, greedy algorithms ont généralement une faiblesse : ils va générer à plusieurs reprises au cours la même solution. Tabu algorithmes sont conçus pour faire face à cette faiblesse. Le tabou de la mot, parfois orthographié tabou, moyens interdits. En termes simples, les algorithmes de tabu maintiennent une liste de données interdites. La partie du traitement de l'algorithme n'est pas autorisée à utiliser tabu données jusqu'à ce que certains interdisant le temps ont passé. Des formes simples d'utilisation d'algorithmes tabu fixe interdisant à temps. Algorithmes avancés tabu adaptent dynamiquement le temps d'interdire tandis que l'algorithme s'exécute.
La figure 2 illustre les idées importantes d'un algorithme de tabu appliqués au problème clique maximale et vous montre où je suis dirigé dans cette colonne.
.png)
La figure 2 Tabu Maximum Clique démo Run
J'ai une application console qui commence par chargement en mémoire le graphique correspondant à celui indiqué dans Figure 1. Le fichier utilise un format de fichier graphique standard appelé DIMACS. Conception et une structure de données de graphe efficace de codage sont un problème important en soi. J'ai expliqué le code de structure de données graphique dans ma colonne d'octobre.
L'algorithme commence en sélectionnant un seul nœud au hasard et de l'initialisation d'une clique avec ce nœud. L'algorithme essaie ensuite itérativement à trouver et à ajouter le nœud meilleur visant à accroître la taille de la clique. J'expliquerai quel meilleur noeud signifie plus tard. Si l'algorithme ne peut pas trouver un nœud à ajouter, il tente de trouver le meilleur nœud à drop de la clique. Dans les coulisses, l'algorithme se souvient de la dernière fois chaque nœud a été déplacé dans la clique de solution actuelle ou déplacé de la clique. L'algorithme utilise cette information pour interdire l'ajout ou abandon récemment utilisé des nœuds pour un certain laps de temps. Il s'agit de la partie tabou de l'algorithme.
L'algorithme lui-même redémarre parfois lorsque aucun progrès n'ont été réalisés en concluant une meilleure clique (plus grande). L'algorithme stocke silencieusement les solutions (cliques), qu'il a vu précédemment. L'algorithme utilise ces informations de histoire de solution d'adapter dynamiquement le temps de l'interdire. Si l'algorithme maintient rencontrant les mêmes solutions, elle augmente le temps d'interdire à décourager les nœuds récemment utilisés ne soit utilisé. Si l'algorithme ne voit pas les mêmes solutions, elle diminue le temps de l'interdire, donc il n'y a un plus grand bassin de nœuds qui permet de choisir. Il s'agit de la partie adaptative de l'algorithme de tabou.
Dans la plupart des situations où un algorithme glouton est utilisé, la solution optimale n'est pas connue, une ou plusieurs conditions de freinage doivent être spécifié. Quand l'algorithme frappe une condition de s'arrêter, la meilleure solution trouvée est affichée.
Dans les sections qui suivent, je vais vous marcher à travers le code qui a produit la capture d'écran Figure 2. Le code source complet est disponible à code.msdn.microsoft.com/mag201112TestRun. Cette rubrique suppose que vous disposez des compétences en programmes niveau intermédiaire avec un langage C-famille ou le Visual Basic.Langue NET. J'utilise c#, mais j'ai écrit le code pour que vous serez capable de refactoriser dans une autre langue comme F # ou Python sans trop de difficulté si vous le souhaitez.
Structure globale de programme
La structure globale du programme indiqué dans Figure 2 est présenté en Figure 3. J'ai décidé de placer tout le code dans une application console unique à l'aide des méthodes statiques pour plus de simplicité, mais vous pouvez modulariser les parties du code dans les bibliothèques de classes et d'utiliser une approche orientée-objet. Le programme est moins compliqué que vous pouvez soupçonner en regardant Figure 3 car la plupart des méthodes sont des méthodes d'assistance court.
La figure 3 Structure du programme global
using System;
using System.Collections.Generic; // List<int>
using System.Text; // StringBuilder
using System.IO; // FileStream
using System.Collections; // Hashtable
namespace TabuMaxClique
{
class TabuMaxCliqueProgram
{
static Random random = null;
static void Main(string[] args) { ...
}
static List<int> FindMaxClique(MyGraph graph, int maxTime,
int targetCliqueSize) { ... }
static List<int> MakePossibleAdd(MyGraph graph,
List<int> clique) { ...
}
static bool FormsALargerClique(MyGraph graph,
List<int> clique, int node) { ...
}
static int GetNodeToAdd(MyGraph graph,
List<int> allowedAdd, List<int> possibleAdd) { ...
}
static int GetNodeToDrop(MyGraph graph, List<int> clique,
List<int> oneMissing) { ...
}
static List<int> MakeOneMissing(MyGraph graph,
List<int> clique) { ...
}
static List<int> SelectAllowedNodes(List<int> listOfNodes,
int time, int prohibitPeriod, int[] lastMoved) { ...
}
static int UpdateProhibitPeriod(MyGraph graph, List<int> clique,
int bestSize, Hashtable history, int time, int prohibitPeriod,
ref int timeProhibitChanged) { ...
}
static string ListAsString(List<int> list) { ...
}
private class CliqueInfo
{
// ...
}
}
public class MyGraph
{
// ...
private class BitMatrix
{
// ...
}
}
} // ns
Le programme comporte deux classes de haut niveau, et chacune de ces classes est une sous-classe d'assistance. Classe TabuMaxCliqueProgram contient la méthode Main et toute logique de l'algorithme, avec sous-classe CliqueInfo, qui est utilisé pour conserver un historique des solutions de la clique du déjà vu. Classe MyGraph encapsule une représentation graphique efficace et contient la sous-classe BitMatrix, qui est utilisé pour stocker des informations d'adjacence nœud sous une forme condensée. Un objet d'aléatoire de portée de classe nommé aléatoire est utilisée pour initialiser la clique sur un nœud aléatoire et de rompre les liens lorsqu'il y a plusieurs nœuds meilleurs pour ajouter ou supprimer.
Avec certaines déclarations WriteLine et le code try-catch supprimé, la méthode Main est :
Console.WriteLine("\nBegin tabu algorithm maximum clique demo\n");
string graphFile = "..
\\..
\\DimacsGraph.clq";
MyGraph graph = new MyGraph(graphFile, "DIMACS");
int maxTime = 50;
int targetCliqueSize = graph.NumberNodes;
List<int> maxClique = FindMaxClique(graph, maxTime, targetCliqueSize);
Console.WriteLine("\nSize of best clique found = " + maxClique.Count);
Console.WriteLine(ListAsString(maxClique));
Le graphique est représenté par un objet MyGraph définies par programme. Le graphique est chargé à partir d'un fichier texte externe qui utilise le format de fichier DIMACS. La principale méthode de MyGraph est AreAdjacent, qui renvoie true si les deux nœuds sont connectés. J'ai défini maxTime 50 itérations d'établir une condition absolue de s'arrêter pour l'algorithme glouton. C'est petit artificiellement. Dans un problème réel maximale clique, le temps maximum est généralement de l'ordre de 1 000 à 100 000. Je définir la taille de targetClique pour établir une deuxième condition d'arrêt ; Si on trouve une clique qui a le même nombre de nœuds qu'il y a dans le graphique, la clique maximale doit avoir été reconnue. La plupart des travaux est effectuée par la méthode FindMaxClique, qui utilise un algorithme de tabu cupides, adaptation à la recherche de la plus grande clique possible. La méthode d'assistance ListAsString simplement crée une représentation de chaîne d'une liste <int> objet.
La méthode FindMaxClique
La méthode FindMaxClique appelle plusieurs méthodes d'assistance, que je décrirai peu de temps. En pseudocode de haut niveau, l'algorithme de FindMaxClique est donné Figure 4. Le pseudo-code laisse plusieurs détails importants pour plus de clarté, mais présente les principaux points de l'algorithme.
La figure 4 algorithme adaptatif de Tabu Maximum Clique
initialize clique with a single node
get list of candidate nodes to add
loop until stop condition met
if there are nodes which can be added
get list of allowed nodes
if there are allowed nodes to add
find best node to add and add to clique
mark added node as recently used
record current clique
else
get list of allowed nodes to drop
if there are allowed nodes which can be dropped
find best node to drop and drop from clique
mark dropped node as recently used
record current clique
else
select a random node to drop and drop from clique
mark dropped node as recently used
record current clique
if lack of progress
restart algorithm
update list of candidate nodes
update prohibit time
end loop
return largest clique found
The FindMaxClique method definition begins:
static List<int> FindMaxClique(MyGraph graph, int maxTime,
int targetCliqueSize)
{
List<int> clique = new List<int>();
random = new Random(1);
int time = 0;
int timeBestClique = 0;
int timeRestart = 0;
int nodeToAdd = -1;
int nodeToDrop = -1;
...
L'objet de la clique du local est la clique de solution actuelle. L'objet aléatoire est instanciée avec une valeur de semences arbitraire de 1. La variable de temps est le compteur de boucle de traitement principale de l'algorithme. Les variables timeBestClique et timeRestart sont utilisées pour déterminer s'il y a eu un manque de progrès pour l'algorithme peut redémarrer lui-même. Suivante :
int prohibitPeriod = 1;
int timeProhibitChanged = 0;
int[] lastMoved = new int[graph.NumberNodes];
for (int i = 0; i < lastMoved.Length; ++i) {
lastMoved[i] = int.MinValue;
}
Hashtable history = new Hashtable();
...
La période d'interdire est initialisée à 1. Cela signifie que — au départ, au moins — après un nœud a été utilisé par l'algorithme, il ne peut être utilisé pour une itération de temps. Si j'avais utilisé la valeur 0, l'effet aurait été à n'ont pas interdire à tout les temps. La plupart des algorithmes de tabu utilisent une valeur fixe pour le temps d'interdire, mais le problème avec cette approche est que la recherche a montré que la meilleure valeur pour un temps fixe interdire varie d'un problème à un problème. L'approche adaptative, je présente des mises à jour le temps d'interdire pendant que l'algorithme s'exécute, basée sur l'histoire des solutions précédentes. J'appelle cette tabu adaptative de technique, mais certains documents de recherche appellent la technique réactif ou dynamique.
Le tableau lastMoved est utilisé pour déterminer si un nœud est autorisé ou interdit à tout moment. L'index du tableau représente un noeud, et la valeur correspondante de tableau est le temps que le nœud a été déplacé de dernière (ajouté ou abandonnée). En utilisant le tableau de lastMoved, j'éliminer le besoin de créer explicitement une liste de nœuds autorisés (ou, de manière équivalente, interdit de nœuds). J'initialise toutes les cellules de lastMoved int.MinValue donc je peux déterminer plus tard si un nœud n'a jamais été utilisé.
L'objet Hashtable histoire possède une collection de cliques de solution de déjà vu. Chaque élément dans la table de hachage est un objet CliqueInfo, que je décrirai en détail plus tard. Je pourrais avez utilisé un objet générique de dictionnaire au lieu de l'objet Hashtable non générique. FindMaxClique continue :
int randomNode = random.Next(0, graph.NumberNodes);
clique.Add(randomNode);
List<int> bestClique = new List<int>();
bestClique.AddRange(clique);
int bestSize = bestClique.Count;
timeBestClique = time;
...
J'Initialise la clique de solution actuelle d'un nœud au hasard dans le graphique. J'instancie une liste de bestClique pour suivre la meilleure solution clique (plus grande), trouvée par l'algorithme. Vient ensuite :
List<int> possibleAdd = MakePossibleAdd(graph, clique);
List<int> oneMissing = MakeOneMissing(graph, clique);
...
La méthode de MakePossibleAdd construit une liste de tous les nœuds qui peuvent être ajoutés à la clique actuelle pour augmenter la taille de la clique par 1. En d'autres termes, la méthode crée une liste de nœuds qui ne sont pas dans la clique mais sont reliés à chaque nœud dans la clique. Cette liste de possibleAdd pourrait avoir un comte de 0 ou puisse contenir des nœuds interdites. MakePossibleAdd appelle la méthode d'assistance FormsALargerClique.
La méthode de MakeOneMissing construit une liste de tous les nœuds connectés à tous sauf exactement un des nœuds de la clique actuelle. Il n'est pas évident, mais il s'avère que le maintien d'une telle liste crée une méthode intelligente pour déterminer quel nœud dans le courant clique est le meilleur nœud à baisser, comme j'expliquerai plus tard. Début de la boucle principale de traitement :
while (time < maxTime && bestSize < targetCliqueSize)
{
++time;
bool cliqueChanged = false;
...
La boucle principale transformation prendra fin lorsque le nombre maximal d'itérations est atteinte ou si une meilleure solution avec la taille de la clique du cible est trouvée. J'utilise la variable cliqueChanged pour contrôler la ramification logique entre ajoutant et en abandonnant les nœuds, comme vous le verrez. La logique d'ajouter un nœud autorisé est montrée dans Figure 5.
Figure 5 la logique d'ajouter un nœud autorisé
if (possibleAdd.Count > 0) {
List<int> allowedAdd = SelectAllowedNodes(possibleAdd, time,
prohibitPeriod, lastMoved);
if (allowedAdd.Count > 0) {
nodeToAdd = GetNodeToAdd(graph, allowedAdd, possibleAdd);
clique.Add(nodeToAdd);
lastMoved[nodeToAdd] = time;
clique.Sort(); cliqueChanged = true;
if (clique.Count > bestSize) {
bestSize = clique.Count;
bestClique.Clear();
bestClique.AddRange(clique);
timeBestClique = time;
}
}
}
L'algorithme vérifie s'il y a les nœuds qui augmenteront la taille de la clique actuelle. Si donc, la méthode SelectAllowedNodes crée une liste de nœuds qui sont autorisés — c'est-à-dire, ne Tabu pas — de la liste des nœuds qui peuvent être ajoutés.
La ligne clée SelectAllowedNodes est :
if (time > lastMoved[currNode] + prohibitPeriod)
result.Add(currNode); // Allowed
Le currNode est l'un des nœuds dans la liste de possibleAdd. La logique vérifie si assez de temps a écoulé depuis que le nœud dernière utilisation afin que le nœud est passée la période de l'interdire. Dans l'affirmative, le nœud est ajouté à la liste de nœuds d'allowedAdd.
Maintenant, si il n'y a que des nœuds qui sont autorisés et augmenteront la taille de la clique, méthode GetNodeToAdd détermine le meilleur noeud pour ajouter à la clique. Le nœud meilleur est le nœud dans la liste d'allowedAdd qui est le plus connecté à nœuds dans la liste de possibleAdd. L'idée est que vous souhaitez ajouter un nœud qui vous donnera les chances la plupart de trouver un nœud d'ajouter dans la prochaine itération de l'algorithme. Il pourrait y avoir plusieurs noeuds dans la liste d'allowedAdd qui sont liés comme le plus branché avec les nœuds dans possibleAdd. Dans l'affirmative, l'un des nœuds liées est sélectionné au hasard. Après avoir ajouté le nœud meilleur, la solution actuelle de la clique est triée pour des raisons que j'expliquerai plus tard. Le code d'abandonner un nœud est :
if (cliqueChanged == false) {
if (clique.Count > 0) {
List<int> allowedInClique = SelectAllowedNodes(clique, time,
prohibitPeriod, lastMoved);
if (allowedInClique.Count > 0) {
nodeToDrop = GetNodeToDrop(graph, clique, oneMissing);
clique.Remove(nodeToDrop);
lastMoved[nodeToDrop] = time;
clique.Sort(); cliqueChanged = true;
}
}
}
...
Si l'algorithme ne peut pas ajouter un noeud, il tente de supprimer un nœud autorisé dans l'espoir qu'un recul donnera une solution qui permettra à un nouveau nœud à ajouter dans la prochaine itération. La liste des nœuds dans la clique actuelle est filtrée par la méthode SelectAllowedNodes pour obtenir des nœuds qui ne sont pas tabou. Le GetNodeToDrop sélectionne le meilleur de ces nœuds d'abandonner à l'aide de la liste des nœuds oneMissing.
L'idée est d'abandonner le nœud autorisé dans la clique actuelle, qui donnera lieu à la plus grande augmentation dans la liste de nœuds de possibleAdd. Une façon de le faire est de tester chaque nœud dans la liste autorisée par supprimer effectivement de la clique actuelle et ensuite calculer la taille de la liste de possibleAdd qui en résulte. Mais il y a une approche beaucoup plus efficace qui utilise une liste de nœuds connectés à tous sauf exactement un des nœuds de la clique actuelle. À l'aide de la liste d'oneMissing des nœuds, la liste peut être utilisée comme suit. Parcourir chaque nœud dans les nœuds de la clique du permis et de compter le nombre de nœuds dans la liste d'oneMissing est notconnected au nœud clique. Le nœud dans la liste de la clique du permis qui est moins connecté aux nœuds dans l'oneMissing liste est le meilleur noeud d'abandonner. Après avoir abandonné ce nœud connectées au moins, tous les nœuds dans la liste d'oneMissing qui n'étaient pas connectés au nœud a chuté seront maintenant entièrement reliés aux nœuds restants dans la clique et deviennent donc possibleAdd de nouveaux nœuds.
À ce stade dans la logique, on pourrait pas possible d'ajouter un nœud autorisé ou de supprimer un nœud autorisé. Pour décoller sous lui-même, l'algorithme supprime un nœud aléatoire de la clique actuelle :
if (cliqueChanged == false) {
if (clique.Count > 0) {
nodeToDrop = clique[random.Next(0, clique.Count)];
clique.Remove(nodeToDrop);
lastMoved[nodeToDrop] = time;
clique.Sort();
cliqueChanged = true;
}
}
...
Ensuite, les contrôles de l'algorithme pour voir s'il y a eu un manque de progrès et, le cas échéant, redémarre elle-même :
int restart = 100 * bestSize;
if (time - timeBestClique > restart && time - timeRestart > restart) {
timeRestart = time;
prohibitPeriod = 1;
timeProhibitChanged = time;
history.Clear();
...
La variable de redémarrage est le nombre d'itérations pour permettre où il n'y a aucune amélioration ou depuis le dernier redémarrage. J'utilise ici une valeur de 100 fois la taille de la meilleure solution actuelle. La valeur à utiliser pour l'intervalle de redémarrage n'est pas bien comprise et vous pouvez essayer les solutions de rechange. (J'ai utilisé une valeur nominale de 2 à produire des redémarrages plus pour la capture d'écran Figure 2). La valeur qu'utiliser travaille bien pour moi dans la pratique, cependant. S'il y a un redémarrage, l'algorithme redéfinit le temps d'interdire et efface la table de hachage histoire holding cliques de solution qui ont été vus. Notez que l'algorithme n'a pas encore mis à jour la table de hachage de l'histoire. Le code de redémarrage n'est pas, cependant, réinitialiser le tableau lastVisited, qui stocke des informations sur quand les nœuds ont été dernière ajoutés ou est passées de la clique de solution. Vient ensuite :
int seedNode = -1;
List<int> temp = new List<int>();
for (int i = 0; i < lastMoved.Length; ++i) {
if (lastMoved[i] == int.MinValue) temp.Add(i);
}
if (temp.Count > 0)
seedNode = temp[random.Next(0, temp.Count)];
else
seedNode = random.Next(0, graph.NumberNodes);
...
L'algorithme tente de semer à nouveau la clique de solution avec un nœud qui n'a jamais été utilisé avant. S'il y a plusieurs nœuds inutilisés, un est sélectionné au hasard. S'il n'y a aucun nœud inutilisés, un nœud aléatoire est sélectionné. Au lieu d'utiliser un nœud aléatoire, alternative inexplorée est de sélectionner le nœud qui était moins récemment déménagé. Le code de redémarrage se termine par ce qui suit :
...
clique.Clear();
clique.Add(seedNode);
}
La boucle principale de traitement et la récapitulation de FindMaxClique comme suit :
...
possibleAdd = MakePossibleAdd(graph, clique);
oneMissing = MakeOneMissing(graph, clique);
prohibitPeriod = UpdateProhibitPeriod(graph, clique, bestSize,
history, time, prohibitPeriod, ref timeProhibitChanged);
} // Main processing loop
return bestClique;
}
Les listes possibleAdd et oneMissing sont régénérées. Une alternative est de maintenir les structures de données auxiliaires et mise à jour de ces deux listes au lieu de recréer à partir de zéro. La méthode UpdateProhibitPeriod est l'élément clé de la partie adaptative de l'algorithme de tabu et je décrirai peu de temps.
Se souvenant des Solutions précédentes
Méthode UpdateProhibitPeriod utilise une table de hachage de solutions déjà vues d'augmenter ou de réduire le temps d'interdire dynamiquement. Rappelons qu'une solution est une clique qui est une liste <int> des nœuds qui sont tous reliés les uns aux autres. Mais j'ai aussi besoin stocker le temps où une solution a été aperçu pour la dernière fois. Par conséquent, j'encapsuler une solution clique et la dernière fois il a été vu dans une classe de CliqueInfo énumérées dans le Figure 6.
Figure 6, la classe de CliqueInfo
private class CliqueInfo
{
private List<int> clique;
private int lastSeen;
public CliqueInfo(List<int> clique, int lastSeen)
{
this.clique = new List<int>();
this.clique.AddRange(clique);
this.lastSeen = lastSeen;
}
public int LastSeen
{
get { return this.lastSeen; }
set { this.lastSeen = value; }
}
public override int GetHashCode()
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < clique.Count; ++i) {
sb.Append(clique[i]);
sb.Append(" ");
}
string s = sb.ToString();
return s.GetHashCode();
}
public override string ToString()
{
string s = "";
for (int i = 0; i < clique.Count; ++i)
s += clique[i] + " ";
return s;
}
}
Parce qu'un élément de CliqueInfo va être ajouté à l'objet Hashtable de solution histoire, j'ai besoin d'une fonction de hachage GetHashCode personnalisée. Écrire des fonctions de hachage personnalisé est étonnamment délicat, et une discussion approfondie sur toutes les questions en jeu exigerait toute une colonne. Dans cette situation, j'utilise le plus simple — mais pas le plus efficace — approche. Je créer une représentation de chaîne des nœuds dans le domaine de la clique, séparé par des espaces et ensuite utiliser la String.GetHashCode intégré. Par exemple, si une clique contenait des nœuds {3 5 8}, générer des "3 5 8" (avec un espace arrière) et ensuite générer un code de hachage de cette chaîne. Rappelons que cliques sont toujours maintenues dans un ordre trié, donc il ne serait pas possible d'avoir un seul clique {3 5 8} et clique une autre {8 3 5}. Je place des espaces entre les nœuds de sorte que clique {3 5 8} se distingue de la clique du {3 58}.
Mise à jour de l'interdire la période
UpdateProhibitPeriod de la méthode adaptative augmente ou diminue le temps d'interdire basé sur les solutions de la clique du déjà vu. La méthode commence :
static int UpdateProhibitPeriod(MyGraph graph, List<int> clique,
int bestSize, Hashtable history, int time, int prohibitPeriod,
ref int timeProhibitChanged)
{
int result = prohibitPeriod;
CliqueInfo cliqueInfo = new CliqueInfo(clique, time);
.
.
.
La méthode retournera un temps d'interdire qui pourraient éventuellement être identique à l'heure actuelle d'interdire. Un objet CliqueInfo holding de la clique du courant et l'heure actuel sont instanciés, comme illustré ici :
if (history.Contains(cliqueInfo.GetHashCode())) {
CliqueInfo ci = (CliqueInfo)history[cliqueInfo.GetHashCode
int intervalSinceLastVisit = time - ci.LastSeen;
ci.LastSeen = time;
if (intervalSinceLastVisit < 2 * graph.NumberNodes - 1) {
timeProhibitChanged = time;
if (prohibitPeriod + 1 < 2 * bestSize) return prohibitPeriod + 1;
else return 2 * bestSize;
}
}
else history.Add(cliqueInfo.GetHashCode(), cliqueInfo);
...
Le code vérifie si la solution actuelle de la clique, sous la forme d'un objet CliqueInfo, a été vu avant — est la clique dans la table de hachage de l'histoire ? Si la clique actuelle a vu avant, l'algorithme calcule combien de temps depuis la clique a été vu. Si cet intervalle est assez court, le temps d'interdire est incrémenté (sous réserve d'une limite supérieure). L'idée est que parce qu'il n'a pas été très longtemps puisque la clique actuelle a été vu, l'algorithme génère des solutions en double. Si on augmente le temps de l'interdire, il n'y aura plus de nœuds tabu et donc moins accueilli nœuds, réduire les chances de générer des solutions en double clique. Si la solution clique actuelle n'a pas été vu avant, elle est ajoutée à la table de hachage de l'histoire.
L'intervalle de « assez court » est deux fois le nombre de nœuds dans le graphique, moins un. Cela est utilisé pour déterminer quand l'incrémenter le temps de l'interdire. La meilleure valeur pour utiliser ici est une autre question ouverte dans la recherche de la clique maximale. La « limite supérieure » pour le temps d'interdire est deux fois la taille de la solution connue actuelle. La meilleure valeur limite supérieure est, comme vous pouvez le deviner probablement maintenant, une autre question de recherche ouvert.
À ce stade, soit la clique actuelle n'a pas été vu avant, ou la clique a été vu avant mais l'intervalle requis pour incrémenter le temps d'interdire n'était pas assez petite. Si l'algorithme maintenant vérifie si la période d'interdire peut être décrémentée, qui va diminuer le nombre de nœuds de tabu et augmenter le nombre de nœuds autorisés, qui donne à son tour, l'algorithme de nœuds plus d'ajouter ou de supprimer :
...
if (time - timeProhibitChanged > 10 * bestSize) {
timeProhibitChanged = time;
if (prohibitPeriod - 1 > 1)
return prohibitPeriod - 1;
else
return 1;
}
else {
return result; // no change
}
} // UpdateProhibitTime
Plutôt que d'explicitement vérifier si elle a été un moment « relativement long » depuis la clique actuelle a été vu, l'algorithme a indirectement vérifie combien de temps depuis la clique actuelle a été vu en examinant le temps lorsque la période d'interdire a été modifiée. Encore une fois, la meilleure valeur pour « relativement long » n'est pas bien comprise. J'utilise une valeur de 10 fois la taille de la meilleure solution actuelle. Notez que le temps d'interdire ne peut abandonner inférieur à 1.
De plus amples recherches
Résultats de la recherche sur le problème de la clique maximale suggèrent qu'une approche gourmande avec une fonctionnalité de tabu adaptative donne les meilleurs résultats globaux lorsque les performances et la qualité de la solution sont pris en compte. DIMACS est un organisme de recherche qui créé un ensemble de problèmes de référence pour le clique du graphe difficile. J'ai couru le code présenté ici contre un problème particulièrement difficile de DIMACS (C2000.9) et le code rapidement (en moins de deux secondes) découvert une clique avec la taille 76 qui relève de 1,5 % de la taille de la solution la plus connue de 77.
À plusieurs reprises dans cette colonne, je l'ai mentionné les résultats des recherches sur le problème de la clique maximale. Si vous êtes intéressé à cette recherche, je recommande que vous chercher sur le Web des documents académiques rédigés par ce qui suit: r. Battiti et coll., w. Pullan et al. et k. Katayama et al. Plusieurs articles par ces trois auteurs et leurs collègues ont été mes premières références.
Une zone inexplorée prometteur pour l'algorithme clique maximale présentée ici est d'incorporer une forme quelconque de ce qu'on appelle la recherche du plateau. Rappelons que l'algorithme clique maximale tente d'abord ajouter un noeud de tabu-non à la solution actuelle de la clique. Ensuite, si ce n'est pas possible, l'algorithme supprime un nœud de la solution actuelle de la clique. L'idée d'une recherche de plateau est de trouver un nœud dans la solution actuelle de clique qui peut être enfichée avec un nœud pas dans la clique. Bien que cela n'est pas augmenter la taille de la clique actuelle, il n'est pas diminuer la taille de la clique, soit.
Dr.James McCaffrey travaille pour Volt Information Sciences Inc., où il gère la formation technique pour les ingénieurs en logiciel travaillant à la Microsoft Redmond, Wash., campus. Il a travaillé sur plusieurs produits Microsoft, y compris Internet Explorer et MSN Search. Dr. McCaffrey est l'auteur de ".NET Test Automation Recipes"(Apress, 2006) et peut être contacté à jammc@microsoft.com.
Grâce à des experts techniques suivants pour l'examen de cet article : Paul Koch, Dan Liebling, Ann Loomis Thompson et Shane Williams