Естественные алгоритмы

Используйте алгоритмы пчелиной колонии для решения нерешаемых задач

Джеймс Маккаффри

Загрузка примера кода

Алгоритмы искусственной пчелиной колонии (Simulated Bee Colony, SBC) моделируют поведение медовых пчел и могут быть применены для поиска решений трудных или нерешаемых комбинаторных задач. В этой статье я объясню, что представляют собой алгоритмы SBC, опишу типы задач, которые можно решать с помощью этих алгоритмов, и представлю полноценный пример, где для решения задачи коммивояжера (Traveling Salesman Problem) используется один из алгоритмов SBC.

Хороший способ прочувствовать алгоритмы SBC и понять суть этой статьи — изучить демонстрационную программу, процесс выполнения которой показан на рис. 1. Эта программа использует алгоритм SBC для анализа набора из 20 городов (помеченных буквами от A до T) и поиска кратчайшего маршрута, по которому можно посетить каждый город ровно один раз. Данные по городам искусственно сформированы так, чтобы лучший маршрут начинался в городе A, продолжался вплоть до города T по порядку, а его длина составляла 19,0 единиц.

Рис. 1. Демонстрации алгоритма SBC

За кулисами алгоритм SBC создает экземпляр улья со 100 искусственными пчелами, у каждой из которых имеется случайное потенциальное решение. Изначально лучшее из случайных решений дает длину маршрута, равную 95,0 единицам. Алгоритм SBC входит в цикл обработки (его ход отображается текстовой полоской прогресса), который имитирует поведение обычных медовых пчел, вылетающих на поиски нектара. В конце цикла обработки SBC лучшее найденное решение охватывает 16 городов из 20, а длина маршрута составляет 26,5 — близко к оптимальному решению, но все же не совсем то.

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

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

О пчелах

В обычной колонии пчел, например Apis mellifera (медоносная пчела домашняя), предполагается, что пчелы со временем выполняют разные роли. В типичном улье может быть от 5000 до 20 000 особей. Взрослые особи (в возрасте от 20 до 40 дней), как правило, становятся фуражирами (foragers). Фуражиры обычно выполняют одну из трех ролей: активные фуражиры, фуражиры-разведчики и неактивные фуражиры.

Активные фуражиры летят к источнику нектара, обследуют соседние источники, собирают нектар и возвращаются в улей.

Разведчики обследуют местность вокруг улья (площадью до 50 квадратных миль) в поисках новых источников нектара. Примерно 10% пчел-фуражиров в улье задействованы в качестве разведчиков.

В любой момент некоторое количество пчел-фуражиров неактивно. Они ждут неподалеку от входа в улей. Когда активные фуражиры и разведчики возвращаются в улей, то — в зависимости от качества источника нектара, который они только что посетили, — они могут исполнять виляющий танец (waggle dance) перед ждущими неактивными пчелами. Есть довольно веские доказательства того, что этот виляющий танец несет информацию неактивным пчелам о местонахождении и качестве источника нектара. Неактивные фуражиры извлекают из виляющего танца эту информацию об источниках нектара и могут становиться активными фуражирами.

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

Задача коммивояжера

Задача коммивояжера (Traveling Salesman Problem, TSP) — одна из самых широко изученных задач в области компьютерных наук. Существует множество вариаций TSP, но неформально задача сводится к поиску кратчайшего маршрута, позволяющего посетить каждый город в заданном наборе ровно один раз.

Взглянув на рис. 1 , вы заметите, что демо-программа SBC использует набор из 20 городов, которые произвольно помечены буквами от A до T. Допустимый маршрут состоит из упорядоченного набора меток 20 городов, где каждый город встречается только раз. Следовательно всего имеется 20! = 2 432 902 008 176 640 000 возможных маршрутов.

С каждой парой городов сопоставлено значение расстояния. Простоты ради, если c1 < c2, то расстояние между городами c1 и c2 равно порядковому расстоянию (ordinal distance) между метками городов. Если c1 > c2, расстояние в 1,5 раза больше порядкового расстояния между c1 и c2. Поэтому расстояние от A до B равно 1,0 произвольным единицам, расстояние от B до A — 1,5 единицам, расстояние от A до C — 2,0 единицам и т. д. Следовательно, самый оптимальный маршрут, позволяющий посетить каждый город лишь раз, — A -> B-> C -> ... -> T, а кратчайшая длина маршрута — (20–1) * 1,0 = 19,0.

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

Кроме как в тривиальных ситуациях, «лобовой» поиск кратчайшего пути не применим. Например, при наличии 20 городов, даже если бы вы могли оценивать миллион маршрутов в секунду, анализ всех 20! возможных путей потребовал бы более 77 000 лет. Именно для таких крайне трудных комбинаторных задач оптимизации отлично подходят алгоритмы SBC.

Эквивалент задачи TSP реализуется в классе CitiesData, показанном на рис. 2. Полный исходный код демонстрационной программы SBC доступен по ссылке code.msdn.microsoft.com/mag0411BeeColony.

Рис. 2. Определение класса CitiesData

class CitiesData {
  public char[] cities;

  public CitiesData(int numberCities) {
    this.cities = new char[numberCities];
    this.cities[0] = 'A';
    for (int i = 1; i < this.cities.Length; ++i)
      this.cities[i] = (char)(this.cities[i - 1] + 1);
  }

