Метод колоній в задачах оптимізації

      CCS – математична модель, призначена для опису процесів, яка зазвичай застосовується при вивченні паралельності. Вона містить набір термів, операторів і аксіом, які використовуються для опису і управління складеними виразами. Вирази характеризують елементи паралельної системи, а управління цими виразами показує, як поводить себе система. Центральним елементом CCS є унікальний іменований агент, який володіє специфічною поведінкою. Поведінка агента визначається багатьма подіями і діями, які він може виконати. Багато дій які виконуються агентом, описуються з допомогою оператора «дія», який позначається як «.». Другий оператор в CCS – оператор «+», який є оператором вибору. Він використовується у випадку, якщо описана участь агента в одній із декількох альтернативних дій.

      Модель  CCS працює з агентами, які описують стан бджоли або групи бджіл, і з діями, які являють собою можливість переходу з одного стану в інший. Таким чином, колонія може бути представленою у вигляді зв’язаного графа, вершинами якого є агенти, а ребра –діями. Наприклад, агент може бути представлений в наступному вигляді:

      Розвідник_b= хороший_b(s). пошук_b(s)+ поганий_b . Незанятий_b .

      Агент b є розвідником який шукає джерело нектару. У випадку якщо він буде погано шукати нектар, то стане незанятою робочою бджолою, якщо добре, то продовжить. Пошук_b (s) деякого джерела s.

      Процес  фуражування можна формалізувати з допомогою CCS в наступному вигляді:

      Використовувати _b(s) = k_b,s. Пошук_b(s),

      Пошук_b(s)= нектар_b,s. Вдало_b(s)+ нічого_s . Невдало_b(s),

      Вдало  _b(s)=  із_b(s).  Вербування _b(s),

      Невдало _b(s)= із _b,sНезайнятий _b

      Вербування_b(s)=танець(b,s).Вербування_b(s)+покинути_b.Використати_b(s),

      Незайнятий_b= танець(b^’,s). Використати_b(s)+ досліджувати_b. Розвідник_b,

      Розвідник_b = хороший _b(s). Пошук _b(s) + поганий _b. Незайнятий _b.

      В даному описі b- унікальний ідентифікатор одного агента;

      b^’ – ідентифікатор другого агента,

      s – джерело нектару. 

      3.3. Методи на основі моделювання бджолиної колонії для розв’язку задач дискретної оптимізації [3, с. 17]

      На  основі запропонованого підходу  розроблений метод бджолиної  колонії для розвязку задачі календарного планування (BCO-JSSP).

      В аспекті розв’язку цієї задачі використовується аналогія джерела нектару шляху, якщо шлях який може розглядатися як рішення задачі календарного планування.

      Після повернення у вулик агент виконує  зигзагоподібний танець з імовірністю  р. Тривалість Di зигзагоподібного танцю і-го агента розраховується за формулою , де А- коефіцієнт масштабування; d_i –відносна корисність джерела нектару, знайденого і-м агентом.

      Абсолютна корисність джерела нектару і-го агента Pf_i для задачі календарного планування розраховується за формулою , де С_і- цільова функція для шляху і-го агента. В даному випадку вона являє собою продовження виконання всіх операцій всіх робіт для шляху.

      Розрахувавши  абсолютну корисність кожного агента, можна получити середню користь всієї колонії Pf _col:

       ,

      де n – кількість зигзагоподібних танців, що виконуються  в момент часу t.

      Таким чином можна розрахувати відносну корисність d_i і-го фуражира:

      

      Імовірність р_і того, що за і-м агентом після виконання ним танцю підуть інші незаняті робочі бджоли, визначається за формулою:

      

      Ймовірність того, що агент вибере наступний j-ий вузол, знаходячись в і-му вузлі, визначається за формулою [3, с. 18]:

       ,

      Де  - вартість дуги між j-им та і-им вузлами;

        евристична відстань між  j-им та і-им вузлами;

      α, β € [0;1] – коефіцієнти, які вибираються  експериментально;

       - множина вузлів, в яку можна  переміститися із і-го вузла.

      Оцінка  визначається за допомогою формули:

       ,

      де k – кількість вузлів, в які можна переміститися з і-го вузла;

      m – змінна переваги шляху, може бути рівна 0 або 1. Кращим вважається шлях, який на якій-небудь ітерації придатний для виконання танцю. При цьому кількість таких, так званих елітних шляхів, обмежена. Таким чином, на початковій ітерації всі ребра мають число m=0, що робить шанси вибору любого ребра рівними.

      Даний метод порівнювався з методом  мурашиних колоній. Експерименти показали, що результати, отримані за допомогою методу бджолиних колоній, майже не відрізняються від результатів, отриманих за допомогою методу мурашиних колоній.

      На  основі методу системи бджіл (Bee System, BS) запропонований метаврестичний метод бджолиної колонії (Bee Colony Optimization Metaheuristic, BCO) і метод нечіткої бджолиної колонії (Fuzzy Bee System, FBS) [3, с. 18].

      В методі BCO на початку процесу пошуку всі агенти знаходяться у вулику. Кожний агент робить ряд локальних переміщень і таким чином поступово складає розв’язок задачі. Процес пошуку складається з ітерацій. Перша ітерація вважається закінченою, коли агенти створять хоча б одне допутистиме рішення. Краще рішення зберігається, а потім відбувається перехід до наступної ітерації. Далі процес складення рішень повторюється. Загальна кількість ітерацій обмежується відповідно до задачі оптимізації.

      При переміщенні в просторі пошуку агенти можуть прямувати в прямому направленні  або зворотньому. При переміщенні  в прямому направленні агенти формують різні приватні рішення, що досягається за рахунок індивідуального дослідження простору пошуку і і колективного досвіду, отриманого на попередніх ітераціях.

      Після створення приватного розв’язку агенти переміщуються в зворотному напрямку, тобто повертаються у вулик, де можуть брати участь в процесі вербування шляхом виконання танцю, тим самим обмінюючись інформацією про різні створені приватні рішення. Після того, як агенти відвідають вулик, вони знову прямують в прямому напрямку і продовжують створювати приватні рішення. Ітерація закінчується тоді, коли створюється хоча б один допустимий розв’язок. Таким чином, BCO, як і методи динамічного програмування, розв’язує комбінаторні задачі оптимізації поетапно.

      Метод FBS призначений для розв’язку задач, що характеризуються невизначеністю, агенти при розвязку задачі використовують правила нечіткої логіки для організації зв’язку між ними і їхніми діями.

      Відповідно  з FBS при додаванні компонента рішень до приватного рішення агент може розглядати компонент розв’язку як : ”менш корисний”, “корисний” або ”більш корисний”.

      При виборі наступного компонента розв’язку для визначення його корисності використовується правило виду:

      ЯКЩО  властивість компонента рішення “дуже добре”, ТО компонент рішення, що розглядається, “дуже корисний”.

      Ймовірність того, що j-а компонента буде добавлена до приватного рішення, розраховується за формулою [3, с. 19]:

       ,

      де - корисність j-ї компоненти рішення; - множина компонентів рішень, які можуть бути добавлені.

      В FBS для порівняння приватних рішень агентів використовується концепція непридатності приватних рішень. Непридатність приватних рішень визначається наступним чином:

       .

      Тут - непридатність приватного рішення, отриманого k-им агентом; - цільова функція, отримана з допомогою приватного рішення k-го агента;

       - цільова функція, отримана  на основі кращого приватного  рішення, знайденого з початку  пошуку;

       - цільова функція, отримана  на основі найгіршого приватного  пошуку, знайденого з початку  пошуку.

      Визначення  придатності приватного розв’язку засновується на приблизних міркувань:

      ЯКЩО  отриманий приватний розвязок “поганий”, ТО його “придатність” низька.

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

      Для визначення корисності приватного рішення  використовуються правила виду:

      ЯКЩО  пропонований шлях “короткий” і кількість  агентів, що пропонують маленька, ТО корисність шляху “середня”.

      Для визначення кількості агентів, які змінюють свій шлях, використовуються наступні правила:

      ЯКЩО  придатність приватного рішення  і-го агента “низька” і корисність приватного розвязку j-го агента “висока”, ТО кількість агентів, які змінюють свій шлях на шлях j-го агента, “велика”.

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

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

• не приводить до циклічності в локальних оптимумах, оскільки базуються на випадковому пошуку;
• пошук кращого рішення базується на рішеннях агентів всієї колонії бджіл;
• застосовуються в динамічних додатках, оскільки здатні адаптовуватись до зміни навколишнього середовища;
• використовуються для розв’язку як дискретних, так і неперервних задач оптимізації;

      До  недоліків методів бджолиної колонії можна віднестии:

• достатньо високу ітеративність;
• труднощі теоретичного аналізу процесу отримання розв’язків, обумовлені тим, що пошук рішень має стохастичну природу;
• апріорну невизначеність часу збігу, хоча збіг гарантується;
• залежність методу від налаштування параметрів, які підбираються експериментально.

      Виходячи  з результатів аналізу методів бджолиної колонії, можна зробити висновок, що незважаючи на різні особливості їх застосування для розвязку задач оптимізації запропонованим методом. існують три основні характеристики, обумовлені властивостями поведінки бджіл.

      1. Всі агенти поділяються на різні типи у відповідності з діями, які вони виконують в процесі розв’язку задачі:

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