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

Ejecución de pruebas

Optimización del método de ameba usando C#

James McCaffrey

Descargar el ejemplo de código

El objetivo de optimización numérica es resolver una ecuación. Hay muchas técnicas deterministas basadas en cálculos disponibles; sin embargo, algunos problemas difíciles, especialmente en las áreas de aprendizaje automático y la inteligencia artificial, no pueden resolverse fácilmente mediante técnicas de optimización clásica. En estos casos, pueden ser alternativas tales como la optimización del método de ameba de valor. Optimización del método de Ameba, que trataré en este artículo, es similar en algunos aspectos para la optimización del enjambre de partículas, que describí en la edición de agosto de 2011 de la MSDN Magazine (msdn.microsoft.com/magazine/hh335067).

Es la mejor forma de entender qué optimización del método de Ameba y a ver hacia dónde debe examinar figura1, que muestra un programa de demostración en acción. El objetivo de este programa es encontrar los valores de x e y que minimizar un problema relativamente simple referencia estándar llamado función de Rosenbrock. Esta función tiene una solución conocida en x = 1.0 y y = 1.0 cuando el valor de la función es 0.

Figura 1 ameba método optimización Demo

El programa de demostración crea una ameba virtual que contiene tres soluciones posibles al azar. Lo mejor de estas soluciones iniciales no es muy bueno, x =-0.66 e y = 5,43, dando un valor de función de 2499.52. El programa de demostración llama a un método de resolver y, detrás de las escenas, se utiliza el método de la ameba iterativamente encontrar soluciones mejores y mejores. Después de 50 iteraciones, el algoritmo tiene éxito en la búsqueda de la solución óptima.

En las secciones siguientes presento y explicar el código fuente completo para el programa de demostración. El código está disponible en archive.msdn.microsoft.com/mag201306TestRun. Este artículo asume que usted tiene habilidades de programación por lo menos de nivel intermedio con un lenguaje moderno procedimiento. Código de la demo utilizando C# pero no debería tener demasiados problemas refactorización la demo a otro idioma, como Visual Basic .NET o Python.

El algoritmo del método de ameba

El algoritmo de optimización del método ameba que presento aquí se basa en el trabajo de investigación de 1965, "Un simple método para función minimización," por J.A. Nelder y R. Mead.

Las partes fundamentales de este algoritmo se ilustran en la figura 2. En cualquier momento, hay varias posibles soluciones. En la mayoría de los casos, la optimización de la ameba usa tres soluciones, de color rojo en la figura. Cada solución tiene un valor de la función objetivo asociados, por lo que habrá una solución peor (la más alta función valor porque el objetivo es reducir al mínimo), una mejor solución (el valor mínimo de la función) y otro (s).

Figura 2 ameba operaciones primitivas de la optimización

El algoritmo es un proceso iterativo. En cada paso, intenta reemplazar la peor solución con una nueva, la mejor solución entre tres candidatos: un punto se refleja, un punto ampliado y un punto de contratados. Cada uno de estos candidatos se encuentra a lo largo de una línea desde el punto de peor a través el centroide — algo que está en el centro de todos los puntos excepto el punto peor. En el caso habitual con tres soluciones, el centroide se acostará a medio camino entre lo mejor y el otro punto (no peor).

Si ni el punto reflejado, ni lo ampliado, ni lo contratado es mejor que la peor solución actual, la ameba se reduce al mover todos los puntos, excepto el mejor punto a mitad de camino hacia lo mejor. Algunos trabajos de investigación llaman a este proceso de contracción múltiples.

Cuando graficaron con el tiempo, si los tres puntos de solución actual son conectados por una línea (como con la línea negra punteada en figura 2), las soluciones forman un triángulo, y su movimiento se asemeja a la de una ameba arrastrándose a través de su entorno. En términos matemáticos, un triángulo en un plano es llamado un simple, por lo que este algoritmo de optimización, además de ser llamado el método de la ameba o el método de Nelder Mead, a veces se llama el método simplex.

Estructura general del programa

Codifiqué el programa de demostración de optimización de ameba como una sola aplicación de consola de C#­cación. He utilizado Visual Studio 2010 (debería funcionar cualquier versión de Visual Studio ) y creó un nuevo proyecto llamado ameba­optimización. Después de carga el proyecto, en la ventana Explorador de soluciones me cambió nombre archivo Program.cs a la AmoebaProgram.cs más descriptivo, que automáticamente­camente renombrado programa de clase. He borrado todo innecesario plantilla-generado mediante declaraciones excepto la única instrucción que hace referencia al espacio de nombres System nivel superior.