  public double Distance(char firstCity, char secondCity) {
    if (firstCity < secondCity)
      return 1.0 * ((int)secondCity - (int)firstCity);
    else
      return 1.5 * ((int)firstCity - (int)secondCity);
  }

  public double ShortestPathLength() {
    return 1.0 * (this.cities.Length - 1);
  }

  public long NumberOfPossiblePaths() {
    long n = this.cities.Length;
    long answer = 1;
    for (int i = 1; i <= n; ++i)
      checked { answer *= i; }
    return answer;
  }

  public override string ToString() {
    string s = "";
    s += "Cities: ";
    for (int i = 0; i < this.cities.Length; ++i)
      s += this.cities[i] + " ";
    return s;
  }
}

Определение какого-либо класса или структуры данных, которая представляет вашу конкретную задачу, будет отличаться от определения, приведенного здесь. Однако задачи, хорошо подходящие для решения по алгоритму SBC, как правило, могут быть представлены нечисловым массивом, нечисловой матрицей или нечисловым неровным массивом массивов (jagged array of arrays).

Конструктор CitiesData принимает количество городов и присваивает первому городу метку A, второму — B и т. д.

Метод Distance определен с учетом одностороннего движения, о котором я рассказывал ранее, и предполагает, что каждый город достижим из любого другого города напрямую.

Метод ShortestPathLength возвращает оптимальную длину маршрута для данного определения Distance. В большинстве случаев использования SBC у вас не будет информации, достаточной для реализации метода, который возвращает оптимальное решение.

Метод NumberOfPossiblePaths просто вычисляет n!, где n — это количество городов. В некоторых случаях TSP количество возможных маршрутов равно n–1! (если начальный город не имеет значения), а в других — n/2! (если не имеет значения направление маршрута).

Метод ToString использует конкатенацию строк вместо более эффективного класса StringBuilder для сборки строки с описательными данными. Конкатенация строк применяется, чтобы упростить рефакторинг кода при его переносе в другие языки программирования.

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

Структура SBC-программ

Алгоритм SBC, показанный на рис. 1, реализован как консольное приложение на C#. Общая структура программы приведена на рис. 3. Заметьте, что структура SBC-программы относительно проста, в ней используется лишь базовое пространство имен System. В программе три класса: Program (содержит единственный метод Main), Hive (содержит всю логику алгоритма SBC) и CitiesData (был представлен в предыдущем разделе). Классу Hive присвоено универсальное имя (Hive), а не более специфическое вроде TravelingSalesmanHive, даже несмотря на сильную зависимость реализаций алгоритма SBC от конкретной задачи, решаемой ими.

Рис. 3. Общая структура программы

using System;
namespace SimulatedBeeColony {
  class Program {
    static void Main(string[] args) {
      Console.WriteLine("\nBegin Simulated Bee Colony algorithm demo\n");
      . . . 
      Console.WriteLine("End Simulated Bee Colony demo");
    } 
  } 

  class Hive {
    public class Bee {
      . . . 
    }

    // Hive data fields here

    public override string ToString() { . . . }
    
    public Hive(int totalNumberBees, int numberInactive,
      int numberActive, int numberScout, int maxNumberVisits,
      int maxNumberCycles, CitiesData citiesData) {
      . . .      
    } 

    public char[] GenerateRandomMemoryMatrix() { . . . }
    
    public char[] GenerateNeighborMemoryMatrix(char[] memoryMatrix) { . . . }
    
    public double MeasureOfQuality(char[] memoryMatrix) { . . . }
    
    public void Solve() { . . . }

    private void ProcessActiveBee(int i) { . . . }

    private void ProcessScoutBee(int i) { . . . }

    private void ProcessInactiveBee(int i) { . . . }

    private void DoWaggleDance(int i) { . . . }
  } 

  class CitiesData {
    . . .
  }

} // ns

Метод Main весьма прост. После отображения начального сообщения создается экземпляр CitiesData:

Console.WriteLine(
  "Loading cities data for SBC Traveling Salesman Problem analysis");
CitiesData citiesData = new CitiesData(20);
Console.WriteLine(citiesData.ToString());
Console.WriteLine("Number of cities = " + citiesData.cities.Length);
Console.WriteLine("Number of possible paths = " + 
  citiesData.NumberOfPossiblePaths().ToString("#,###"));
Console.WriteLine("Best possible solution (shortest path) length = " + 
  citiesData.ShortestPathLength().ToString("F4"));

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

Далее подготавливаются инициализирующие значения для Hive и вызывается его конструктор:

int totalNumberBees = 100;
int numberInactive = 20;
int numberActive = 50;
int numberScout = 30;
int maxNumberVisits = 100; 
int maxNumberCycles = 3460;
       
Hive hive = new TravelingSalesmanHive(totalNumberBees,
  numberInactive, numberActive, numberScout, maxNumberVisits,
  maxNumberCycles, citiesData);

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

Значение переменной totalNumberBees можно было бы получать на основе трех других переменных, однако дополнительная переменная улучшает здесь читаемость кода. Общее количество пчел будет зависеть от конкретной задачи. Чем больше пчел, тем лучше, но тем медленнее выполняется программа. Наконец, по эмпирическим наблюдениям наилучшие результаты достигаются при следующем соотношении трех типов пчел: 75% активных, 10% неактивных и 15% разведчиков. 

