Cet article a fait l'objet d'une traduction automatique.

Série de tests

Recuit simulé et test

James McCaffrey

Dans la colonne de ce mois-ci, je présente de code c# qui implémente un algorithme de recuit simulé (SA) pour résoudre un problème de programmation. Un algorithme de SA est une technique d'intelligence artificielle basée sur le comportement de refroidissement de métal. Il peut être utilisé pour trouver des solutions aux problèmes d'optimisation combinatoire difficile, voire impossible.

La meilleure façon de voir où je suis dirigé est de jeter un regard sur Figure 1 et Figure 2. Dans la table Figure 1 décrit un problème de programmation : les travailleurs de cinq et six tâches. Chaque entrée de la table représente combien de temps il faut pour un travailleur accomplir une tâche. Par exemple, w2 travailleur doit 5,5 heures pour compléter la tâche t3. Une entrée vide dans une ligne indique que le travailleur correspondant ne peuvent pas effectuer une tâche. Le problème consiste à attribuer à chacune des six tâches à un des travailleurs de telle manière que le temps total de remplir toutes les tâches est minimisé. En outre, nous supposons que chaque fois qu'un travailleur bascule vers une nouvelle tâche, il y a une pénalité de réoutillage de 3,5 heures.

La figure 1 heure pour travailleur compléter la tâche

	T0	T1	T2	T3	T4	T5
W0	7.5	3.5	2.5
W1		1.5	4.5	3.5
W2			3.5	5.5	3.5
w3				6.5	1.5	4.5
W4	2.5				2.5	2.5

La figure 2 SimulatedAnnealing en Action

La figure 2 montre un programme qui utilise un algorithme de SA pour trouver une solution au problème d'ordonnancement. Le programme commence en générant une solution aléatoire. Dans la terminologie de la SA, une solution potentielle est appelée l'État du système. L'état initial est [4 0 2 0 2 3], qui signifie tâche 0 a été attribué au travailleur 4, tâche 1 a été attribué au travailleur 0, tâche 2 a été attribué au travailleur 0, tâche 3 a été attribué au travailleur 2, tâche 4 a été attribué au travailleur 2 et tâche 5 a été attribué au travailleur 3. Le temps total pour l'état initial d'aléatoire est 2,5 + 3,5 + 2,5 + 5.5 + 3,5 + 4,5 = 22 heures plus une pénalité réoutillage de 3,5 heures pour travailleur 0 et une pénalité de 3,5 heures pour travailleur 2, pour un total de 29 heures. Dans la terminologie de la SA, la quantité que vous essayez de réduire au minimum (ou moins fréquemment maximiser) est appelée l'énergie de l'État.

Le programme entre dans une boucle. Dans chaque itération de la boucle, l'algorithme de SA génère un État adjacent et évalue cet État adjacent pour voir si elle est meilleure que l'état actuel. Dans les coulisses, l'algorithme de SA utilise une variable de température qui diminue lentement, comme j'expliquerai sous peu. La boucle SA se termine lorsque la température refroidit suffisamment proche de zéro. Le programme se termine en affichant la meilleure solution trouvée.

Cet exemple est artificiellement simple car avec des six tâches où chaque tâche peut être effectuée par l'un des trois ouvriers, il y a seulement 36 combinaisons possibles, ce qui équivaut 729, donc vous pourrait simplement évaluer chacun. Mais supposons que vous avez eu un problème avec 20 tâches où chaque tâche peut être effectuée par l'un des 12 travailleurs. Il y aurait des combinaisons de 1220, ce qui équivaut à une somme exorbitante 3,833,759,992,447,475,122,176. Même si vous pourrait évaluer les solutions possibles de 1 million par seconde, vous devrez environ 121 millions d'années évaluer toutes les possibilités.

SA est une métaheuristique — c'est-à-dire un cadre conceptuel général qui peut être utilisé pour créer un algorithme spécifique pour résoudre un problème spécifique. Il sert surtout pour des problèmes d'optimisation combinatoire où il n'y a aucun algorithme de solution déterministe pratique. Tout d'abord décrit dans un document de 1983 par s. Kirkpatrick, c. Gelatt et M. Vecchi, SA est basé sur le comportement de recuit de métal de refroidissement. Lorsque certains métaux est chauffés à haute température, les atomes et les molécules rompre leurs liens. Lorsque le métal est refroidi lentement, les atomes et les molécules réformer leurs obligations de telle manière que l'énergie du système est réduit au minimum.

