Este artigo foi traduzido por máquina.
Inteligência artificial
Otimização por nuvem de partículas
James McCaffrey
.jpg "James McCaffrey")
Otimização de swarm de partícula (PSO) é uma técnica de inteligência artificial (AI) que pode ser usada para encontrar soluções aproximadas extremamente difícil ou impossível numérico maximização e minimização problemas. A versão do PSO que descrevi neste artigo primeiro foi apresentada em uma pesquisa de 1995 por j. Kennedy e r. Eberhart. Flexível, o PSO é modelado no comportamento do grupo, como, por exemplo, pássaro flocking e schooling de peixe. A melhor maneira de você para ter uma idéia para o qual é o PSO e ver onde eu estou título aqui é examinar a Figura 1.
A primeira parte da figura descreve um problema fictício que está sendo resolvido por um programa do PSO de demonstração. O objetivo é encontrar valores x 0 e 1 de x, o valor da função f = 3 + x 0 ^ 2 + 1 de x ^ 2 é minimizado. Aqui, usarei a notação ^ 2 para indicar a operação multiplies. Observe que escolhi deliberadamente um problema inacreditavelmente simple para manter as idéias do PSO clara. É óbvio que a solução para esse problema é x 0 = 0,0 e x 1 = 0.0, o que produz um valor mínimo de função do 3.0, portanto, não é realmente necessário usar PSO. Falarei sobre os problemas mais realistas que podem ser resolvidos por PSO neste artigo. Neste exemplo, a dimensão da função para minimizar é 2, porque precisamos resolver para 2 valores numéricos. Em geral, o PSO é adequado para problemas numéricos com dimensões de 2 ou maior. Na maioria das situações, o PSO deve ter algumas restrições no intervalo de valores possíveis de x. Aqui x 0 e 1 de x são arbitrariamente limitados para o intervalo de-100.0 como 100,0.
.jpg)
Figura 1 executar a demonstração de otimização de Swarm de partícula
A próxima parte do a Figura 1 indica que o programa do PSO está usando 10 partículas e que o programa irá iterar 1.000 vezes. Como você verá em breve, cada partícula representa uma possível solução para o problema do PSO que está sendo resolvido. PSO é uma técnica iterativa e na maioria dos casos não é possível saber quando foi encontrada uma solução ideal. Portanto, os algoritmos PSO geralmente devem ter algum limite no número de iterações para executar.
A próxima linhas a Figura 1 indicam que cada um dos 10 partículas no swarm é inicializada para uma posição aleatória. A posição de uma partícula representa uma possível solução para o problema de otimização para ser resolvido. O melhor gerado aleatoriamente a posição inicial é x 0 = 26.53 e x 1 =-6.09, que corresponde a uma adequação (medida de qualidade da solução) de 3 + 26.53 ^ 2 + (-6.09) ^ 2 = 744.12. O algoritmo do PSO, em seguida, insere um loop de processamento principal onde a posição do cada partícula é atualizada cada vez que passa através do loop. O procedimento de atualização é o coração do PSO e explicarei em detalhes posteriormente neste artigo. Depois de 1.000 iterações, o algoritmo do PSO na verdade fez encontrará a solução ideal de x 0 = 0,0 e x 1 = 0,0, mas deixe-me enfatizar que, na maioria das situações, que você não saberá se um programa do PSO encontrou uma solução ideal.
Neste artigo, irá explicar em detalhes o algoritmo do PSO e orientá-lo linha por linha, por meio do programa mostrado em execução na a Figura 1. Codifiquei o programa de demonstração em C#, mas você deve ser capaz de adaptar facilmente o código apresentado aqui para outro idioma, como, por exemplo, Visual Basic.NET ou Python. O código-fonte completo do programa apresentados neste artigo está disponível em code.msdn.microsoft.com/mag201108PSO. Este artigo pressupõe que tenham habilidades de codificação intermediárias com uma linguagem moderna de procedimento, mas não assume que saber nada sobre PSO ou técnicas relacionadas do AI.
Partículas
Ao usar o PSO, uma possível solução para o problema de otimização numérica sob investigação é representada pela posição de uma partícula. Além disso, cada partícula tem uma velocidade atual, o que representa uma magnitude e direção na direção de um novo, presumivelmente, melhor solução/posição. Uma partícula também tem uma medida da qualidade da sua posição atual, conhecida melhor posição da partícula (isto é, uma posição anterior com a qualidade mais conhecida) e a qualidade da posição melhor conhecida. Codifiquei uma classe de partículas, como mostrado na a Figura 2.
Figura 2 a definição de partícula
public class Particle
{
public double[] position;
public double fitness;
public double[] velocity;
public double[] bestPosition;
public double bestFitness;
public Particle(double[] position, double fitness,
double[] velocity, double[] bestPosition, double bestFitness)
{
this.position = new double[position.Length];
position.CopyTo(this.position, 0);
this.fitness = fitness;
this.velocity = new double[velocity.Length];
velocity.CopyTo(this.velocity, 0);
this.bestPosition = new double[bestPosition.Length];
bestPosition.CopyTo(this.bestPosition, 0);
this.bestFitness = bestFitness;
}
public override string ToString()
{
string s = "";
s += "==========================\n";
s += "Position: ";
for (int i = 0; i < this.position.Length; ++i)
s += this.position[i].ToString("F2") + " ";
s += "\n";
s += "Fitness = " + this.fitness.ToString("F4") + "\n";
s += "Velocity: ";
for (int i = 0; i < this.velocity.Length; ++i)
s += this.velocity[i].ToString("F2") + " ";
s += "\n";
s += "Best Position: ";
for (int i = 0; i < this.bestPosition.Length; ++i)
s += this.bestPosition[i].ToString("F2") + " ";
s += "\n";
s += "Best Fitness = " + this.bestFitness.ToString("F4") + "\n";
s += "==========================\n";
return s;
}
} // class Particle
A classe de partícula tem cinco membros de dados públicos: posição, adequação, velocity, bestPosition e bestFitness. Quando usando o PSO, simplicidade prefiro usando os campos públicos de escopo, mas talvez você queira usar campos particulares, juntamente com obtém e definir propriedades em vez disso. O campo chamado posição é uma matriz do tipo double e representa uma possível solução para o problema de otimização sob investigação. Embora PSO pode ser usado para solucionar problemas de não-numéricos, é geralmente mais recomendados para a solução de problemas numéricos. Adequação do campo é uma medida da boa como a solução representada pela posição. Para os problemas de redução, que são os tipos mais comuns dos problemas resolvidos por PSO, valores menores do campo de adequação são melhores do que valores maiores; para problemas de maximização, valores maiores de adequação são melhores.
Velocity de campo é uma matriz do tipo double e representa as informações necessárias para atualizar a posição atual/solução de uma partícula. Explicarei velocity de partícula detalhadamente em breve. Os campos de quarto e quinto no tipo de partícula são bestPosition e bestFitness. Esses campos mantêm a melhor posição/solução encontrada pelo objeto partícula e a adequação de associado da melhor posição.
A classe de partícula tem um único construtor que aceita cinco parâmetros que correspondem a cada um dos cinco campos de dados da partícula. O construtor simplesmente copia cada valor de parâmetro para o campo de dados correspondente. Como todos os campos de partícula cinco têm escopo público, eu poderia ter omitido o construtor e usadas apenas instruções de atribuição do campo no código do PSO, mas acha que o construtor leva ao código de limpo.
A definição de classe de partícula contém um método ToString que ecoa os valores dos campos de dados de cinco. Como com o construtor porque declarei que a posição, a adequação, o velocity, bestPosition e bestFitness campos com escopo público, não realmente preciso um método ToString para exibir os valores do objeto de uma partícula, mas incluindo ele simplifica a exibição os campos e ele á útil para depuração de estilo WriteLine durante o desenvolvimento. O método ToString utilizo concatenação de seqüência de caracteres em vez de usar a classe StringBuilder mais eficiente para facilitar o refactor meu código de não-Microsoft.NET Framework idioma base se desejar.
O algoritmo do PSO
Embora o coração do algoritmo de thePSO é bastante simple, você precisará entendê-lo completamente para modificar o código neste artigo para atender às suas necessidades. PSO é um processo iterativo. Em cada iteração de loop de processamento principal do PSO, velocidade atual do cada partícula primeiro é atualizada com base na velocidade atual da partícula, informações de local da partícula e swarm global. Em seguida, a posição do cada partícula é atualizada usando o velocity de novo da partícula. Matemática termos que duas equações de atualização são:
v(t+1) = (w * v(t)) + (c1 * r1 * (p(t) – x(t)) + (c2 * r2 * (g(t) – x(t))
x(t+1) = x(t) + v(t+1)
Seja paciente comigo aqui; o processo de atualização de posição é realmente muito mais simples do que essas equações sugerem. A primeira equação atualiza a velocidade de uma partícula. O termo v(t + 1) significa que a velocidade em vez t + 1. Observe que v está em negrito, indicando que velocity é um valor de vetor e tem vários componentes, como {1,55,-0.33} em vez de ser um único valor escalar. A nova velocidade depende de três termos. O primeiro termo é w * v(t). O fator w é chamado o peso da inércia e é simplesmente uma constante como 0.73 (mais sobre isso em breve); v(t) é a velocidade atual em tempo de t. O segundo termo é c1 * r1 * (p(t) – x(t)). O fator de c1 é uma constante denominada o peso cognitivo (ou pessoal ou local). O fator de r1 é uma variável aleatória no intervalo [0, 1), que é maior ou igual a 0 e estritamente menor que 1. O pvalor de vetor (t) é a melhor posição da partícula encontrada até o momento. O xvalor de vetor (t) é a posição atual da partícula. O terceiro termo na equação de atualização velocity é (c2 * r2 * (g(t) – x(t)). O fator de c2 é uma constante denominada o social — ou global — peso. O fator de r2 é uma variável aleatória no intervalo [0, 1). O **g (**t) o valor de vetor é a posição mais conhecida encontrada por nenhuma partícula até o momento em que o swarm. Uma vez a nova velocidade, v(t+1), tiver sido determinado, ele é usado para calcular a nova posição da partícula x(t + 1).
Um exemplo concreto ajudará a fazer com que o processo de atualização limpar. Suponha que você está tentando minimizar 3 + x 0 ^ 2 + 1 de x ^ 2, conforme descrito na seção Introdução deste artigo. A função é plotada na Figura 3. A base do cubo contendo no a Figura 3 representa valores de x 0 e 1 de x e o eixo vertical representa o valor da função. Note que a superfície de plotagem é minimizada com f = 3 quando x 0 = 0 e x 1 = 0.
.jpg)
Figura 3 a plotagem de f = 3 + x 0 ^ 2 + 1 de x ^ 2
Digamos que uma partícula do atual posição, x(t) é {x 0, 1} = {3.0, 4.0}, e que a partícula atual velocity, v(t) é {-1,0,-1.5}. Suponhamos também que constante w = 0,7, c1 constante = 1.4, constante c2 = 1.4 e números aleatórios r1 e r2 são 0,5 e 0,6 respectivamente. Finalmente, suponha que a partícula da famosa posição é p(t) = {2.5, 3.6} e a posição global mais conhecida por nenhuma partícula no swarm é g(t) = {2,3, 3.4}. Em seguida, os novos valores de velocidade e a posição são:
v(t + 1) = (0,7 * {-1,0,-1.5}) +
(1.4 * 0.5 * {2.5, 3.6} - {3.0, 4.0}) +
(1.4 * 0.6 * {2.3, 3.4} – {3.0, 4.0})
= {-0.70, -1.05} + {-0.35, -0.28} + {-0.59, -0.50}
= {-1.64, -1.83}
x(t + 1) = {3.0, 4.0} + {-1.64,-1.83}
= {1.36, 2.17}
Lembre-se de que a solução ideal é {x 0, 1} = (0,0, 0,0}. Observe que o processo de atualização melhorou a antiga posição/solução de (3.0, 4.0} para {1.36, 2,17}. Se você mull sobre o processo de atualização um pouco, você verá que a nova velocidade é a velocidade do antiga (horários um peso) mais um fator que depende da posição de uma partícula famosa mais outro fator que depende da posição mais conhecida de todas as partículas no swarm. Portanto, a nova posição de uma partícula tende mover na direção de uma posição melhor com base na posição de melhor conhecida da partícula e a posição mais conhecida de todas as partículas. O gráfico na a Figura 4 mostra a movimentação de uma das partículas durante as primeiras oito iterações da demonstração PSO execução. A partícula começa com x 0 = 100.0, x 1 = 80.4 e tende a se mover em direção a solução ideal de x 0 = 0 x 1 = 0. O movimento de espiral é típico de um PSO.
.jpg)
Figura 4 movimento de partícula em direção a solução ideal
Implementando o algoritmo do PSO
Figura 5 apresenta a estrutura geral do programa PSO que produziu o programa executado mostrado na a Figura 1. Usei o Visual Studio para criar um C# de projeto de aplicativo console chamado ParticleSwarmOptimization. O código do PSO é razoavelmente básico, portanto, qualquer versão do.NET Framework (1.1 a 4) funcionará bem. Eu removi tudo Visual Studio gerado usando instruções, exceto para a referência ao namespace System do núcleo. Declarei um objeto de escopo de classe do tipo aleatório para gerar os números aleatórios cognitivas e sociais descritos na seção anterior. Também usei o objeto Random para gerar aleatório Sprite inicial e posições para cada objeto de partícula. Dentro do método Main, quebrar o todo o meu código em um único alto nível tente instrução para capturar exceções.
Figura 5 estrutura de programa do PSO
using System;
namespace ParticleSwarmOptimization
{
class Program
{
static Random ran = null;
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin PSO demo\n");
ran = new Random(0);
int numberParticles = 10;
int numberIterations = 1000;
int iteration = 0;
int Dim = 2; // dimensions
double minX = -100.0;
double maxX = 100.0;
Particle[] swarm = new Particle[numberParticles];
double[] bestGlobalPosition = new double[Dim];
double bestGlobalFitness = double.MaxValue;
double minV = -1.0 * maxX;
double maxV = maxX;
// Initialize all Particle objects
double w = 0.729; // inertia weight
double c1 = 1.49445; // cognitive weight
double c2 = 1.49445; // social weight
double r1, r2; // randomizations
// Main processing loop
// Display results
Console.WriteLine("\nEnd PSO demo\n");
}
catch (Exception ex)
{
Console.WriteLine("Fatal error: " + ex.Message);
}
} // Main()
static double ObjectiveFunction(double[] x)
{
return 3.0 + (x[0] * x[0]) + (x[1] * x[1]);
}
} // class Program
public class Particle
{
// Definition here
}
} // ns
Após instanciar o objeto de Random com um valor de semente arbitrário de 0, inicializo algumas variáveis do PSO principais:
int numberParticles = 10;
int numberIterations = 1000;
int iteration = 0;
int Dim = 2;
double minX = -100.0;
double maxX = 100.0;
Usar o dez objetos de partícula. Como regra geral, mais objetos de partícula são melhores que o menor, mas mais podem reduzir consideravelmente o desempenho do programa. Definir o número de iterações do loop de processamento principal para 1.000. O número de iterações que você vai querer usar dependerá da complexidade do problema que você está tentando otimizar e a capacidade de processamento de sua máquina host. Normalmente, os programas do PSO usam um valor entre 1.000 e 100.000. A variável chamada iteração é um contador para controlar o número de iterações do loop principal. A variável Dim contém o número de valores x em uma solução/posição. Porque meu problema de exemplo precisa localizar os valores de x 0 e 1 de x minimizar 3 + x 0 ^ 2 + 1 de x ^ 2, defina Dim como 2. Como mencionei anteriormente, na maioria das situações do PSO você desejará limitar os valores de x que compõem o vetor de posição/solução para alguns intervalo dependente do problema. Sem alguns limites, você efetivamente pesquisando de double.MinValue para double.MaxValue. Aqui eu arbitrariamente limitar x 0 e 1 de x para [-100.0, +100.0].
Em seguida, me preparar para instanciar o swarm de partícula:
Particle[] swarm = new Particle[numberParticles];
double[] bestGlobalPosition = new double[Dim];
double bestGlobalFitness = double.MaxValue;
double minV = -1.0 * maxX;
double maxV = maxX;
Criar uma matriz de objetos nomeados swarm de partícula. Também configurei uma matriz para manter a posição de melhor conhecida global determinada por nenhuma partícula — indicado por g(t) no algoritmo — e a adequação correspondente dessa matriz de posição. Definir restrições para os valores máximo e mínimos para um novo velocity. A idéia aqui é como um novo velocity determina a posição de uma partícula novo, eu não quero a magnitude de qualquer um dos componentes velocity para ser enorme.
O código para inicializar o swarm é o seguinte:
for (int i = 0; i < swarm.Length; ++i)
{
double[] randomPosition = new double[Dim];
for (int j = 0; j < randomPosition.Length; ++j) {
double lo = minX;
double hi = maxX;
randomPosition[j] = (hi - lo) * ran.NextDouble() + lo;
}
...
Posso iterar em cada objeto de partícula no array denominado swarm. Eu declaro uma matriz de tamanho Dim para manter uma posição aleatória para a partícula atual. Em seguida, para cada valor de x da posição gerar um valor aleatório entre minX (-100.0) e maxX (+100.0). Em muitos problemas PSO realistas, o intervalo para cada valor de x serão diferente, portanto, você terá que adicionar o código para lidar com cada valor de x na matriz de posição separadamente.
Agora, posso continuar o processo de inicialização:
double fitness = ObjectiveFunction(randomPosition);
double[] randomVelocity = new double[Dim];
for (int j = 0; j < randomVelocity.Length; ++j) {
double lo = -1.0 * Math.Abs(maxX - minX);
double hi = Math.Abs(maxX - minX);
randomVelocity[j] = (hi - lo) * ran.NextDouble() + lo;
}
swarm[i] = new Particle(randomPosition, fitness, randomVelocity,
randomPosition, fitness);
...
Primeiro, eu calculo a qualidade da matriz atual posição aleatória, passando a matriz para o método ObjectiveFunction. Se você consultar novamente a a Figura 5, você verá que o método ObjectiveFunction simplesmente calcula o valor da função que estou tentando minimizar, isto é, de 3 + x 0 ^ 2 + 1 de x ^ 2. Em seguida, calculo um velocity aleatório para o objeto atual da partícula. Depois de obter uma posição aleatória, a adequação de posição aleatória e uma velocidade de aleatória, transfiro esses valores para o construtor de partícula. Lembre-se de que o quarto e quinto parâmetros são a posição mais conhecida da partícula e sua adequação associada, portanto, ao inicializar uma partícula inicial aleatório posição e adequação são os valores mais conhecidos.
O código de inicialização de swarm termina com:
...
if (swarm[i].fitness < bestGlobalFitness) {
bestGlobalFitness = swarm[i].fitness;
swarm[i].position.CopyTo(bestGlobalPosition, 0);
}
} // End initialization loop
Posso verificar se a adequação da partícula atual é a melhor (o menor no caso de um problema de minimização) encontrada até o momento de adequação. Em caso afirmativo, posso atualizar matriz bestGlobalPosition e o bestGlobalFitness de variável correspondente.
Em seguida, me preparar para inserir o loop de processamento do PSO principal:
double w = 0.729; // inertia weight
double c1 = 1.49445; // cognitive weight
double c2 = 1.49445; // social weight
double r1, r2; // randomizers
Definir o valor de w, o peso de inércia para 0.729. Esse valor foi recomendado por um trabalho de pesquisa investigou os efeitos dos vários valores de parâmetro PSO em um conjunto de problemas de minimização de benchmark. Em vez de um valor constante único para w, uma abordagem alternativa é variar o valor de w. Por exemplo, se seu algoritmo PSO estiver definido como iterar 10 mil vezes, você pode inicialmente definida w para 0.90 e diminuir gradualmente w para 0,40 reduzindo w 0.10 após todas as iterações de 2.000. A idéia de um w dinâmico é que logo no início do algoritmo que você deseja explorar alterações maiores na posição, mas posteriormente você deseja que os movimentos de partícula menores. Definir os valores para c1 e c2, pesos cognitivas e sociais, para 1.49445. Novamente, esse valor foi recomendado por um estudo de pesquisa. Se você definir o valor de c1 será maior que o valor de c2, coloque o peso mais na posição mais conhecida de uma partícula que na posição da famosa global do swarm e vice-versa. As variáveis aleatórias r1 e r2, adicionar um componente aleatório para o algoritmo do PSO e ajudam a impedir que o algoritmo ficando preso em uma solução de mínima ou máxima local não ideal.
Em seguida, começar o loop de processamento do PSO principal:
for (int i = 0; i < swarm.Length; ++i)
{
Particle currP= swarm[i];
for (int j = 0; j < currP.velocity.Length; ++j)
{
r1 = ran.NextDouble();
r2 = ran.NextDouble();
newVelocity[j] = (w * currP.velocity[j]) +
(c1 * r1* (currP.bestPosition[j] - currP.position[j])) +
(c2 * r2 * (bestGlobalPosition[j] - currP.position[j]));
...
Posso iterar por meio de cada objeto de partícula na matriz swarm usando i como uma variável de índice. Criar uma referência ao objeto atual de partícula chamado currP para simplificar o meu código, mas poderia ter usado swarm [i] diretamente. Conforme explicado na seção anterior, a primeira etapa é atualizar o vetor do cada partícula velocity. Para o objeto atual de partícula, eu percorrer cada um dos valores na matriz de velocidade do objeto, gerar r2 e variáveis aleatórias r1 e atualize cada componente velocity conforme explicado na seção anterior.
Depois de eu computo um novo componente de velocidade para o objeto atual da partícula, posso verificar se esse componente está entre os valores mínimos e máximo para um componente do velocity:
if (newVelocity[j] < minV)
newVelocity[j] = minV;
else if (newVelocity[j] > maxV)
newVelocity[j] = maxV;
} // each j
newVelocity.CopyTo(currP.velocity, 0);
...
Se o componente está fora do intervalo, devo colocá-lo novamente no intervalo. A idéia aqui é que não quero extremas valores para o componente velocity porque valores extremos poderiam causar a minha nova posição para fora dos limites de rotação. Depois de terem sido computados todos os componentes do programa velocity, atualizar matriz de velocidade atual do objeto partícula usando o prático.Método CopyTo da NET.
Depois que a velocidade da partícula atual tiver sido determinada, posso usar a nova velocidade para calcular e atualizar a posição da partícula atual:
for (int j = 0; j < currP.position.Length; ++j)
{
newPosition[j] = currP.position[j] + newVelocity[j];
if (newPosition[j] < minX)
newPosition[j] = minX;
else if (newPosition[j] > maxX)
newPosition[j] = maxX;
}
newPosition.CopyTo(currP.position, 0);
...
Novamente, executo uma verificação de intervalo, desta vez em cada um dos novos componentes de posição da partícula atual. De certa forma, isso é uma verificação redundante porque eu já tenha restringido o valor de cada componente do velocity, mas na minha opinião a verificação extra está garantido por aqui.
Agora que tenho a nova posição do atual do objeto partícula, computar o novo valor de adequação e atualizar o campo de adequação do objeto:
newFitness = ObjectiveFunction(newPosition);
currP.fitness = newFitness;
if (newFitness < currP.bestFitness) {
newPosition.CopyTo(currP.bestPosition, 0);
currP.bestFitness = newFitness;
}
if (newFitness < bestGlobalFitness) {
newPosition.CopyTo(bestGlobalPosition, 0);
bestGlobalFitness = newFitness;
}
} // each Particle
} // main PSO loop
...
Depois de atualizar a partícula atual, posso verificar se a nova posição é a posição mais conhecida da partícula; Posso também verificar se a nova posição é uma melhor posição de swarm globais. Observe que, logicamente, pode haver uma nova posição melhor global somente se houver uma melhor posição local, portanto, poderia ter aninhados a verificação de melhor global dentro da seleção para uma posição melhor local.
Neste momento meu loop de algoritmo PSO principal for concluído e pode exibir meus resultados:
Console.WriteLine("\nProcessing complete");
Console.Write("Final best fitness = ");
Console.WriteLine(bestGlobalFitness.ToString("F4"));
Console.WriteLine("Best position/solution:");
for (int i = 0; i < bestGlobalPosition.Length; ++i){
Console.Write("x" + i + " = " );
Console.WriteLine(bestGlobalPosition[i].ToString("F4") + " ");
}
Console.WriteLine("");
Console.WriteLine("\nEnd PSO demonstration\n");
}
catch (Exception ex)
{
Console.WriteLine("Fatal error: " + ex.Message);
}
} // Main()
Estendendo e modificando
Agora que você já viu como escrever um PSO básica, vamos discutir como você pode estender e modificar o código que apresentei. Resolver o problema do exemplo é artificial no sentido de que não é necessário usar o PSO para encontrar uma solução aproximada, porque o problema ser resolvido exatamente. Onde o PSO é realmente útil é quando o problema numérico sob investigação é extremamente difícil ou Impossível resolver usando técnicas padrão. Considere o seguinte problema. Você deseja prever a pontuação de um jogo de futebol (americano) entre as equipes a e b. Você tem dados históricos que consiste nos resultados anteriores a e b em relação a outras equipes. Você matematicamente modelar a classificação de histórica de uma equipe x de tal forma que se a equipe vence um jogo, a classificação da equipe sobe por algum valor fixo (digamos, 16 pontos), mais outro valor que varia de acordo com a diferença entre as classificações das equipes (digamos 0,04 vezes a diferença, se a equipe de classificação x é menor do que a equipe adversária). Além disso, você modelar a margem prevista da vitória de uma equipe como alguma função da diferença nas classificações da equipe; Por exemplo, se a equipe x é classificada como 1,720 e equipe y é classificada como 1,620, o seu modelo prevê uma margem de vitória x igual a 3,5 pontos. Em suma, você tem uma grande quantidade de dados e precisa determinar vários valores numéricos (como, por exemplo, o 16 e o 0,04) que minimizam os erros de previsão. Essa estimativa orientados por dados de parâmetro é o tipo de problema que está à direita, até os alley do PSO.
PSO é apenas uma das várias técnicas de AI, com base no comportamento dos sistemas naturais. Talvez a técnica mais próxima de algoritmos do PSO é algoritmos genética (GAs). Ambas as técnicas são bem adequadas para problemas difíceis de numéricos. Gás têm sido muito estudados por décadas. Uma vantagem do PSO sobre gás é que os algoritmos do PSO são significativamente mais simples de implementar de gás. Não está claro no momento se PSOs são mais ou menos eficazes de gás ou aproximadamente igual a eles.
A versão do PSO que apresentei aqui pode ser modificada de diversas maneiras. Uma modificação particularmente interessante é usar várias sub-swarms de partículas, em vez de um swarm global. Com design, cada partícula pertence a um sub-swarm e a nova velocidade de uma partícula poderia dependem em termos de quatro em vez de três: o velocity antigo, a posição mais conhecida da partícula, a posição mais conhecida de nenhuma partícula na sub-swarm e a posição mais conhecida de qualquer partícula. A idéia desse design sub-swarm é reduzir as chances do algoritmo do PSO ficando preso em uma solução não ideal. O melhor que o meu conhecimento como um design não ainda foi completamente investigou.
Dr. James McCaffrey trabalha para a Volt Information Sciences Inc., onde gerencia o treinamento técnico para engenheiros de software, trabalhando com a Microsoft Redmond, Wash campus. Ele trabalhou em vários produtos da Microsoft, como Internet Explorer e MSN Search. Dr. McCaffrey é autor de ".NET Test Automation Recipes"(Apress, 2006) e pode ser contatado pelo jammc@microsoft.com.
Graças aos seguintes especialistas técnicos da Microsoft para a revisão deste artigo: Paul Koch, Dan Liebling, Anne Loomis Thompson e Shane Williams