Значение 100, присвоенное переменной maxNumberVisits, я поясню чуть позже, но оно относится к количеству смежных решений (neighbor solutions), релевантных для данного решения.

Переменная maxNumberCycles используется, чтобы управлять числом итераций процедуры Solve; это необходимо потому, что при применении алгоритма SBC обычно не известно, когда достигается оптимальное решение. (Если вы знаете оптимальное решение, то на самом деле вам нечего решать.) В данном случае значение maxNumberCycles было ограничено до 3460 специально для того, чтобы алгоритм SBC не давал идеального результата. Суть в том, что, хотя алгоритмы SBC могут давать оптимальные результаты, как правило, у вас нет возможности узнать об этом и вы должны стремиться к принятию «хорошего» результата.

При выполнении конструктор создает набор пчел, у каждой из которых есть случайное решение. Объект Hive отслеживает лучший в целом (кратчайший) маршрут, найденный любой из пчел из улья и длину маршрута, сопоставленную с лучшим решением.

После вызова конструктора Hive метод Main использует метод ToString для отображения начальных, случайным образом сгенерированных значений Hive, вызывает метод Solve с параметром, указывающим на необходимость вывода текстовой полоски прогресса, а затем показывает лучший маршрут и связанную с ним длину пути:

...
  Console.WriteLine("\nInitial random hive");
  Console.WriteLine(hive);

  bool doProgressBar = true;
  hive.Solve(doProgressBar);

  Console.WriteLine("\nFinal hive");
  Console.WriteLine(hive);
  Console.WriteLine("End Simulated Bee Colony demo");
}

Класс Bee

Как показано на рис. 3, класс Hive содержит определение вложенного класса Bee. Это определение приведено на рис. 4.

Рис. 4. Определение класса Bee

public class Bee {
  public int status;
  public char[] memoryMatrix;
  public double measureOfQuality; 
  public int numberOfVisits;

  public Bee(int status, char[] memoryMatrix, 
    double measureOfQuality, int numberOfVisits) {
    this.status = status;
    this.memoryMatrix = new char[memoryMatrix.Length];
    Array.Copy(memoryMatrix, this.memoryMatrix, memoryMatrix.Length);
    this.measureOfQuality = measureOfQuality;
    this.numberOfVisits = numberOfVisits;
  }

  public override string ToString() {
    string s = "";
    s += "Status = " + this.status + "\n";
    s += " Memory = " + "\n";
    for (int i = 0; i < this.memoryMatrix.Length-1; ++i)
      s += this.memoryMatrix[i] + "->";
    s += this.memoryMatrix[this.memoryMatrix.Length-1] + "\n";
    s += " Quality = " + this.measureOfQuality.ToString("F4");
    s += " Number visits = " + this.numberOfVisits;
    return s;
  }
}

В классе Bee есть три поля данных, общих для всех реализаций SBC, и одно поле данных, специфичное для конкретной задачи. Последнее поле называется memoryMatrix. В каждой реализации SBC нужно каким-то образом представлять решение. В случае TSP, рассматриваемом в этой статье, решение может быть представлено массивом типа char. Подчеркну, что объект, представляющий решение, сильно зависит от конкретной задачи и что для каждой задачи нужен отдельный анализ, чтобы подобрать осмысленное представление решения.

Поле status содержит значение типа int, которое указывает тип объекта Bee: активная пчела, неактивная или разведчик. Если вы кодируете на языке с поддержкой перечислимых типов, стоит сделать поле status перечислением.

В поле measureOfQuality хранится значение типа double, представляющее добротность memoryMatrix объекта Bee. В случае TSP естественной единицей измерения качества решения является длина маршрута, представленная объектом memoryMatrix. Заметьте, что в этой ситуации более короткие длины лучше, поэтому меньшие значения поля measureOfQuality представляют более эффективные решения. Каждая реализация SBC должна предусматривать какой-либо способ вычисления степени добротности решения. Во многих ситуациях эту единицу лучше всего представлять значением типа double.

Третье общее поле в классе Bee — numberOfVisits. В нем хранится значение типа int, указывающее, сколько раз объект Bee посещал конкретный источник нектара, не находя более эффективного смежного решения. Это поле используется для моделирования пчелы, посещающей источник нектара до тех пор, пока он не иссякнет. Моделируемая пчела, если она относится к активному типу, исчерпает источник, когда значение поля numberOfVisits превысит пороговое значение, и перейдет в неактивное состояние (а неактивная пчела перейдет в активное состояние).

Конструктор Bee принимает значения для этих четырех полей данных — status, memoryMatrix, measureOfQuality и numberOfVisits. Заметьте, что конструктор Bee должен принимать значение для measureOfQuality, так как Bee не может напрямую вычислять его на основе собственного поля memoryMatrix; определение степени добротности зависит от информации, хранящейся в специфичном для конкретной задачи объекте CitiesData.

Определение класса Bee содержит метод ToString, который обеспечивает доступ к значениям четырех полей данных. Метод Bee.ToString не является абсолютно необходимым, но может быть весьма полезен при разработке SBC в обнаружении ошибок с использованием выражений WriteLine.

Поля данных Hive

Код класса Hive показан на рис. 5. В нем 14 полей данных, и знание каждого из них является ключом к пониманию того, как реализуется конкретный алгоритм SBC.

Рис. 5. 14 полей данных Hive

static Random random = null;

public CitiesData citiesData;