Cette rubrique suppose que vous disposez des compétences de programmes de niveau intermédiaire. Je mettre en œuvre le programme de SA utilisant c#, mais vous ne devraient pas avoir trop d'ennuis refactorisation mon code pour une autre langue tels que Visual Basic ou Python. Dans les sections qui suivent, je vais vous marcher à travers le programme qui a généré Figure 2. Tout le code est disponible en téléchargement de archive.msdn.microsoft.com/mag201201TestRun. Je pense que vous trouverez la capacité de comprendre et d'utiliser SA un ajout intéressant et peut-être utile à votre ensemble de compétences personnelles.

Structure du programme

J'ai mis en place le programme de démonstration de SA comme une seule application de console c#. La structure d'ensemble du programme est indiquée dans Figure 3.

La figure 3 la Structure du programme de SimulatedAnnealing

using System;
namespace SimulatedAnnealing
{
  class SimulatedAnnealingProgram
  {
    static Random random;
    static void Main(string[] args)
    {
      try
      {
        // Set up problem data.
// Create random state.
// Set up SA variables for temperature and cooling rate.
while (iteration < maxIteration && currTemp > 0.0001)
        {
          // Create adjacent state.
// Compute energy of adjacent state.
// Check if adjacent state is new best.
// If adjacent state better, accept state with varying probability.
// Decrease temperature and increase iteration counter.
}
        // Display best state found.
}
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
        Console.ReadLine();
      }
    } // Main
    static double[][] MakeProblemData(int numWorkers, int numTasks) { ...
}
    static int[] RandomState(double[][] problemData) { ...
}
    static int[] AdjacentState(int[] currState,
      double[][] problemData) { ...
}
    static double Energy(int[] state, double[][] problemData) { ...
}
    static double AcceptanceProb(double energy, double adjEnergy,
      double currTemp) { ...
}
    static void Display(double[][] matrix) { ...
}
    static void Display(int[] vector) { ...
}
    static void Interpret(int[] state, double[][] problemData) { ...
}
  } // Program
} // ns

J'ai utilisé Visual Studio pour créer un programme d'application console nommé SimulatedAnnealing. Dans la fenêtre de l'Explorateur de solutions, j'ai renommé le fichier Program.cs par défaut à SimulatedAnnealingProgram.cs, qui renomme automatiquement la classe unique dans le projet. J'ai supprimé tous les généré par modèle utilisant des déclarations sauf pour l'espace de noms du système — SA est assez simple et généralement n'est pas besoin de beaucoup bibliothèque charge. J'ai déclaré une portée de la classe Random objet nommé aléatoire. Les algorithmes de SA sont probabilistes, comme vous le verrez peu de temps.

Au cœur de la transformation d'algorithme de SA est un alors que boucle. La boucle est contrôlée par une variable de compteur de boucle nommée « itération » et par une variable qui représente la température du système. En pratique, la variable de température est presque toujours atteint près de zéro et se termine la boucle avant que le compteur de boucle atteint sa valeur maximale et se termine à la boucle.

Les algorithmes de SA doivent avoir trois méthodes de problème spécifique tel que suggéré dans Figure3. L'algorithme de SA doit avoir une méthode qui génère une état/solution (habituellement aléatoire) initiale. L'algorithme de SA doit avoir une méthode qui génère un État adjacente par rapport à un État donné. L'algorithme de SA doit avoir une méthode qui calcule le coût / l'énergie d'un état — la valeur que vous essayez de réduire au minimum ou maximum. En Figure 3 ce sont adjacentes des méthodes RandomState,­État et l'énergie, respectivement. Méthode AcceptanceProb génère une valeur utilisée pour déterminer si l'état actuel du système de transitions vers l'État adjacent, même lorsque l'État adjacent est pire que l'état actuel. Méthode MakeProblemData est une application d'assistance et crée une matrice de structure de données qui correspond avec Figure 1. Les méthodes surchargées d'affichage et la méthode Interpret sont des aides justes pour afficher des informations.

