Структура 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.