Il presente articolo è stato tradotto automaticamente.

Esecuzione di test

Ameba Metodo ottimizzazione utilizzando c#

James McCaffrey

Scarica il codice di esempio

L'obiettivo di ottimizzazione numerica è di risolvere un'equazione.Ci sono molte tecniche di base di calcolo deterministiche disponibile; Tuttavia, alcuni problemi difficili, soprattutto nelle zone di machine learning e intelligenza artificiale, non possono essere risolto facilmente utilizzando tecniche di ottimizzazione classica.In tali situazioni, alternative come l'ottimizzazione del metodo ameba possono essere di valore.Ottimizzazione del metodo ameba, che tratterò in questo articolo, è simile per alcuni aspetti a particle swarm optimization, che ho descritto nel numero di agosto 2011 di MSDN Magazine (msdn.microsoft.com/magazine/hh335067).

È il modo migliore per capire quali ottimizzazione Metodo ameba e vedere dove sono diretto, è possibile esaminare Figura1, che mostra un programma demo in azione.L'obiettivo di questo programma è quello di trovare i valori di x e y che minimizzare un problema relativamente semplice benchmark standard chiamato funzione di Rosenbrock.Questa funzione è una soluzione nota a x = 1.0 e y = 1.0 quando il valore della funzione è 0.

Figura 1 ameba Metodo Optimization Demo

Il programma demo crea un ameba virtuale che contiene tre possibili soluzioni casuali.Il meglio di queste soluzioni iniziale non è molto buono, a x =-0.66 e y = 5.43, producendo un valore di funzione di 2499.52.Il programma demo chiama un metodo solve e, dietro le quinte, viene utilizzato il metodo ameba iterativamente trovare soluzioni sempre migliore.Dopo 50 iterazioni, l'algoritmo riesce a trovare la soluzione ottima.

Nelle sezioni che seguono I presentare e spiegare il codice sorgente completo per il programma demo.Il codice è disponibile presso archive.msdn.microsoft.com/mag201306TestRun.Questo articolo presuppone che hai competenze di programmazione di livello intermedio con almeno con un moderno linguaggio procedurale.Ho codificato il demo utilizzando c#, ma non dovreste avere troppi problemi la demo in un'altra lingua, ad esempio Visual Basic .NET o Python di refactoring.

L'algoritmo del metodo ameba

L'algoritmo di ottimizzazione del metodo ameba che presento qui è basato sul libro della 1965 ricerca, "Un semplice metodo per la funzione di minimizzazione," di J.A.Nelder e R.Mead.

