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

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

      Основна ідея генетичного алгоритму полягає в еволюції популяції, що повторює деякі риси еволюції організмів в живій природі [4]. Якщо мета еволюції в живій природі – забезпечення найбільшої життєздатності популяції в умовах навколишнього середовища, то мета еволюції в генетичних алгоритмах –  отримання зразків з найкращими значеннями певних критеріїв, що характеризують якість зразка.

      Будь-який конкретний екземпляр хромосоми називають генотипом (комплекс усіх генів організму, які зумовлюють спадкові властивості), а сукупність характеристик, властивих індивіду на певній стадії розвитку – фенотипом.

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

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

      Члени вихідного покоління генеруються випадковим чином [4]. При цьому для кожного гена задана область визначення, наприклад, у вигляді інтервалу , та значення генів вибираються з рівною імовірністю в його межах. Результатом кожного чергового витка зовнішнього циклу є нове покоління, про якість якого судять по примірнику хромосоми з кращим значенням функції корисності F. Характер наближення до екстремуму зазвичай такий, що на початкових витках швидкість поліпшення цільової функції досить значна, але в міру наближення до екстремуму вона сповільнюється і може наступити припинення поліпшення F на деякому віддаленні від екстремальної точки. Це явище називають стагнацією. Зазвичай воно відбувається через виродження популяції – втрати різноманітності генного матеріалу. Пошук припиняють найчастіше при появі ознак стагнації, про що свідчить відсутність покращення стану цільової функції протягом кількох останніх поколінь, або після закінчення відведеного часу на вирішення завдання.

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

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

      Частіше за все для вибору батьків застосовують правило, зване правилом рулетки. У ньому ймовірність Pk вибору k-го члена популяції як батька визначається як відношення корисності даного члена до сумарної корисності всіх членів популяції. Якщо цільова функція мінімізується, то 
  =( - )/ ( - )

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

      Схрещення (кросове) полягає в розриві двох обраних батьківських хромосом і рекомбінуванні створених хромосомних відрізків, що дає пару хромосом-нащадків.

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

      Формування нового покоління (селекція) – це відбір членів нового покоління серед нащадків, отриманих в результаті схрещення і мутацій в даному поколінні. У базовому генетичному алгоритмі в нове покоління включається кращий з двох нащадків, породжених після схрещення. Внутрішній цикл закінчується, коли виявиться сформованим нове покоління, тобто в ньому виявиться N членів. 

      1.3. Застосування генетичних алгоритмів [1, с. 360-361]

       Основна проблема, пов'язана з використанням генетичних алгоритмів - це їх евристичний характер. Говорячи більш строго, яка ймовірність досягнення популяцією глобального оптимуму в заданій області? В даний час не існує відповіді і теоретично обґрунтованих оцінок. Є припущення, що генетичний алгоритм може стати ефективною процедурою пошуку оптимального рішення, якщо:

      - простір пошуку досить великий;

      - завдання не вимагає знаходження глобального оптимуму, необхідно досить швидко знайти прийнятне «хороше» рішення, що досить часто зустрічається в реальних завданнях.

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

      Наявність у генетичних алгоритмів цілої «популяції» розв’язків, спільно з імовірнісним механізмом мутації, дозволяють припускати 