Initialisation du programme

La méthode Main commence comme sorte :

try
{
  Console.WriteLine("\nBegin Simulated Annealing demo\n");
  Console.WriteLine("Worker 0 can do Task 0 (7.5) Task 1 (3.5) Task 2 (2.5)");
  Console.WriteLine("Worker 1 can do Task 1 (1.5) Task 2 (4.5) Task 3 (3.5)");
  Console.WriteLine("Worker 2 can do Task 2 (3.5) Task 3 (5.5) Task 4 (3.5)");
  Console.WriteLine("Worker 3 can do Task 3 (6.5) Task 4 (1.5) Task 5 (4.5)");
  Console.WriteLine("Worker 4 can do Task 0 (2.5) Task 4 (2.5) Task 5 (2.5)");
 ...

J'envelopper tout le code SA dans un bloc try-catch unique de haut niveau et d'afficher le problème factice que j'ai l'intention de mettre en place. Ici, j'utilise un exemple simple artificiellement — mais qui est représentatif des types de problèmes combinatoires adaptées pour une solution par des algorithmes de SA. Vient ensuite :

random = new Random(0);
int numWorkers = 5;
int numTasks = 6;
double[][] problemData = MakeProblemData(numWorkers, numTasks);

J'Initialise l'objet aléatoire à l'aide d'une valeur de semences arbitraire de 0. Puis j'appelle la méthode d'assistance MakeProblemData pour construire la structure de données illustrée dans Figure 1. Je vais présenter MakeProblemData et les autres méthodes d'assistance après que je termine présentant tout le code dans la méthode Main. Vient ensuite :

int[] state = RandomState(problemData);
double energy = Energy(state, problemData);
int[] bestState = state;
double bestEnergy = energy;
int[] adjState;
double adjEnergy;

J'appelle la méthode d'assistance RandomState pour générer un État aléatoire /­solution pour le problème. État est représenté comme un tableau int où l'index de tableau représente une tâche et la valeur dans le tableau à l'index le travailleur affecté à la tâche. Méthode d'assistance énergétique calcule le temps total requis par son paramètre d'État, prenant en compte la peine de 3,5 heures pour la réingénierie, chaque fois qu'un travailleur est une tâche supplémentaire. Je vais suivre le meilleur état trouvé et son énergie correspondante, afin je déclare bestEngery et bestState de variables. AdjEnergy et adjState de variables servent à retenir un État qui est adjacent à l'état actuel et l'énergie correspondante. Vient ensuite :

int iteration = 0;
int maxIteration = 1000000;
double currTemp = 10000.0;
double alpha = 0.995;

La boucle de traitement primaire SA se termine sur l'une des deux conditions : Lorsqu'un compteur dépasse une valeur maximale, ou lorsque la variable de la température décroît à une valeur proche de zéro. I nom de la boucle Canada "itération" compteur, mais je pourrais avez appelé « counter » ou « temps » ou « tique » ou quelque chose de similaire. I nom de la variable currTemp de température plutôt que de temp, donc il n'y a moins de chance quelqu'un d'examiner le code pourrait interpréter comme une variable temporaire. Alpha variable représente le taux de refroidissement, ou un facteur qui détermine comment la variable de température diminue ou cools, chaque fois que la boucle de traitement. Vient ensuite :

Console.WriteLine("\nInitial state:");
Display(state);
Console.WriteLine("Initial energy: " + energy.ToString("F2"));
Console.WriteLine("\nEntering main Simulated Annealing loop");
Console.WriteLine("Initial temperature = " + currTemp.ToString("F1") + "\n");

Avant d'entrer dans la boucle principale transformation, afficher des messages d'information sur l'état initial, l'énergie et la température. Vous pouvez afficher des informations supplémentaires telles que le taux de refroidissement. Voici la boucle :

while (iteration < maxIteration && currTemp > 0.0001)
{
  adjState = AdjacentState(state, problemData);
  adjEnergy = Energy(adjState, problemData);
  if (adjEnergy < bestEnergy)
  {
    bestState = adjState;
    bestEnergy = adjEnergy;
    Console.WriteLine("New best state found:");
    Display(bestState);
    Console.WriteLine("Energy = " + bestEnergy.ToString("F2") + "\n");
  }
...

Notez que le contrôle de la boucle se termine lorsque la variable de la température tombe en dessous de 0,0001 plutôt que lorsqu'elle frappe 0,0. Vous pouvez paramétrer cette valeur de température minimale. Après avoir créé un État adjacent et informatique de son énergie, vérifier si cet État adjacent est une nouvelle solution de meilleure mondiale, et si donc sauvegarder ces informations. Je peux copier le meilleur état par référence parce que la méthode AdjacentState alloue un nouveau tableau, mais je pourrais avez apporté une copie explicite. Chaque fois qu'un nouvel État meilleur mondial est trouvé, afficher il et son énergie. La boucle principale de traitement se termine comme suit :

double p = random.NextDouble();
  if (AcceptanceProb(energy, adjEnergy, currTemp) > p)
  {
    state = adjState;
    energy = adjEnergy;
  }
  currTemp = currTemp * alpha;
  ++iteration;
} // While

La boucle se termine en première générant un p aléatoire de valeur supérieur ou égal à 0.0 et strictement inférieure à 1.0 et en comparant cette valeur contre le retour de la méthode d'assistance AcceptanceProb. Si la probabilité d'acceptation dépasse la valeur aléatoire, l'état actuel les transitions vers l'État adjacent. Ensuite, la température actuelle est a légèrement diminuée en multipliant par le facteur de refroidissement, et la variable de compteur de boucle est incrémentée. Vient ensuite :

Console.Write("Temperature has cooled to (almost) zero ");
Console.WriteLine("at iteration " + iteration);
Console.WriteLine("Simulated Annealing loop complete");
Console.WriteLine("\nBest state found:");
Display(bestState);
Console.WriteLine("Best energy = " + bestEnergy.ToString("F2") + "\n");
Interpret(bestState, problemData);
Console.WriteLine("\nEnd Simulated Annealing demo\n");
Console.ReadLine();

Après la boucle de la transformation de SA principale, afficher l'État meilleur (solution) trouvé et son énergie correspondante (heures). La méthode Main se termine comme suit :

...
} // Try
  catch (Exception ex)
  {
    Console.WriteLine(ex.Message);
    Console.ReadLine();
  }
} // Main

