Метод роя частиц

Метод роя частиц (particle swarm optimization, PSO) относится к искусственному интеллекту (artificial intelligence, AI) и применим для поиска приближенных решений крайне сложных или нерешаемых задач нахождения числовых максимумов и минимумов. Версия PSO, о которой я расскажу в этой статье, впервые была представлена в научной статье Дж. Кеннеди (J. Kennedy) и Р. Эберхарта (R. Eberhart) в 1995 г. PSO имитирует групповое поведение, например стаи птиц и косяка рыб. Лучший способ прочувствовать, что такое PSO, и понять, куда я держу курс, изучить рис. 1.

В первой части экранного снимка описывается фиктивная задача, решаемая демонстрационной программой PSO. Цель — найти значения x₀and x₁ при которых значение функции f = 3 + x₀² + x₁²минимально.Здесь я обозначаю операцию возведения в квадрат с помощью нотации ^2.. Заметьте, что я умышленно выбрал нереалистично простую задачу, чтобы не затуманивать идеи PSO. Очевидно, что решение этой задачи: x₀ = 0.0 и x₁ = 0.0, при которых минимальное значение функции равно 3,0, поэтому нужды в использовании здесь PSO на самом деле нет. Более реалистичные задачи, которые можно решить методом PSO, мы обсудим позже.В этом примере размерность пространства функции (dimension of function), для которой нужно найти минимум, равна 2, так как мы должны найти решения для двух числовых значений.В целом, PSO отлично подходит для числовых задач с размерностями пространства от двух и больше. В большинстве ситуаций PSO требует некоторых ограничений на диапазон возможных значенийx.Здесь x₀ и x₁ произвольно ограничены диапазоном от –100,0 до 100,0.

В целом, PSO отлично подходит для числовых задач с размерностями пространства от двух и больше.

Рис. 1. Демонстрация метода роя частиц

В следующей части рис. 1 указывается, что программа PSO использует 10 частиц и что она выполнит 1000 итераций. Как вы вскоре увидите, каждая частица представляет возможное решение задачи методом PSO. PSO является итеративным методом, и в большинстве случаев невозможно узнать, когда было найдено оптимальное решение. Следовательно, алгоритмы PSO обычно требуют задания некоего лимита на количество выполняемых итераций.

В следующих строках на рис. 1 видно, что каждые 10 частиц в рое инициализируются случайной позицией. Позиция частицы представляет возможное решение выполняемой задачи оптимизации. Лучшая начальная позиция, сгенерированная случайным образом, — это x₀ = 26.53 и x₁ = -6.09, что соответствует добротности (мера качества решения), равной 3 + 26,53² + (-6.09)² = 744.12. Затем алгоритм PSO входит в основной цикл обработки, где позиция каждой частицы изменяется при каждом проходе цикла. Процедура изменения — это сердцевина PSO, и я подробно расскажу о ней немного позже. После 1000 итераций алгоритм PSO фактически нашел оптимальное решение: x₀ = 0.0 and x₁ = 0.0,однако позвольте мне еще раз подчеркнуть, что в большинстве случаев вы не узнаете, нашла ли программа PSO оптимальное решение.

В этом статье я детально рассмотрю алгоритм PSO, и мы пошагово пройдем по строкам программы, выполнение которой было показано на рис. 1. Я написал эту демо-программу на C#, но ее код легко адаптировать для какого-нибудь другого языка, например Visual Basic .NET или Python. Полный исходный код программы, представленной в моей статье, доступен по ссылке code.msdn.microsoft.com/mag201108PSO. В этой статье предполагается, что вы владеете навыками кодирования на среднем уровне в современном процедурном языке, но знания PSO или соответствующих методов AI от вас не требуется.

Частицы

При использовании PSO возможное решение задачи числовой оптимизации представляется позицией частицы. Вдобавок у каждой частицы есть текущая скорость, которая отражает ее абсолютную величину (magnitude) и направление к новому, предположительно лучшему, решению/позиции. У частицы также имеются мера добротности ее текущей позиции, лучшая известная позиция (т. е. предыдущая позиция с лучшей известной добротностью) и добротность лучшей известной позиции. Я написал класс Particle, как показано на рис. 2.

Рис. 2. Определение частицы

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;
  }
} // класс Particle

