Тоді моделювання поведінки бджіл у термінах CCS можна зобразити як подано на рис. 7.7.
Немає
Немає
Немає
Немає
Незанятий (b i ,1…n)
Танець(b i ,1…n)
Розвідник b l
Поганий b m
Гарний (b j ,1…n)
Нічого(b i ,1…n)
Невдало(b i ,1…n)
Використати(b i ,1…n)
Пошук (b i ,1…n)
Нектар(b i ,1…n)
Вдало (b i ,1…n)
Незайнятий(b i ,1…n)
Корисність джерела d i
Корисність агента фуражира d i
Занятий (b i ,1…n)
Вербування (b i ,1…n)
Дослідження (b i ,1…n)
Нектар є ?
Нектар є ?
Обмеження в часі є ?
Залишити танець (b i ,1…n)
Перехід (b i ,1…n)
Рис. 7.7. Алгоритм моделювання поведінки бджіл за допомогою CCS
Процес фуражування можна формалізувати за допомогою CCS у такому вигляді:
Вдало (b i ,1…n) (s) = Зайнятий (b i ,1…n) (s). Вербування (b i ,1…n)(s),
Невдало (b i ,1…n)(s) = Нічого (b i ,1…n). Незайнятий (b i ,1…n) (s),
Вербування (b i ,1…n)(s) = Танець (b i ,1…n). Вербування b (s) + Покинути (b i ,1…n). Використати (b i ,1…n)(s),
Незайнятий (b i ,1…n) = танець (b i ,1…n)(s). Використати (b i ,1…n)(s) + Дослідження (b i ,1…n). Розвідник (b i ,1…n),
Розвідник (b i ,1…n) = Гарний (b j ,1…n)(s). Пошук (b j ,1…n)(s) + Поганий (b j ,1…n). Незайнятий (b j ,1…n).
Використати (b j ,1…n)(s) = Перехід (b i ,1…n)(s). Пошук (b i ,1…n)(s),
Пошук (b i ,1…n)(s) = Нектар (b i ,1…n)(s). Вдало (b i ,1…n)(s) + Нічого (b i ,1…n). Невдало (b i ,1…n)(s),
Отже, за допомогою запропонованої формалізації моделюється поведінка бджіл. Незайнятий агент перебуває у вулику доти, поки не одержить сигнал від зайнятого фуражира за допомогою звивистого танцю; якщо такий сигнал отримано, то агент переміщується до відповідного джерела нектару; у протилежному випадку — він може сам стати розвідником через деякий час; якщо в передбачуваному джерелі є нектар, то агент приносить його у вулик і моделює виконання виляючого танцю.
18.7. Особливості модифікацій методів бджолиної колонії
На основі запропонованого підходу було розроблено метод бджолиної колонії для розв’язання задачі календарного планування (Bee Colony Optimization for Job-Shop Scheduling Problem, BCO-JSSP).
Задача календарного планування виробництва може характеризуватися множиною робіт, кожна з яких складається з однієї або більше операцій. Операції виконуються на специфічній послідовності спеціальних машин. Метою планування є складання розкладу робіт, що мінімізує (максимізує) міру виконання.
Задача календарного планування належить до NP-важких. Міра виконання включає: завантаження устаткування (коефіцієнт використання устаткування), час виробничого циклу, продуктивність (витрату, пропускну здатність) і рівень запасів.
У загальному випадку задача календарного планування подається за допомогою диз’юнктивного графа. Граф складаєть-
Оскільки головними особливостями методу бджолиної колонії є звивистий танець і процес фуражування, то запропонована модифікація для розв’язання задачі календарного планування відрізняється саме цими етапами роботи методу бджолиної колонії порівняно із запропонованим раніше методом. Аналогією джерела нектару в даній модифікації є шлях, що може розглядатись як розв’язок задачі календарного планування.
Після повернення у вулик агент виконує звивистий танець з імовірністю p. Тривалість D i звивистого танцю i-го агента обчислюється за формулою: де A — коефіцієнт масштабування, d i — відносна корисність знайденого джерела нектару i-го агента.
Абсолютна корисність джерела нектару i-го агента Pf i для задачі календарного планування обчислюється за формулою: i де C i — цільова функція для шляху i-го агента. У цьому випадку вона являє собою тривалість виконання усіх операцій всіх робіт для шляху.
Тоді, розрахувавши абсолютну корисність кожного агента, можна одержати середню корисність усієї колонії Pf colony : де n — кількість звивистих танців, що виконуються у момент часу t.
Таким чином, можна розрахувати відносну корисність d i i-го фуражира: colony
ся з вузлів, що являють собою операції. Також є два додаткових вузли, які становлять ресурси й витрати. Множина орієнтованих дуг використовується для опису переваги кожної роботи.
Оскільки в процесі кормодобування агенти формують рішення шляхом переміщення з вузла до вузла на графі, що описує можливі роботи, треба розрахувати імовірність додавання до шляху агента заданого вузла. Імовірність P ij того, що агент вибере наступний j-ий вузол, перебуваючи в i-му вузлі, обчислюється за формулою: ? ? ??? ??? ?? ?? = k Jj ijij ijij ij d d P, де ? ij — вартість дуги між j-им та i-им вузлами; d ij — евристична відстань між j-им та i-им вузлами; ?, ? ? [0; 1] — коефіцієнти, обрані експериментально; J k — множина вузлів, у які можна переміститися з i-го вузла.
Оцінка ? ij визначається за допомогою формули: mk m ij ? ?? =?
1 , де k — кількість вузлів, у які можна переміститися з i-го вузла; m
— число переваги шляху, що може дорівнювати 1 або 0. Кращим вважається шлях, що на якій-небудь ітерації вважався придатним для виконання танцю. При цьому кількість так званих елітних шляхів обмежена. Отже, на початковій ітерації всі ребра мають число m = 0, що зрівнює шанси вибору будь-якого ребра.
Даний метод порівнювався з методом мурашиних колоній та з пошуком з табу, створеним Гловером Фредом У. в 1986 році. Експерименти довели, що результати, отримані за допомогою методу бджолиної колонії, майже не відрізняються від результатів, отриманих за допомогою методу мурашиних колоній, і не гірші результатів, отриманих за допомогою пошуку з табу.
Імовірність p i того, що за i-им агентом після виконання ним танцю підуть інші незайняті фуражири, визначається за формулою: ? ? ? ? ? ? ? ? ?i colonyicolony colonyicolony colonyi i Pf PfPfPf PfPffP PfPf p
За методом BCO на початку процесу пошуку всі агенти перебувають у вулику. У процесі пошуку агенти зв’язуються один з одним опосередковано. Кожний агент виконує низку локальних переміщень, і в такий спосіб поступово формує рішення задачі. Процес пошуку складається з ітерацій. Перша ітерація вважається закінченою, коли агенти створять хоча б одне прийнятне рішення. Краще рішення зберігається, а потім відбувається перехід до наступної ітерації. Далі процес складання рішень повторюється. Загальна кількість ітерацій обмежується виходячи із задачі оптимізації.
При переміщенні в просторі пошуку агенти можуть переміщуватися в прямому або у зворотному напрямку. При переміщенні в прямому напрямку агенти формують різні часткові рішення, що досягається за рахунок індивідуального дослідження простору пошуку та за рахунок колективного досвіду, отриманого на попередніх ітераціях.
Після створення часткового рішення агенти переміщуються у зворотному напрямку, тобто вони повертаються у вулик, де можуть брати участь у процесі вербування шляхом виконання танцю, тим самим обмінюючись інформацією про різні створені часткові рішення. Після відвідування вулика агенти знову переміщуються у прямому напрямку й продовжують створювати часткові рішення. Ітерація закінчується тоді, коли створюється хоча б одне припустиме рішення. Таким чином, BCO, як і методи динамічного програмування, вирішує комбінаторні задачі оптимізації поетапно.
Виходячи з викладеного, можна зазначити, що у BCO, на відміну від описаного раніше методу бджолиної колонії, немає поділу в ролях агентів (зайняті фуражири, незайняті фуражири й розвідники), і рішення складається поетапно, у міру знаходження часткових рішень, поки не буде отримано повне прийнятне рішення.
Метод FBS призначений для розв’язання задач, що характеризуються невизначеністю, агенти під час розв’язання задачі вико-
Lucic і Teodorovic першими використали основні принципи колективного інтелекту бджіл для розв’язання задач комбінаторної оптимізації. Вони розробили так званий метод системи бджіл (Bee System, BS) і перевірили його під час вирішення задачі комівояжера. На основі BS було запропоновано метаевристичний метод бджолиної колонії (Bee Colony Optimization Metaheuristic, BCO) і метод нечіткої бджолиної системи (Fuzzy Bee System, FBS).
Відповідно до FBS при додаванні компонента рішення до власного рішення агент може розглядати його як: «менш корисний», «корисний» або «більш корисний». Також агенти здатні розрізняти додаткові властивості: «короткий», «середній» або «довгий», «нецінний», «середній» або «цінний».
Особливості розглянутих модифікацій методу бджолиної колонії та відмінності між ними наведено в таблиці 7.2.
Таблиця 7.2
ВІДМІННОСТІ Й ОСОБЛИВОСТІ МОДИФІКАЦІЙ
МЕТОДУ БДЖОЛИНОЇ КОЛОНІЇ
Критерій порівняння |
Метод |
BCO-JSSP |
BCO |
FBS |
Процедура виконання звивистого танцю |
Моделюється тривалість виконання танцю |
Виконується залежно від якості складеного рішення |
Як такої процедури кружляючого танцю немає. Моделюється шляхом виконання вербування |
Вибір агентіврозвідників |
Початкова кількість агентів-розвідників дорівнює загальній кількості агентів. Після вербування кількість розвідників зменшується |
Розвідниками є всі незайняті фуражири |
Усі незайняті фуражири є розвідниками |
Особливості вибору рішень розвідником |
Розвідники знаходять рішення випадковим |
Розвідники створюють випадкові рі |
Використовується інформація, залишена попередніми |
|
|
|
|
|
|
|
|
|
|
|
|
чином
шення
агентами
Дослідження рішень за рахунок інших агентів |
Здійснюється за рахунок того, що вербування здійснюється фактично в кожному вузлі |
Завербовані агенти просто переміщуються по обраному рішенню |
Не відбувається. Зайняті фуражири переміщуються по обраному рішенню |
Клас розв’язуваних задач |
Задача календарного планування |
Задачі комбінаторної оптимізації |
Задача про складання пар |
Вербування |
Здійснюється при виборі агентом наступного пункту в графі рішень |
Здійснюється після створення власного рішення |
Вербування відбувається виходячи з корисності рішення |
ристовують правила нечіткої логіки для організації зв’язку між агентами та їхніми діями.
Виходячи з різних застосувань методу бджолиної колонії можна виділити такі переваги останнього:
— метод є несхильним до зациклення в локальних оптимумах, оскільки заснований на випадковому пошуку;
— мультиагентність реалізації;
— пошук кращого рішення ґрунтується на рішеннях агентів усієї колонії бджіл;
— може використовуватися в динамічних застосуваннях, оскільки здатен адаптуватися до змін навколишнього середовища;
— може використовуватися для вирішення як дискретних, так і безперервних задач оптимізації.
— не приводить до циклічності в локальних оптимумах, оскільки базується на випадковому пошуку;
— застосовується в динамічних додатках, оскільки здатний адаптовуватися до змін навколишнього середовища;
До недоліків методу бджолиної колонії можна віднести:
— досить високу ітеративність;
— труднощі теоретичного аналізу процесу одержання рішень, обумовлені тим, що пошук рішення має стохастичну природу;
— апріорну невизначеність часу збіжності, хоча збіжність гарантується;
— залежність методу від налаштування параметрів, які підбираються експериментально.
18.8. PSO-метод
Оптимізація з використанням рою часток (Particle Swarm Optimization, PSO)
— це метод пошуку, що базується на понятті популяції, і моделює поведінку птахів у зграї та косяків риб. Первісною метою використання концепції рою часток була графічна імітація гарного й непередбачуваного руху птахів або риб у зграї, з метою виявлення базових принципів, завдяки яким птахи літають (риби плавають) синхронно та вміють змінювати напрямок руху з перегрупуванням в оптимальні формації. З тих часів концепція розвинулася в простий і перспективний оптимізаційний метод.
У PSO-методі особини, що називаються частками, переміщуються в багатовимірному просторі рішень. Зміни координат часток усередині простору пошуку обумовлюються природною соціально-психологічною тенденцією часток конкурувати між собою. Отже, зміни в стані частки залежать від досвіду й знань її
Особини в рої часток мають дуже просту поведінку: вони прагнуть перевершити досягнення сусідніх часток і поліпшити власні. Таким чином, емергентна властивість даної системи полягає в дослідженні оптимальних ділянок багатовимірного простору пошуку. PSO-метод керує роєм часток і кожна частка являє собою потенційне рішення. За аналогією з еволюційними стратегіями, рій можна трактувати як популяцію, а частку як індивіда (або хромосому). Отже, частка «літає» у багатовимірному просторі рішень, а її позиція визначається виходячи із власного досвіду і досвіду своїх сусідів.
За допомогою x i (t) позначається позиція частки i у просторі пошуку в момент часу t (t позначає дискретні значення часу). Позиція частки змінюється додаванням швидкості v i (t) до поточної позиції:
Початковий стан визначається в такий спосіб:
),()0( maxmin xxUx i = чисел з діапазону [a,b]. Ця формула (13.1) являє собою вектор швидкості й визначає сам оптимізаційний процес, а також відображає використання як отриманих знань частки, так і обмін інформацією із сусідніми частками. Власні знання самої частки, що також називаються когнітивним компонентом формули швидкості, прямо пропорційні поточній відстані частки від її найкращого положення, що було знайдено з моменту старту її життєвого циклу. А обмін інформацією даної особини з іншими є соціальним компонентом формули швидкості. Історично було розроблено два підходи, які фактично є різновидами базового PSO-методу: gbest та lbest; вони відрізняються ступенем зв’язаності часток у просторі пошуку. ),()0( maxmin xxUx i = , де U(a, b) є функцією генерації випадкових чисел з діапазону [a,b]. Ця формула (13.1) являє собою вектор швидкості й визначає сам оптимізаційний процес, а також відображає використання як отриманих знань частки, так і обмін інформацією із сусідніми частками. Власні знання самої частки, що також називаються когнітивним компонентом формули швидкості, прямо пропорційні поточній відстані частки від її найкращого положення, що було знайдено з моменту старту її життєвого циклу. А обмін інформацією даної особини з іншими є соціальним компонентом формули швидкості. Історично було розроблено два підходи, які фактично є різновидами базового PSO-методу: gbest та lbest; вони відрізняються ступенем зв’язаності часток у просторі пошуку.
18.9. Аналіз різновидів PSO-методу
У різновиді gbest PSO-методу кожна частка зв’язана з усім роєм. Частки утворюють так звану соціальну мережу, що в gbest відповідає топології типу «зірка» (рис. 7.8). Кожна частка може взаємодіяти з усіма іншими частками, і вона тяжіє до кращого рішення всього рою. Частка імітує загальне оптимальне рішення,
сусідів. У цьому випадку слово «знання» є синонімом «інформації». Результат такого моделювання полягає в тому, що процес пошуку мотивує частки недетермінованим чином повертатися в оптимальні ділянки простору рішень.
Рис. 7.8. Топологія типу «зірка»
У gbest PSO-методі швидкість частки обчислюється за формулою: ijстанти прискорення, які використовуються для варіювання ваг когнітивного й соціального компонентів швидкості частки відпо]1,0[. Ці випадкові величини привносять стохастичний елемент у роботу методу.
Величина y i відображає найкращу позицію частки i, яку вона відвідувала, починаючи з першої ітерації. Наступна оптимальна де ??? x n f: — фітнес-функція, x n ? — множина значень незалежних змінних, що оптимізується. Так само, як і в еволюційних під-
тому її швидкість залежить від інформації, одержуваної від усіх інших. У цьому випадку соціальним компонентом швидкості є найкраща досягнута позиція рою (у просторі рішень), і вона позначається як ).(*ty
Глобальний найкращий оптимум )(*ty у момент часу t визначається як: ))},(()),...,((min{))(*(|)}(),...,({)(*
00 tyftyftyftytyty s n s n =? де s n — загальна кількість часток у рої. Важливо відзначити, що відповідно до формули (13.4) *y — це найкраща позиція, знайдена кожною із часток. Глобальний оптимум також може бути розрахований на основі інформації про частки з даного рою: ))}.(()),...,((min{)(*
0 txftxfty s n =
Локально найкраща позиція частки i y*, тобто краща позиція, знайдена в сусідстві N i та визначається як: ,)},(min{))}1(*(|{)1(* iiii ?xxftyf?ty??=+?+ де сусідство визначається за формулою: )},(),...,(),(),(),...,(),({
111 tytytytytytyN i N niiii i N ni i N nii++?+?? = для сусідства розмірністю i N n .
Виконаємо порівняння різновидів базового PSO-методу. Включимо в аналіз також модифікований метод, що гнучко регулює швидкості часток у просторі пошуку. Порівняльний аналіз проведемо на основі найбільш важливих і істотних розбіжностей, виявлених під час дослідження їх, а також на основі запропонованих критеріїв. Аналіз наведено у табл. 7.3.
Різновиди lbest і gbest базового PSO-методу подібні в тому плані, що в обох випадках вони рухаються до глобального оптимуму при оновленні компонентів швидкості.
Але між цими підходами існує дві важливі розбіжності, що впливають на збіжність:
— через більший ступінь зв’язності часток між собою (топологія «зірка») gbest PSO-метод сходиться швидше; однак швидка збіжність веде до менш ретельного дослідження простору рішень;
— різновид lbest PSO-методу має менший шанс потрапити в локальний оптимум і знайти, таким чином, тільки субоптимальне рішення; з другого боку, даний метод працює більш повільно, ніж gbest.
ходах, вона є мірою близькості даного рішення до оптимального, а також фітнес-функція визначає продуктивність, або якість частки.
Таблиця 7.3
ПОРІВНЯЛЬНИЙ АНАЛІЗ РІЗНОВИДІВ PSO-МЕТОДУ
Розглянемо компоненти швидкості більш детально.
1. Попередня швидкість v i (t) виступає в ролі пам’яті частки, тобто містить інформацію про її переміщення в минулому. Цю пам’ять можна визначити як імпульс, що запобігає стрибкоподібним змінам напрямку руху частки. Дана швидкість також є інерційним компонентом.
2. Когнітивний компонент c
1 r
1 (y i – x i ) визначає продуктивність i-ої частки відносно минулих результатів і виступає в ролі індивідуальної пам’яті про найбільш оптимальні позиції даної частки. Використовуючи його, частка може повертатися в стани, які були найкращими для неї в минулому. Це є однією з емергентних властивостей системи в цілому.
3. Соціальний компонент c
2 r
2 (y* – x i ) у gbest PSO або )*(
22ii xyrc? в lbest PSO визначає продуктивність частки відносно сусідніх або зв’язаних з нею. Завдяки йому частка має можливість пересуватися в оптимальні позиції, які були знайдені сусідніми частками.
Ступінь внеску когнітивного й соціального компонентів визначається випадковими величинами c
1 r
1 та c
2 r
2 , відповідно.
Ефект впливу швидкості на поведінку частки можна зобразити графічно. Розглянемо рух частки у двовимірному просторі рішень. Рис. 7.9, а) відображає стан одиничного рою в момент часу
t. У момент часу t + 1, як показано на рис. 7.9, б) індивідуальна найкраща позиція частки не змінилася, але інші компоненти однаково пересувають її у напрямку кращої частки )(*ty.t. У момент часу t + 1, як показано на рис. 7.9, б) індивідуальна найкраща позиція частки не змінилася, але інші компоненти однаково пересувають її у напрямку кращої частки )(*ty.
Інерція x(t + 1)
Нова швидкість x(t + 2)
Нова швидкість x(t + 1)
Когнітивна швидкість швидкість Інерція x(t + 1)
Нова швидкість x(t + 2)
Когнітивна швидкість y(t) x(t) Інерція
Нова швидкість
Соціальна швидкість x(t + 1) y*(t) х
1 х
2 а)б)х
1 х
2 y(t) x(t) x(t + 1) y*(t)
Когнітивна швидкість
Нова швидкість x(t + 2)
Рис. 7.9. Геометрична ілюстрація зміни швидкості й позиції частки:
а) момент часу t; б) момент часу t + 1 а) момент часу t; б) момент часу t + 1
18.10. Напрями використання PSO-методу
Перші напрями використання PSO-методу варто віднести до навчання нейронних мереж (НМ) прямого поширення. З тих пір у цілій низці робіт було доведено, що PSO-метод також можна застосовувати як метод навчання НМ будь-якої архітектури. У подібних розробках варто визначити потрібний вигляд фітнесфункції, що може бути подана як функція помилки, яку потрібно мінімізувати. Кожна частка в PSO-методі являє собою окреме рішення оптимізаційної проблеми, у цьому випадку — це ціла НМ. А кожна координата частки в просторі пошуку — це значення відповідного вагового коефіцієнта.
Р. Еберат та Д. Кеннеді надали перші результати застосування різних модифікацій PSO-методу в задачах навчання НМ з учителем і без нього. Мендес досліджував якість роботи цих методів з використанням різноманітних топологій (кільце, квадрат, зірка, піраміда). Хірата досліджував можливості gbest і lbest підходів у задачах навчання.
С. Жанг та Х. Шао запропонували використання PSO-методу до безперервної оптимізації ваг НМ і її архітектури. Для цього варто використати два рої часток: перший шукає оптимальну архітектуру, а другий — оптимізує ваги. Частки в першому рої пересуваються тільки у двох вимірах: перша координата — кількість схованих шарів, а друга — щільність зв’язків. На першій ітерації роботи алгоритму частки ініціалізуються випадковим чи-
Нехай d attract — глибина атрактанта (корисних речовин) клітини, а w attract — міра ширини атрактанта. Клітини виключають одна одну за допомогою локального споживання, а також за рахунок того, що клітини не є їжею одна для одної. Нехай h repellent = d attract — висота шкідливої речовини (репелент), і w repellent — міра ширини репеленту. Таким чином, можна використати функцію J i cc (X), i = 1, 2, ... , S для моделювання сигналів між клітинами за допомогою виділення бактеріями атрактанта й репеленту: ?? ??? == === ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??+ + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???== S i p j i jjrepellentrepellent S i p j i jjattractattract S i i cccc XXwh XXwdJXJ
11 2
1 ,)(exp )(exp)( де X = [x
2
11
1 , ... , x p ] T — точка в просторі оптимізації.
Важливими особливостями такого підходу до розрахунку J cc (X) є:
— значення J cc (X) не залежить від значення цільової функції в точці ?;
— за рахунок варіювання коефіцієнтів w attract та w repellent можна впливати на поведінку популяції бактерій у процесі пошуку: при малих значеннях w attract і більших значеннях w repellent популяція схильна до великого розсіювання в просторі пошуку, у протилежному випадку, тобто при малих значеннях w attract і більших значеннях w repellent популяція схильна до групування в невеликих областях пошуку.
Очевидно, що сила виділення хімічних речовин бактеріями залежить від навколишнього середовища, тобто бактерія, що перебуває в середовищі з високою концентрацією корисних речовин, виділятиме більш сильний атрактант, ніж та сама бактерія в області з низькою концентрацією корисних речовин. Тому в даному методі використовується функція J ar (?) для моделювання взаємодії між областями з урахуванням особливостей навколишнього середовища: J ar (X) = exp(M – J(X))J cc (X), де M — параметр, значення якого обирається експериментально. Отже, для пошуку оптимуму необхідно мінімізувати вираз (J(i, j, k, l) + J ar (X i (j, k,
ном у заданих інтервалах. Частки другого рою шукають оптимальний набір ваг НМ. Даний PSO-метод для кожної частки з першого рою створює групу часток у другому. Після того як метод закінчить свою роботу, вибирається потрібна архітектура й відповідна їй оптимальна множина ваг НМ.
Отже, метод оптимізації на основі моделювання переміщення бактерій з групуванням за рахунок зв’язку між областями відрізняється від базового методу тим, що мінімізується не просто функція J(i, j, k, l), а мінімізується сума: J(i, j, k, l) + J ar (X i (j, k, l)), що дозволяє враховувати становище всіх бактерій у популяції.