Le parti principali di questo algoritmo sono illustrate Figura 2.In qualsiasi momento, ci sono diverse soluzioni possibili.Nella maggior parte dei casi, ottimizzazione ameba utilizza tre soluzioni, di colore rosso in figura.Ogni soluzione ha un valore di funzione obiettivo associato, quindi ci sarà una soluzione peggiore (la più alta funzione valore perché l'obiettivo è quello di ridurre al minimo), una soluzione migliore (il più piccolo valore della funzione) e altri (s).

Figura 2 ameba ottimizzazione operazioni Primitive

L'algoritmo è un processo iterativo.Ad ogni passo, tenta di sostituire la soluzione peggiore con un nuovo, migliore soluzione fra tre candidati: un riflesso punto, un punto espanso e una contratta.Ognuno di questi candidati si trova lungo una linea dal punto peggiore attraverso il centroide — un punto che è al centro di tutti i punti tranne il punto peggiore.Nel caso di solito con tre soluzioni, il baricentro si trova a metà strada tra il punto migliore e l'altro punto (non peggiore).

Se il punto di riflesso, né il punto espanso, né il punto contrattato è meglio che l'attuale soluzione peggiore, l'ameba si ristringe spostando tutti i punti, eccetto il punto migliore, a metà strada verso il punto migliore.Alcune ricerche chiamano questo processo più contrazione.

Quando rappresentati graficamente nel tempo, se i tre punti di soluzione corrente sono collegati da una linea (come con la linea tratteggiata nera in Figura 2), le soluzioni formano un triangolo, e il loro movimento è simile a quello di un'ameba strisciare attraverso il suo ambiente.In termini matematici, un triangolo su un piano è chiamato un simplex, pertanto questo algoritmo di ottimizzazione, oltre a essere chiamato il metodo ameba o Nelder-Mead, a volte viene chiamato il metodo del simplesso.

Struttura generale del programma

Ho codificato il programma demo ottimizzazione di ameba come una singola applicazione console c#­cazione.Ho usato Visual Studio 2010 (qualsiasi versione di Visual Studio dovrebbe funzionare) e creato un nuovo progetto denominato ameba­ottimizzazione.Dopo il caricamento del progetto, nella finestra Solution Explorer sono stati rinominati file Program. cs per il AmoebaProgram.cs più descrittivo, quale automatico­camente ribattezzata classe Program.Ho eliminato tutti i necessari modello generato utilizzando le istruzioni tranne l'unica istruzione che fa riferimento il primo livello dello spazio dei nomi System.

La struttura dell'intero programma, con alcuni commenti e istruzioni WriteLine rimosse, è elencata Figura 3.

Figura 3 ameba ottimizzazione struttura del programma

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 funzione obiettivo

Ottimizzazione del metodo ameba è più spesso utilizzato per risolvere un problema di minimizzazione numerica. Generalmente viene chiamata la funzione di minimizzare una funzione di costo o funzione obiettivo. Il programma demo in Figura 1 sta risolvendo un problema fittizio di riferimento matematica chiamato funzione di Rosenbrock. La funzione ha due variabili di input, x e y e viene definita come f(x,y) = 100 * (y - x ^ 2) ^ 2 > + (1 - x) ^ 2 >. La funzione ha una soluzione x = 1.0, y = 1.0, che dà un valore di 0.0. Figura 4 Mostra un grafico tridimensionale della funzione di Rosenbrock.

Figura 4 grafico della funzione obiettivo

In situazioni reali, ottimizzazione ameba è utilizzato per trovare la soluzione ai problemi difficili che sono basati su dati. Si supponga, ad esempio, che si sta cercando di prevedere i prezzi del mercato azionario. Si potrebbe venire con un elenco di fattori che credi sono predittori e un'equazione, ma è necessario determinare un set di costanti numeriche per l'equazione che minimizzano l'errore su un set di dati di training che ha conosciuto i risultati.

La funzione obiettivo per il programma demo è definita nella classe principale del programma:

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

Utilizzare un parametro di input fittizio denominato dataSource per indicare che nella maggior parte dei casi la funzione obiettivo dipende da qualche fonte dati esterna, ad esempio un file di testo o una tabella SQL. Poiché la funzione è dichiarata utilizzando i modificatori statici e public, la funzione è visibile a tutto il codice nel programma demo.

La classe di soluzione

Ottimizzazione di ameba gestisce un insieme di possibili soluzioni, definito in una classe di soluzione:

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 classe deriva dall'interfaccia IComparable affinché gli oggetti soluzione possono essere ordinati automaticamente. Un oggetto Solution ha solo due campi significativi: uno è un array di double denominato vettore che contiene i valori numerici della soluzione, e l'altro è il valore della funzione obiettivo. Io uso campi membro ambito pubblico e rimuovere tutti i error checking per semplicità. L'oggetto Random statico consente il codice generare soluzioni casuali.

Il primo costruttore di soluzione crea una soluzione casuale:

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

Il costruttore accetta una dimensione del problema e i limiti per ogni componente del vettore. La quota per il programma demo è 2 perché la funzione di Rosenbrock ha due variabili di input, x e y. Dopo l'allocazione dello spazio di vettore campo membro, il costruttore assegna valori casuali tra minX e maxX per la matrice del vettore e quindi chiama la funzione obiettivo globalmente accessibile per calcolare il campo valore.

Il secondo costruttore di soluzione crea una soluzione da una matrice specificata di double:

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

Poiché la classe soluzione deriva dall'interfaccia IComparable, la classe deve implementare un metodo CompareTo. CompareTo è definito in modo che gli oggetti soluzione verranno automaticamente ordinati dai migliori (più piccoli) al peggiore (più grandi) valori della funzione obiettivo:

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

Per la visualizzazione e scopi di debug, la classe soluzione definisce un semplice metodo ToString utilizza la concatenazione di stringhe:

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 classe ameba

La classe ameba è essenzialmente una matrice di oggetti soluzione plus un metodo Solve che utilizza l'algoritmo del metodo ameba. La struttura della classe ameba è elencata Figura 5.

Figura 5 la classe 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() { .
.
}
}