У класса Particle пять открытых полей данных: position, fitness, velocity, bestPosition и bestFitness. Для простоты я предпочел использовать открытые поля, но можно применять закрытые поля с аксессорами get и set. Поле position является массивом типа double и представляет возможное решение изучаемой задачи оптимизации. Хотя PSO применим для решения не числовых задач, в целом он лучше подходит для числовых. Поле fitness — это мера того, насколько хорошим является решение, представленное позицией. Для задач нахождения минимумов, которые относятся к наиболее распространенным типам проблем, решаемых PSO, меньшие значения поля fitness лучше больших; однако для задач нахождения максимумов все с точностью до наоборот: большие значения поля fitness лучше.

Поле velocity — массив типа double; представляет информацию, необходимую для обновления текущей позиции/решения частицы. Вскоре я подробно объясню, что такое скорость частицы. Четвертое и пятое поля в типе Particle — bestPosition и bestFitness. В этих полях хранятся соответственно лучшая позиция/решение, найденная объектом Particle, и добротность лучшей позиции.

У класса Particle единственный конструктор, который принимает пять параметров, соответствующих пяти полям этого класса. Конструктор просто копирует значение каждого параметра в соответствующее поле данных. Поскольку все пять полей в Particle являются открытыми, я мог бы просто присваивать значения полям с помощью выражений в коде, минуя конструктор, но считаю, что наличие конструктора дает более четкий код.

Я написал демо-программу на C#, но ее код легко адаптировать для какого-нибудь другого языка.

В определении класса Particle содержится метод ToString, который «вторит эхом» значения пяти полей данных. Из-за того, что я объявил поля position, fitness, velocity, bestPosition и bestFitness открытыми, метод ToString, как и конструктор, на самом деле не требуется для просмотра значений объекта Particle, но его включение упрощает просмотр полей и полезно при отладке в стиле WriteLine. В методе ToString я использую конкатенацию строк вместо более эффективного класса StringBuilder для того, чтобы упростить рефакторинг моего кода для языка, не основанного на Microsoft .NET Framework.

Алгоритм PSO

Хотя в своей основе алгоритм PSO довольно прост, вы должны хорошо понимать его, чтобы иметь возможность модифицировать код в этой статье под свои потребности. PSO является итеративным процессом. На каждой итерации в основном цикле обработки сначала обновляется текущая скорость каждой частицы; при этом учитываются текущая скорость частицы, локальная информация частицы и глобальная информация роя. Затем позиция каждой частицы обновляется с использованием значения новой скорости этой частицы. С точки зрения математики эти два уравнения обновления выглядят так:

{Для верстки: сохраните выделения полужирным в следующих уравнениях.}

