ФЕВРАЛЯ 2016

ТОМ 31 НОМЕР 2

Тесты - Оптимизация на основе распространения тараканов

Джеймс Маккафри | ФЕВРАЛЯ 2016

James McCaffrey Исходный код можно скачать по ссылке msdn.com/magazine/0216magcode.

Оптимизация на основе распространения тараканов (roach infestation optimization) — это численный алгоритм оптимизации, в какой-то мере имитирующий поведение обычных тараканов вроде Periplaneta americana (американский таракан). Да, вы прочли все правильно. Позвольте мне объяснить.

В машинном обучении алгоритм численной оптимизации часто применяется для нахождения набора значений для переменных (обычно называемых весовыми значениями), которые минимизируют некую меру ошибки. Например, в классификации по логистической регрессии используется математическое уравнение, где при наличии n переменных-предикторов нужно определить n+1 весовых значений. Процесс определения весовых значений называют обучением модели. Идея заключается в использовании набора обучающих данных, имеющих известные правильные выходные значения. Алгоритм численной оптимизации находит весовые значения, которые минимизируют ошибку, т. е. разницу между вычисленными и правильными выходными значениями.

Алгоритмов численной оптимизации очень много. Самый распространенный базируется на производных из области математического анализа (calculus derivatives), но существуют и алгоритмы, основанные на поведении природных систем. Их иногда называют имитирующими биологические системы (bio-inspired algorithms). В этой статье поясняется сравнительно новый метод (впервые опубликованный в 2008 году), называемый оптимизацией на основе распространения тараканов (roach infestation optimization, RIO). Оптимизация RIO вольно моделирует поведение стаи тараканов, связанное с поиском и добыванием пищи.

Хороший способ получить представление о том, что такое RIO, и понять, куда я клоню в этой статье, — взглянуть на демонстрационную программу на рис. 1. Цель этой программы — использовать RIO для нахождения минимального значения функции Растригина (Rastrigin function) при восьми входных переменных. Это стандартная эталонная функция, применяемая для оценки эффективности алгоритмов численной оптимизации. Функция имеет известное минимальное значение 0.0 при x = (0, 0, . . 0), где количество нулевых значений равно количеству входных значений.


Рис. 1. Алгоритм оптимизации на основе распространения тараканов в действии

Функция Растригина трудна для большинства алгоритмов оптимизации, так как имеет много пиков и впадин, создающих локальные минимальные значения, в которых могут застрять алгоритмы. Функцию Растригина с восемью входными значениями невозможно легко визуализировать, но можно получить неплохое представление о характеристиках этой функции, изучая ее график для двух входных значений (рис. 2).

Функция Растригина с двумя входными значениями
Рис. 2. Функция Растригина с двумя входными значениями

Rastrigin's function Функция Растригина

Демонстрационная программа задает количество тараканов, равным 20. Каждый моделируемый таракан имеет позицию, которая представляет возможное решение проблемы нахождения минимума. Большее количество тараканов увеличивает шанс на нахождение истинно оптимального решения ценой уменьшения производительности. В RIO обычно используют от 10 до 100 тараканов.

RIO является итеративным процессом и требует указывать максимальное количество циклов. В демонстрации это значение равно 10 000 итераций. Максимальное число итераций будет варьироваться в зависимости от задачи, но обычно используются значения между 1000 и 100 000. В RIO есть элемент случайности, и демонстрационная программа задает начальное (зародышевое) значение 6 для генератора случайных чисел, потому что это дает репрезентативный демонстрационный вывод.

В демонстрации на рис. 1 лучшая (наименьшая) ошибка, связанная с лучшей позицией таракана, которая была найдена на данный момент, отображается через каждые 500 единиц времени. По окончании алгоритма лучшая найденная позиция для любого таракана была x = (0, 0, 0, 0, 0, 0, 0, 0), что фактически является правильным ответом. Но заметьте: если бы максимальное количество итераций было бы задано равным 5000 вместо 10 000, то алгоритм RIO не сумел бы найти этот единственный глобальный минимум. RIO, как и почти все алгоритмы численной оптимизации, не гарантируют на практике нахождение оптимального решения.

В этой статье предполагается, что вы умеете программировать хотя бы на среднем уровне, но ничего не знаете о численной оптимизации или об алгоритме оптимизации на основе распространения тараканов. Демонстрационная программа написана на C#, но у вас не должно возникнуть особых проблем, если вы захотите выполнить рефакторинг кода под другой язык вроде Visual Basic или JavaScript.

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