public int totalNumberBees; 
public int numberInactive; 
public int numberActive;
public int numberScout;

public int maxNumberCycles;
public int maxNumberVisits; 

public double probPersuasion = 0.90;
public double probMistake = 0.01; 

public Bee[] bees;
public char[] bestMemoryMatrix;
public double bestMeasureOfQuality;
public int[] indexesOfInactiveBees;

Для упрощения отладки с помощью выражений WriteLine все 14 полей данных объявлены открытыми. В производственном коде эти поля стоит сделать закрытыми и создать свойства для тех полей, к которым вам нужно обращаться извне этого класса.

Первое поле, random, имеет тип Random. Алгоритмы SBC являются вероятностными, и для генерации псевдослучайных чисел используется объект random. Экземпляр объекта random будет создаваться в конструкторе Hive.

Второе поле данных — объект типа CitiesData. Реализации SBC должны быть известны детали решаемой задачи. В большинстве случаев, в том числе в данном, исходные данные задачи представляются объектом. Вспомните, что в CitiesData есть список меток городов и метод, который возвращает расстояние между любыми двумя городами.

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

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

Восьмое поле данных, maxNumberVisits, хранит пороговое значение, не дающее пчеле слишком долго задерживаться на одном решении. На каждой итерации основного цикла обработки в методе Solve, если пчела не находит соседний источник нектара с более высоким качеством, счетчик numberOfVisits этой пчелы увеличивается на 1. Как только счетчик numberOfVisits в объекте Bee превысит пороговое значение maxNumberVisits, пчела переходит в неактивное состояние.

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

Значение probPersuasion «зашито» в код и равно 0.90, т. е. неактивная пчела будет считать необходимым принять более удачное решение в 90% случаев. Значение probPersuasion, равное 0.90, получено в результате исследований, но вы можете поэкспериментировать с другими значениями. Более высокие значения будут заставлять алгоритм SBC быстрее приближаться к конечному решению, но вероятность того, что это решение окажется менее оптимальным, будет возрастать.

Десятое поле данных, probMistake, является вероятностным пороговым значением, позволяющим указать, будет ли ошибаться активная пчела, т. е. ошибочно отклонять смежное решение (соседний источник нектара), более эффективное ее текущего решения, или ошибочно принимать смежное решение, хуже текущего. Значение probMistake «зашито» в код и равно 0.01, а это означает, что активная пчела будет ошибаться в оценке смежного решения примерно в 1% случаев.

Одиннадцатое поле данных, bees, — это массив объектов Bee. Вспомните, что у каждой пчелы имеются состояние (активная, неактивная, разведчик), решение (memoryMatrix), степень добротности решения (measureOfQuality) и счетчик числа посещений конкретного виртуального источника нектара без нахождения более качественного соседнего источника (numberOfVisits). Поскольку Bee определен как класс, каждый элемент массива bees является ссылкой на объект Bee.

Двенадцатое поле данных, bestMemoryMatrix, — массив char, представляющий лучшее решение в массиве bees. Вспомните: поскольку алгоритмы SBC являются специфическими реализациями мета-эвристической логики, представление решения зависит от конкретной задачи. Вместо того чтобы зашивать в код определение типа решения, можно применить альтернативный подход — параметризацию этого поля данных как обобщенного типа. Но, когда я использую алгоритм SBC, я обычно пытаюсь решить специфическую задачу, поэтому предпочитаю создавать каждую новую реализацию SBC с нуля.

Тринадцатое поле данных, bestMeasureOfQuality, определяет качество (добротность) решения в bestMemoryMatrix.

Последнее поле данных, indexesOfInactiveBees, — массив типа int. В нем хранятся индексы неактивных в данный момент пчел в улье. Вспомните, что активные пчелы могут переходить в неактивное состояние, а неактивные — в активное состояние. В реализации алгоритма SBC приходится часто определять, какие пчелы неактивны в момент, когда активная пчела исполняет виртуальный виляющий танец, поэтому хранение индексов неактивных пчел увеличивает производительность по сравнению с перебором всего массива bees и проверкой поля данных status для каждой пчелы.

Визуальное представление возможного объекта Hive дано на рис. 6. В этом улье (hive) 10 пчел: пять активных, два разведчика и три неактивных. Текущие неактивные пчелы имеют индексы 2, 7 и 4 в массиве bees. В объекте CitiesData хранится пять городов. Текущее лучшее решение таково:

A->B->E->C-D

Это решение имеет длину маршрута в единицах расстояния:

1.0 + (3 * 1.0) + (2 * 1.5) + 1.0 = 8.0

Заметьте, что поле citiesData является ссылкой на объект CitiesData, определенный вне объекта улья.

Рис. 6. Представление Hive

Конструктор Hive

Код этого конструктора показан на рис. 7. Он принимает семь входных параметров. Шесть из них являются скалярными, а один представляет объект (citiesData). Параметр totalNumberBees избыточен в том смысле, что его можно вычислить на основе значений numberInactive, numberActive и numberScout, но на мой взгляд ради улучшения читаемости можно пойти на некоторое увеличение кода.

Рис. 7. Конструктор Hive

