Il presente articolo è stato tradotto automaticamente.

Esecuzione di test

Simulazione di annealing e test

James McCaffrey

In mese questo vi presento il codice c# che implementa un algoritmo di ricottura simulata (SA) per risolvere un problema di programmazione.Un algoritmo SA è una tecnica di intelligenza artificiale basata sul comportamento di raffreddamento di metallo.Può essere utilizzato per trovare soluzioni ai problemi di ottimizzazione combinatoria difficile o impossibile.

Il modo migliore per vedere dove sono diretto è quello di dare un'occhiata a Figura 1 e Figura 2.La tabella Figura 1 viene descritto un problema di programmazione: Cinque lavoratori e sei compiti.Ogni voce nella tabella rappresenta quanto tempo ci vuole per un lavoratore completare un'attività.Ad esempio, w2 lavoratore deve 5,5 ore per completare il compito t3.Una voce vuota in una riga indica che il lavoratore corrispondente non è possibile eseguire un'attività.Il problema è per ciascuno dei sei compiti assegnare ad uno dei lavoratori in modo tale che il tempo totale per completare tutte le attività è ridotto al minimo.Inoltre, ci assumiamo che ogni volta che un lavoratore passa a una nuova attività, c'è una sanzione di riattrezzamento 3,5 ore.

Figura 1 volta per lavoratore completare attività

	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

Figura 2 SimulatedAnnealing in azione

Figura 2 mostra un programma che utilizza un algoritmo SA di trovare una soluzione al problema di programmazione.Il programma inizia generando una soluzione casuale.Nella terminologia di SA, una potenziale soluzione viene chiamata lo stato del sistema.Lo stato iniziale è [4 0 2 0 2 3], che significa compito 0 è stato assegnato al lavoratore 4, attività 1 è stato assegnato al lavoratore 0, compito 2 è stato assegnato al lavoratore 0, attività 3 è stato assegnato al lavoratore 2, attività 4 è stato assegnato al lavoratore 2 e attività 5 è stato assegnato al lavoratore 3.Il tempo totale per lo stato iniziale casuale è 2.5 + 3.5 + 2.5 + 5.5 + 3.5 + 4.5 = 22 ore plus una sanzione di riattrezzamento 3.5 ore per lavoratore 0 e una sanzione di 3,5 ore per lavoratore 2, per un totale di 29 ore.Nella terminologia di SA, la quantità che si sta cercando di minimizzare (o massimizzare meno frequentemente) viene chiamata l'energia dello stato.

Il programma entra in un ciclo.In ogni iterazione del ciclo, l'algoritmo SA genera uno stato adiacente e valuta tale stato adiacente per vedere se è meglio che lo stato corrente.Dietro le quinte, l'algoritmo di SA utilizza una variabile di temperatura che diminuisce lentamente, come spiegherò in breve.Il ciclo di SA termina quando la temperatura si raffredda sufficientemente vicino a zero.Il programma si conclude visualizzando la migliore soluzione trovata.

Questo esempio è artificialmente semplice perché con le sei mansioni dove ogni attività può essere eseguita da uno dei tre operai, ci sono solo 36 combinazioni possibili, che è uguale a 729, così si potrebbe valutare solo ogni uno.Ma supponiamo che hai avuto un problema con 20 attività dove ogni attività può essere eseguita da uno dei 12 lavoratori.Non ci sarebbe 1220 combinazioni, che equivale a un enorme 3,833,759,992,447,475,122,176.Anche se si potrebbero valutare possibili soluzioni 1 milione al secondo, dovresti circa 121 milioni di anni valutare tutte le possibilità.

SA è un metaheuristic — che è, un quadro concettuale generale che può essere utilizzato per creare un algoritmo specifico per risolvere un problema specifico.È meglio utilizzato per problemi di ottimizzazione combinatoria dove non esiste alcun algoritmo di soluzione pratica deterministica.In primo luogo descritto in un documento del 1983 da s.Kirkpatrick, c.Gelatt e M.Vecchi, SA è vagamente basato sul comportamento ricottura di raffreddamento di metallo.Quando alcuni metalli sono riscaldati ad alta temperatura, atomi e molecole rompono loro obbligazioni.Quando il metallo lentamente è raffreddato, atomi e molecole riformare le loro obbligazioni in modo tale che l'energia del sistema è ridotto al minimo.

Questa colonna si presuppone la abilità di programmazione di livello intermedio.Io implementato il programma SA utilizzando c#, ma non dovreste avere troppi problemi refactoring del mio codice per una lingua diversa, come Visual Basic o Python.Nelle sezioni che seguono, esaminerò è il programma che ha generato Figura 2.Tutto il codice è disponibile come download da archive.msdn.microsoft.com/mag201201TestRun.Penso che troverete la capacità di comprendere e utilizzare SA un'aggiunta interessante e forse utile per il tuo set di abilità personali.