меншу ймовірність знаходження локального оптимуму й більшу ефективність роботи на багатоекстремальному ландшафті. Сьогодні генетичні алгоритми успішно застосовуються для вирішення задач оптимізації в просторах з великою кількістю вимірювань, низки економічних завдань оптимального характеру, наприклад, завдань розподілу інвестицій. 

      2. Мурашині алгоритми оптимізації [2].

      Мурахи  належать до так званих «соціальних  комах», тобто комах, що живуть в  межах певного колективу — сім'ї або колонії. На Землі біля двох відсотків комах є «соціальними», половина з яких припадає на мурах. Поведінка мурах під час транспортування їжі, обминання перешкод, побудови мурашника тощо наближається до теоретично оптимальної. Основу «соціальної» поведінки мурах складає самоорганізація — сукупність динамічних механізмів, за допомогою яких система досягає глобальної мети в результаті взаємодії елементів на низькому рівні.  Принциповою особливістю такої низькорівневої взаємодії є використання елементами системи лише локальної інформації, без будь-якого централізованого управління та звернення до глобального образу, який репрезентує систему у зовнішньому світі. Самоорганізація є результатом взаємодії таких чотирьох компонентів:

      1) випадковість;

      2) додатний зворотний зв'язок;

      3) від'ємний зворотний зв'язок;

      4) багатократність взаємодій.

      Мурахи  використовують два способи передачі інформації: прямий — обмін харчами, мандибулярний, візуальний та хімічний контакти тощо, та непрямий — стигмержі. Стигмержі — це рознесений у часовому просторі тип взаємодії між елементами системи, коли один суб'єкт взаємодії змінює деяку частину оточуючого середовища, а решта використовує інформацію про її стан пізніше, коли знаходяться в її околі. Біологічно, стигмержі здійснюється через феромон — спеціальний секрет, який відкладається як слід під час руху мурахи. Чим вища концентрація феромону на стежці, тим більше мурах буде рухатись по ній. Феромон з часом випаровується, що дозволяє мурахам адаптувати свою поведінку до зміни оточуючого середовища. Розподіл феромону по простору пересування мурах є своєрідною глобальною пам'яттю, яка динамічно змінюється. Кожна мураха може сприймати та змінювати лише локальну чарунку цієї глобальної пам'яті мурашника.

Рис.2. Асиметричний міст 
 

      Розглянемо, як колективна поведінка біологічних мурах забезпечує знаходження найкоротшого шляху до їжі на прикладі експериментів на асиметричному мості [2, с. 63]. Асиметричний міст (рис.2) з'єднує гніздо мурах з джерелом їжі двома гілками різної довжини. Експерименти проводилися за такою схемою:

      1) будувався міст А-В-С-D;

      2) відчинялися дверцята в точці  А; 

      3) фіксувалась кількість мурах, які обрали довгий (А-С-D) та короткий (А-В-D) На початку експериментів мурахи обирали обидві гілки з однаковою ймовірністю тому, що на мості не було феромонів. Через деякий час майже усі мурахи пересувались найкоротшим маршрутом А-В-D, що пояснюється таким чином. Мурахи, які обрали короткий маршрут А-В-D-В-А, скоріше поверталися з їжею в гніздо, залишаючи феромонні сліди на короткій гілці мосту. При наступному виборі маршруту мурахи віддавали перевагу короткій гілці мосту, тому що на ній вища концентрація феромонів. Таким чином, феромон швидше накопичується на гілці А-В-D, що підштовхує мурах до вибору найкоротшого маршруту. 
 

      3. Метод бджолиних колоній.

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

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

      3.1. Біологічні основи методу бджолиної колонії [3, с. 15]

      Для описання поведінки бджіл в природі  використовуються три основні поняття: джерело нектару (квітка), зайняті робочі бджоли (фуражири), незайняті робочі бджоли.

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

      Зайняті робочі бджоли закріплені за віддаленим джерелом, в якому вони добувають нектар, тобто «зайняті» ним. Зайняті робочі бджоли володіють такою інформацією про дане джерело нектару, як: відстань і напрямок від вулика, корисність джерела.

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

      Кожна незайнята бджола може полетіти до джерела нектару за бджолою-розвідником, яка знайшла дорогу до квітки. Це досягається за рахунок того, що кожний вулик має так звану закриту площину для танцю, на якій бджоли, знайшовши джерело нектару, виконують «зигзагоподібний танець», тим самим намагаються привабити інших незайнятих бджіл іти за ними. Якщо бджола вирішує залишити вулик, щоб дістати нектар, вона летить за однією із бджіл-розвідників до місця з нектаром. Таким чином, незайнята бджола стає занятою. Механізми, у відношенні з якими вона вирішує іти за іншою бджолою, дослідженні недостатньо добре, але припускається, що вербування серед бджіл з математичної точки зору завжди являється функцією якості джерела нектару.

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

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

      3.2. Формалізація поведінки бджіл в процесі фуражування [3, с. 16]

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