public Hive(int totalNumberBees, int numberInactive,
  int numberActive, int numberScout, int maxNumberVisits,
  int maxNumberCycles, CitiesData citiesData) {

  random = new Random(0);
      
  this.totalNumberBees = totalNumberBees;
  this.numberInactive = numberInactive;
  this.numberActive = numberActive;
  this.numberScout = numberScout;
  this.maxNumberVisits = maxNumberVisits;
  this.maxNumberCycles = maxNumberCycles;

  this.citiesData = citiesData;

  this.bees = new Bee[totalNumberBees];
  this.bestMemoryMatrix = GenerateRandomMemoryMatrix();
  this.bestMeasureOfQuality = 
    MeasureOfQuality(this.bestMemoryMatrix);

  this.indexesOfInactiveBees = new int[numberInactive]; 

  for (int i = 0; i < totalNumberBees; ++i) {
    int currStatus; 
    if (i < numberInactive) {
      currStatus = 0; // inactive
      indexesOfInactiveBees[i] = i; 
    }
    else if (i < numberInactive + numberScout)
      currStatus = 2; // scout
    else
      currStatus = 1; // active
    
    char[] randomMemoryMatrix = GenerateRandomMemoryMatrix();
    double mq = MeasureOfQuality(randomMemoryMatrix);
    int numberOfVisits = 0;

    bees[i] = new Bee(currStatus, 
      randomMemoryMatrix, mq, numberOfVisits); 
        
    if (bees[i].measureOfQuality < bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix, 
        bees[i].memoryMatrix.Length);
      this.bestMeasureOfQuality = bees[i].measureOfQuality;
    }
  } 
}

Объект random, видимый в пределах класса, создается с зародышевым значением (seed value), равным 0. Передача зародышевого значения позволяет воспроизводить результаты. Далее шесть значений входных параметров для скалярных полей данных копируются в поля данных Hive. В объекте Hive всего 14 полей данных; пороговые значения probPersuasion и probMistake «зашиты» в код.

Конструктор Hive принимает входной параметр citiesData присваивает ему ссылку на поле citiesData. Альтернатива этому подходу с передачей по ссылке — создание новой копии данных задачи, например:

int n = citiesData.cities.Length;
this.citiesData = new CitiesData(n);

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

В этот момент в конструкторе Hive все элементы массива bees будут null. Далее конструктор инициализирует глобально лучшее решение (т. е. лучшее решение среди всех пчел в улье) и соответствующую добротность решения:

this.bestMemoryMatrix = GenerateRandomMemoryMatrix();
this.bestMeasureOfQuality = 
  MeasureOfQuality(this.bestMemoryMatrix);

Вспомогательный метод GenerateRandomMemoryMatrix генерирует случайное решение, а вспомогательный метод MeasureOfQuality принимает случайным образом сгенерированное решение и вычисляет его добротность. Код для этих двух методов мы обсудим чуть позже.

После инициализации глобально лучшего решения и соответствующей ему добротности конструктор Hive создает массив indexesOfInactiveBees массива bees, используя значение в поле numberInactive. На этой стадии все значения в массиве индексов равны 0.

Следующая часть кода конструктора перебирает каждый объект Bee в массиве bees и создает его экземпляр с помощью конструктора Bee. Логика этого цикла предполагает, что первые ячейки numberInactive в массиве bees соответствуют неактивным пчелам, следующие ячейки numberScout — разведчикам, а остальные ячейки — активным.

Например, если у вас пять активных пчел, две неактивные и три разведчика, конструктор инициализирует в массиве bees 10 ячеек, при этом ячейки 0 и 1 создаются как неактивные пчелы, ячейки 2–4 — как разведчики и ячейки 5–9 — как активные пчелы. Кроме того, массив indexesOfInactiveBees получит размер 2 и будет изначально хранить значения 0 и 1.

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

char[] randomMemoryMatrix = GenerateRandomMemoryMatrix();
double mq = MeasureOfQuality(randomMemoryMatrix);
int numberOfVisits = 0;
bees[i] = new Bee(currStatus, randomMemoryMatrix, 
  mq, numberOfVisits);

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

Вместо явного копирования памяти пчелы в массив bestMemoryMatrix можно использовать альтернативный подход — присваивание по ссылке. Этот подход повышает производительность ценой увеличения сложности кода.

Три важнейших в SBC метода

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

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

public char[] GenerateRandomMemoryMatrix() {
  char[] result = new char[this.citiesData.cities.Length];
  Array.Copy(this.citiesData.cities, result,
    this.citiesData.cities.Length);      
  for (int i = 0; i < result.Length; i++) {
    int r = random.Next(i, result.Length);
    char temp = result[r];
    result[r] = result[i];
    result[i] = temp;
  }
  return result;
}

Поскольку решение задачи TSP — это массив типа char, где каждый элемент типа char представляет метку города, метод GenerateRandomMemoryMatrix возвращает именно такой массив. Размер локального массива result определяется на основе объекта CitiesData улья, а потом в него копируются идентификаторы городов, хранящиеся в поле данных Hive, которое ссылается на объект CitiesData. Далее порядок значений в массиве result случайным образом перемешивается с использованием объекта random, видимого в пределах класса, и алгоритма перестановки Фишера-Йетса (Fisher-Yates shuffle algorithm) (иногда называемого перестановкой Кнута) (Knuth shuffle).

Поначалу может показаться, что метод GenerateRandomMemoryMatrix концептуально относится к объекту Bee. Однако, так как генерация случайного решения отчасти зависит от данных, специфичных для конкретной задачи (в нашем случае — CitiesData), размещение метода генерации случайного решения в общем определении улья будет правильнее с точки зрения архитектуры.