La estructura de todo el programa, con algunos comentarios y declaraciones de WriteLine quitadas, cotiza en figura 3.

Estructura de los programas de optimización de figura 3 ameba

using System;
namespace AmoebaOptimization
{
  class AmoebaProgram
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin amoeba method optimization demo\n");
        int dim = 2;  // problem dimension
        int amoebaSize = 3;  // number potential solutions
        double minX = -10.0;
        double maxX = 10.0;
        int maxLoop = 50;
        Console.WriteLine("Creating amoeba with size = " + amoebaSize);
        Amoeba a = new Amoeba(amoebaSize, dim, minX, maxX, maxLoop);
        Console.WriteLine("\nInitial amoeba is: \n");
        Console.WriteLine(a.ToString());
        Solution sln = a.Solve();
        Console.WriteLine("Final amoeba is: \n");
        Console.WriteLine(a.ToString());
        Console.WriteLine("\nBest solution found: \n");
        Console.WriteLine(sln.ToString());
        Console.WriteLine("\nEnd amoeba method optimization demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
      }
    }
    public static double ObjectiveFunction(
      double[] vector, object dataSource) { .
.
}
  }
  public class Solution : IComparable<Solution> { .
.
}
  public class Amoeba { .
.
}
}

La función objetivo

Optimización del método de ameba se suele utilizar para resolver un problema de minimización numérica. Generalmente se llama a la función a minimizar una función de coste o la función objetivo. El programa de demostración en figura 1 es resolver un problema de dummy de referencia matemática llamado función de Rosenbrock. La función tiene dos variables de entrada, x e y y se define como f = 100 * (y - x ^ 2) ^ 2 > + (1 - x) ^ 2 >. La función tiene una solución de x = 1.0, y = 1.0, que da un valor de 0.0. Figura 4 muestra una representación gráfica tridimensional de la función de Rosenbrock.

Figura 4 gráfica de la función objetivo

En situaciones del mundo real, optimización de la ameba se utiliza para encontrar la solución a problemas difíciles que se basan en datos. Por ejemplo, supongamos que usted está tratando de predecir los precios del mercado accionario. Usted podría subir con una lista de factores que se cree son predictores y una ecuación, pero es necesario determinar un conjunto de constantes numéricas para la ecuación que minimizar el error en un conjunto de datos de entrenamiento que ha conocido los resultados.

La función objetivo para el programa de demostración es definida en la clase principal del programa como:

public static double ObjectiveFunction(
  double[] vector, object dataSource)
{
  double x = vector[0];
  double y = vector[1];
  return 100.0 * Math.Pow((y - x * x), 2) + 
    Math.Pow(1 - x, 2);
}

Utilizar un parámetro de entrada ficticio llamado dataSource para indicar que en la mayoría de las situaciones la función objetivo depende de alguna fuente de datos externos, como un archivo de texto o una tabla SQL. Porque la función se declara utilizando los modificadores públicos y estáticos, la función es visible a todo el código en el programa de demostración.

La clase de solución

Optimización de la ameba mantiene una colección de posibles soluciones, definidas en una clase de solución:

public class Solution : IComparable<Solution>
{
  public double[] vector;
  public double value;
  static Random random = new Random(1);
  public Solution(int dim, double minX, double maxX) { .
.
}
  public Solution(double[] vector) { .
.
}
  public int CompareTo(Solution other) { .
.
}
  public override string ToString() { .
.
}
}

La clase se deriva de la interfaz IComparable para que objetos de la solución pueden ordenarse automáticamente. Un objeto de solución tiene sólo dos campos importantes: uno es una matriz de doble llamado vector que contiene los valores numéricos de la solución, y el otro es el valor de la función objetivo. Usar campos de miembros del ámbito público y eliminar toda comprobación de errores para simplicidad. El objeto aleatorio estático permite que el código generar soluciones al azar.

El primer constructor de solución crea una solución aleatoria:

public Solution(int dim, double minX, double maxX)
{
  this.vector = new double[dim];
  for (int i = 0; i < dim; ++i)
  this.vector[i] = (maxX - minX) * random.NextDouble() + minX;
  this.value = AmoebaProgram.ObjectiveFunction(this.vector, null);
}

El constructor acepta una dimensión del problema y límites para cada componente del vector. La dimensión para el programa de demostración es 2 porque la función de Rosenbrock tiene dos variables de entrada, x e y. Después de asignar espacio para el vector de campo de miembro, el constructor asigna valores aleatorios entre minX y maxX a la matriz de vector y luego llama a la función objetiva globalmente accesible para calcular el campo valor.

