Zoom

Алгоритм мурашиної колонії

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

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

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

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

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

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

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

Рис.1. Інтерфейс програми мурашиної колонії

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

Використано два варіанти проблем з збиранням їжі.

• Додавання води до навколишнього середовища, де мурашки будуть збирати їжу. Розміщення потоку у навколишньому середовищі, що повністю відділяє мурашок від води, створює потребу в більшій кількості мурах. Мурашки будуть змушені будувати "мурашиний міст", щоб перетнути воду. Деяким мурахам доведеться перебратися в потік і загинути, щоб побудувати міст для інших мурах, які переносять їжу. Якщо кожний мураха пірне у воду, щоб збудувати міст, тоді вони всі загинуть, і не лишиться кому зібрати їжу. Якщо жодна мураха не зануриться у воду, то вони не зможуть зібрати їжу.
• Важкий шматок їжі можна підняти лише кількома мурашками, щоб донести до мурашника. Мурашки не лише повинні працювати разом, але й повинні знайти спосіб повідомити оточуючих про потребу в допомозі. Також виникає проблема, коли всі мурашки чекають біля різних шматків їжі, щоб інші мурахі допомогли це донести. Якщо є три мурашки, кожна окремо намагається підняти свій шматок їжі, для підняття якого потрібно дві мурашки, то нічого не вийде. Для деяких мурашок, але не всіх, потрібно знайти спосіб відмовитися від їжі та допомогти іншим мурашкам. Це надзвичайно складно, оскільки всі мурашки працюють за однією програмою.

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

Інтерфейс додатку Ant Food Collection містить 3 вкладки:

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

Вкладка 2: Програма. На цій вкладці можна переглянути рішення, яке було щойно реалізовано. Також можна подивитися деякі готові рішення або написати власні.

Вкладка 3: Симулятор. Ця вкладка містить карту в якій наочно спостерігати виконання алгоритмів поведінки мурашок. Можна запустити програму, для якої здійснено налаштування, програму, яку написано власноруч, або одне з готових рішень, що входять до додатку. Також, можна створити власну карту для запуску алгоритму або налаштувати її на вкладці Evolver.

Еволютор

Ця вкладка є фактичною еволюційною програмою і використовується для розробки рішення певної проблеми. За замовченням все налаштовано, щоб почати вирішення простої проблеми з збиранням їжі, потрібно просто натиснути Start Genetic Program (Запустити генетичну програму) (рис.2).

Рис. 2. Вкладка Еволютор

Для застосування власних налаштувань доступні наступні опції:

• Вибір карти для демонстрації алгоритму. Зазвичай, залежить від складності проблеми. Карту обирають за допомогою комбінованого вікна "Завантажити карту". Можна вибрати кілька готових карт або спроектувати власну карту на 3-й вкладці додатку. Додавання води, перешкод або важких шматків їжі (що потребує більше ніж 1 мураху для піднімання), це ускладнює роботу алгоритму.
• Вибір набору інструкцій для дій мурашок. Зліва наведено перелік інструкцій, які можна включити в програми мурашок. Не відмічена Інструкція не буде використовуватися для створення початкової конфігурації або під час мутації. Детальну інформацію про кожну інструкцію можна отримати в Наборі інструкцій.
• Як мінімум, має бути увімкнута інструкція PickUpFood, інакше мурашки не зможуть донести їжу до мурашника. Якщо зняти прапорець "Автоматично викидати їжу, коли мураха знаходиться в мурашнику", тоді слід включити інструкцію DropFood. Існує кілька різних інструкцій, які дозволяють мурахам рухатися і потрібно увімкнути хоча б одну з них. Також непогано включити інструкцію "Два стани (Two Statements)", які зберігаються у бінарному дереві і дозволяє виконувати дві різні інструкції в блоці if або else.
• Якщо їжа знаходиться за водним потоком, то є два варіанти.
• Якщо на карті розміщені дерева, можна включити стани PickUpLeaf та DropLeafInWater. Це дозволяє збирати листя з дерева, щоб використовувати міст через воду.
• Якщо на карті немає дерев, потрібно включити стан MoveIntoWater. Це призведе до того, що мурашки занурюються у воду і гинуть. Це створює мурашиний міст для того, щоб інші мурашки переходили по ньому через воду.
• Інші статуси не потрібні, але потрібно вибрати деякі з них, щоб допомогти мурахам приймати рішення. Наприклад, якщо не увімкнуто стан if (Food Carried), мураха не може знати, чи варто повертатися до мурашника чи слід продовжувати шукати їжу. Варто подивитися інформацію на сторінці "Результати (Results)", де наведено актуальні результати еволюційної програми або на сторінці "Рішення (Solutions)", що рішення деяких стандартних проблем. Переглянути готові рішення можна на другій вкладці програми.
• Не варто робити проблему надто складною, щоб мурашки не змогли розпочати роботу. Якщо вся їжа знаходиться через річку, то більшість програм алгоритму нічого не виконає. Якщо частина їжі знаходиться поблизу мурашника, то деякі програми, які можуть знайти та забрати їжу, матимуть кращу придатність, ніж ті, що не можуть, хоча жодна програма не дозволить мурашкам перепливати воду. Таким чином, програми, які можуть забрати їжу поблизу, частіше будуть як "батьки" в кросовер-операції. В іншому випадку до програми, яка є всіма NoOp, трактуються так само, як майже повне рішення, яке просто не може перетнути воду.

