Este artículo proviene de un motor de traducción automática.

Ejecución de prueba

Recocido simulado y pruebas

James McCaffrey

En la columna de este mes presento código C# que implementa un algoritmo de recocido simulado (SA) para resolver un problema de programación. Un algoritmo de SA es una técnica de inteligencia artificial basada en el comportamiento de metal frío. Se puede usar para encontrar soluciones a problemas de optimización combinatoria difícil o imposible.

Es la mejor manera para ver donde estoy enfilé a echar un vistazo a figura 1 y figura 2. La tabla figura 1 describe un problema de programación: cinco trabajadores y seis tareas. Cada entrada en la tabla representa cuánto tarda un trabajador completar una tarea. Por ejemplo, w2 trabajador necesita 5,5 horas para completar la tarea t3. Una entrada en una fila vacía indica que el trabajador correspondiente no puede realizar una tarea. El problema consiste en asignar a cada una de las seis tareas a uno de los trabajadores de tal manera que se minimice el tiempo total para completar todas las tareas. Además, suponemos que cada vez que un trabajador pasa a una nueva tarea, hay una penalización de reconversión de 3.5 horas.

Figura 1 hora por trabajador completar la tarea

Figura 2 SimulatedAnnealing en acción

Figura 2 muestra un programa que utiliza un algoritmo de SA para encontrar una solución al problema de programación. El programa comienza por generar una solución aleatoria. En la terminología de SA, una posible solución se llama el estado del sistema. El estado inicial es [4 0 0 2 2 3], que significa trabajador 4, tarea 1 ha asignado tareas 0 se ha asignado al trabajador 0, tarea 2 se ha asignado al trabajador 0, tarea 3 se ha asignado al trabajador 2, tarea 4 se ha asignado al trabajador 2 y trabajador 3 ha asignado tareas 5. El tiempo total para el estado inicial aleatorio es 2.5 + 3,5 + 2,5 + 5.5 + 3,5 + 4.5 = 22 horas más castigo reconversión 3.5-hora por trabajador 0 y una pena de 3.5 horas para el trabajador 2, para un total de 29 horas. En la terminología de SA, la cantidad que intenta minimizar (o menos frecuentemente maximizar) se llama la energía del Estado.

El programa entra en un bucle. En cada iteración del bucle, el algoritmo de SA genera un Estado adyacente y evalúa ese Estado adyacente para ver si es mejor que el estado actual. Detrás de las escenas, el algoritmo de SA utiliza una variable de la temperatura que disminuye lentamente, como explicaré en breve. El bucle de SA termina cuando la temperatura se enfría lo suficientemente cercano a cero. El programa concluye mostrando la mejor solución encontrada.

Este ejemplo es simple artificialmente porque con las seis tareas donde cada tarea puede realizarse por uno de los tres trabajadores, sólo hay 36 posibles combinaciones, que equivale a 729, por lo que sólo podría evaluar cada uno. Pero supongamos que usted tenía un problema con 20 tareas donde cada tarea puede realizarse por uno de los 12 trabajadores. Sería 1220 combinaciones, que equivale a una friolera 3,833,759,992,447,475,122,176. Aunque podría evaluar posibles soluciones 1 millón por segundo, necesitaría unos 121 millones de años evaluar todas las posibilidades.

SA es un metaheurísticas — es decir, un marco conceptual general que puede utilizarse para crear un algoritmo específico para resolver un problema específico. Mejor es usado para problemas de optimización combinatoria donde no hay ningún algoritmo de solución práctica determinista. Descrita por primera vez en un documento de 1983 por S. Kirkpatrick, C. Gelatt y M. Vecchi, SA se inspira en el comportamiento de recocido de metal de refrigeración. Cuando algunos metales se calientan a alta temperatura, los átomos y moléculas rompen sus lazos. Cuando el metal se enfría lentamente, los átomos y moléculas reformar sus bonos de tal manera que se minimice la energía del sistema.

Esta columna se supone que tienes habilidades de programación de nivel intermedio. Implemento el programa de SA utilizando C#, pero no deberían tener demasiados problemas refactorización mi código a un idioma diferente, como Visual Basic o Python. En las secciones siguientes, te guiará a través del programa que genera figura 2. Todo el código está disponible como una descarga de archive.msdn.microsoft.com/mag201201TestRun. Creo que encontrará la capacidad de entender y utilizar SA una adición interesante y posiblemente útil para el conjunto de habilidades personales.