El segundo constructor de solución crea una solución de una matriz especificada de doble:

public Solution(double[] vector)
{
  this.vector = new double[vector.Length];
  Array.Copy(vector, this.vector, vector.Length);
  this.value = AmoebaProgram.ObjectiveFunction(this.vector, null);
}

Porque la clase de solución se deriva de la interfaz IComparable, la clase debe implementar un método CompareTo. CompareTo se define de modo que objetos de la solución se ordenarán automáticamente de mejores valores (mayores) (menores) a peor de la función objetivo:

public int CompareTo(Solution other)
{
  if (this.value < other.value) return -1;
  else if (this.value > other.value) return 1;
  else return 0;
}

Para la visualización y depuración, la clase de solución define un método ToString simple mediante la concatenación de cadenas:

public override string ToString()
{
  string s = "[ ";
  for (int i = 0; i < this.vector.Length; ++i) {
    if (vector[i] >= 0.0) s += " ";
    s += vector[i].ToString("F2") + " ";
  }
  s += "]  val = " + this.value.ToString("F4");
  return s;
}

La clase de ameba

La clase de la ameba es esencialmente una matriz de objetos de la solución y un método de resolver que utiliza el algoritmo del método de ameba. La estructura de la clase de ameba cotiza en figura 5.

Figura 5 la clase de ameba

public class Amoeba
{
  public int amoebaSize;  // Number of solutions
  public int dim;         // Problem dimension
  public Solution[] solutions;  // Potential solutions (vector + value)
  public double minX;
  public double maxX;
  public double alpha;  // Reflection
  public double beta;   // Contraction
  public double gamma;  // Expansion
  public int maxLoop;   // Limits main solving loop
  public Amoeba(int amoebaSize, int dim, double minX,
    double maxX, int maxLoop) { .
.
}
  public Solution Centroid() { .
.
}
  public Solution Reflected(Solution centroid) { .
.
}
  public Solution Expanded(Solution reflected, Solution centroid) { .
.
}
  public Solution Contracted(Solution centroid) { .
.
}
  public void Shrink() { .
.
}
  public void ReplaceWorst(Solution newSolution) { .
.
}
  public bool IsWorseThanAllButWorst(Solution reflected) { .
.
}
  public Solution Solve() { .
.
}
  public override string ToString() { .
.
}
}

Declaro que todos los campos y métodos utilizando el ámbito público de simplicidad y de más fácil depuración durante el desarrollo. El campo de la amoebaSize especifica el número de posibles soluciones en el objeto de la ameba. En gran medida el valor más común es 3, pero puede que desee experimentar con valores mayores. El dim campo representa el número de variables en la función objetivo que deben ser resueltos para — dos en el caso de la función de Rosenbrock.

Soluciones de la matriz contiene objetos potenciales de la solución. Aunque no está claro de la declaración, soluciones de matriz deben ordenarse en todo momento, desde la mejor solución (campo de valor más pequeño) a la peor solución. MaxX y minX campos restringen los valores iniciales en cada objeto de la solución. Estos valores varían de un problema a problema.

Gamma, beta y alfa de campos son constantes que se utilizan por métodos auxiliares, llamados por el método de resolver. Campo maxLoop limita el número de iteraciones del bucle de procesamiento en Solve.

El constructor de ameba solo crea una matriz de amoebaSize objetos de la solución, cada una de ellas tiene un campo del vector de tamaño dim. Todo el trabajo se realiza por el método Solve; todos los métodos en la clase ameba son métodos auxiliares.

El constructor de la ameba se define como:

public Amoeba(int amoebaSize, int dim, 
  double minX, double maxX, int maxLoop)
{
  this.amoebaSize = amoebaSize;
  this.dim = dim;
  this.minX = minX; this.maxX = maxX;
  this.alpha = 1.0; this.beta = 0.5; this.gamma = 2.0;
  this.maxLoop = maxLoop;
  this.solutions = new Solution[amoebaSize];
  for (int i = 0; i < solutions.Length; ++i)
    solutions[i] = new Solution(dim, minX, maxX);
  Array.Sort(solutions);
}

Gamma, beta y alfa de campos controlan el comportamiento del método Solve y tienen asignados un valor codificado de 0.5, 1.0 y 2.0, respectivamente. Investigaciones han demostrado que estos valores generalmente dan buenos resultados, pero tal vez quiera experimentar. Después de soluciones de matriz se ha asignado, un objeto al azar de la solución se asigna a cada célula. El método Array.Sort ordena las soluciones de mejor a peor.

La clase de ameba tiene un simple método ToString para visualización y depuración más fácil:

public override string ToString()
{
  string s = "";
  for (int i = 0; i < solutions.Length; ++i)
    s += "[" + i + "] " + solutions[i].ToString() +
      Environment.NewLine;
  return s;
}

Los primitivos de algoritmo

Un aspecto clave del algoritmo de optimización de Ameba es que se sustituye la peor solución actual, si conduce a un mejor conjunto de soluciones, por un supuesto punto reflejado, ampliado punto o contratados a punto.

Ameba clase helper método centroide crea un objeto de solución que es en cierto sentido una solución intermedia entre todas las soluciones en la ameba excepto la peor solución (la peor solución es el que tiene el mayor valor de la solución porque el objetivo es minimizar la función objetivo, y se encuentra en el índice amoebaSize-1):

public Solution Centroid()
{
  double[] c = new double[dim];
  for (int i = 0; i < amoebaSize - 1; ++i) 
    for (int j = 0; j < dim; ++j)
      c[j] += solutions[i].vector[j];  
  // Accumulate sum of each component
  for (int j = 0; j < dim; ++j)
    c[j] = c[j] / (amoebaSize - 1);
  Solution s = new Solution(c);
  return s;
}

Método auxiliar reflejado crea un objeto de la solución que está en la dirección general de mejores soluciones. Alfa constante, que normalmente se establece a 1.0, controla la distancia del centroide moverse producir la solución reflejada. Valores más grandes de alfa generan reflejadas puntos que están más lejos el centroide:

public Solution Reflected(Solution centroid)
{
  double[] r = new double[dim];
  double[] worst = this.solutions[amoebaSize - 1].vector;  // Convenience only
  for (int j = 0; j < dim; ++j)
    r[j] = ((1 + alpha) * 
    centroid.vector[j]) - (alpha * worst[j]);
  Solution s = new Solution(r);
  return s;
}

Método auxiliar ampliada crea un objeto de la solución que está incluso más lejos el centroide de la solución reflejada. Gamma constante, que normalmente se establece a 2.0, controla el punto se refleja hasta qué punto es desde el centroide:

public Solution Expanded(Solution reflected, Solution centroid)
{
  double[] e = new double[dim];
  for (int j = 0; j < dim; ++j)
    e[j] = (gamma * reflected.vector[j]) + 
    ((1 - gamma) * centroid.vector[j]);
  Solution s = new Solution(e);
  return s;
}

Método auxiliar contratados crea un objeto de solución que es más o menos entre la peor solución y el centroide. Beta constante, que normalmente se establece a 0.50, controla tan cerca a la peor solución que lo contratado es:

public Solution Contracted(Solution centroid)
{
  double[] v = new double[dim];  // Didn't want to reuse 'c' from centroid routine
  double[] worst = 
    this.solutions[amoebaSize - 1].vector;  // Convenience only
  for (int j = 0; j < dim; ++j)
    v[j] = (beta * worst[j]) + 
    ((1 - beta) * centroid.vector[j]);
  Solution s = new Solution(v);
  return s;
}

Método auxiliar ReplaceWorst reemplaza la peor solución actual, situada en el índice amoebaSize-1, con una solución diferente (reflejada, ampliado o contratados punto):

public void ReplaceWorst(Solution newSolution)
{
  for (int j = 0; j < dim; ++j)
    solutions[amoebaSize-1].vector[j] = newSolution.vector[j];
  solutions[amoebaSize - 1].value = newSolution.value;
  Array.Sort(solutions);
}

Si se refleja, ni ampliado, ni lo contratado da un mejor conjunto de soluciones, el algoritmo de la ameba contrae el conjunto actual de solución. Cada punto de la solución, excepto el mejor punto en el índice 0, se mueve a medio camino desde su ubicación actual hacia lo mejor:

public void Shrink()
{
  for (int i = 1; i < amoebaSize; ++i)  // start at [1]
  {
    for (int j = 0; j < dim; ++j) {
      solutions[i].vector[j] =
        (solutions[i].vector[j] + solutions[0].vector[j]) / 2.0;
      solutions[i].value = AmoebaProgram.ObjectiveFunction(
        solutions[i].vector, null);
    }
  }
  Array.Sort(solutions);
}

El método de resolver

La optimización de la ameba resolver algoritmo se da figura 6, en pseudocódigo de alto nivel.

Figura 6 la optimización de la ameba resolver algoritmo

generate amoebaSize random solutions
while not done loop
  compute centroid
  compute reflected
  if reflected is better than best solution then
    compute expanded
    replace worst solution with better of reflected, expanded
  else if reflected is worse than all but worst then
    if reflected is better than worst solution then
      replace worst solution with reflected
    end if
    compute contracted
    if contracted is worse than worst
      shrink the amoeba
    else
      replace worst solution with contracted
    end if
  else
    replace worst solution with reflected
  end if