Общая структура демонстрационной программы

Общая структура программы представлена на рис. 3. Чтобы создать демонстрационную программу, я запустил Visual Studio и выбрал шаблон C# Console Application. Я назвал проект RoachOptimization. В этой программе нет значимых зависимостей от .NET Framework, поэтому подойдет любая недавняя версия Visual Studio.

Рис. 3. Структура демонстрационной программы

using System;
namespace RoachOptimization
{
  class RoachOptimizationProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin roach optimization demo");
      // Сюда помещается код
      Console.WriteLine("End roach demo");
      Console.ReadLine();
    }

    static double[] SolveRastrigin(int dim, int numRoaches,
      int tMax, int rndSeed) { . . }

    public static double Error(double[] x) { . . }
 
    static double Distance(double[] pos1,
      double[] pos2) { . . }

    static void Shuffle(int[] indices, int seed) { . . }

  } // Program

  public class Roach
  {
    // Определяется здесь
  }
}

После загрузки кода шаблона я переименовал в окне Solution Explorer файл Program.cs в более описательный RoachOptimizationProgram.cs, и Visual Studio автоматически переименовала класс Program за меня. В начале кода я удалил все лишние выражения using, оставив только ссылку на пространство имен верхнего уровня System.

Я кодировал демонстрационную программу, используя по большей части подход со статическими методами, а не полноценный объектно-ориентированный подход. Вся управляющая логика программы находится в Main. Этот метод начинает с настройки значений входных параметров алгоритма:

Console.WriteLine("Begin roach optimization demo");
int dim = 8;
int numRoaches = 20;
int tMax = 10000;
int rndSeed = 6;

Переменная dim задает количество входных значений для функции Растригина. В реальном сценарии машинного обучения dim представляет количество весовых значений в модели прогнозирования. Число тараканов задано равным 20. Переменная tMax — это максимальное количество итераций. RIO, как и большинство алгоритмов, имитирующих биологические системы, является вероятностным. Здесь начальное случайное значение равно 6.

Затем параметры RIO выводятся в консоль:

Console.WriteLine("Goal is to minimize Rastrigin's " +
  "function in " + dim + " dimensions");
Console.WriteLine("Problem has known min value = 0.0 " +
  "at (0, 0, .. 0) ");
Console.WriteLine("Setting number of roaches = " +
  numRoaches);
Console.WriteLine("Setting maximum iterations = " +
  tMax);
Console.WriteLine("Setting random seed = " + rndSeed);;

Алгоритм оптимизации на основе распространения тараканов вызывается так:

Console.WriteLine("Starting roach optimization ");
double[] answer = SolveRastrigin(dim, numRoaches,
  tMax, rndSeed);
Console.WriteLine("Roach algorithm completed");

Метод Main завершается отображением результатов:

double err = Error(answer);
Console.WriteLine("Best error found = " +
  err.ToString("F6") + " at: ");
for (int i = 0; i < dim; ++i)
  Console.Write(answer[i].ToString("F4") + " ");
Console.WriteLine("");
Console.WriteLine("End roach optimization demo");
Console.ReadLine();

Алгоритм оптимизации на основе распространения тараканов, представленный в этой статье, основан на научной статье Т. Хэвенса (T. Havens), К. Спейна (C. Spain), Н. Салмона (N. Salmon) и Дж. Келлера (J. Keller) «Roach Infestation Optimization» за 2008 год. Вы найдете эту статью в нескольких местах в Интернете.

Вникаем в алгоритм оптимизации на основе распространения тараканов

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

Выраженный в очень высокоуровневом псевдокоде, алгоритм оптимизации на основе распространения тараканов представлен на рис. 4. На первый взгляд, алгоритм кажется довольно простым; однако в нем есть множество деталей, не очевидных в этом псевдокоде.

Рис. 4. Алгоритм RIO в высокоуровневом псевдокоде

Инициализируем n тараканов в случайных позициях
Цикл tMax раз
  Вычисляем расстояния между всеми тараканами
  Вычисляем медианное расстояние
  Цикл for each таракана
    Вычисляем количество соседей
    Обмениваемся данными с соседями
    if not голоден
      Вычисляем новую скорость
      Вычисляем новую позицию
      Проверяем, является ли эта позиция новой лучшей
    else if голоден
      Перемещаем в новую позицию
    end if
  end for each