La méthode se terminera par la gestion des exceptions simplement en affichant le message de l'exception.

Les méthodes d'assistance

Le code de la méthode d'assistance MakeProblemData est :

static double[][] MakeProblemData(int numWorkers, int numTasks)
{
  double[][] result = new double[numWorkers][];
  for (int w = 0; w < result.Length; ++w)
    result[w] = new double[numTasks];
  result[0][0] = 7.5; result[0][1] = 3.5; result[0][2] = 2.5;
  result[1][1] = 1.5; result[1][2] = 4.5; result[1][3] = 3.5;
  result[2][2] = 3.5; result[2][3] = 5.5; result[2][4] = 3.5;
  result[3][3] = 6.5; result[3][4] = 1.5; result[3][5] = 4.5;
  result[4][0] = 2.5; result[4][4] = 2.5; result[4][5] = 2.5;
  return result;
}

J'ai décidé d'utiliser le type double [] [] — c'est-à-dire, un tableau de tableaux — de tenir ma définition ordonnancement du problème. Le langage c#, contrairement à nombreux langages de C-famille, prend en charge un tableau à deux dimensions intégré, donc je pourrais avez utilisé de type double [,], mais un tableau de tableaux est plus facile de refactoriser si vous voulez recode mon exemple à une langue qui ne supporte pas les tableaux à deux dimensions. Dans cet exemple, j'ai mis arbitrairement l'index de travailleur première et l'indice de tâche Deuxièmement (donc le résultat [1] [3] est le temps requis par travailleur 1 pour effectuer la tâche 3), mais je pourrais avez inversé l'ordre. Notez que c# automatiquement initialise les cellules de tableau double de type à 0.0, donc je n'ai pas explicitement de le faire. Je pourrais avez déjà utilisé une autre valeur, tels que -1,0 pour indiquer qu'un travailleur ne peut pas effectuer une tâche particulière.