Dichiaro che tutti i campi e metodi utilizzando l'ambito pubblico per semplicità e per la più facile debug durante lo sviluppo. Il campo amoebaSize specifica il numero di possibili soluzioni nell'oggetto ameba. Il valore più comune è di gran lunga 3, ma si consiglia di sperimentare con i valori più grandi. Il campo dim rappresenta il numero di variabili nella funzione obiettivo che deve essere risolto per — due nel caso di funzione di Rosenbrock.

Soluzioni di matrice contiene gli oggetti soluzione potenziali. Anche se non è chiaro dalla dichiarazione, soluzioni di matrice devono essere ordinati in tutti i tempi, da (campo di valore più piccolo) la soluzione migliore per soluzione peggiore. MaxX e campi minX vincolare i valori iniziali in ogni oggetto di soluzione. Questi valori variano da problema a problema.

Gamma, beta e campi alpha sono costanti che vengono utilizzate da metodi di supporto chiamati dal metodo Solve. MaxLoop campo limita il numero di iterazioni del ciclo di lavorazione in Solve.

L'unico costruttore di ameba crea una matrice di amoebaSize soluzione oggetti, ognuno dei quali dispone di un campo vettoriale di dimensione dim. Tutto il lavoro è eseguito dal metodo Solve; tutti gli altri metodi nella classe ameba sono metodi di supporto.

Il costruttore di ameba è definito come:

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 e alpha campi controllano il comportamento del metodo Solve e vengono assegnati i valori hardcoded di 0.5, 1.0 e 2.0, rispettivamente. La ricerca ha dimostrato che questi valori generalmente danno buoni risultati, ma si potrebbe desiderare di sperimentare. Dopo soluzioni di matrice è stata allocata, ogni cella viene assegnato un oggetto casuale soluzione. Il metodo Array. Sort ordina le soluzioni dal valore migliore al peggiore.

La classe ameba è un semplice metodo ToString per la visualizzazione e il debug di più facile:

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

Le primitive di algoritmo

Un aspetto chiave dell'algoritmo di ottimizzazione di ameba è che l'attuale soluzione peggiore è sostituita — se conduce ad un migliore set di soluzioni — da un cosiddetto punto riflesso, ampliato punto o punto un contratto.

Ameba classe helper Metodo centroide crea un oggetto di soluzione che è in un certo senso una soluzione intermedia tra tutte le soluzioni in ameba fatta eccezione per la soluzione peggiore (la soluzione peggiore è quella con il più grande valore di soluzione perché l'obiettivo è quello di minimizzare la funzione obiettivo, e si trova all'indice 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;
}

Metodo di supporto riflessa crea un oggetto soluzione nella direzione generale di soluzioni migliori. Alfa costante, in genere impostato su 1.0, controlla come lontano dal centroide di muoversi per produrre la soluzione riflessa. I valori più elevati di alfa generano punti riflessi che sono più lontana dal baricentro:

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

Metodo di supporto espanso crea un oggetto di soluzione che è anche più lontana dal baricentro rispetto alla soluzione riflessa. Gamma costante, in genere impostato su 2.0, controlla quanto è il punto di riflesso dal baricentro:

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

Metodo Helper contratto crea un oggetto di soluzione che è all'incirca tra la soluzione peggiore e il baricentro.Beta costante, tipicamente impostata a 0,50, controlla quanto vicino alla soluzione peggiore che è il punto di contratto:

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

