Три важнейших в 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 является той процедурой, которая занимает большую часть времени выполнения программы. А значит, этот метод нужно тщательно оптимизировать.