Конец цикла
Возвращаем лучшую найденную позицию

Класс Roach

Определение класса Roach начинается так:

public class Roach
{
  public int dim;
  public double[] position;
  public double[] velocity;
  public double error;
...

Поле dim определяет размерность задачи, которая в демонстрации равна 8. Поле position — это массив, который концептуально представляет местоположение таракана, а также возможное решение задачи нахождения минимума. Поле velocity является массивом значений, определяющих, куда будет перемещаться таракан в следующую единицу времени. Например, если dim = 2, position = (5.0, 3.0), а velocity = (1.0, –2.0), таракан переместится в позицию (6.0, 1.0). Поле error — это ошибка, связанная с текущей позицией.

Определение продолжается следующим кодом:

public double[] personalBestPos;
public double personalBestErr;
public double[] groupBestPos;
public int hunger;
private Random rnd;

Поле personalBestPos хранит лучшую позицию, найденную имитируемым тараканом в любой точке в процессе его движения, поле personalBestError — ошибку, соответствующую personalBestPos, а поле groupBestPos — лучшую позицию, найденную любой группой соседних тараканов. Поле hunger — целое число, представляющее, насколько голоден таракан. Объект Random с именем rnd используется для инициализации таракана в случайной позиции.

Определение класса Roach продолжается определением конструктора:

public Roach(int dim, double minX, double maxX,
  int tHunger, int rndSeed)
{
  this.dim = dim;
  this.position = new double[dim];
  this.velocity = new double[dim];
  this.personalBestPos = new double[dim];
  this.groupBestPos = new double[dim];
...

Параметры minX и maxX используются для задания ограничений для компонентов вектора position. Параметр tHunger — это максимальное значение голода. Когда голод таракана достигает значения tHunger, таракан будет двигаться в новое место. Конструктор выделяет пространство для четырех полей-массивов.

Далее конструктор инициализирует объект Random, а потом использует его для присваивания случайного значения начальному значению hunger:

this.rnd = new Random(rndSeed);
this.hunger = this.rnd.Next(0, tHunger);

Затем конструктор присваивает массивам начальной позиции, скорости, индивидуального лучшего места и лучшего места группы случайные значения между minX и maxX:

for (int i = 0; i < dim; ++i) {
  this.position[i] = (maxX - minX) * rnd.NextDouble() + minX;
  this.velocity[i] = (maxX - minX) * rnd.NextDouble() + minX;
  this.personalBestPos[i] = this.position[i];
  this.groupBestPos[i] = this.position[i];
}

Определение конструктора Roach завершается так:

...
    error = RoachOptimizationProgram.Error(this.position);
    personalBestErr = this.error;
  } // конструктор
} // класс Roach

Поле error задается вызовом внешнего метода Error, определенного в классе вызывающей программы. Альтернативный подход — вычислять значение ошибки до вызова конструктора, а затем передавать его в конструктор как параметр.

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

Алгоритм RIO заключен в статический метод SolveRastrigin, определение которого начинается следующим образом:

static double[] SolveRastrigin(int dim, int numRoaches,
  int tMax, int rndSeed)
{
  double C0 = 0.7;
  double C1 = 1.43;
  double[] A = new double[] { 0.2, 0.3, 0.4 };
...

Константы C0 и C1 используются при вычислении новой скорости таракана, как вы вскоре увидите. Значения для этих констант (0.7 и 1.43) взяты из теории роя частиц. Возможно, вы захотите исследовать другие значения.

Тараканы, находящиеся близко друг к другу, называются соседями. Соседи иногда, но не всегда, обмениваются информацией. Массив с именем A хранит вероятности. Первое значение, 0.2, — это вероятность того, что таракан с одним соседом обменяется с ним информацией, второе значение, 0.3, — вероятность того, что таракан обменяется информацией, если у него есть два соседа, третье значение, 0.4, — вероятность обмена информацией, если у таракан три или более соседей.

Эти значения вероятностей (0.2, 0.3, 0.4) отличаются от тех, которые использовались в исходной научной статье. В ней значения вероятностей были (0.49, 0.63, 0.65), что соответствует реальному поведению таракана, описанному в научной статье по биологии. Я обнаружил, что вероятности, соответствующие поведению настоящих тараканов, оказались не столь эффективны, как искусственные значения вероятностей, примененные в демонстрации.

Определение метода SolveRastrigin продолжается так:

int tHunger = tMax / 10;
double minX = -10.0;
double maxX = 10.0;
int extinction = tMax / 4;
Random rnd = new Random(rndSeed);

Локальная переменная tHunger определяет, когда таракан проголодается и покинет свое текущее место и соседей. Например, если tMax равно 10 000, как в демонстрации, то, когда значение hunger таракана достигнет tMax / 10 = 1000, этот таракан переместится в новую позицию.

Переменные minX и maxX задают лимиты в векторе position таракана. Значения (–10.0, +10.0) являются обычными для машинного обучения весами, а также соответствуют обычным ограничениям для функции Растригина. Так, для задачи с размерностью, равной 3, вектор position — это массив из трех ячеек, которые имеют значения между –10.0 и +10.0.

Локальная переменная extinction определяет, когда все тараканы погибнут и возродятся в новых позициях. Этот механизм обеспечивает перезапуск и помогает предотвращать застревание алгоритма в неоптимальном решении.

Локальный объект Random с именем rnd используется алгоритмом в трех целях. Порядок обработки тараканов случаен, обмен информацией между соседними тараканами происходит с определенной вероятностью, и в каждом новом значении velocity таракана имеется случайный компонент.

Метод SolveRastrigin продолжается так:

Roach[] herd = new Roach[numRoaches];
for (int i = 0; i < numRoaches; ++i)
  herd[i] = new Roach(dim, minX, maxX, tHunger, i);

Набором имитируемых тараканов является массив herd. Для групп разных животных придуманы самые интересные названия, например стадо китов, косяк рыб или стадо гусей. Оказывается, группа тараканов называется… нашествием тараканов. (Эта информация может пригодиться вам в споре.)

Заметьте, что переменная индекса цикла, i, передается в конструктор Roach. Переменная индекса действует как случайное начальное значение для объекта Random, который является частью определения класса Roach. Передача переменной индекса цикла в качестве случайного начального значения — распространенный прием в машинном обучении. Определение метода продолжается следующим кодом:

int t = 0;  // счетчик цикла (время)
int[] indices = new int[numRoaches];
for (int i = 0; i < numRoaches; ++i)
  indices[i] = i;

double bestError = double.MaxValue;
double[] bestPosition = new double[numRoaches];
int displayInterval = tMax / 20;

Массив indices хранит значения (0, 1 2, . . numRoaches–1). Этот массив будет перетасован в основном цикле обработки, чтобы каждый раз порядок обработки тараканов был разным. Локальные переменные bestPosition и bestError хранят лучшую позицию/решение и связанную ошибку, найденные любым тараканом в любой момент. Локальная переменная displayInterval определяет, когда в консоль будет выведено сообщение о прогрессе. Затем создается экземпляр матрицы в стиле массив массивов, и в нее помещаются расстояния между всеми парами тараканов:

double[][] distances = new double[numRoaches][];
for (int i = 0; i < numRoaches; ++i)
  distances[i] = new double[numRoaches];

Например, если distances[0][3] = 7.89, то distances[3][0] тоже 7.89 и расстояние между тараканом 0 и тараканом 3 составляет 7.89. Заметьте, что избыточные данные несерьезны, потому что в большинстве случаев у вас не будет огромного количества тараканов.

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

while (t < tMax)
{
  if (t > 0 && t % displayInterval == 0) {
    Console.Write("time = " + t.ToString().PadLeft(6));
    Console.WriteLine(" best error = " +
      bestError.ToString("F5"));
  }
...

Далее вычисляются расстояния между тараканами:

for (int i = 0; i < numRoaches - 1; ++i) {
  for (int j = i + 1; j < numRoaches; ++j) {
    double d = Distance(herd[i].position,
                 herd[j].position);
    distances[i][j] = distances[j][i] = d;
  }
}

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

double[] sortedDists =
  new double[numRoaches * (numRoaches - 1) / 2];
int k = 0;
for (int i = 0; i < numRoaches - 1; ++i) {
  for (int j = i + 1; j < numRoaches; ++j) {
    sortedDists[k++] = distances[i][j];
  }
}

Размер массива проще всего пояснить на примере. Пусть количество тараканов n = 4. Тогда матрица distances будет иметь размер 4×4. Значения по диагонали, [0][0], [1][1], [2][2] и [3][3], будут 0.0 и не должны включаться. Это оставляет шесть значений в [0][1], [0][2], [0][3], [1][2], [1][3] и [2][3]. Вам не нужны идентичные значения расстояний по симметричным индексам [1][0], [2][0] и т. д. Поэтому всего разных значений расстояний будет n * (n–1) / 2. Далее вычисляется медианное расстояние между тараканами, и индексы тараканов случайным образом перетасовываются:

Array.Sort(sortedDists);
double medianDist = sortedDists[sortedDists.Length / 4];
Shuffle(indices, t); // t используется как случайный зародыш

Здесь, поскольку я делю на 4, расстояние составляет одну четвертую от начала массива отсортированных расстояний, так что на самом деле результатом является не медиана, а квартиль (quartile). В исходной научной статье использовали настоящую медиану (делением на 2), но я нашел, что квартиль лучше медианы. Идея в том, что медиана или квартиль определяет, сколько соседей есть у таракана, что в свою очередь влияет на то, насколько близко группируются тараканы. Применение квартили позволяет удерживать тараканы на большем расстоянии, что повышает шансы на нахождение глобального минимального значения для целевой функции.

Индексы тараканов перетасовываются случайным образом через вспомогательный метод Shuffle, который тоже будет вскоре представлен. Заметьте, что переменная-индекс t передается методу Shuffle и выступает в роли зародышевого значения для генератора случайных чисел в Shuffle. Потом начинается цикл обработки каждого таракана:

for (int i = 0; i < numRoaches; ++i) // каждый таракан
{
  int idx = indices[i]; // индекс таракана
  Roach curr = herd[idx]; // ссылка на текущего таракана
  int numNeighbors = 0;
...

Создается ссылка на текущего таракана, herd[idx], и ей присваивается имя curr. Это делается просто для удобства. Затем вычисляется число соседей у текущего таракана:

for (int j = 0; j < numRoaches; ++j) {
  if (j == idx) continue;
  double d = distances[idx][j];
  if (d < medianDist) // является соседом
    ++numNeighbors;
}

Условие j == idx предотвращает включение текущего таракана в качества соседа к самому себе. Далее определяется эффективное количество соседей:

int effectiveNeighbors = numNeighbors;
if (effectiveNeighbors >= 3)
  effectiveNeighbors = 3;

Вспомните, что цель расчета количества соседей заключается в определении вероятности того, что соседи обменяются информацией. Но вероятность обмена информацией одинакова для трех или более соседей. Алгоритм определяет, должен ли состояться обмен информацией:

for (int j = 0; j < numRoaches; ++j) {
  if (j == idx) continue;
  if (effectiveNeighbors == 0) continue;
  double prob = rnd.NextDouble();
  if (prob > A[effectiveNeighbors - 1]) continue;
...

Текущий таракан сравнивается со всеми остальными тараканами. Если у текущего таракана нет соседей, никакого обмена информацией не происходит. Если же у текущего таракана есть один или более соседей, при принятии решения об обмене информацией используется массив вероятностей A. Далее:

double d = distances[idx][j];
if (d < medianDist) { // сосед
  if (curr.error < herd[j].error) { // curr better than [j]
    for (int p = 0; p < dim; ++p) {
      herd[j].groupBestPos[p] = curr.personalBestPos[p];
      curr.groupBestPos[p] = curr.personalBestPos[p];
    }
  }
...

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

...
    else { // [j] лучше, чем curr
      for (int p = 0; p < dim; ++p) {
        curr.groupBestPos[p] = herd[j].personalBestPos[p];
        herd[j].groupBestPos[p] = herd[j].personalBestPos[p];
      }
    }
  } // если сосед
} // j, каждый сосед

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

if (curr.hunger < tHunger) {
  for (int p = 0; p < dim; ++p)
    curr.velocity[p] = (C0 * curr.velocity[p]) +
     (C1 * rnd.NextDouble() * (curr.personalBestPos[p] -
       curr.position[p])) +
     (C1 * rnd.NextDouble() * (curr.groupBestPos[p] -
       curr.position[p]));

Новая скорость имеет три компонента. Первый — прошлая скорость, которая иногда называется инерцией в терминологии алгоритмов роя частиц. Инерция сохраняет движение таракана в прежнем направлении. Второй компонент — лучшая известная позиция таракана, иногда называемая когнитивным членом (cognitive term). Когнитивный компонент предотвращает перемещение таракана в плохие позиции. Третий компонент — лучшая известная позиция соседей данного таракана. Этот компонент более-менее уникален для RIO и не имеет стандартного названия. Он заставляет группы тараканов держаться вместе.

После расчета скорости текущий таракан перемещается:

for (int p = 0; p < dim; ++p)
  curr.position[p] = curr.position[p] + curr.velocity[p];

double e = Error(curr.position);
curr.error = e;

После перемещения текущего таракана проверяем, является ли его нынешняя позиция новой лучшей:

if (curr.error < curr.personalBestErr) {
  curr.personalBestErr = curr.error;
  for (int p = 0; p < dim; ++p)
    curr.personalBestPos[p] = curr.position[p];
}

Затем новая позиция проверяется на предмет того, является ли она новой лучшей глобальной, и увеличивается счетчик голода:

if (curr.error < bestError) {
    bestError = curr.error;
    for (int p = 0; p < dim; ++p)
      bestPosition[p] = curr.position[p];
  }
  ++curr.hunger;
} // если не голоден

Цикл по каждому таракану завершается обработкой голодных тараканов:

else { // таракан голоден
  {
    herd[idx] = new Roach(dim, minX, maxX, tHunger, t);
  }
} // j – индекс таракана

Если счетчик голода таракана достигает порогового значения tHunger, таракан перемещается в новую случайную позицию. После обработки всех тараканов алгоритм проверяет, не пришла ли пора для глобального уничтожения, увеличивая счетчик времени основного цикла и возвращая лучшую позицию, найденную каким-либо тараканом:

if (t > 0 && t % extinction == 0) { // уничтожение?
      Console.WriteLine("Mass extinction at t = " +
        t.ToString().PadLeft(6));
      for (int i = 0; i < numRoaches; ++i)
        herd[i] = new Roach(dim, minX, maxX, tHunger, i);
    }

    ++t;
  } // основной цикл while

  return bestPosition;
} // задача решена

Заметьте, что этот алгоритм содержится в методе с именем SolveRastrigin, а не в методе с более универсальным названием наподобие Solve. Здесь идея в том, что RIO на самом деле является метаэвристическим алгоритмом, а не предписывающим (prescriptive algorithm) и требует адаптации к конкретной задаче нахождения минимума.

Вспомогательные методы

Метод SolveRastrigin вызывает вспомогательные методы Distance, Error и Shuffle. Вспомогательный метод Distance возвращает евклидово расстояние (квадратный корень от суммы квадратичных разностей):

static double Distance(double[] pos1, double[] pos2)
{
  double sum = 0.0;
  for (int i = 0; i < pos1.Length; ++i)
    sum += (pos1[i] - pos2[i]) * (pos1[i] - pos2[i]);
  return Math.Sqrt(sum);
}

Вспомогательный метод Error возвращает квадрат разности между вычисленным значением функции Растригина в позиции x данного таракана и истинным минимальным значением, равным нулю:

public static double Error(double[] x)
{
  double trueMin = 0.0; double rastrigin = 0.0;
  for (int i = 0; i < x.Length; ++i) {
    double xi = x[i];
    rastrigin += (xi * xi) -
      (10 * Math.Cos(2 * Math.PI * xi)) + 10;
  }
  return (rastrigin - trueMin) * (rastrigin - trueMin);
}

Метод Shuffle случайным образом меняет порядок значений в массиве, используя мини-алгоритм Фишера-Йетса:

static void Shuffle(int[] indices, int seed)
{
  Random rnd = new Random(seed);
  for (int i = 0; i < indices.Length; ++i) {
    int r = rnd.Next(i, indices.Length);
    int tmp = indices[r]; indices[r] = indices[i];
    indices[i] = tmp;
  }
}

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

Пара комментариев

Итак, насколько эффективна оптимизация на основе распространения тараканов по сравнению с другими численными методами оптимизации? На основе нескольких ограниченных экспериментов, выполненных мной, по всем признакам одни эталонные задачи RIO решает лучше, чем другие алгоритмы, а другие — хуже. Я пришел к выводу, что, хотя RIO не является фантастически новым универсальным алгоритмом оптимизации, он может быть полезен для некоторых специфических задач нахождения минимума. И конечно же, оптимизация на основе распространения тараканов имеет одно из самых необычных названий во всей компьютерной науке.


Джеймс Маккафри (Dr. James McCaffrey) работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и Bing. С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи экспертам Microsoft Тодду Беллоу (Todd Bello), Марсиано Морено Диасу Коваррубиасу (Marciano Moreno Diaz Covarrubias) и Аллисону Солу (Alisson Sol).