Metodo di supporto ReplaceWorst sostituisce la soluzione peggiore corrente, situata a indice amoebaSize-1, con una soluzione diversa (il riflesso, espansa o contratta 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);
}

Se il riflesso, né l'espanso, né il contratto punto dà un insieme migliore delle soluzioni, l'algoritmo di ameba si restringe il set corrente di soluzione. Ogni punto di soluzione, fatta eccezione per il miglior punto in corrispondenza dell'indice 0, è spostata a metà dalla posizione corrente verso il punto migliore:

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

Metodo Solve

L'ottimizzazione di ameba risolvere algoritmo è dato Figura 6, in pseudo-codice ad alto livello.

Figura 6 l'ottimizzazione ameba risolvere 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

Anche se l'algoritmo è breve, è un po ' più complicato di quanto sembra prima e probabilmente dovrete esaminarlo attentamente se si desidera modificarlo per qualche motivo. Metodo di supporto IsWorseThanAllButWorst rende il metodo Solve abbastanza un po ' più ordinato. L'helper esamina un soluzione oggetto e restituisce true solo se l'oggetto di soluzione (sempre la soluzione riflessa nell'algoritmo) è peggio (ha un valore di funzione obiettivo maggiore) rispetto a tutte le altre soluzioni con l'ameba, tranne forse la peggiore soluzione (che si trova all'indice 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 tutti i metodi di supporto sul posto, il metodo Solve, elencati Figura 7, è piuttosto breve. Il ciclo di elaborazione in Solve esce dopo maxLoop iterazioni. In generale, un buon valore di maxLoop varia da problema a problema e deve essere determinato attraverso prove ed errori. Una condizione di arresto aggiuntivi o alternativi è all'uscita del ciclo di elaborazione quando l'errore medio delle soluzioni nell'ameba scende di sotto di un valore dipendente dal problema.

Figura 7 il metodo di risolvere

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
}

Personalizzazione del codice

Il codice di esempio e spiegazione presentato in questo articolo dovrebbe ottenere operativi se si desidera sperimentare o utilizzare ottimizzazione Metodo ameba in un sistema software.Ci sono diverse modifiche che si potrebbe desiderare di prendere in considerazione.Nel ciclo principale algoritmo, prima calcolo del baricentro e soluzioni riflesse, spesso calcolare una soluzione puramente casuale e controllare per vedere se questa soluzione casuale è meglio che l'attuale soluzione peggiore.Questo approccio aiuta a prevenire l'algoritmo di ottimizzazione di rimanere bloccati in una soluzione di minima locale.

Un'altra possibilità di personalizzazione è quello di calcolare più punti di riflessi.Invece di un singolo punto riflesso che si trova sulla linea tra l'attuale soluzione peggiore e il baricentro, si possono calcolare ulteriori punti riflessi che si trovano su linee diverse.Questo approccio aiuta anche a evitare le trappole di minimi locali.

Dr. James McCaffrey funziona per Volt Information Sciences Inc., dove gestisce la formazione tecnica per gli ingegneri software Microsoft Redmond, Wash., campus. Si è occupato di diversi prodotti Microsoft, inclusi Internet Explorer e MSN Search. Egli è 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: Darren Gehring (Microsoft) e Mark Marron (Microsoft)
Mark Marron lavora per Microsoft Research in Redmond, Washington.Ha conseguito un BA in matematica applicata da UC Berkeley e il pH.d.dall'Università del New Mexico.Sua esperienza è nella zona del programma analisi e sintesi del programma, con un'enfasi sull'utilizzo di queste informazioni per supportare applicazioni di ingegneria del software e ottimizzazione.Il suo sito Web è a https://research.microsoft.com/en-us/um/people/marron/.
Darren Gehring è un Test Manager presso Microsoft Research in Redmond, Washington.Prima di lavorare in Microsoft Research, ha lavorato nel gruppo merceologico Microsoft SQL Server per 10 anni.Pagina Web di Darrenè al https://research.microsoft.com/en-us/people/darrenge/.