Estructura del programa

Había implementado el programa de demostración de SA como una sola aplicación consola de C#. Se muestra la estructura general del programa figura 3.

Figura 3 estructura de programa 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

He utilizado Visual Studio para crear un programa de aplicación de consola denominado SimulatedAnnealing. En la ventana Explorador de soluciones, había renombrado el archivo Program.cs predeterminado a SimulatedAnnealingProgram.cs, que automáticamente la única clase en el proyecto. He eliminado todo la plantilla generada utilizando sentencias excepto para el espacio de nombres System — SA es bastante sencillo y normalmente no necesita mucho biblioteca de soporte. Declaró un objeto aleatorio de ámbito de clase el nombre aleatorio. SA algoritmos son probabilísticos, como verá en poco tiempo.

El corazón de la transformación del algoritmo de SA es un rato bucle. El bucle es controlado por una variable de contador de bucle denominada "iteración" y por una variable que representa la temperatura del sistema. En la práctica, la variable de temperatura casi siempre llega a cerca de cero y termina el bucle antes de que el contador de bucle alcanza su valor máximo y termina el bucle.

Algoritmos de SA deben tener tres métodos específicos del problema como se sugiere en figura3. El algoritmo de SA debe tener un método que genera una estado/solución inicial (generalmente aleatoria). El algoritmo de SA debe tener un método que genera un Estado adyacente relativo a un determinado Estado. Y el algoritmo de SA debe tener un método que calcula el energía y el costo de un Estado — el valor que intenta minimizar o maximizar. En figura 3 estos son métodos RandomState, junto­Estado y energía, respectivamente. Método AcceptanceProb genera un valor que se utiliza para determinar si el estado actual del sistema pasa al Estado adyacente incluso cuando el estado adyacente es peor que el estado actual. Método MakeProblemData es un auxiliar y crea una matriz de estructura de datos que corresponde con figura 1. Los métodos sobrecargados de visualización y el método de interpretación son ayudantes sólo para mostrar la información.

Inicialización del programa

El método Main comienza como así:

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

Envuelven todo el código SA en un bloque try-catch único y de alto nivel y mostrar el problema ficticio que intención de configurar. Aquí, estoy usando un ejemplo simple artificialmente, pero uno que sea representativo de los tipos de problemas combinatorias que son adecuadas para una solución por algoritmos de SA. Viene a continuación:

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

Inicializar el objeto de Random utilizando un valor arbitrario de semillas de 0. Y luego llame el método auxiliar MakeProblemData para construir la estructura de datos se muestra en la figura 1. Te presentamos MakeProblemData y los otros métodos auxiliares después de terminar de presentar todo el código en el método Main. Viene a continuación:

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

Tiene la palabra el método auxiliar RandomState para generar un Estado aleatorio /­solución para el problema. Estado es representada como una matriz int donde el índice de la matriz representa una tarea y el valor de la matriz en el índice el trabajador asignado a la tarea. Método auxiliar energía calcula el tiempo total necesario por su parámetro de Estado, teniendo en cuenta la pena 3.5 horas para capacitarse cada vez que un trabajador una tarea adicional. Te pista el mejor estado que se encuentra y su correspondiente energía, por lo que declaro bestEngery y bestState de variables. AdjEnergy y adjState de las variables se utilizan para contener un Estado que colinda con el estado actual y la energía correspondiente. Viene a continuación:

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

El lazo de procesamiento primario de SA termina en uno de dos condiciones: Cuando un contador supera un valor máximo o cuando la variable de la temperatura disminuye a un valor cercano a cero. Nombre el bucle "iteración" de contador, pero pude has llamado "contador" o "tiempo" o "marca" o algo similar. Nombre el currTemp variable de la temperatura en lugar de temporal, por lo que hay menos posibilidades alguien revisar el código podría interpretarlo como una variable temporal. Variable Alfa representa la velocidad de enfriamiento, o un factor que determina cómo la variable de la temperatura disminuye o se enfría, cada vez que a través del bucle de procesamiento. Viene a continuación:

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

