Алгоритм мурахи

Алгоритм мурахи 

Тут розглядається ефективний алгоритм, заснований на застосуванні декількох агентів, за допомогою якого можна вирішувати найрізноманітніші завдання. Алгоритми мурахи (Ant algorіthms), або оптимізація за принципом мурашиної колонії (ця назва була придумана винахідником алгоритму, Марко Дориго (Marco Dorіgo)), мають специфічні властивості, властиві мурахам, що використовують їх для орієнтації у фізичному просторі. Природа пропонує різні методики для оптимізації деяких процесів (наприклад, "метод відпалу"). Алгоритми мурахи особливо цікаві тому, що їх можна використовувати для рішення не тільки статичних, але й динамічних проблем, наприклад, проблем маршрутизації у мінливих мережах. 

Природна мотивація 

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

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

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

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

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

Коли одна мураха досягає їжі, вона бере один з об'єктів і повертається до мурашника по тому ж шляху. За час T2 друга мураха вже повернулася в мурашник з їжею, а перша мураха лише досягла їжі. 

При переміщенні кожної мурахи на шляху залишається небагато ферменту. Для першої мурахи за час T0-T2 шлях був покритий ферментом тільки один раз. У той же самий час друга мураха покрила шлях ферментом двічі. За час T4 перша мураха повернулася в мурашник, а друга мураха вже встигла ще раз сходити до їжі й повернутися. При цьому концентрація ферменту на нижньому шляху буде у два рази вище, ніж на верхньому. Тому перша мураха наступного разу вибере нижній шлях, оскільки там концентрація ферменту вище.

У цьому й складається базова ідея алгоритму мурахи – оптимізація шляхом непрямого зв'язку між автономними агентами.

Алгоритм мурахи

Докладно розглянемо алгоритм мурахи, щоб зрозуміти, як він працює при рішенні конкретної проблеми.

Граф

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

Мураха

Мураха – це програмний агент, що є членом великої колонії й використовується для рішення якої-небудь проблеми. Мураха забезпечується набором простих правил, які дозволяють йому вибирати шлях у графі. Він підтримує список табу (tabu lіst), тобто список вузлів, які він уже відвідав. Таким чином, мураха повинен проходити через кожен вузол тільки один раз. Шлях між двома вузлами графа, по якому мураха відвідала кожен вузол тільки один раз, називається шляхом Гамільтона (Hamіltonіan path), по імені математика сера Вільяма Гамільтона (Sіr Wіllіam Hamіlton).

Вузли в списку "поточної подорожі" розташовуються в тому порядку, у якому мураха відвідувала їх. Пізніше список використовується для визначення довжини шляхів між вузлами.

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

Початкова популяція

Після створення популяції мурахи порівну розподіляється по вузлах мережі. Необхідний рівний поділ мурах між вузлами, щоб всі вузли мали однакові шанси стати відправною точкою. Якщо всі мурахи почнуть рух з однієї точки, то це буде означати, що дана точка є оптимальною для старту, а насправді ми цього не знаємо.
Рух мурахи
Рух мурахи ґрунтується на одному й дуже простому імовірнісному рівнянні. Якщо мураха ще не закінчила шлях (path), тобто не відвідала всі вузли мережі, для визначення наступної грані шляху використовується рівняння 4.1:

Тут

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

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

Зверніть увагу, що дане рівняння застосовується до всього шляху, при цьому кожна грань позначається ферментом пропорційно довжині шляху. Тому варто дочекатися, поки мураха закінчить подорож і тільки потім обновити рівні ферменту, у противному ж випадку реальна довжина шляху залишиться невідомою. Константа – це значення між 0 й 1. Випаровування ферменту На початку шляху в кожної грані є шанс бути обраною. Щоб поступово видалити грані, які входять у гірші шляхи в мережі, до всіх граней застосовується процедура випаровування ферменту (Pheromone evaporatіon). Використовуючи константу р з рівняння 4.3, ми одержуємо рівняння 4.4.

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

Повторний запуск 

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

Приклад ітерації 

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

Дві мурахи перебувають у вузлі V0 й позначаються як A0 й A1. Оскільки ймовірність вибору будь-якого шляху однакова, у цьому циклі ми проігноруємо рівняння вибору шляху. На мал. 4.6 кожна мураха вибирає свій шлях (мураха A0 йде по верхньому шляху, а мураха A1 – по нижньому). У таблиці на мал. 4.6 показано, що мураха A0 зробив 20 кроків, а мураха A1, - тільки 10. По рівнянню 4.2 розраховуємо кількість ферменту, що повинен бути "нанесений".

(Примітка. Роботу алгоритму можна змінити, перевизначивши його параметри (наприклад, , a чи b), наприклад додавши більшу вагу ферменту або відстані між вузлами.) 

Далі по рівнянню 4.3 розраховується кількість ферменту, що буде нанесено. Для мурахи A0 результат становить: 0,1 + 0,5·0,6 = 0,4. 

Для мурахи A1 результат становить: 0,1 + 1,0·0,6 = 0,7. 

Далі за допомогою рівняння 4.4 визначається, яка частина ферменту випарується й, відповідно, скільки залишиться. Результати (для кожного шляху) відповідно становлять: 

= 0,4 ·(1,0 0,6) = 0,16; 

=0,7 ·(1,0 0,6) = 0,28. 

Ці значення представляють нову кількість ферменту для кожного шляху (верхнього й нижнього, відповідно). Тепер перемістимо мурах назад у вузол V0 і скористаємося імовірнісним рівнянням вибору шляху 4.1, щоб визначити, який шлях повинні вибрати мурахи. Імовірність того, що мураха вибере верхній шлях (представлений кількістю ферменту 0,16), становить:

(0,16)3 ·(0,5)1 /((0,16)3 · (0,5)1 + ((0,28)3 ·(1.0)1 ) = 0,002048/0,024 = Р(0,085). 

Імовірність того, що мураха вибере нижній шлях (0.28 ферменту) становить: (0,28)3 ·(1,0)1 / ((0,16)3 ·(0.5)1 ) + ((0,28)3 ·(1,0)1 ) = 0,021952 / 0,024 = Р(0,915). 

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

Інші області застосування 

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

При рішенні завдання розподілу ресурсів (Quadratіc Asіgment Problem – QAP) необхідно задати групу ресурсів n для ряду адресатів m і при цьому мінімізувати витрати на перерозподіл (тобто функція повинна знайти найкращий спосіб розподілу ресурсів). Виявлено, що алгоритм мурахи дає рішення такої ж якості, як і інші, більш стандартні способи. 

Набагато складніша проблема розподілу роботи (Job-shop Shedulіng Problem – JSP). У цьому завданні група машин М и завдань J (що складаються з послідовності дій, здійснюваних на машинах) повинні бути розподілені таким чином, щоб всі завдання виконувалися за мінімальний час. Хоча рішення, знайдені за допомогою алгоритму мурахи, не завжди є оптимальними, застосування алгоритму для даної проблеми показує, що з його допомогою можна вирішувати аналогічні завдання. 

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

Підсумки 

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