v(t+1) = (w * v(t)) + (c₁ * r₁ * (p(t) – x(t)) + (c₂ * r₂ * (g(t) – x(t))

 x(t+1) = x(t) + v(t+1)

Не спешите: процесс обновления позиции на самом деле намного проще, чем предлагаемые уравнения. Первое уравнение предназначено для обновления скорости частицы. Член уравнения v(t+1) обозначает скорость в момент t+1. Заметьте: v выделено полужирным, указывая на то, что скорость является векторной величиной и имеет множество компонентов вроде {1.55, -0.33}, а не просто одно скалярное значение. Новая скорость зависит от трех членов. Первый — w * v(t). Множитель w называется весовой долей инерции (inertia weight) и просто является константой, например 0,73 (подробности — чуть позже); v(t) — это текущая скорость в момент t. Второй член — c₁ * r₁ * (p(t) – x(t)). Множительc₁— константа, называемая когнитивной (или персональной, или локальной) весовой долей. Множительr₁ является случайной переменной в диапазоне [0, 1), а значит, может принимать значения от 0 до любого значения, меньше 1. Векторная величина p(t) — это лучшая позиция частицы, найденная на данный момент, а векторная величинаx(t) — текущая позиция частицы. Третий член в уравнении обновления скорости — (c₂ * r₂ * (g(t) – x(t)).Множитель c₂ является константой, называемой социальной (или глобальной) весовой долей. Множительr₂— случайная переменная в диапазоне[0, 1). Величина вектора g(t) — лучшая известная позиция, найденная на данный момент любой из частиц в рое. Как только определяется новая скорость, v(t+1),она используется для вычисления новой позиции частицы — x(t+1).

Для простоты я предпочел использовать открытые поля, но можно применять закрытые поля с аксессорами get и set.

Конкретный пример поможет прояснить процесс обновления. Допустим, вы пытаетесь найти минимум функции 3 + x₀² + x₁², как было описано во вступительной части статьи. График этой функции приведен на рис. 3. Основание охватывающего куба на рис. 3 представляет значения x₀ and x₁, а вертикальная ось — значение функции. Заметьте, что поверхность графика минимизируется при f = 3, когда x₀ = 0 и x₁ = 0.

{Рисунок}

Рис. 3. График f = 3 + x₀² + x₁²

Пусть текущая позиция частицы, x(t), равна {x0, x1} = {3,0, 4,0}, а ее текущая скорость, v(t), — {–1,0, –1,5}. Также предположим, что константа w = 0,7, константа c1 = 1,4, константа c2 = 1,4, а случайные числа r1 и r2 соответственно равны 0,5 и 0,6. Наконец, допустим, что лучшая известная позиция частицы — p(t) = {2,5, 3,6} и глобальная лучшая известная позиция любой частицы в рое — g(t) = {2,3, 3,4}. Тогда значения новой скорости и позиции будут следующими:

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}

Вспомните, что оптимальное решение таково: {x0, x1} = (0,0, 0,0}. Заметьте, что процесс обновления улучшил прежнюю позицию/решение с (3,0, 4,0} до {1,36, 2,17}. Если вы немного поразмыслите, то увидите, что новая скорость равна старой (помноженной на весовую долю) плюс множитель, который зависит от лучшей известной позиции частицы, плюс другой множитель, который зависит от лучшей известной позиции всех частиц в рое. Следовательно, новая позиция частицы смещается в более оптимальную на основе лучших известных позиций данной частицы и всех частиц. График на рис. 4 показывает движение одной из частиц в течение первых восьми итераций, выполненных демо-программой PSO. Частица начинает с x0 = 100,0, x1 = 80,4 и движется к оптимальному решению x0 = 0, x1 = 0. Спиральное движение типично для PSO.

Рис. 4. Движение частицы к оптимальному решению

Реализация алгоритма PSO

На рис. 5 представлена общая структура программы PSO, вывод которой был показан на рис. 1.

Рис. 5. Структура программы 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;
 
        // Инициализируем все объекты Particle
 
        double w = 0.729; // весовая доля инерции
        double c1 = 1.49445; // когнитивная весовая доля
        double c2 = 1.49445; // социальная весовая доля
        double r1, r2; // рандомизация
 
        // Основной цикл обработки
 
        // Отображаем результаты
        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]);
    }
 
  } // конец класса Program
 
  public class Particle
  {
    // здесь определение
  }
 
}

Я использовал Visual Studio, чтобы создать проект консольного приложения ParticleSwarmOptimization на C#. Код PSO обходится базовой функциональностью, поэтому он нормально работает с любой версией .NET Framework (от 1.1 до 4). Я удалил все сгенерированные Visual Studio выражения using, кроме предназначенного для ссылки на базовое пространство имен System. Я объявил объект типа Random для генерации случайных когнитивных и социальных весовых долей, описанных в предыдущем разделе. Я также использовал этот объект для генерации случайных начальных скоростей и позиций для каждого объекта Particle. В методе Main я обертываю весь свой код в одно выражение try верхнего уровня для перехвата любых исключений.

После создания экземпляра объекта Random с произвольным зародышевым значением 0 я инициализирую некоторые ключевые переменные PSO:

int numberParticles = 10;
int numberIterations = 1000;
int iteration = 0;
int Dim = 2;
double minX = -100.0;
double maxX = 100.0;

Я задействовал 10 объектов Particle. Эмпирическое правило гласит: больше объектов Particle — лучше, чем меньше, но может значительно замедлить выполнение программы. Количество итераций основного цикла обработки я задал равным 1000. Это значение зависит от сложности задачи оптимизации и процессорных мощностей вашего компьютера. Обычно программы PSO используют значение между 1000 и 100 000. Переменная iteration — это счетчик, отслеживающий количество итераций основного цикла. Переменная Dim содержит x-значения в решении/позиции. Поскольку моей программе нужно найти значения x0 и x1, которые определяют минимум в 3 + x0^2 + x1^2, я задаю Dim равной 2. Как я упоминал, в большинстве случаев вам потребуется ограничивать x-значения, образующие вектор позиции/решения неким диапазоном в зависимости от конкретной задачи. Без ограничений вы будете вести поиск от double.MinValue до double.MaxValue. Здесь я произвольно ограничиваю x0 и x1 до [–100,0, +100,0].

Далее я создаю экземпляр роя частиц:

Particle[] swarm = new Particle[numberParticles];
double[] bestGlobalPosition = new double[Dim];
double bestGlobalFitness = double.MaxValue;
double minV = -1.0 * maxX;
double maxV = maxX;