Struttura del programma

Ho implementato il programma demo SA come una singola applicazione console c#.La struttura complessiva del programma è mostrata in Figura 3.

Struttura del programma SimulatedAnnealing di figura 3

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

Ho utilizzato Visual Studio per creare un programma di applicazione console denominato SimulatedAnnealing. Nella finestra Solution Explorer ho rinominato il file Program. cs predefinito a SimulatedAnnealingProgram.cs, che automaticamente rinominato la singola classe nel progetto. Ho cancellato tutto il modello generato utilizzando istruzioni ad eccezione di spazio dei nomi System — SA è abbastanza semplice e in genere non serve molto libreria supporta. Ho dichiarato un oggetto Random ambito di classe denominato casuale. SA algoritmi sono probabilistici, come si vedrà in poco tempo.

Il cuore del trattamento algoritmo SA è un po ' di tempo ciclo. Il ciclo è controllato da una variabile contatore di ciclo denominato "iterazione" e da una variabile che rappresenta la temperatura del sistema. In pratica, quasi sempre la variabile temperatura raggiunge quasi zero e termina il ciclo prima il contatore di ciclo raggiunge il suo valore massimo e termina il ciclo.

Algoritmi SA devono avere tre metodi specifici del problema, come suggerito nel figura3. L'algoritmo SA deve avere un metodo che genera un stato/soluzione iniziale (di solito casuale). L'algoritmo SA deve disporre di un metodo che genera uno stato adiacente relativo a un determinato stato. E l'algoritmo SA deve disporre di un metodo che consente di calcolare il costo/energia di uno stato — il valore che si sta cercando di ridurre al minimo o massimo. In Figura 3 questi sono metodi RandomState, adiacente­stato ed energia, rispettivamente. Metodo AcceptanceProb genera un valore utilizzato per determinare se lo stato corrente del sistema transizioni allo stato adiacente, anche quando lo stato adiacente è peggio che lo stato corrente. Metodo MakeProblemData è un aiutante e crea una matrice di struttura di dati che corrisponde con Figura 1. I metodi di overload Display e il metodo interpreta sono pochi collaboratori per visualizzare le informazioni.

Inizializzazione del programma

Il metodo Main inizia come così:

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)");
 ...

Ho avvolgere tutto il codice SA in un blocco try-catch singola, ad alto livello e visualizzare il problema fittizio che ho intenzione di impostare. Qui, sto usando un esempio semplice artificialmente — ma che è il rappresentante dei tipi di problemi combinatorie che sono adatti per una soluzione da algoritmi di SA. Successiva è:

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

Inizializzo l'oggetto Random utilizzando un valore di inizializzazione arbitrario di 0. Quindi chiamare il metodo di supporto MakeProblemData per costruire la struttura di dati mostrata in Figura 1. Sarò presente MakeProblemData e altri metodi di supporto dopo che finisco presentando tutto il codice nel metodo Main. Successiva è:

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

Chiamare il metodo di supporto RandomState per generare uno stato casuale /­soluzione per il problema. Stato è rappresentato come una matrice int dove l'indice di matrice rappresenta un'attività e il valore della matrice in corrispondenza dell'indice rappresenta il lavoratore assegnato all'attività. Il metodo di supporto energia calcola il tempo totale necessario dal suo parametro di stato, prendendo in considerazione la pena di 3,5 ore per riattrezzamento ogni volta che un lavoratore fa un compito supplementare. Sarò pista migliore stato trovato e alla sua energia corrispondente, quindi dichiaro di bestEngery e bestState di variabili. AdjEnergy e adjState variabili sono utilizzati per tenere uno stato che è adiacente allo stato attuale e l'energia corrispondente. Successiva è:

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

Il ciclo di elaborazione primario SA termina su una delle due condizioni: Quando un contatore supera un valore massimo o quando la variabile di temperatura decresce ad un valore vicino a zero. I nome del ciclo "iterazione" di contatore, ma ho potuto hai chiamato "contatore" o "tempo" o "tick" o qualcosa di simile. I nome la temperatura variabile currTemp anziché temp, quindi non c'è meno possibilità qualcuno rivedere il codice potrebbe interpretarlo come una variabile temporanea. Alfa variabile rappresenta il tasso di raffreddamento, o un fattore che determina come la variabile temperatura diminuisce o raffredda, ogni volta che il ciclo di lavorazione. Successiva è:

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");