Інші розділи, які потрібно налаштувати, щоб розпочати роботу, - це: початкова популяція, кросовер / мутація, обчислення та параметри транслятора. Отримати детальну інформацію про ці параметри можна на сторінці " Параметри Parameters".

• Параметри "Початкова популяція (Initial Population)" використовуються для створення початкового набору випадкових мурашиних програм: налаштувати кількість програм та відносний розмір кожної програми.
• Кросовер та мутація використовуються для створення нових програм (рішень) мурашок на основі поточної популяції. Дві кращі програми популяції обираються як «батьки». Ці дві програми використовуються для створення двох нових програм «нащадків», що мали б бути кращими, ніж батьки. Після кросовера кожний нащадок піддається мутації. Мутація випадковим чином змінює одну інструкцію в програмі.
• Параметри обчислення фітнес-функції (функції придатності) використовуються для оцінювання кожної програми. Чим нижча функції придатності, тим краще. Параметри придатності визначають, наскільки кожний параметр впливатиме на функцію придатності. Наприклад, за замовченням принесення їжі до мурашника є найважливішим, тому це має найвищу цінність і найбільший вплив на придатність.
• Інтерпретатор використовується для виконання програми мурашок на даній карті. Варіанти інтерпретатора впливають на поведінку мурах.

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

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

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

Програма

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

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

Рис.3. Вкладка Програма

Симулятор

На вкладці тренажера будуть показані мурашині програми в дії. Для запуску програми мурашок потрібно вибрати карту та програмне рішення. За замовченням на карті все налаштовано для простої проблеми з збиранням їжі (рис.4).

Рис.4. Вкладка Симулятор

Карту можна вибрати з поля "Завантажити карту", створити власну або використовувати карту з першої вкладки. Щоб створити ландшафт карти, слід натиснути одну з піктограм карт, а потім клацнути на карті, щоб розмістити цей елемент. Кожна карта повинна містити мурашник і хоча б один шматочок їжі.

Використовуйте текстове поле "Завантажити рішення", щоб вибрати рішення для запуску. Можна вибрати розроблене рішення з Вкладки 1, рішення, що створене вручну з Вкладки 2, або скористатися одним із готових рішень.

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

Після налаштування слід натиснути кнопку «Тестувати Рішення (Test Solution)», щоб запустити алгоритм.

Параметри

Успіх генетичної програми ґрунтується на обраних параметрах з першої вкладки додатку.

Набір інструкцій

Програми мурашок зберігаються як бінарне дерево. Набір інструкцій для мурашиних програм поділяється на дві категорії: "Стан Листа" та "Стан не Листа ". "Стан Листа" – це дії, які виконує мураха. Ці стани не можуть мати нащадків. "Стан Не Листа" - це умови. Якщо умова істинна, виконується ліва гілка вузла НЕ Лист. Якщо умова помилкова, виконується права гілка. Умови також можуть мати побічні ефекти. Ці побічні ефекти - це дії, які виконуються, якщо умова справжня, перед виконанням лівої гілки.

Карта додатку

Типовий розмір карти - 40x40. Карту можна завантажити з файлу або створити за допомогою інтерфейсу користувача. Елементи карти та їх символи, які можуть відображатися у файлі карти, наведено нижче.

• Рішення - письмові рішення можливих рішень різних проблем.
• Результати - результати різних тестів.
• Завантажити додаток
• Вихідний код

Еволюційне моделювання

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

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

Генетичний ставок

Це комп'ютерне моделювання простору, де розвиваються сотні віртуальних організмів - свімботів. У свімбота є два базових інстинкту: харчування і розмноження. Їхні тіла складаються з сегментів, якими свімбот повинен ворушити певним чином, щоб плисти. Рух свімбота моделюється відповідно до реальної фізики поведінки тіл у рідких середовищах. Чим краще він плаває, тим більша ймовірність, що не загине від голоду, знайде партнера для розмноження, і, отже, передасть свої гени майбутньому поколінню (рис.5).

