Zoom

Ідентификатор персональної конференції 687-349-9091
https://us04web.zoom.us/j/6873499091?pwd=amVFZWthTTR6anhuYVhQSkhQWVpEdz09
Password L4yVV1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Еволютор

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

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

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

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

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

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

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

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

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

Програма

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

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

Ant Program Tab 2
Рис.3. Вкладка Програма
Симулятор

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

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

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

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

Рішення Карта
Легкі купки їжі Три купки (може підняти 1 мураха)
Важкі купки їжі Шість купок їжі (1,3,6 – може підняти відповідна кількість мурашок)
Сім купок їжі (6 - можуть підняти 6 мурашок)
Десять купок їжі (9 - можуть підняти 9 мурашок)
Водний потік, який можна перетнути через мурашиний міст Одна легка (1) купка їжі (1) і водний потік
Водний потік і дерева. Річку можна перетнути через міст з листя Три купки легкої їжі (1), дерево
Важкі купки їжі і водний потік Шість купок важкої їжі (5) і водний потік

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

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

Параметри

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

Параметр Значення за замовчуванням Опис
Чисельність популяції 1000 Кількість мурашок у популяції. Це кількість випадкових рішень, які будуть створені при запуску еволюційної програми.
Ймовірність, що вузол є листом в дереві рішень 55 Під час створення випадкових мурашиних програм, це ймовірність, що даний вузол буде вузлом листя у дереві двійкових програм. Числа менше 50% можуть спричиняти нескінченно великі програми, тому існує параметр Максимальний розмір програми.
Максимальний розмір програми 99 Під час випадкового створення мурашиних програм це максимальна кількість вузлів у дереві двійкових програм.
Розмір турніру 4 Кількість мурашиних програм з популяції, які відібрані для проведення змагання для кросовера. Кращі два рішення з турніру використовуються в кросовері і замінюють два гірші рішення в турнірі.
Мутація% 100 Шанси, що нові мурашині програми, що створені кросовером, будуть змінені. Мутація змінить одну інструкцію в програмі мурашок. Листові вузли замінюються іншими листовими вузлами. Нелистові вузли (якщо висловлювання) замінюються іншими нелистовими вузлами.
Жадібна мутація% 80 Ймовірність, що мутація буде жадібною (придатність повинна збільшуватися при мутації). Якщо мутація не покращує програму, то мутація відхиляється.
Залишкова харчова цінність 100000000 Скільки кожного шматка їжі, не принесеного до мурашника, впливає на придатність мурашиної програми.
Не використана цінність їжі 1000000 Скільки кожного не знайденого (не підібраного) шматка їжі впливає на пристосованість мурашиної програми.
Залишкова цінність води 1000 Скільки кожного квадрата води на карті впливає на придатність програми мурашок. Примітка: Це небезпечна властивість для функції придатності, оскільки вона може винагородити мурашок за загибель особин, що втопилися у воді і зробили мурашиний міст.
Значення складності програми 100 Наскільки розмір мурашиної програми впливає на придатність мурашиної програми. Дивіться групу складності програми нижче.
Складність програми для груп 50 Використовується для групування мурашиних програм подібних розмірів, так що значення складності програми менше впливає на придатність. Таким чином, за всіх інших рівних факторів рішення з 1 вузлом і з 49 вузлами матиме однакову придатність, тоді як рішення з 50 вузлами буде гіршим.
Значення швидкості рішення 1 Кількість часу для того, щоб перенести всю їжу до мурашника впливає на пристосованість програми мурашок. Кількість ітерацій, необхідних для виконання програми, ділиться на 100 і потім множиться на це число.
Кількість мурашок 25 Кількість мурашок, які виконують складають популяцію.
Сила феромону 300 Кількість феромону, що виділяється на ReleasePheromone
Швидкість поширення феромону 40 Кількість феромону, який поширюється на сусідні квадрати. Якщо це число становить 40%, то 10% феромонів поширюються до кожного з 4 сусідніх квадратів. Феромони повністю розпиляються через помилку округлення.
Очікування на допомогу % 98 Коли мураха намагається підняти важку їжу, а мурашок бракує - це ймовірність, що інструкція if (TiredOfWaiting) буде True.
Кількість обертів на мураху 1000 Максимальна кількість обертів мурашок, щоб знайти всю їжу. Кожен раз, коли кожна мураха виконує програму мурашок, - це один оборот.
Автоматичне скидання їжі коли мураха перебуває у мурашнику Відмічено Якщо мураха досягає мурашника, то автоматично скидає їжу. Якщо це не встановлено, тоді DropFood оператор повинен бути включений до набору інструкцій.
Набір інструкцій

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