Prima di entrare nel ciclo di elaborazione principale, visualizzare alcuni messaggi informativi sulla stato iniziale, energia e temperatura. Si potrebbe voler visualizzare informazioni aggiuntive come il tasso di raffreddamento. Ecco il loop:

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");
  }
...

Si noti che il controllo del ciclo esce quando la variabile di temperatura scende di sotto di 0,0001 piuttosto che quando colpisce 0.0. Si potrebbe voler parametrizzare tale valore di temperatura minima. Dopo la creazione di uno stato adiacente e informatica la sua energia, controllare per vedere se tale stato adiacente è una nuova soluzione globale migliore, e se così salvare tali informazioni. Posso copiare lo stato migliore di riferimento perché metodo AdjacentState alloca una nuova matrice, ma potrei hai fatto una copia esplicita. Ogni volta che un nuovo stato globale migliore viene trovato, mi display esso e la sua energia. Il ciclo di elaborazione principale termina come questo:

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

Il ciclo finisce in primo luogo generando un valore casuale p maggiore o uguale a 0,0 e rigorosamente inferiore a 1,0 e confrontare tale valore contro il ritorno dal metodo di supporto AcceptanceProb. Se la probabilità di accettazione supera il valore casuale, lo stato corrente passa allo stato adiacente. Successivamente, la temperatura attuale è leggermente diminuita moltiplicando per il fattore di raffreddamento e la variabile contatore del ciclo viene incrementata. Successiva è:

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();

Dopo aver completato il ciclo di elaborazione principale di SA, visualizzare lo stato migliore (soluzione) trovato e la sua energia corrispondente (ore). Il metodo Main finisce come questo:

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

Il metodo avvolge mediante la gestione di eventuali eccezioni semplicemente esponendo il messaggio dell'eccezione.

I metodi di supporto

Il codice per il metodo di supporto MakeProblemData è:

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;
}

Ho deciso di utilizzare il tipo double [] [] — che è, una matrice di matrici — a tenere la mia definizione di problema pianificazione. Il linguaggio c#, a differenza di molte lingue della famiglia C, supportano una matrice bidimensionale incorporata, quindi potrei hai utilizzato tipo double [,] ma una matrice di matrici è più facile a refactor se volete ricodificare il mio esempio su una lingua che non supporta matrici bidimensionali. In questo esempio ho messo arbitrariamente l'indice di lavoratore prima e l'indice di attività secondo la (quindi risultato [1] [3] è il tempo richiesto da lavoratore 1 per eseguire attività 3), ma ho potuto aver invertito l'ordine. Si noti che c# automaticamente Inizializza tipo matrice doppia celle su 0.0, così non devo farlo in modo esplicito. Potrei aver usato qualche altro valore, come ad esempio -1,0 per indicare che un lavoratore non può svolgere un compito particolare.

Metodo di supporto RandomState è:

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;
}

Ricordiamo che uno stato rappresenta una soluzione e che uno stato è una matrice int dove l'indice è il compito e il valore è il lavoratore. Per ogni cella nello stato, generare un lavoratore casuale w. Ma che lavoratore potrebbe non essere in grado di svolgere il compito, così posso controllare per vedere se il valore corrispondente nella matrice dati problema è 0.0 (cioè che il lavoratore non può fare il compito), e se così provo il lavoratore prossimo, stando attenti ad avvolgere torna al lavoratore 0 se I superi l'indice dell'ultimo operaio.

Metodo di supporto AdjacentState è:

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;
}

Metodo AdjacentState inizia con un determinato stato, quindi seleziona un'attività caso e quindi seleziona un lavoratore casuale che può fare attività. Si noti che questo è un approccio piuttosto grezzo; esso non controlla per vedere se il lavoratore nuovo generato in modo casuale è la stessa come lavoratore attuale, quindi lo stato restituito potrebbe essere lo stesso lo stato corrente. A seconda della natura del problema sta presi di mira da un algoritmo SA, si potrebbe voler inserire logica del codice che garantisce che uno stato adiacente è diverso dallo stato corrente.

Il metodo di energia è mostrato in Figura 4.

Figura 4 il metodo di energia

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;
}

Il metodo di energia prima passeggiate attraverso ogni attività della matrice di stato, afferra il valore assegnato lavoratore, alza il tempo richiesto nella matrice di dati del problema e si accumula il risultato. Successivamente, il metodo conta il numero di volte in cui un lavoratore più di un compito e aggiunge una sanzione di riattrezzamento 3.5 ore per ogni compito supplementare. In questo esempio, l'energia di uno stato l'informatica è rapida; Tuttavia, negli algoritmi di SA più realistici, il metodo di energia domina il tempo di esecuzione, quindi ti consigliamo di verificare che il metodo è più efficiente possibile.