Antes de entrar en el bucle principal de procesamiento, mostrar algunos mensajes informativos sobre el estado inicial, la energía y la temperatura. Tal vez desee mostrar información adicional como la velocidad de enfriamiento. Aquí está el bucle:

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

Observe que el control de bucle termina cuando la variable de la temperatura cae por debajo de 0,0001 más que cuando golpea a 0.0. Tal vez desee parametrizar ese valor de temperatura mínima. Después de crear un Estado adyacente y calcular su energía, reviso para ver si ese Estado adyacente es una nueva solución global mejor, y así guardar dicha información. ¿Puedo copiar el mejor estado por referencia porque método AdjacentState asigna una nueva matriz, pero pude ha realizado una copia explícita. Cuando se encuentra un nuevo estado global mejor, mostrar y su energía. El bucle de procesamiento principal termina así:

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

El bucle termina primero generar un valor aleatorio p mayor o igual a 0.0 y estrictamente inferior a 1.0 y comparando ese valor contra el regreso del método auxiliar AcceptanceProb. Si la probabilidad de aceptación supera el valor aleatorio, el estado actual pasa al Estado adyacente. A continuación, la temperatura actual es disminuida ligeramente multiplicando por el factor de enfriamiento y se incrementa la variable de contador de bucle. Viene a continuación:

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

Una vez finalizada el bucle principal transformación SA, mostrar el mejor estado (solución) encontró y su correspondiente energía (horas). El método Main termina así:

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

El método envuelve controlando cualquier excepción simplemente por mostrar el mensaje de la excepción.

Los métodos auxiliares

El código para el método auxiliar MakeProblemData es:

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

Decidí usar el tipo double [] [] — es decir, una matriz de matrices: celebrar mi definición de problema de programación. El lenguaje C#, a diferencia de muchos lenguajes C-familia, apoyar una matriz bidimensional incorporada, por lo que yo pude has usado tipo double [,] pero una matriz de matrices es más fácil para refactorizar si desea codificar mi ejemplo en un idioma que no admite matrices bidimensionales. En este ejemplo puse arbitrariamente el índice trabajador primero y el índice de tarea segundo (modo resultado [1] [3] es el tiempo requerido por trabajador 1 para realizar la tarea 3), pero yo pude has invertido el orden. Tenga en cuenta que C# automáticamente inicializa tipo matriz doble células a 0,0, para no tener que hacerlo explícitamente. Pude has usado algún otro valor, como -1,0 para indicar que un trabajador no puede realizar una tarea determinada.

Método auxiliar RandomState es:

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

Recordar que un Estado representa una solución y que un Estado es una matriz int donde el índice es la tarea y el valor es el trabajador. Para cada celda en estado, generar una trabajador aleatoria w. Pero ese trabajador no pueda realizar la tarea, para que compruebe si el valor correspondiente en la matriz de datos del problema es 0.0 (lo que significa que el trabajador no puede hacer la tarea), y si lo intento el siguiente trabajador, tenga cuidado de envolver al trabajador 0 si superan el índice del último trabajador.

Método auxiliar AdjacentState es:

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étodo AdjacentState comienza con un Estado determinado, y luego selecciona una tarea aleatoria y, a continuación, selecciona un trabajador aleatorio que puede hacer que tarea. Tenga en cuenta que se trata de un enfoque bastante crudo; no comprueba para ver si el trabajador nuevo generado aleatoriamente es el mismo que el trabajador actual, por lo que el estado de retorno podría ser el mismo que el estado actual. Dependiendo de la naturaleza del problema están dirigido por un algoritmo de SA, tal vez desee insertar la lógica de código que garantiza que un Estado adyacente es diferente de la situación actual.

El método de energía se muestra en la figura 4.

Figura 4 el método de energía

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

El método de energía primero recorre cada tarea en la matriz de Estado, agarra el valor de trabajador asignado, busca el tiempo requerido en la matriz de datos del problema y acumula el resultado. A continuación, el método cuenta el número de veces que un trabajador más de una tarea y agrega una pena reconversión de 3.5 horas para cada tarea adicional. En este ejemplo, calcular la energía de un Estado es rápido; Sin embargo, en los algoritmos más realistas de SA, el método de energía domina el tiempo de ejecución, por lo que querrá asegurarse de que el método es tan eficaz como sea posible.

