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