Бджолиний алгоритм та штучна колонія бджіл

1. Біологія пошуку їжі медоносними бджолами

Колонії медоносних бджіл оптимізують пошук їжі колективно через стигмергічну комунікацію: бджоли змінюють спільне середовище (танцювальний майданчик у вулику) таким чином, щоб впливати на поведінку інших. Колонія повинна ефективно розподіляти фуражирів між кількома джерелами їжі, якість і відстань яких постійно змінюються.

Фуражирський вильот має три фази. Спочатку незайнята бджола — без інформації про активні джерела їжі — вибирає між двома варіантами: стати розвідницею (досліджувати випадкове місце) або слідувати за танцюристкою (використовувати відоме джерело). По-друге, опинившись у джерела, завербована бджола збирає нектар, оцінюючи якість (концентрація нектару × об'єм на відвідування). По-третє, повернувшись у вулик, бджола або мовчки повертається до того ж джерела (зайнята фуражирка), або танцює, рекламуючи джерело, або покидає джерело й повертається в незайнятий пул.

2. Ваггловий танець — кодування інформації

Карл фон Фріш розшифрував ваггловий танець у серії експериментів з 1943 по 1973 рік, за що отримав Нобелівську премію з фізіології або медицини 1973 року. Танець виконується на вертикальній стільниці всередині темного вулика та одночасно кодує два фрагменти інформації:

• Відстань кодується тривалістю (точніше, кількістю вагглів) центрального вагглового пробігу. Кожні 75 мс вагглового пробігу відповідають приблизно 100 метрам відстані польоту.
• Напрямок кодується кутом вагглового пробігу відносно вертикалі. Якщо ваггловий пробіг спрямований прямо вгору, їжа знаходиться в напрямку сонця. Якщо він спрямований на 40° ліворуч від вертикалі, їжа знаходиться на 40° ліворуч від поточного азимуту сонця.

Кількість циклів танцю, яку виконує бджола, пропорційна (логарифму) відносній якості джерела. Бджола, що відвідує бідніше джерело, танцюватиме менше циклів після повернення і зрештою припинить танцювати — природно видаляючи джерело з пулу реклами.

Завербовані з танцю бджоли не є точними копіями — вони підходять до закодованого місця з гауссівською кутовою похибкою приблизно ±10° і похибкою відстані ±15%. Цей шум забезпечує біологічний еквівалент оператора мутації, запобігаючи сходженню всього рою до єдиної точки.

3. Три ролі бджіл у ABC

Алгоритм штучної колонії бджіл (Карабога, 2005) моделює вулик з використанням трьох популяцій, що безпосередньо відповідають біологічним ролям:

Ключовий структурний баланс: кількість зайнятих бджіл дорівнює кількості джерел їжі (рішень). Кожна зайнята бджола відповідає рівно за одне рішення в будь-який момент, забезпечуючи розподіл тиску використання по всьому пулу.

4. Алгоритм штучної колонії бджіл

ABC — ітеративний алгоритм. Один цикл складається з трьох послідовних фаз. Загальна популяція — SN (розмір рою), з SN/2 зайнятими бджолами та SN/2 глядачками.

Фаза 1: Фаза зайнятих бджіл

Кожна зайнята бджола i генерує нового кандидата v_i, збурюючи своє поточне джерело x_i вздовж випадково обраного виміру j, використовуючи випадкового сусіда k ≠ i:

Фаза 2: Фаза глядачок

Кожна глядачка обирає джерело i з імовірністю, пропорційною фітнесу, а потім виконує той самий крок збурення, що й зайнята бджола для обраного джерела.

Фаза 3: Фаза розвідниць

Будь-яке джерело i, лічильник спроб якого досягає параметра limit, покидається. Зайнята бджола, пов'язана з ним, стає розвідницею та генерує абсолютно випадкове нове джерело в межах пошуку:

5. Математичне формулювання

ABC підтримує SN/2 позицій джерел їжі x_i ∈ ℝᴰ, де D — розмірність задачі. Пошук функції f: ℝᴰ → ℝ є глобальною оптимізацією:

6. Налаштування параметрів і збіжність

ABC має менше параметрів, ніж більшість інших метаевристик: розмір рою SN, limit і максимальна кількість циклів MCN. Рекомендоване значення за замовчуванням для limit — SN × D / 2 (Karaboga і Basturk, 2007). Це гарантує, що кожне джерело їжі відвідується приблизно D × SN / 2 разів перед покиданням, забезпечуючи достатній локальний пошук у кожному вимірі.

Поширені режими відмови

• limit занадто малий: Джерела покидаються до належної експлуатації; алгоритм поводиться як випадковий рестарт.
• limit занадто великий: Застарілі джерела з низьким фітнесом зберігаються надто довго; різноманітність зникає, алгоритм стагнує у локальних оптимумах.
• SN занадто малий: Недостатня різноманітність; рання передчасна збіжність.

7. JavaScript-реалізація

// Штучна колонія бджіл (ABC) — мінімізація
// Приклад: мінімізувати f(x) = Σ x[i]² (функція Sphere)

const D       = 10;
const SN      = 40;
const LIMIT   = SN / 2 * D;
const MCN     = 500;

const lb = Array(D).fill(-5.12);
const ub = Array(D).fill( 5.12);

function f(x) {
  return x.reduce((s, xi) => s + xi * xi, 0);
}

function fitness(obj) {
  return obj >= 0 ? 1 / (1 + obj) : 1 + Math.abs(obj);
}

function randomSource() {
  return Array.from({ length: D }, (_, j) =>
    lb[j] + Math.random() * (ub[j] - lb[j])
  );
}

function runABC() {
  const nEmp = SN / 2;
  let sources = Array.from({ length: nEmp }, randomSource);
  let objs    = sources.map(f);
  let trials  = new Array(nEmp).fill(0);
  let bestX   = sources[0].slice();
  let bestObj = objs[0];
  objs.forEach((o, i) => { if (o < bestObj) { bestObj = o; bestX = sources[i].slice(); } });

  function perturbSource(i) {
    const j = Math.floor(Math.random() * D);
    let k;
    do { k = Math.floor(Math.random() * nEmp); } while (k === i);
    const phi = (Math.random() * 2 - 1);
    const v = sources[i].slice();
    v[j] = Math.min(ub[j], Math.max(lb[j],
           sources[i][j] + phi * (sources[i][j] - sources[k][j])));
    const newObj = f(v);
    if (newObj < objs[i]) {
      sources[i] = v; objs[i] = newObj; trials[i] = 0;
      if (newObj < bestObj) { bestObj = newObj; bestX = v.slice(); }
    } else { trials[i]++; }
  }

  for (let cycle = 0; cycle < MCN; cycle++) {
    // Фаза зайнятих бджіл
    for (let i = 0; i < nEmp; i++) perturbSource(i);

    // Фаза глядачок
    const fits = objs.map(o => fitness(o));
    const sumF = fits.reduce((a, b) => a + b, 0);
    const probs = fits.map(f => f / sumF);
    for (let b = 0; b < nEmp; b++) {
      let r = Math.random(), chosen = 0, cumP = 0;
      for (let i = 0; i < nEmp; i++) { cumP += probs[i]; if (r < cumP) { chosen = i; break; } }
      perturbSource(chosen);
    }

    // Фаза розвідниць
    for (let i = 0; i < nEmp; i++) {
      if (trials[i] >= LIMIT) {
        sources[i] = randomSource(); objs[i] = f(sources[i]); trials[i] = 0;
      }
    }
  }
  return { bestX, bestObj };
}

const result = runABC();
console.log('Найкраще значення:', result.bestObj.toFixed(8));
        

8. Порівняння з PSO та ACO

Усі три основні сімейства роїного інтелекту — Оптимізація роєм частинок, Оптимізація мурашиною колонією та Штучна колонія бджіл — були натхненні соціальними комахами, але використовують різні стратегії:

Ключова перевага ABC перед PSO — явний механізм покидання: вичерпані джерела відкидаються й замінюються випадковими розвідницями, запобігаючи передчасній збіжності. Ключова перевага PSO — ефективність на гладких задачах: вектори швидкості дають частинкам імпульс, що забезпечує швидшу збіжність на унімодальних функціях.