Méthode d'assistance RandomState est :

static int[] RandomState(double[][] problemData)
{
  int numWorkers = problemData.Length;
  int numTasks = problemData[0].Length;
  int[] state = new int[numTasks];
  for (int t = 0; t < numTasks; ++t) {
    int w = random.Next(0, numWorkers);
    while (problemData[w][t] == 0.0) {
      ++w; if (w > numWorkers - 1) w = 0;
    }
    state[t] = w;
  }
  return state;
}

Rappelons qu'un État représente une solution et qu'un État est un tableau int où l'indice est la tâche et la valeur est le travailleur. Pour chaque cellule dans l'État, générer un travailleur aléatoire w. Mais ce travailleur n'est peut-être pas en mesure d'effectuer la tâche, afin de vérifier si la valeur correspondante dans la matrice de données du problème est 0,0 (c'est-à-dire que le travailleur ne peut pas faire la tâche), et si j'essaie donc le travailleur prochain, en prenant soin d'envelopper retour au travailleur 0 si j'excède l'index du dernier travailleur.

Méthode d'assistance AdjacentState est :

static int[] AdjacentState(int[] currState, double[][] problemData)
{
  int numWorkers = problemData.Length;
  int numTasks = problemData[0].Length;
  int[] state = new int[numTasks];
  int task = random.Next(0, numTasks);
  int worker = random.Next(0, numWorkers);
  while (problemData[worker][task] == 0.0) {
    ++worker; if (worker > numWorkers - 1) worker = 0;
  }
  currState.CopyTo(state, 0);
  state[task] = worker;
  return state;
}

Méthode AdjacentState commence par un État donné, puis sélectionne une tâche aléatoire et puis sélectionne un travailleur aléatoire qui peut le faire tâche. Notez qu'il s'agit d'une approche assez brute ; Il ne vérifie pas si le travailleur nouveau généré de façon aléatoire est le même que le travailleur actuel, ainsi l'État retour pourrait être le même que l'état actuel. Selon la nature du problème ciblé par un algorithme de SA, vous pouvez insérer la logique de code qui assure qu'un État adjacent est différent de l'état actuel.

La méthode de l'énergie est montrée dans Figure 4.

La figure 4, la méthode d'énergie

static double Energy(int[] state, double[][] problemData)
{
  double result = 0.0;
  for (int t = 0; t < state.Length; ++t) {
    int worker = state[t];
    double time = problemData[worker][t];
    result += time;
  }
  int numWorkers = problemData.Length;
  int[] numJobs = new int[numWorkers];
  for (int t = 0; t < state.Length; ++t) {
    int worker = state[t];
    ++numJobs[worker];
    if (numJobs[worker] > 1) result += 3.50;
  }
  return result;
}

La méthode d'énergie d'abord parcourt chaque tâche dans le tableau de l'État, extrait la valeur assignée travailleur, recherche le temps requis dans la matrice de données du problème et s'accumule le résultat. Ensuite, la méthode compte le nombre de fois où un travailleur plus d'une tâche et ajoute une pénalité réoutillage de 3,5 heures pour chaque tâche supplémentaire. Dans cet exemple, le calcul de l'énergie d'un État est rapide ; Toutefois, dans les algorithmes de SA plus réalistes, la méthode d'énergie domine le temps d'exécution, donc vous devrez vous assurer que la méthode est aussi efficace que possible.

Méthode d'assistance AcceptanceProb est :

static double AcceptanceProb(double energy, double adjEnergy,
  double currTemp)
{
  if (adjEnergy < energy)
    return 1.0;
  else
    return Math.Exp((energy - adjEnergy) / currTemp);
}

Si l'énergie de l'État adjacent est moins (ou plus, dans le cas d'un problème de maximisation) l'énergie de l'état actuel, la méthode retourne 1.0, de sorte que l'état actuel de transition sera toujours à l'état de nouvelle, mieux adjacente. Mais si l'énergie de l'État adjacent est le même qu'ou pire que l'état actuel, la méthode retourne une valeur inférieure à 1.0, qui dépend de la température actuelle. Pour des valeurs élevées de la température au début de l'algorithme, la valeur de retour est proche de 1,0, donc l'état actuel sera souvent transition vers l'État nouveau, pire adjacente. Mais comme les température cools, la valeur de retour de AcceptanceProb devienne plus petite et plus petites, donc il n'y a moins de chance de transition vers un état pire.

L'idée ici est que vous parfois — surtout au début de l'algorithme — veulent aller à un état pire, donc vous ne convergent sur une solution locale non optimale. En allant parfois à un état pire, vous pouvez s'échapper des États impasse non optimales. Notez que parce que la fonction effectue division arithmétique par la valeur de la température courante, la température ne peut être accueillie pour atteindre 0. La fonction d'acceptation utilisée ici est la fonction plus courante et est basée sur certaines hypothèses sous-jacentes de math, mais il n'y a aucune raison que vous ne pouvez utiliser d'autres fonctions d'acceptation.

Les méthodes d'affichage et d'assistance à interpréter sont extrêmement simples, comme le montre Figure 5.

Figure 5 l'affichage et à interpréter des méthodes d'assistance

static void Display(double[][] matrix)
{
  for (int i = 0; i < matrix.Length; ++i) {
    for (int j = 0; j < matrix[i].Length; ++j)
      Console.Write(matrix[i][j].ToString("F2") + " ");
    Console.WriteLine("");
  }
}
static void Display(int[] vector)
{
  for (int i = 0; i < vector.Length; ++i)
    Console.Write(vector[i] + " ");
  Console.WriteLine("");
}
static void Interpret(int[] state, double[][] problemData)
{
  for (int t = 0; t < state.Length; ++t) { // task
    int w = state[t]; // worker
    Console.Write("Task [" + t + "] assigned to worker ");
    Console.WriteLine(w + ", " + problemData[w][t].ToString("F2"));
  }
}

Certaines faiblesses.

Les algorithmes de SA sont simples à mettre en œuvre et peuvent être des outils puissants, mais ils ont des faiblesses. Parce que ces algorithmes sont plus souvent utilisés dans des situations où il n'y aucun algorithme de résolution de problèmes déterministe bon, en général vous ne saurez pas quand, ou même si, vous touchez une solution optimale. Par exemple, en Figure 1, la meilleure solution trouvée avait une énergie de 20,5 heures, mais en exécutant l'algorithme un peu plus longtemps, vous pouvez trouver un État qui a une énergie de 19,5 heures. Ainsi, lors de l'utilisation de SAs, vous devez être prêt à accepter une solution bonne mais pas nécessairement optimale. Une faiblesse connexe avec des algorithmes de SA et autres algorithmes basés sur le comportement des systèmes naturels, c'est qu'elles nécessitent la spécification de paramètres libres tels que la température initiale et le taux de refroidissement. L'efficacité et la performance de ces algorithmes, y compris les SAs, sont souvent très sensibles aux valeurs que vous sélectionnez pour les paramètres libres.

Les algorithmes de SA sont étroitement liés aux algorithmes de la colonie de Bee simulée (SBC), dont j'ai parlé dans le numéro d'avril 2011 (msdn.microsoft.com/magazine/gg983491). Les deux techniques sont bien adaptés pour résoudre les problèmes d'optimisation combinatoire, non numériques. En général, SAs sont plus rapidement que les CPE, mais les CPE ont tendance à produire les meilleures solutions au détriment des performances.

L'utilisation des techniques d'intelligence artificielle dans les tests de logiciels est un domaine qui est presque entièrement inexplorés. Il est un exemple où SAs pourraient être utilisés dans le test de logiciels comme la validation de l'algorithme. Supposons que vous ayez des problèmes combinatoires qui peuvent en fait être résolus à l'aide d'un algorithme déterministe. Le problème de chemin le plus court graphique, qui peut être résolu par plusieurs efficace mais relativement complexes algorithmes tels que l'algorithme de Dijkstra est un exemple. Si vous avez codé un algorithme plus court chemin, vous pourrait le tester en rapidement de codage d'un algorithme de SA simple et en comparant les résultats. Si le résultat de SA est meilleur que l'algorithme déterministe, vous savez que vous avez un bug dans votre algorithme déterministe.

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