Я создаю массив объектов Particle с именем swarm. Я также подготавливаю массив для хранения глобальной лучшей известной позиции, определенной любым Particle, — в алгоритме обозначается как g(t) — и соответствующей добротности этого массива позиций. Далее задаются ограничения для максимального и минимального значений новой скорости. Здесь идея в том, что, поскольку новая скорость определяет новую позицию частицы, мне нежелательно, чтобы величина любого из компонентов скорости была огромной.

Код для инициализации swarm выглядит так:

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

Я перебираю каждый объект Particle в массиве swarm. Для хранения случайной позиции текущего Particle объявляется массив размера Dim. Затем для каждого x-значения позиции генерируется случайное значение между minX (–100,0) и maxX (+100,0). Во многих задачах PSO на практике диапазон каждого x-значения будет разным, поэтому вы должны добавить код, чтобы обрабатывать каждое x-значение в массиве позиций отдельно.

Теперь продолжаем процесс инициализации:

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

Сначала вычисляется качество текущего случайного массива позиций, передавая его в метод ObjectiveFunction. Если вы вернетесь к рис. 5, то заметите, что ObjectiveFunction просто вычисляет значение функции, для которой я пытаюсь найти минимум, а именно: 3 + x0^2 + x1^2. Затем вычисляется случайная скорость для текущего объекта Particle. Получив случайную позицию, ее добротность и случайную скорость, я передаю эти значения конструктору Particle. Вспомните, что четвертый и пятый параметры — это лучшая известная позиция частицы и ее добротность, поэтому при инициализации Particle начальные значения случайной позиции и добротности являются лучшими из известных.

Код инициализации роя заканчивается следующим:

...
  if (swarm[i].fitness < bestGlobalFitness) {
    bestGlobalFitness = swarm[i].fitness;
    swarm[i].position.CopyTo(bestGlobalPosition, 0);
  }
} // конец цикла инициализации

Я проверяю, является ли добротность текущего Particle лучшей на данный момент (минимальной в случае задачи нахождения минимума). Если да, я обновляю массив bestGlobalPosition и соответствующую переменную bestGlobalFitness.

Далее готовимся к вхождению в основной цикл обработки PSO:

double w = 0.729; // весовая доля инерции
double c1 = 1.49445; // когнитивная весовая доля
double c2 = 1.49445; // социальная весовая доля
double r1, r2; // рандомизация

Я задаю для w (весовой доли инерции) значение 0,729. Это значение было рекомендовано в одной из научных статей, где изучалось влияние различных значений параметров PSO на наборе эталонных задач нахождения минимумов. Альтернативный подход заключается в варьировании значения w. Например, если ваш алгоритм PSO настроен на 10 000 итераций, вы могли бы изначально задать w равной 0,90, а затем постепенно уменьшать w до 0,40 с шагом 0,10 через каждые 2000 итераций. Идея динамической w заключается в том, что на ранних этапах работы алгоритма вы исследуете большие изменения в позициях, но впоследствии получаете меньшие перемещения частиц. Переменным c₁ и c₂ (когнитивной и социальной весовым долям) я присваиваю значение 1,49445. И вновь это рекомендуемое значение. Если вы присвоите c₁ значение больше, чем c₂, вы придадите больший вес лучшей известной позиции частицы, уменьшив аналогичный показатель для глобальной лучшей известной позиции роя, и наоборот. Переменные r₁ и r₂ вносят элемент случайности в алгоритм PSO и помогают избежать затыкания алгоритма на неоптимальном локальном минимуме или максимуме.

Потом мы начинаем основной цикл обработки:

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

Каждый объект Particle в массиве swarm перебирается с использованием в качестве индекса переменной i. Я создаю ссылку на текущий объект Particle с именемcurrP для упрощения кода, но мог бы напрямую использовать swarm[i]. Как объяснялось в предыдущем разделе, первый шаг заключается в обновлении вектора скорости каждой частицы. Для текущего объекта Particle я перебираю каждое из значений в массиве скоростей объекта, генерирую случайные значения переменных r₁ и r₂, а затем обновляю каждый элемент скорости, как было показано в предыдущем разделе.

После вычисления нового элемента скорости для текущего объекта Particle я проверяю, находится ли его значение между максимумом и минимумом:

if (newVelocity[j] < minV)
    newVelocity[j] = minV;
  else if (newVelocity[j] > maxV)
    newVelocity[j] = maxV;
} // каждый j
newVelocity.CopyTo(currP.velocity, 0);
...

