CCC'2019

Природні алгоритми

Генетичні алгоритми

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

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

Особливості генетичних алгоритмів:

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

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

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

  • Ініціалізація, або вибір вихідної популяції хромосом.
  • Оцінка пристосованості хромосом в популяції.
  • Перевірка умови зупинки алгоритму.
  • Селекція хромосом.
  • Застосування генетичних операторів.
  • Формування нової популяції.
  • Вибір «найкращої» хромосоми.

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

Симулятори еволюції автомобілів

Джерело (http://rednuht.org/genetic_cars_2/)

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

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

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

У геномі автомобіля закодовано наступні параметри:

  • Форма: 8 генів, що кодують вершини трикутників.
  • Розмір коліс: 2 гена.
  • Розміщення коліс: 2 гена.
  • Щільність коліс: 2 гена.
  • Щільність шасі: 2 гена.

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

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

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

  • маса торкнеться землі
  • час закінчиться.

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

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

Перетворення слів за допомогою генетичного алгоритму

Джерела (http://planetcalc.ru/475/ http://planetcalc.ru/638/)

Емулятор покроково перетворює задане слово в інше задане слово, заміною однієї букви в попередньому слові, так щоб на кожному кроці виходило правильне слово. Емулятор працює зі словником (https://planetcalc.ru/542/), що містить слова, які складаються з 4 або 5 літер.

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

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

Як додатковий критерій зупинки введено обмеження на максимальний розмір ланцюжка. Алгоритм зупиниться, якщо після відтворення заданого числа поколінь не буде отриманий шуканий результат.
Функція пристосованості (подібності поточного слова на кінцеве) оцінювала кожне варіант за 12 бальною шкалою.

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

Таким чином, кінцеве слово СЛОН оцінювалося в 12 балів, а початкова МУХА всього в 2.

Рішення задачі комівояжера за допомогою генетичного алгоритму

Джерело (http://www.lalena.com/AI/Tsp/)

Задача комівояжера (Travelling salesman problem, TSP) - одна з найвідоміших задач комбінаторної оптимізації, що полягає у знаходженні самого вигідного маршруту, що проходить через зазначені міста хоча б по одному разу з наступним поверненням в початкове місто. В умовах задачі вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості і т. п. Як правило, вказується, що маршрут повинен проходити через кожне місто тільки один раз.

Розроблено рішення задачі комівояжера (TSP) за допомогою генетичного алгоритму (ГА). У задачі комівояжера, мета - знайти найкоротшу відстань між N різними містами. Шлях, по якому продавець повинен пройти називається туром.

Перевірка всіх варіантів проходу по N містах буде N!. Для розрахунку 30 турів по місту доведеться виміряти загальну відстань в 2,65 X 1032 різних турів. Припускаючи близько трильйона операцій в секунду, це займе 252.333.390.232.297 років. Додавання ще одного міста призведе до збільшення кількості розрахунків на 31!. Очевидно, що такий підхід неприпустимий.

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

Основні кроки у вирішенні завдання комівояжера допомогою генетичного алгоритму.

  1. Створити групу з багатьох випадкових турів в початковій популяції. Цей алгоритм використовує жадібні обчислення для формування початкової популяції, віддаючи перевагу зв'язкам міст, що знаходяться близько один до одного.
  2. Вибрати з двох кращих батьків (найкоротших турів) в популяції і скомбінувати їх, зробити двох нових нащадків. Сподіваючись, що ці нащадки будуть краще, ніж будь-який з батьків.
  3. З невеликою ймовірністю нащадки піддаються мутацї. Це робиться, щоб запобігти ідентичності всіх турів в популяції.
  4. Кращі нащадки (короткі тури) замінюють собою самі довжелезні тури в популяції. Чисельність особин в популяції залишається незмінною.
  5. Процес ітераційне повторюється до досягнення бажаної мети.

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

Для виконання роботи дивіться опис додатку.

Ройовий алгоритм птахів

Джерело (https://www.lalena.com/AI/Flock/)

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

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

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

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

Спостереження за птахами надихнуло Крейга Рейнольдса (Craig Reynolds) на створення алгоритму Boids, де запрограммовано поведінку кожного з птахів окремо, а також їх взаємодію. Розроблена поведінкова модель може бути розширена введенням додаткових чинників - таких, як пошук їжі або уникання від хижаків.

Птахи дотримуються трьох простих правил алгоритму.

  • Розділення: Кожен птах прагне уникнути зіткнень з іншими птахами..
  • Вирівнювання: Птахи прагнуть рухатися на однаковій відстані одна від одної.
  • Згуртованість: Кожен птах рухається в тому ж напрямку, що і навколиші птахи.

Для виконання роботи дивіться опис додатку.

Еволюційний алгоритм мурашиної колонії

Джерело: (https://www.lalena.com/AI/Ant/)

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

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

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

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

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

Для виконання роботи дивіться опис додатку.

Порядок роботи

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

Зміст звіту

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