Рис.5. Інтерфейс симулятора «Генетичний ставок»

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

Основними діями свімботів є базові функції:

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

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

Пункти меню:

• Pool. Створення початкової конфігурації ставка, збереження поточної та завантаження збережених конфігурацій. Створюючи новий ставок, можна заселити його повністю випадковими істотами, створити групу споріднених істот, заселити весь басейн зеленими істотами з двома гребними лапками, або ж підготувати порожню ємність.
• Tweak. Налаштування параметрів ставка: швидкість наростання і поширення їжі, приріст енергії для свімбота від їжі, межа залишкової енергії, нижче якої інстинкт розмноження поступається місцем інстинкту харчування і відсоток енергії, який віднімається від свімбота при народженні у нього нащадка. В цій закладці можна налаштувати ознаку, за якою свімботи будуть вибирати кращого партнера для схрещування (колір, розмір, енергійність, форма тіла).
• Swimbot. Інформація про обраний свімбот, а також меню для зміни його генів. ДНК свімбота містить послідовність з 70 чисел, кожне з яких кодується 1 байтом (28 = 256 значень). Отже, можлива множина різних комбінацій, що призводять до появи нових різноманітних особин. Кодується забарвлення і будова тіла, траєкторії руху частинами свого тіла, залежно від напрямку на ціль. Можна зберігати ДНК цікавих екземплярів і обмінюватися ними.
• Population. Графіки зміни населення басейну і кількості їжі. Якщо свімбот вчасно не прийме їжу, то він починає поступово гинути: забарвлення починає сіріти, рухи стають млявими. Користувач можете допомогти певній особині вижити – піднести свімбота до крихти їжі. В актиного, ситого свімбота з'являється білий вектор, що свідчить про наявність енергії щодо схрещення і продукування нащадків. Спостерігається залежність: більше їжі – більше нащадків, більше нащадків – менше їжі, менше їжі – загибель особин і виродження популяції.
• View. Вибір режиму перегляду, зокрема, можна знайти найбільш енергетично ефективного свімбота, який залишив найбільшу кількість нащадків або з'їв найбільшу кількість їжі.

Клітинні автомати та гра «Життя Конвея»

Гра "Життя" відноситься до категорії моделюючих ігор, які в тій чи іншій мірі імітують процеси, що відбуваються в реальному житті. Життя, як природний процес - явище настільки складне і захоплююче, що тисячі вчених намагалися розкрити її таємниці. Свій внесок у вирішення цієї проблеми зробив і чоловік, не мав до біології ніякого відношення, англійський математик Джон Хортон Конвей.

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

Місце дії гри на площині, що поділена на клітинки. Кожна клітинка може перебувати в одному з двох станів: бути живою або бути мертвою. Клітинка має вісім сусідів. Розподіл живих клітинок на початку гри називається першим поколінням (рис.6).

Рис. 6. Поле для гри «Життя Конвея»

Кожне наступне покоління утворюється на основі попереднього за усталеними правилами.

• Якщо в живої клітини є два чи три живих сусіди – то вона лишається жити.
• Якщо в живої клітини є один чи жодного живого сусіда – то вона помирає від «самотності».
• Якщо в живої клітини є чотири та більше живих сусідів – вона помирає від «перенаселення».
• Якщо в мертвої клітини є три живих сусіди – то вона оживає.

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

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

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

Фігури

Ці прості правила призводять до виникнення величезної кількості різноманітних форм, кожна з яких має дещо спільне з попередньою. На цей час склалася така система їхньої класифікації:

• Стійкі фігури. Лишаються незмінними після кожної ітерації
• Періодичні фігури (осцилятори). Фігури, стан яких повторюється через деяку кількість поколінь.
• Рухливі фігури (космічні кораблі, глайдери або планери). Фігури, стан яких повторюється, але з деяким зсувом у просторі.
• Гармати. Фігури, стан яких повторюється, але кожен цикл вони додатково створюють фігури, що рухаються.
• Паротяги. Рухливі фігури, які залишають за собою сліди у вигляді стійких або періодичних фігур.
• Пожирачі. Стійкі (або періодичні) фігури, які можуть при зіткненні з деякими рухливими фігурами зберігати свій стан, знищуючи рухому фігуру.
• Довгожителі. Фігури, що довго змінюються, перш ніж стабілізуватися (тобто, перетворитися на групу фігур, стан яких постійний чи періодично повторюється)

Відео лабораторної роботи