Metodo di supporto AcceptanceProb è:

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

Se l'energia dello stato adiacente è minore di (o più che, nel caso di un problema di massimizzazione) l'energia dello stato attuale, il metodo restituisce 1.0, così lo stato corrente sempre transizione allo stato nuovo, meglio adiacente. Ma se l'energia dello stato adiacente è lo stesso come o peggio lo stato corrente, il metodo restituisce un valore inferiore a 1,0 che dipende dalla temperatura attuale. Per alti valori di temperatura all'inizio nell'algoritmo, il valore restituito è vicino a 1.0, così lo stato corrente spesso transizione allo stato nuovo, peggio adiacente. Ma come raffredda la temperatura, il valore restituito da AcceptanceProb diventa più piccolo e più piccoli, quindi non c'è meno possibilità di transizione verso una condizione peggiore.

L'idea è che a volte si — specialmente nei primi mesi dell'algoritmo — vuole andare a uno stato peggio, così voi non convergono su una soluzione locale non ottima. A volte, andando a uno stato peggio, si possono sfuggire stati vicolo cieco non ottimali. Si noti che poiché la funzione esegue aritmetica divisione dal valore della temperatura attuale, la temperatura non può essere consentita di raggiungere 0. La funzione di accettazione utilizzata qui è la funzione più comune e si basa su alcune ipotesi matematica sottostante, ma non non c'è alcun motivo che non è possibile utilizzare altre funzioni di accettazione.

I metodi di visualizzazione e interpretare Helper sono estremamente semplici, come illustrato nella Figura 5.

Nella figura 5 il Display e interpretare i metodi di supporto

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"));
  }
}

Alcuni punti deboli

Algoritmi SA sono semplici da implementare e può essere strumenti potenti, ma hanno punti deboli. Perché questi algoritmi sono più spesso utilizzati in situazioni dove non non c'è alcun buon algoritmo deterministico risolvere, in generale non si sa quando, o anche se, si colpisce una soluzione ottimale. Per esempio, in Figura 1, la soluzione migliore trovata ha un'energia di 20,5 ore, ma eseguendo l'algoritmo un po' più a lungo, è possibile trovare uno stato che ha energia di 19,5 ore. Così, quando si utilizza SAs, deve essere disposto ad accettare una soluzione buona, ma non necessariamente ottima. Una debolezza correlata con algoritmi SA ed altri algoritmi basati sul comportamento dei sistemi naturali è che richiedono la specifica di parametri liberi come ad esempio la temperatura iniziale e il tasso di raffreddamento. L'efficacia e le prestazioni di questi algoritmi, tra cui SAs, spesso sono molto sensibili ai valori che si seleziona per parametri liberi.

Algoritmi SA sono strettamente correlati agli algoritmi simulato Bee Colonia (SBC), che ho descritto nel numero di aprile 2011 (msdn.microsoft.com/magazine/gg983491). Entrambe le tecniche sono particolarmente adatte per risolvere problemi di ottimizzazione combinatoria, non numerici. In generale, SAs sono più veloce di SBC, ma SBC tendono a produrre soluzioni migliori a scapito delle prestazioni.

L'uso di tecniche di intelligenza artificiale in testing del software è una zona che è quasi interamente inesplorato. Un esempio dove SAs potrebbe essere utilizzato in testing del software è come convalida algoritmo. Si supponga di avere qualche problema combinatorio che in realtà può essere risolto utilizzando un algoritmo deterministico. Un esempio è il problema del percorso più breve di grafico, che può essere risolto da più efficiente ma relativamente complessi algoritmi come algoritmo di Dijkstra. Se voi avete codificato un algoritmo del percorso più breve, potrebbe testare rapidamente un semplice algoritmo SA di codifica e confrontando i risultati. Se il risultato di SA è meglio che l'algoritmo deterministico, sai che hai un bug nel vostro algoritmo deterministico.

Dr. James McCaffrey lavora per Volt Information Sciences Inc., dove gestisce la formazione tecnica per gli ingegneri software della Microsoft di Redmond, Washington, campus. Ha lavorato su diversi prodotti Microsoft, tra cui Internet Explorer e MSN Search. Dr. McCaffrey è l'autore di ".NET Test Automation Recipes"(Apress, 2006) e può essere raggiunto a jammc@microsoft.com.

Grazie ai seguenti esperti tecnici per la revisione di questo articolo: Paul Koch, Dan Liebling, Ann Loomis Thompson e Shane Williams