Головна

Структура SBC-програм

  1. I. Структура і оформлення ділових листів
  2. II. СТРУКТУРА НАВЧАЛЬНОЇ ДИСЦИПЛІНИ
  3. III СТРУКТУРА ВИПУСКНИЙ ПИСЬМОВІЙ КВАЛІФІКАЦІЙНОЇ РОБОТИ ТА ОСНОВНІ ВИМОГИ ДО ЇЇ ОФОРМЛЕННЯ
  4. Nbsp; Структура УКТ ЗЕД
  5. PR-ПІДРОЗДІЛИ У КОМЕРЦІЙНИХ СТРУКТУРАХ
  6. А. Структура змісту дисципліни (1 модуль)
  7. Адміністративна юрисдикція: основні риси, принципи, структура

Алгоритм 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

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.

Про бджіл | Поля даних Hive


Три найважливіших в SBC методу | метод Solve | метод ProcessActiveBee | Підбиваючи підсумки |

© 2016-2022  um.co.ua - учбові матеріали та реферати