Метод для генерации смежного решения, GenerateNeighborMemoryMatrix, приведен на рис. 8.

Рис. 8. Генерация смежного решения

public char[] GenerateNeighborMemoryMatrix(char[] memoryMatrix) {
  char[] result = new char[memoryMatrix.Length];
  Array.Copy(memoryMatrix, result, memoryMatrix.Length);

  int ranIndex = random.Next(0, result.Length);
  int adjIndex;
  if (ranIndex == result.Length - 1)
    adjIndex = 0;
  else
    adjIndex = ranIndex + 1;

  char tmp = result[ranIndex];
  result[ranIndex] = result[adjIndex];
  result[adjIndex] = tmp;  return result;
}

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

Например, если текущее решение задачи TSP — A,B,C,D,E, то вполне логичным смежным решением является A,C,B,D,E. Это не столь очевидно, если перестановка позиций любых двух произвольных городов (в противоположность двум соседним городам) дает допустимое смежное решение. Является ли A,D,C,B,E допустимым смежным решением в предыдущем примере? Определение смежного решения для алгоритма SBC зависит от конкретной задачи и, как правило, включает субъективные критерии.

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

Метод GenerateNeighborMemoryMatrix принимает текущий memoryMatrix пчелы (представление решения) как входной параметр и копирует его в массив result. Этот метод выбирает один случайный индекс в текущем массиве result, используя объект random, видимый в пределах класса. Если случайный индекс указывает на последнюю ячейку, то меняются местами первый и последний идентификаторы городов; в ином случае меняются местами идентификаторы, на которые указывают случайный и следующий индекс.

Концепция смежных решений связана со значением maxNumberVisits. В результате некоторых исследований предлагается делать так, чтобы значение maxNumberVisits было примерно в пять раз больше числа смежных решений, возможных для любого данного решения. Например, в случае трех городов (A,B,C), если смежное решение определяется перестановкой любой пары соседних городов, существует три возможных соседа (перестановка A и B, B и C, A и C). Поэтому для 20 городов приемлемое значение maxNumberVisits составляет примерно 20 * 5 = 100.

Метод, оценивающий добротность решения пчелы, MeasureOfQuality, выглядит так:

public double MeasureOfQuality(char[] memoryMatrix) {
  double answer = 0.0;
  for (int i = 0; i < memoryMatrix.Length - 1; ++i) {
    char c1 = memoryMatrix[i];
    char c2 = memoryMatrix[i + 1];
    double d = this.citiesData.Distance(c1, c2);
    answer += d;
  }
  return answer;
}

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

В нашем примере метод MeasureOfQuality просто перебирает каждую пару из последовательности идентификаторов городов в решении, представленном параметром memoryMatrix, определяет расстояние между каждой парой с помощью метода Distance объекта CitiesData и вычисляет общее расстояние. Вспомните, что данные по городам сконструированы искусственно так, чтобы расстояние между любыми двумя городами можно было бы легко и быстро вычислить, просто используя порядковое расстояние (ordinal distance) между двумя идентификаторами городов. Но в практической задаче расстояние между двумя городами скорее всего придется искать в какой-то структуре данных. Поэтому в реализациях SBC метод MeasureOfQuality является той процедурой, которая занимает большую часть времени выполнения программы. А значит, этот метод нужно тщательно оптимизировать.

Метод Solve

В методе Solve заключена вся логика, которая моделирует поведение пчел-фуражиров, решающих задачу. Этот метод в меру сложен и использует три вспомогательных метода: ProcessActiveBee, ProcessScoutBee и ProcessInactiveBee. Первые два метода используют еще один вспомогательный метод — DoWaggleDance. Исходный код метода Solve показан на рис. 9.

Рис. 9. Метод Solve

public void Solve(bool doProgressBar) {
  bool pb = doProgressBar;
  int numberOfSymbolsToPrint = 10; 
  int increment = this.maxNumberCycles / numberOfSymbolsToPrint;
  if (pb) Console.WriteLine("\nEntering SBC Traveling Salesman Problem algorithm main processing loop\n");
  if (pb) Console.WriteLine("Progress: |==========|");
  if (pb) Console.Write("           ");
  int cycle = 0;
      
  while (cycle < this.maxNumberCycles) {
    for (int i = 0; i < totalNumberBees; ++i) {
      if (this.bees[i].status == 1)
        ProcessActiveBee(i);
      else if (this.bees[i].status == 2)
        ProcessScoutBee(i);
      else if (this.bees[i].status == 0)
        ProcessInactiveBee(i);
    } 
    ++cycle;

    if (pb && cycle % increment == 0)
      Console.Write("^");
  } 

  if (pb) Console.WriteLine("");
}

Большая часть работы выполняется вспомогательными методами ProcessActiveBee, ProcessScoutBee и ProcessInactiveBee. Булев входной параметр, передаваемый Solve, указывает, надо ли выводить рудиментарную текстовую полоску прогресса. Это удобно при реализации алгоритма SBC для наблюдения за скоростью работы реализации и помогает вскрывать узкие места. Такой подход предполагает, что метод Solve является частью консольного приложения.