Если этот элемент выходит за диапазон, я возвращаю его в диапазон. Здесь идея в том, что мне не нужны экстремальные значения для элемента скорости, так как они могли бы вызвать выход новой позиции за границы. После вычисления всех элементов скорости я обновляю массив скоростей текущего объекта Particle, используя удобный .NET-метод CopyTo.

Определив скорость текущего объекта Particle, ее можно применять для вычисления и обновления текущей позиции Particle:

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

И вновь выполняется проверка на попадание в диапазон — на этот раз с каждым элементом новой позиции текущей частицы. В каком-то смысле это избыточная проверка, так как я уже ограничил значение каждого элемента скорости, но на мой взгляд она служит дополнительной гарантией.

Теперь, когда у меня есть новая позиция текущего объекта Particle, я вычисляю новое значение добротности и обновляю поле fitness объекта:

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;
    }
 
  } // каждый Particle
} // основной цикл PSO
...

После обновления текущей частицы я проверяю, соответствует ли новая позиция лучшей известной для этой частицы; я также проверяю, является ли новая позиция лучшей глобальной позицией роя. Заметьте, что с логической точки зрения новая глобальная лучшая позиция может быть только в том случае, если есть лучшая локальная позиция, поэтому я мог бы вложить проверку на глобальную лучшую позицию в проверку на локальную лучшую позицию.

К этому моменту основной цикл PSO завершается, и я могу показать результаты:

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

Расширение и модификация

Теперь, когда вы увидели, как пишется базовый код PSO, давайте обсудим, как можно расширить и модифицировать представленный мной код. Задача, которую я решаю здесь в качестве примера, искусственна в том плане, что для поиска приближенного решения использовать PSO нет нужды, так как у этой задачи есть точное решение. По-настоящему PSO полезен, когда численную задачу крайне трудно или невозможно решить стандартными методами.

Возьмем такую задачу. Вы хотите предсказать счет в матче между командами A и B. У вас есть исторические данные по прошлым результатам игр команд A и B против других команд. Вы математически моделируете исторический рейтинг команды X так, чтобы при победе этой команды ее рейтинг вырастал на некое фиксированное значение (скажем, на 16 очков) плюс другое значение, которое зависит от разницы между рейтингами команд (скажем, на 0,04, умноженное на разницу, если рейтинг команды X меньше, чем у ее соперника). Более того, вы моделируете предсказываемый отрыв команды от соперников как некую функцию разницы рейтингов команд; например, если рейтинг команды X составляет 1720, а команды Y — 1620, ваша модель предсказывает отрыв X от соперника на 3,5 очка. Короче говоря, вы имеете дело с большим объемом данных, и вам нужно определить несколько числовых значений (вроде 16 и 0,04), которые сводят к минимуму ваши ошибки в предсказании. Такая оценка параметров в зависимости от имеющихся данных как раз и относится к тому типу задач, которые лучше всего подходят для решения алгоритмом методом роя частиц.

PSO — лишь один из нескольких AI-методов, основанных на поведении природных систем. Вероятно, самые ближайшие к алгоритмам PSO генетические алгоритмы — Genetic Algorithms (GA). Оба метода отлично подходят для решения сложных численных задач. В последние десятилетия велись очень активные исследования GA. Преимущество PSO над GA заключается в том, что алгоритмы PSO значительно проще в реализации, чем алгоритмы GA. Однако в настоящее время еще не ясно, какой из методов эффективнее (или же они примерно одинаковы по эффективности).

Версия PSO, которую я представил здесь, может быть модифицирована многими способами. Одна особенно интересная модификация состоит в использовании нескольких вторичных роев (sub-swarms) частиц вместо одного глобального роя. При такой организации каждая частица относится к какому-либо вторичному рою, и новая скорость частицы зависит не от трех факторов, а от четырех: предыдущей скорости, лучшей известной позиции частицы, лучшей известной позиции любой частицы во вторичном рое и лучшей известной позиции любой частицы во всех вторичных роях. Смысл деления на вторичные рои в том, чтобы уменьшить вероятность затыкания алгоритма PSO на неоптимальном решении. Насколько мне известно, такая организация алгоритма PSO пока еще не изучалась.

ДжеймсМаккаффри (Dr. James McCaffrey) руководит в компании Volt Information Sciences Inc. повышением квалификации инженеров ПО из Microsoft, работающих в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и MSN Search. Автор книги «.NET Test Automation Recipes» (Apress, 2006). С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи экспертам Полу Коху (Paul Koch), Дэну Либлингу (Dan Liebling), Энн Лумис Томпсон(Anne Loomis Thompson) и Шейну Уильямсу (Shane Williams).