end loop
return best solution found

A pesar de que el algoritmo es corto, es un poco más complicado de lo que aparece por primera vez y probablemente tendrás que examinarla muy de cerca, si usted quiere modificar por alguna razón.Método auxiliar IsWorseThanAllButWorst hace que el método de resolución bastante un poco más ordenado.El ayudante examina un objeto de la solución y devuelve true sólo si el objeto de la solución (siempre la solución reflejada en el algoritmo) es peor (tiene un mayor valor de la función objetivo) que todas las demás soluciones en la ameba, excepto posiblemente la peor solución (situada en el índice amoebaSize-1):

public bool IsWorseThanAllButWorst(Solution reflected)
{
  for (int i = 0; i < amoebaSize - 1; ++i) {
    if (reflected.value <= solutions[i].value) // Found worse solution
      return false;
  }
  return true;
}

Con todos los métodos auxiliares en su lugar, el método Solve, enumerados en figura 7, es bastante corto. El bucle de procesamiento en Solve sale después de iteraciones de maxLoop. En general, una buena relación de maxLoop varía de un problema a problema y debe ser determinada por ensayo y error. Una condición de parada alternativo o adicional es salir del bucle de procesamiento cuando el promedio de errores de las soluciones en la ameba cae por debajo de cierto valor dependiente del problema.

Figura 7 el método de resolver

public Solution Solve()
{
  int t = 0;  // Loop counter
  while (t < maxLoop)
  {
    ++t;
    Solution centroid = Centroid();
    Solution reflected = Reflected(centroid);
    if (reflected.value < solutions[0].value)
    {
      Solution expanded = Expanded(reflected, centroid);
      if (expanded.value < solutions[0].value)
        ReplaceWorst(expanded);
      else
        ReplaceWorst(reflected);
      continue;
    }
    if (IsWorseThanAllButWorst(reflected) == true)
    {
      if (reflected.value <= solutions[amoebaSize - 1].value)
        ReplaceWorst(reflected);
      Solution contracted = Contracted(centroid);
      if (contracted.value > solutions[amoebaSize - 1].value)
        Shrink();
      else
        ReplaceWorst(contracted);
      continue;
    }
    ReplaceWorst(reflected);
  } // loop
  return solutions[0];  // Best solution
}

Personalizar el código

El código de ejemplo y explicación presentados en este artículo deben conseguir tú arriba y corriendo si desea experimentar con o utilizar la optimización del método de ameba en un sistema de software. Hay varias modificaciones, que quizás quiera considerar. En el circuito del algoritmo principal, antes de computación el centroide y soluciones reflejadas, yo a menudo computar una solución puramente aleatoria y verifique si esta solución al azar es mejor que la peor solución actual. Este enfoque ayuda a evitar que el algoritmo de optimización quedar atascado en una solución mínima local.

Otra posibilidad de personalización es calcular varios puntos reflejadas. En lugar de un único punto reflejado que se encuentra en la línea entre la peor solución actual y el centroide, puedes calcular puntos reflejadas adicionales que se encuentran en diferentes líneas. Este enfoque también ayuda a evitar las trampas de los mínimos locales.

Dr.James McCaffrey trabaja para Volt Information Sciences Inc., donde dirige el entrenamiento técnico para ingenieros de software trabajando en el Microsoft Redmond, Washington, campus. Ha trabajado en varios productos de Microsoft Internet Explorer y MSN Search. Él es el autor de ".NET Test Automation recetas" (Apress, 2006) y puede ser contactado en jammc@microsoft.com.

Gracias a los siguientes expertos técnicos por su ayuda en la revisión de este artículo: Darren Gehring (Microsoft) y Mark Marron (Microsoft)
Mark Marron trabaja para Microsoft Research en Redmond, Washington. Recibió una licenciatura en matemática aplicada de la UC Berkeley y su pH.d. de la Universidad de nuevo México. Su experiencia es en el área de programa de análisis y síntesis de programa, con énfasis en utilizar esta información para apoyar la optimización y aplicaciones de la ingeniería de software. Su sitio Web está en https://research.microsoft.com/en-us/um/people/marron/.
Darren Gehring es un Test Manager en Microsoft Research en Redmond, Washington. Antes de trabajar en Microsoft Research, trabajó en el grupo de producto de Microsoft SQL Server durante 10 años. Página de Web de Darrenes en https://research.microsoft.com/en-us/people/darrenge/.