Значение булева параметра передается в локальную булеву переменную pb просто потому, что работать с коротким именем переменной удобнее. Значение numberOfSymbolsToPrint задается равным 10, чтобы каждое приращение полоски состояния отражало 10% от общего прогресса, который определяется значением maxNumberCycles (переменная increment используется, чтобы выяснить, сколько циклов представляет 10% прогресса).

После инициализации переменной cycle, управляющей циклом, нулевым значением для обработки каждой пчелы в улье используется цикл while. (Вместо него можно было бы легко задействовать цикл for.) На каждой итерации этого цикла с помощью цикла for перебирается массив bees и каждый объект Bee обрабатывается соответствующим вспомогательным методом. После обработки всех пчел, если булев параметр doProgressBar равен true, в коде с помощью оператора % проверяется, не пора ли обновить полоску прогресса (используется символ «^»).

Метод ProcessActiveBee

Этот метод является сердцевиной алгоритма SBC и самым сложным по своей логике (в нем много ветвлений и много кода). Метод ProcessActiveBee приведен на рис. 10.

Рис. 10. Метод ProcessActiveBee

private void ProcessActiveBee(int i) {
  char[] neighbor = GenerateNeighborMemoryMatrix(bees[i].memoryMatrix);
  double neighborQuality = MeasureOfQuality(neighbor); 
  double prob = random.NextDouble();
  bool memoryWasUpdated = false;
  bool numberOfVisitsOverLimit = false; 

  if (neighborQuality < bees[i].measureOfQuality) { // better
    if (prob < probMistake) { // mistake
      ++bees[i].numberOfVisits;
      if (bees[i].numberOfVisits > maxNumberVisits)
        numberOfVisitsOverLimit = true;
    }
    else { // No mistake
      Array.Copy(neighbor, bees[i].memoryMatrix, neighbor.Length);
      bees[i].measureOfQuality = neighborQuality;
      bees[i].numberOfVisits = 0; 
      memoryWasUpdated = true; 
    }
  }
  else { // Did not find better neighbor
    if (prob < probMistake) { // Mistake
      Array.Copy(neighbor, bees[i].memoryMatrix, neighbor.Length);
      bees[i].measureOfQuality = neighborQuality;
      bees[i].numberOfVisits = 0;
      memoryWasUpdated = true; 
    }
    else { // No mistake
      ++bees[i].numberOfVisits;
      if (bees[i].numberOfVisits > maxNumberVisits)
        numberOfVisitsOverLimit = true;
    }
  }

  if (numberOfVisitsOverLimit == true) {
    bees[i].status = 0; 
    bees[i].numberOfVisits = 0;
    int x = random.Next(numberInactive); 
    bees[indexesOfInactiveBees[x]].status = 1; 
    indexesOfInactiveBees[x] = i; 
  }
  else if (memoryWasUpdated == true) {
    if (bees[i].measureOfQuality < this.bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix,
        bees[i].memoryMatrix.Length); 
      this.bestMeasureOfQuality = bees[i].measureOfQuality
    }
    DoWaggleDance(i);
  }
  else {
    return;
  }
}

Метод ProcessActiveBee принимает единственный параметр, i, который является индексом пчелы в массиве bees. Активная пчела сначала получает смежное решение, относительное ее текущему решению, которое хранится в memoryMatrix, а затем определяет добротность этого смежного решения:

char[] neighbor =
  GenerateNeighborMemoryMatrix(bees[i].memoryMatrix); 
double neighborQuality = MeasureOfQuality(neighbor);

Далее алгоритм инициализирует три локальные переменные, которые будут использоваться позже:

double prob = random.NextDouble();)
bool memoryWasUpdated = false; 
bool numberOfVisitsOverLimit = false;

Переменная prob имеет значение между 0.0 и 1.0 и будет сравниваться со значением поля probMistake, чтобы определить, совершила ли ошибку пчела при оценке смежного решения, т. е. отклонила более эффективное смежное решение или приняла менее эффективное.

Булево значение memoryWasUpdated будет использоваться, чтобы определить, должна активная пчела исполнить виляющий танец для неактивных пчел (если true) или нет (если false). Булево значение numberOfVisitsOverLimit будет сравниваться с полем maxNumberVisits, чтобы выяснить, исчерпала ли пчела конкретный источник нектара, не найдя более эффективного смежного решения. Если да, то ее состояние должно быть переведено из активного в неактивное.

Если текущая пчела находит более эффективное смежное решение, алгоритм определяет, приняла ли она более эффективное решение или совершила ошибку, отклонив более эффективное смежное решение. Аналогично, если текущая пчела не нашла более эффективное смежное решение, алгоритм определяет, совершила ли пчела ошибку, приняв менее эффективное смежное решение, или не ошиблась, отклонив такое решение.

Заметьте, что возможны два типа ошибок, причем с одинаковой вероятностью (probMistake = 0.01). Это тоже взято не с потолка, а в результате исследований, которые показали, что разные вероятности двух типов ошибок не повышают эффективность алгоритмов SBC, но вы можете поэкспериментировать с пороговыми значениями.

После того как текущая активная пчела принимает или отвергает смежное решение, алгоритм проверяет, не превысил ли счетчик числа визитов пороговое значение maxNumberVisits. Если да, текущая пчела переводится в неактивное состояние, а наугад выбранная неактивная пчела становится активной и обновляется массив indexesOfInactiveBees. Далее алгоритм проверяет, была ли обновлена память этой пчелы. Если да, новое решение проверяется на пригодность в качестве нового глобального лучшего решения, а затем вызывается закрытый вспомогательный метод DoWaggleDance, чтобы имитировать возврат пчелы в улей и передачу информации о новом источнике нектара неактивным пчелам.

