Este artigo foi traduzido por máquina.
Execução de teste
Otimização de método de ameba usando c#
.jpg)
O objetivo da otimização numérica é resolver uma equação. Existem muitas técnicas de determinísticas baseada em cálculo disponível; no entanto, alguns problemas difíceis, especialmente nas áreas de aprendizado de máquina e inteligência artificial, não podem ser resolvidos facilmente usando técnicas de otimização clássica. Em tais situações, alternativas, como a otimização do método de ameba podem ser de valor. Otimização de método de ameba, que abordarei neste artigo, é similar em alguns aspectos a otimização de enxame de partículas, que descrevi na edição de agosto de 2011 da MSDN Magazine (msdn.microsoft.com/magazine/hh335067).
É a melhor maneira de entender o que otimização de método de ameba e ver onde eu estou indo é examinar Figura1, que mostra um programa demo em ação. O objetivo deste programa é encontrar os valores de x e y que minimizar um problema relativamente simples de referência padrão chamado função na Rosenbrock. Esta função tem uma solução conhecida no x = 1.0 e y = 1.0, quando o valor da função é 0.
.png "Demo de otimização de método de ameba")
Figura 1 Demo de otimização de método de ameba
O programa de demonstração cria uma ameba virtual que contém três soluções possíveis aleatórias. O melhor dessas soluções inicial não é muito bom, em x =-0.66 e y = 5.43, produzindo um valor da função de 2499.52. O programa de demonstração chama um método de resolução e, nos bastidores, ele usa o método de ameba iterativamente encontrar soluções cada vez melhores. Após 50 iterações, o algoritmo consegue encontrar a solução ideal.
As seções a seguir, apresentar e explicar o código-fonte completo para o programa de demonstração. O código está disponível em archive.msdn.microsoft.com/mag201306TestRun. Este artigo pressupõe que você tem habilidades de programação de nível intermediário, pelo menos com uma moderna linguagem procedural. Eu codifiquei o demo usando o c#, mas você não deve ter muita dificuldade de refatoração a demo para outro idioma, como Visual Basic .NET ou Python.
O algoritmo do método de ameba
O algoritmo de otimização de método de ameba que apresento aqui é baseado no trabalho de pesquisa de 1965, "A simples método para a função de minimização," por J.A. Nelder e R. Mead.
As peças-chave deste algoritmo são ilustradas em Figura 2. Em qualquer momento, existem várias soluções possíveis. Na maioria dos casos, a otimização de ameba usa três soluções, colorido em vermelho na figura. Cada solução tem um valor de função objetivo associado, para que haja uma solução pior (a mais alta função valor porque o objetivo é minimizar), uma melhor solução (o menor valor de função) e outro (s).
.png "ameba operações de otimização primitivas")
Figura 2 ameba operações de otimização primitivas
O algoritmo é um processo iterativo. A cada passo, ele tenta substituir a pior solução com um novo, a melhor solução entre os três candidatos: um ponto refletido, um ponto expandido e um ponto contratado. Cada um dos candidatos encontra-se ao longo de uma linha do ponto pior através do centróide — um ponto que está no meio de todos os pontos, exceto o ponto pior. O caso usual com três soluções, centróide caberá a meio caminho entre o ponto de melhor e o outro ponto (não-pior).
Se o ponto refletido, nem o ponto expandido, nem o ponto contratado é melhor do que a atual solução pior, a ameba encolhe-se, movendo todos os pontos, exceto para o melhor ponto, a meio caminho em direção o ponto de melhor. Alguns trabalhos de pesquisa chamam este processo de contração de vários.
Quando graficamente ao longo do tempo, se os três pontos de solução atual são conectados por uma linha (tal como acontece com a linha tracejada preta em Figura 2), as soluções formam um triângulo, e seu movimento se assemelha ao de uma ameba rastejando através de seu ambiente. Em termos matemáticos, um triângulo sobre um plano é chamado um simplex, então este algoritmo de otimização, além de ser chamado o método de ameba ou o método de Nelder-Mead, às vezes é chamado o método simplex.
Estrutura geral do programa
Eu codifiquei o programa de demonstração de otimização de ameba como um único c# console applicação. Eu usei Visual Studio 2010 (qualquer versão de Visual Studio deve funcionar) e criado um novo projeto chamado amebaotimização. Depois que o projeto carregado, na janela Solution Explorer renomeei arquivo Program. cs para o AmoebaProgram.cs mais descritivo, que automáticamente renomeado classe Program. Eu deletei todos desnecessários modelo gerado usando instruções exceto a única instrução que referencia o namespace de sistema a nível superior.
A estrutura de todo o programa, com alguns comentários e WriteLine instruções removidas, está listada em Figura 3.
Estrutura de programa de otimização de ameba Figura 3
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 { . . }
}
A função objetivo
Otimização de método de ameba é mais frequentemente usada para resolver um problema de minimização numérica. A função de minimizar geralmente é chamada uma função objetiva ou função de custo. O programa de demonstração em Figura 1 é resolver um problema de referência matemática fictício chamado função na Rosenbrock. A função tem duas variáveis de entrada, x e y e é definida como f(x,y) = 100 * (y - x ^ 2) ^ 2 > + (1 - x) ^ 2 >. A função tem uma solução de x = 1.0, y = 1,0, o que dá um valor de 0.0. Figura 4 mostra uma trama tridimensional da função do Rosenbrock.
.png "gráfico da função objetivo")
Figura 4 gráfico da função objetivo
Em situações do mundo real, otimização de ameba é usada para encontrar a solução para problemas difíceis que são baseados em dados. Por exemplo, suponha que você está tentando prever os preços do mercado de ações. Você pode vir acima com uma lista de fatores que você acredita são preditores e uma equação, mas você precisa determinar um conjunto de constantes numéricas para a equação que minimizam o erro em um conjunto de dados de treinamento conhecidos resultados.
A função objetivo para o programa de demonstração é definida na classe principal do 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);
}
Eu uso um parâmetro de entrada fictício chamado dataSource para indicar que, na maioria das situações, a função objetivo depende alguma fonte de dados externa, como um arquivo de texto ou tabela SQL. Porque a função é declarada usando os modificadores públicos e estáticos, a função é visível a todo o código no programa demo.
A classe de solução
Otimização de ameba mantém um conjunto de possíveis soluções, definido em uma classe de solução:
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() { . . }
}
A classe deriva a interface IComparable para que objetos de solução podem ser automaticamente classificados. Um objeto de solução tem apenas dois campos importantes: um é uma matriz de duplo vetor nomeado que contém os valores numéricos da solução, e o outro é o valor da função objetivo. Eu uso campos membro de escopo público e remover todos os erros de verificação para a simplicidade. O objeto aleatório estático permite que o código gerar soluções aleatórias.
O primeiro construtor de solução cria uma solução aleatória:
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);
}
O construtor aceita uma dimensão do problema e limites para cada componente do vetor. A dimensão para o programa de demonstração é 2, porque a função do Rosenbrock tem duas variáveis de entrada, x e y. Após alocar espaço para vetor de campo do membro, o construtor atribui valores aleatórios entre minX e maxX para a matriz de vetor e então chama a função objectiva globalmente acessível para calcular o campo de valor.
O segundo Construtor solução cria uma solução de um especificado matriz de 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);
}
Porque a classe de solução deriva o IComparable interface, a classe deve implementar um método CompareTo. CompareTo é definido para que objetos de solução serão automaticamente classificados dos melhores valores (maiores) (menores) para o pior da função objetiva:
public int CompareTo(Solution other)
{
if (this.value < other.value) return -1;
else if (this.value > other.value) return 1;
else return 0;
}
Para visualização e fins de depuração, a classe de solução define um método ToString simples usando concatenação de seqüência de caracteres:
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;
}
A classe de ameba
A classe de ameba é essencialmente uma matriz de objetos de solução mais um método de resolução que usa o algoritmo do método de ameba. A estrutura da classe de ameba é listada em Figura 5.
Figura 5 da classe 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 os campos e métodos usando o escopo público para simplicidade e depuração mais fácil durante o desenvolvimento. O campo de amoebaSize especifica o número de possíveis soluções no objeto ameba. De longe o valor mais comum é 3, mas você pode querer experimentar com valores maiores. Dim campo representa o número de variáveis na função objetiva que deve ser resolvido para — duas no caso de função na Rosenbrock.
Soluções de matriz contém os objetos de solução potenciais. Embora não seja evidente a partir da declaração, soluções de matriz devem ser classificadas em todos os momentos, da melhor solução (campo de valor menor) a pior solução. MaxX e campos minX restringem os valores iniciais de cada objeto de solução. Esses valores variam de um problema para o problema.
Gama, beta e alfa de campos são constantes que são usadas por métodos auxiliar chamados pelo método Solve. MaxLoop de campo limita o número de iterações do loop de processamento em Solve.
O único Construtor de ameba cria uma matriz de amoebaSize objetos de solução, cada qual tem um campo vetorial de tamanho não ofuscante. Todo o trabalho é executado pelo método Solve; todos os outros métodos na classe ameba são métodos auxiliares.
O construtor de ameba é definido 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);
}
Gama, beta e alfa campos controlam o comportamento do método Solve e são atribuídos valores codificados de 1,0, 0,5 e 2,0, respectivamente. A pesquisa mostrou que esses valores geralmente dão bons resultados, mas você pode querer experimentar. Depois que alocou-se soluções de matriz, um objeto de solução aleatório é atribuído a cada célula. O método Array. Sort classifica as soluções de valor melhor para o pior.
A classe de ameba tem um simples método ToString para visualização e depuração mais 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;
}
Os primitivos de algoritmo
Um aspecto-chave do algoritmo de otimização de ameba é que a atual solução pior é substituída — se ele leva a um melhor conjunto de soluções — por um chamado ponto refletido, expandiu o ponto ou contratados ponto.
Método de auxiliar de classe de ameba centróide cria um objeto de solução que é, em certo sentido, uma solução intermediária entre todas as soluções na ameba exceto a pior solução (a pior solução é aquele com o maior valor de solução, porque o objetivo é minimizar a função objetivo, e será localizado no í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 refletido cria um objeto de solução que está na direção geral de soluções melhores. Constante alfa, normalmente é definida como 1.0, controla quão longe de centróide para mover-se para produzir a solução refletida. Valores maiores de alfa geram refletidos pontos que estão mais longe de centróide:
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 Expanded cria um objeto de solução que é ainda mais distante o centróide do que a solução refletida. Gama constante, normalmente definida como 2.0, controla até que ponto o ponto refletido é de centróide:
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 contrado cria um objeto de solução que é mais ou menos entre a pior solução e centróide. Beta constante, normalmente definida como 0,50, controla como fechar para a pior solução que é o ponto de contratados:
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 substitui a atual solução pior, localizada no índice amoebaSize-1, com uma solução diferente (refletida, expandido ou contraído ponto):
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 refletido, nem o expandido, nem o ponto contratado dá um melhor conjunto de soluções, o algoritmo de ameba encolhe o conjunto atual de solução. Cada ponto de solução, exceto para o melhor ponto no índice 0, é movido pela metade do seu local atual para o ponto de melhor:
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);
}
O método Solve
A otimização de ameba resolver algoritmo é dado Figura 6, em pseudocódigo de alto nível.
Figura 6 a otimização de 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
Mesmo que o algoritmo é curto, é um pouco mais complicado do que ele aparece pela primeira vez e você provavelmente vai ter que examiná-lo atentamente, se você quiser modificá-lo por algum motivo.Método auxiliar IsWorseThanAllButWorst faz com que o método de resolver completamente um bocado mais puro.O auxiliar examina um objeto de solução e retorna true somente se o objeto de solução (sempre a solução refletida no algoritmo) é pior (tem um maior valor da função objetivo) que todas as outras soluções de ameba, exceto possivelmente a pior solução (localizada no í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;
}
Com todos os métodos do helper no lugar, o método de resolução, listados em Figura 7, é um pouco curto. O loop de processamento em Solve é encerrado depois de iterações de maxLoop. Em geral, um bom valor de maxLoop varia de problema para problema e deve ser determinado por tentativa e erro. Uma condição de parada alternativa ou adicional é para sair do loop de processamento, quando o erro médio das soluções da ameba cai abaixo de algum valor dependente do problema.
Figura 7 o 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
}
Personalizando o código
O código de exemplo e explicação apresentada neste artigo devem obter-se e correr se você quiser experimentar ou usar otimização de método de ameba, em um sistema de software.Há várias modificações que você pode querer considerar.O loop de algoritmo principal, antes de computar o centróide e soluções refletidas, eu muitas vezes calcular uma solução puramente aleatória e verificar para ver se esta solução aleatória é melhor do que a atual solução pior.Essa abordagem ajuda a evitar que o algoritmo de otimização ficando preso em uma solução de mínima local.
Outra possibilidade de personalização é calcular vários pontos refletidos.Em vez de um único ponto refletido que se encontra na linha entre a atual solução pior e centróide, você pode computar pontos refletidos adicionais que se encontram em linhas diferentes.Essa abordagem também ajuda a evitar as armadilhas de mínimos locais.
Dr. James McCaffrey trabalha para a Volt Information Sciences Inc., onde gerencia o treinamento técnico para engenheiros de software trabalham no Microsoft Redmond, Wash., campus. Ele trabalhou em vários produtos da Microsoft, incluindo o Internet Explorer e o MSN Busca e Ele é autor de “.NET Test Automation Recipes” (Apress, 2006) e pode ser contatado pelo email jammc@microsoft.com.
Agradecemos aos seguintes especialistas técnicos pela revisão deste artigo: Darren Gehring (Microsoft) e Mark Marron (Microsoft)
Mark Marron funciona para Microsoft Research em Redmond, Washington.Ele recebeu o Bacharelado em matemática aplicada da Universidade de Berkeley e pH.d.da Universidade do Novo México.Sua experiência é na área do análise de programa e síntese de programa, com ênfase em usar esta informação para apoiar a otimização e aplicações de engenharia de software.Seu site é no https://research.microsoft.com/en-us/um/people/marron/.
Darren Gehring é um Gerenciador de teste Microsoft Research em Redmond, Washington.Antes de trabalhar na Microsoft Research, ele trabalhou no grupo de produtos de Microsoft SQL Server por 10 anos.Darrenna página está em https://research.microsoft.com/en-us/people/darrenge/.