Método auxiliar AcceptanceProb es:

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

Si la energía del Estado adyacente es menos (o más, en el caso de un problema de maximización) la energía del estado actual, el método devuelve 1.0, por lo que el estado actual siempre se cambiarán para el nuevo estado mejor adyacente. Pero si la energía del Estado adyacente es el mismo, o peor que el estado actual, el método devuelve un valor inferior a 1.0, que depende de la temperatura actual. Para valores altos de temperatura en el algoritmo, el valor devuelto es cercano a 1.0, por lo que a menudo se cambiarán el estado actual para el nuevo estado peor adyacente. Pero como la temperatura enfría, el valor devuelto por AcceptanceProb se hace más pequeño y más pequeño, por lo tanto hay menos posibilidades de la transición a un Estado peor.

La idea aquí es que usted a veces — especialmente temprano en el algoritmo: quiero ir a un Estado peor por lo que no converge en una solución local no óptima. A veces yendo a un Estado peor, puede escapar no óptimos Estados callejón sin salida. Observe que debido a que la función realiza división aritmética por el valor de la temperatura actual, la temperatura puede llegar a 0. La función de aceptación utilizada aquí es la función más común y se basa en algunos supuestos subyacentes de matemáticas, pero no hay ninguna razón que no se pueden utilizar otras funciones de aceptación.

Los métodos de visualización y auxiliar de interpretar son extremadamente simples, como se muestra en figura 5.

Figura 5 la visualización e interpretar métodos auxiliares

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

Algunas debilidades

Algoritmos de SA son fáciles de implementar y pueden ser herramientas poderosas, pero tienen debilidades. Porque estos algoritmos se utilizan más a menudo en situaciones donde no hay ningún buen algoritmo solución determinista, en general no vas a saber cuándo, o incluso si, consigues una solución óptima. Por ejemplo, en figura 1, la mejor solución encontrada tenía una energía de 20,5 horas, pero al ejecutar el algoritmo de un poco más se puede encontrar un Estado que tiene energía de 19.5 horas. Así, cuando se utilizan SAs, deben ser dispuestos a aceptar una solución buena, pero no necesariamente óptima. Una debilidad relacionada con algoritmos de SA y otros algoritmos basados en el comportamiento de los sistemas naturales es que requieren la especificación de parámetros libres, como la temperatura inicial y la velocidad de enfriamiento. La eficacia y el rendimiento de estos algoritmos, incluyendo SAs, suelen ser muy sensibles a los valores que se selecciona para los parámetros libres.

Algoritmos de SA están estrechamente relacionados con algoritmos de Colonia de abeja simulado (SBC) que descrito en la edición de abril de 2011 (msdn.microsoft.com/magazine/gg983491). Ambas técnicas están bien adaptados para resolver problemas de optimización combinatoria, no numéricos. En general, SAs son más rápidos que SBCs pero SBCs tienden a producir soluciones mejores a expensas de rendimiento.

El uso de técnicas de inteligencia artificial en pruebas de software es un área casi enteramente inexplorada. Un ejemplo donde SAs podrían utilizarse en pruebas de software es como la validación del algoritmo. Supongamos que tiene algún problema combinatoria que de hecho puede ser resueltos mediante un algoritmo determinístico. Un ejemplo es el problema de ruta más corta de gráfico, que puede ser resueltos por varios eficiente pero relativamente complicados algoritmos como el algoritmo de Dijkstra. Si ha codificado un algoritmo del camino más corto, podría probar un simple algoritmo SA de codificación y comparación de resultados rápidamente. Si el resultado de SA es mejor que el algoritmo determinístico, sabes que tienes un error en su algoritmo determinístico.

Dr.James McCaffrey  trabaja para Volt Information Sciences Inc., donde administra formación técnica para ingenieros de software trabajando en el Microsoft Redmond, Washington, campus. Trabajó en varios productos de Microsoft, Internet Explorer y MSN Search. Dr. McCaffrey es el autor de ".Recetas de automatización de prueba NET"(Apress, 2006) y puede ser contactado en jammc@microsoft.com.

Gracias a los siguientes expertos técnicos para revisar este artículo: Paul Koch, Dan Liebling, Ann Loomis Thompson y Shane Williams