О пчелах

В обычной колонии пчел, например 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.