Метод DoWaggleDance

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

private void DoWaggleDance(int i) {
  for (int ii = 0; ii < numberInactive; ++ii) {
    int b = indexesOfInactiveBees[ii]; 
    if (bees[i].measureOfQuality < bees[b].measureOfQuality) {
      double p = random.NextDouble(); 
      if (this.probPersuasion > p) {
        Array.Copy(bees[i].memoryMatrix, bees[b].memoryMatrix,
          bees[i].memoryMatrix.Length);
        bees[b].measureOfQuality = bees[i].measureOfQuality;
      } 
    } 
  } 
}

Входной параметр i — индекс текущей пчелы, исполняющей виртуальный виляющий танец. Степень добротности решения текущей пчелы сравнивается со степенью добротности решений у всех неактивных пчел. Если решение текущей пчелы лучше и текущая неактивная пчела принимает его (с вероятностью probPersuasion = 0.90), память текущей активной пчелы копируется в память неактивной.

Заметьте, что во многих местах кода, представленного в этой статье, стоило бы вставить проверку на ошибки. Например, внутри цикла for в DoWaggleDance следует проверять состояние текущей неактивной пчелы с помощью:

if (bees[b].status != 0) throw new Exception(. . .);

Или проверять счетчик числа визитов неактивной пчелы:

if (bees[b].numberOfVisits != 0) throw new Exception(. . .);

ProcessScoutBee и ProcessInactiveBee

Вспомогательный метод ProcessScoutBee, используемый методом Solve, моделирует действие пчелы-разведчика, осуществляющей случайный поиск привлекательных источников нектара. Метод ProcessScoutBee показан на рис. 11.

Рис. 11. Метод ProcessScoutBee

private void ProcessScoutBee(int i) {
  char[] randomFoodSource = GenerateRandomMemoryMatrix();
  double randomFoodSourceQuality = 
    MeasureOfQuality(randomFoodSource);
  if (randomFoodSourceQuality < bees[i].measureOfQuality {
    Array.Copy(randomFoodSource, bees[i].memoryMatrix,
      randomFoodSource.Length);
    bees[i].measureOfQuality = randomFoodSourceQuality;
    if (bees[i].measureOfQuality < bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix,
        bees[i].memoryMatrix.Length);
      this.bestMeasureOfQuality = bees[i].measureOfQuality;
    } 
    DoWaggleDance(i);
  }
}

Входной параметр i представляет индекс пчелы-разведчика в массиве bees. Пчела-разведчик генерирует случайное решение, проверяет, лучше ли оно текущего решения в памяти, и, если да, копирует его в память. Вспомните, что меньшие значения добротности лучше. Если пчела-разведчик нашла более эффективное решение, алгоритм проверяет, можно ли считать новое решение глобально лучшим.

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

Метод ProcessInactiveBee сейчас выглядит так:

`private void ProcessInactiveBee(int i) {
  return;
}
private void ProcessInactiveBee(int i) {
  return;
}

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

Подводя итоги

В целом, процесс реализации алгоритма SBC начинается с идентификации задачи. Хорошими кандидатами на обработку алгоритмом SBC являются сложные нечисловые комбинаторные задачи оптимизации, не имеющие детерминированных решений. Для целевой задачи должен быть какой-то способ представления решения (зачастую в виде массива или матрицы), и у каждого решения должна быть какая-то форма смежного решения (neighbor solution) и мера качества решения.

Например, рассмотрим задачу разбиения графа на две части так, чтобы количество соединений внутри каждой части было максимальным, а между двумя частями — минимальным. Эта задача разбиения графа является комбинаторной, и для поиска оптимального решения никакого быстрого алгоритма не существует (хотя имеются детерминированные алгоритмы, способные находить близкие к оптимальным решения). Есть много других НП-полных (NP-complete) и НП-трудных (NP-hard) задач (НП — недетерминированных полиномиальных), которые могут быть решены с использованием SBC.

Алгоритмы SBC основаны на поведении естественных систем. Существуют и другие алгоритмы такого рода, в том числе генетические алгоритмы (genetic algorithms, GA), основанные на естественном отборе и эволюции, оптимизация по принципу муравьиной колонии (ant colony optimization, ACO), основанная на поведении муравьев, и методы имитации отжига (simulated annealing, SA), основанные на физических свойствах остывающих металлов.

Алгоритмы на базе естественных систем зачастую реализуются легче по сравнению с детерминированными подходами. Однако алгоритмы, основанные на естественных системах, как правило, требуют спецификации значений для нескольких параметров, которые сильно влияют на скорость сходимости решения (solution convergence speed) и его точность. В случае SBC к параметрам, требующим тонкой настройки для каждой задачи, относятся количество пчел каждого типа, максимально число визитов до истощения источника нектара, вероятность превращения пчел в неактивные и вероятность ошибок, совершаемых активными пчелами.

Хотя алгоритмы SBC неприменимы ко всем задачам, в некоторых случаях они могут оказаться чрезвычайно эффективными. 

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

Выражаю благодарность за рецензирование статьи экспертам Microsoft Research Дэну Либлингу (Dan Liebling) и Энн Лумис Томпсон (Anne Loomis Thompson)