Оператори Опис
MoveRandom Переміщення мурашки на один інтервал в будь-якому з 4 кардинальних напрямків.
MoveQuasiRandom Те саме, що і MoveRandom, але має більшу ймовірність для просування мурашки вперед, і меншу для пересування назад.
MoveToNest Переміщення мурашки у напрямку до мурашника. Передбачається, що мурахи знають, як без допомоги повернутися до свого гнізда.
MoveToNest-ThroughWater Те саме, що і MoveToNest, але якщо на шляху є вода, мураха залишає їжу, занурюється у воду і гине, щоб збудувати мурашиний міст.
TurnLeft Поворот ліворуч на 90 градусів.
TurnRight Поворот праворуч на 90 градусів.
MoveForward Перемістіть один крок вперед.
PickUpFood Взяти їжу, якщо їжа існує в поточному місці, а мураха не несе на цей момент їжу чи листок
DropFood Викинути їжу, що несе мураха, а в даному місці немає їжі чи листя.
PickUpLeaf Взяти лист, якщо в поточному місці є дерево або листя, якщо мураха не несе листок або їжу.
DropLeaf Викинути лист, що несе мураха, а в поточному місці немає листя або їжі.
DropLeafInWater Якщо перед мурашкою є вода, то скинути лист у цей простір.
ReleasePheromone Вивільнення феромонів.
MoveIntoWater Якщо вода попереду, зануритися у неї і загинути. Викинути їжу, якщо мураха її несе.
EscapePheromone Просуватися вперед, поки не виявлено феромон. Якщо трапляється перешкода, повернути у випадковому напрямку та продовжувати рух. Після 20 ходів відмовитися від спроб уникнути феромону.
NoOp Не робіти нічого.

Оператори не з переліку Опис
Two Statements () Інструкція, що дозволяє виконувати 2 твердження в блоці if або else.
if (FoodAhead) Якщо в просторі перед мурашкою є їжа.
if (FoodLeft) Якщо в лівому місці від мурашки є їжа.
if (FoodRight) Якщо в правому просторі від мурашки є їжа.
if (FoodAdjacent) Якщо в будь-якому з 4-х просторів поруч з мурашкою є їжа.
if (FoodHere) Якщо є їжа в тому самому місці, що і мурашка.
if (PheromoneHere) Якщо є феромони в тому ж місці, що і мураха.
if (LeafHere) Якщо є листя або дерево в тому ж місці, що і мурашка.
if (CarryingFood) Якщо мураха несе їжу. Ця умова справедлива, навіть якщо мураха не може підняти їжу.
if (CarryingLeaf) Якщо мурашка несе лист.
if (AtNest) Якщо мурашка знаходиться в місці мурашника.
if (MoveToAdjacentFood) Якщо є сусідній шматок їжі (перейти до їжі).
if (MoveToAdjacentLeaf) Якщо в одному з двох напрямків від мурашки є лист або дерево (переміститися до листя).
if (MoveTo-Pheromone
AwayFromNest)
Якщо в одному з двох напрямків від мурашника є феромон (просуватися до феромону, просуватися до найсильнішого, якщо в обох напрямках є феромони).
if (MoveToDeadAnt) Якщо попереду мертва мураха (просуватися до мертвої мурахи).
if (MoveTo Strongest-Pheromone) Якщо є сусідній феромон (перейти до найсильнішого сусіднього феромону).
if (MoveToNest) Якщо немає перешкод, що перегороджує шлях до мурашника (пересуватися до мурашника).
if (MoveToNest-ThroughWater) Якщо немає перешкод, що перегороджує шлях до мурашника (пересуватися до гнізда. Якщо попереду вода, кинути їжу, пірнути у воду і загинути).
if (WaterAhead) Якщо попереду вода.
if (ObstacleAhead) Якщо попереду стіна.
if (AnotherAntHere) Якщо в цьому місці є ще одна мурашка.
if (CantLiftFood) Якщо в цьому місці недостатньо мурашок, що допомагає підняти важкий шматок їжі.
if (TiredOfWaiting) Якщо чекати на допомогу інших мурашок, щоб підняти важкий шматок їжі протягом певного періоду часу

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

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

Символ Предмет Опис
Нічого Пробіл у місці розташування нічого не вказує.
N Гніздо Куди починають мурашки і куди привозять їжу.
W Вода Можна перетнути мурах, що рухаються до води та будують мурашиний міст.
O Перешкода Мурахи не можуть перетнути.
T Дерево Дерево, з якого мураха може отримати листя.
1-9 Їжа Кількість - це кількість мурашок, необхідних для підбору їжі.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фігури

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

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

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

Контрольні запитання

  1. Для вирішення яких завдань призначені алгоритми колективної поведінки.
  2. Які корисні властивості мурашиної колонії запозичено для реалізації алгоритмів колективної поведінки.
  3. Назвати основні параметри програми мурашиної колонії, що впливають на якість результатів.
  4. Які програмні команди можна налаштувати для поведінки мурах.
  5. Назвати особливості еволюційних алгоритмів, який практичний зміст вони несуть.
  6. Які основні налаштування закладено в програмі «Генетичний ставок»
  7. Назвати критерії за якими особини обирають свою пару, як їх можна змінити.
  8. Чим завершується еволюція в генетичному ставку при різних параметрах.
  9. Назвати правила поведінки в грі «Життя Конвея».
  10. Перелічіть основні фігури, що утворюються в грі «Життя Конвея»

Лабораторне завдання

  1. Ознайомитися з теоретичними матеріалами щодо алгоритмів еволюції та колективної поведінки.
  2. Запустити програми і ознайомитися з описом роботи додатків. Здійснити низку досліджень в кожному з додатків: з параметрами, що встановлено за замовченням, зі зміненими параметрами.
  3. Проаналізувати отримані результати, з'ясувати причини неякісних результатів і зробити висновки.
  4. По результатах роботи оформити звіт. Під час захисту лабораторної роботи вільно володіти теоретичним матеріалом: особливості алгоритмів, усталені терміни, коло практичного застосування алгоритмів.

Зміст звіту

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