Поля данных 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 можно использовать альтернативный подход — присваивание по ссылке. Этот подход повышает производительность ценой увеличения сложности кода.