НОУ ІНТУЇТ | лекція | мурашині алгоритми

1. 12.1. Біологічний прототип і найпростіші моделі

Анотація: Дана лекція присвячена методам оптимізації, заснованим на поведінці мурашиних колоній (Ant Colony Optimization - ACO), які останнім часом набули широкого поширення. Розглядається біологічний прототип і непряма форма спілкування особин колонії - стігметрія, яка заснована на тому, що мурахи по шляху руху відкладають спеціальний фермент - феромон. Моделювання цього способу обміну інформацією лежить в основі даного підходу. Запроваджується базовий мурашиний алгоритм з основними формулами визначення відкладається концентрації феромона і ймовірності вибору шляху в залежності від цієї концентрації. Мурашиний алгоритм ілюструється на прикладі задач вибору оптимальних шляхів на графах (наприклад, завдання комівояжера). Описано численні модифікації і узагальнення базового мурашиного алгоритму. Розглянуто його параметри і їх вплив на ефективність методу. Обговорюється застосування цього методу в мінливому середовищі. Виконано порівняння мурашиних і генетичних алгоритмів.

12.1. Біологічний прототип і найпростіші моделі

Мурахи з'явилися на землі більше 100 мільйонів років тому і в даний час їх популяція складає особин [ 1 ], Загальна вага якої можна порівняти з вагою проживають людей. Більшість мурах є соціальними комахами, які живуть колоніями від 30 до мільйона особин. При відносно простому поведінці кожної окремої особини мурашині колонії представляють складну соціальну структуру і здатні вирішувати складні завдання, наприклад, знаходити оптимальні шляхи від гнізда до джерела їжі. Це привернуло увагу багатьох дослідників, які вивчали механізми взаємодії особин колонії. Серед них, перш за все, привернула увагу дослідників непряма форма зв'язку між особинами, яка була названа "стігметрія" ( "stigmergy") і являє собою рознесене в часі взаємодія, при якому одна особина змінює деяку область навколишнього середовища, а інші особи використовують цю інформацію в процесі виконання завдання. Ця інформація (зміна навколишнього середовища) носить локальний характер - вона може бути змінена (і сприйнята) тільки комахами, які відвідали цей локус - ділянку середовища. Стігметрія є непрямий і асинхронної формою комунікації, в якій комахи змінюють навколишнє середовище для передачі інформації іншим комахам, які реагують на цю зміну. Слово "stigmergy" утворено з двох грецьких слів: "stigma", що означає знак; "Ergon" - робота. Особи сприймають сигнали (у вигляді знаків), які породжують деякий відгук або дію. Визначено дві форми стігметріі [ 2 ]: Сематектоніческая (sematectonic) і знакова (sign-based). Сематектоніческая відноситься до комунікації за допомогою зміни фізичних характеристик навколишнього середовища. Прикладом сематектоніческой стігметріі є дії при будівництві гнізда, його очищення і вирощуванні виводка. Сигнальна стігметрія реалізує комунікацію за допомогою сигнального механізму у вигляді хімічних сполук, що відкладаються мурахами.

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

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

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

Розглянемо експерименти з перешкодами, які показані на ріс.12.1 , ріс.12.2 , рис.12.3 , рис.12.4 [ 3 ].

Рис.12.1.

Рух мурах без перешкоди.
Рис. 12.2. Перешкода на шляху між гніздом і їжею.
Рис. 12.3. Початкова фаза руху мурах з перешкодою.
Рис. 12.4. Вибір мурахами найкоротшого шляху.

Тут на першому малюнку показано рух мурах між гніздом і джерелом їжі без перешкоди. далі на ріс.12.1 , ріс.12.2 , рис.12.3 , рис.12.4 показаний характер руху в тому випадку, коли на шляху виникла перешкода.

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

Не менш відомий експеримент з двома мостами був проведений з колонією аргентинських мурашок, який представлений на ріс.12.5 , ріс.12.6 [ 4 ] .Тут на шляху між гніздом і їжею необхідно зробити вибір одного з двох мостів.

Експеримент з двома мостами.
Рис. 12.6. Вибір найкоротшого шляху.

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

нехай і позначають число мурах на шляхах A і B відповідно в момент часу . Емпірично було знайдено, що ймовірність вибору моста в момент часу відбувається у відповідності з наступною формулою [ 4 ]:

де характеризує ступінь "привабливості" недослідженою гілки, і визначає зміщення при використанні феромону в процесі вибору варіанта рішення. На основі ймовірностей, які визначаються (12.1), правило вибору мурахою моста можна сформулювати наступним чином. Нехай випадковим чином генерується число U (0,1) в інтервалі (0,1).

якщо , То мураха вибирає шлях A, інакше - шлях B.

Відзначимо, що незважаючи на те, що мурашина колонія демонструє складне адаптивне поведінку, яке дозволяє їй вирішувати складні завдання, поведінка одного мурашки підпорядковується досить простим правилам. Мурахи можна розглядати як агента, яке зазнає впливу і формує на нього відповідну реакцію: мураха сприймає концентрацію феромона і на цій основі виконує дію. Тому мураха абстрактно може розглядатися як простий обчислювальний агент. Штучний мураха алгоритмічно моделює проста поведінка реального мурашки (точніше його цікавлять нас аспекти). Логіка поведінки штучного мурашки представлена ​​в алгоритмі А12.1 [ 2 ].

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