Природні та еволюційні алгоритми

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

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

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

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

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

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

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

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

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

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

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

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

Перевірка всіх варіантів проходження по N містах буде N!. Для розрахунку 20 турів по місту доведеться виміряти загальну відстань приблизно в 2.43 × 10¹⁸ маршрутів різних турів. Припускаючи близько трильйона операцій в секунду, це займе мільйони років. Додавання ще одного міста призведе до збільшення кількості розрахунків на 21!. Очевидно, що такий підхід неприпустимий і перевірка всіх варіантів для 20 міст практично неможлива.

Саме тому використовують евристики та метаевристики (генетичні алгоритми, алгоритми мурашиної колонії, бджолиний алгоритм, рій частинок тощо)

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

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

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

Рис. 1. JS-демонстрація вирішення задачі комівояжера генетичним алгоритмом

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

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

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

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

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

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

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

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

Рис. 2. JS-демонстрація мурашиного алгоритму

Еволюційні симуляції

Життя Конвея (Conway's Game of Life)

«Гра життя» — це найвідоміший приклад клітинного автомата, який у 1970 році винайшов математик Джон Конвей. Це не «гра» у звичному розумінні, бо в ній немає гравців, які роблять ходи. Це «гра з нульовою кількістю гравців»: ви задаєте початковий стан клітин, а далі лише спостерігаєте, як система розвивається сама за певними правилами. Всесвіт гри — це безкінечна сітка з квадратних клітинок, кожна з яких може бути або «живою», або «мертвою».

Основні правила

Кожне наступне покоління клітин розраховується на основі попереднього за трьома простими правилами, що враховують 8 сусідів кожної клітини:

• Виживання: Якщо у живої клітини є 2 або 3 живих сусіди, вона залишається живою.
• Смерть: Якщо у живої клітини менше 2 сусідів (самотність) або більше 3 (перенаселення), вона помирає.
• Народження: Якщо у мертвої клітини є рівно 3 живих сусіди, вона «оживає».

Незважаючи на простоту цих правил, у грі виникають надзвичайно складні структури:

• Статичні фігури, що не змінюються (наприклад, «Блок»).
• Фігури, що циклічно змінюють свою форму (наприклад, «Блінкер»).
• Рухомі фігури (Космічні кораблі, Glider), які переміщуються по полю.

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

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

Рис.3. Демонстрація Життя Конвея

Генетичний ставок GenePool (Оригінал)

GenePool — це відома симуляція штучного життя (Alife), створена Джеффрі Вентреллою (Jeffrey Ventrella). Якщо «Гра життя» Конвея — це математична абстракція, то GenePool — це віртуальна лабораторія еволюції. У цій симуляції живуть цифрові організми («плавці» або «swimmers»), які існують у 2D-середовищі, шукають їжу, розмножуються та передають свої гени наступним поколінням.

В основі лежить генетичний алгоритм. Кожна істота має свій «геном», який визначає:

• Кількість частин тіла, їхню форму, довжину, товщину та колір.
• Поведінку, як ці частини рухаються (амплітуда, частота, фаза коливань).

Процес еволюції відбувається поетапно:

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

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

Хоча GenePool виглядає як наукова забава, принципи еволюційного моделювання можна використати в галузі штучного інтелекту

• Еволюція нейронних мереж (Neuroevolution). Замість стандартного навчання через помилки (backpropagation), можна використовувати генетичний алгоритм для «вирощування» структури нейронної мережі та підбору її ваг.
• Ігрова індустрія. Створення процедурно-генерованих істот або адаптивних NPC (неігрових персонажів), які змінюють свою стратегію бою, підлаштовуючись під гравця.

Рис.4. Демонстрація GenePool

Реалізації природних алгоритмів у Python

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

1. Універсальні фреймворки (багато алгоритмів в одному)

Ці бібліотеки є найбільш потужними, оскільки дозволяють порівнювати різні підходи (PSO, ACO, ABC тощо) в межах одного коду.

• PyPop7. Сучасна та дуже потужна бібліотека, яка підтримує величезну кількість популяційних алгоритмів, включаючи PSO, ABC, Firefly, Bat, Cuckoo Search та багато інших.
• Mealpy. Мабуть, найбільш повна бібліотека. Вона містить понад 150 алгоритмів, включаючи всі згадані вами: Wolf Pack, Monkey Search, Fish School, Ant Colony та інші.
• NiaPy. Мікро-фреймворк для природних алгоритмів. Добре структурований, підтримує PSO, BA, FFA, CSS.
• PySwarms. Спеціалізована та дуже популярна бібліотека саме для PSO (Particle Swarm Optimization). Вона має докладну документацію та інтеграцію з NumPy.

2. Спеціалізовані рішення за типами алгоритмів

• PSO (Рой частинок). PySwarms, MealPy
• ACO (Мурахи). AntColony (для задачі комівояжера) або MealPy
• ABC (Бджоли). BeePy або Mealpy
• CSA (Зозулі). CuckooSearch (у складі NiaPy або MealPy)
• WPS, BA, FFA, MS, FSS. Найкраще реалізовано в NiaPy або MealPy

3. Гібридні та еволюційні фреймворки

Якщо вам потрібна висока продуктивність або можливість створювати власні варіації алгоритмів:

• DEAP (Distributed Evolutionary Algorithms in Python). Це "золотий стандарт" для еволюційних обчислень. Хоча вона більше орієнтована на генетичні алгоритми, її гнучкість дозволяє легко реалізувати PSO або ACO.
• PyGMO (Python Parallel Global Multiobjective Optimization). Дуже швидка (написана на C++ з інтерфейсом Python), підтримує паралельні обчислення та складні топології роїв.

Вибір алгоритму

• Якщо потрібно швидко протестувати різні алгоритми (наприклад, порівняти Вовків з Кажанами) — обирайте Mealpy.
• Якщо це наукове дослідження і потрібна стабільність та візуалізація PSO — обирайте PySwarms.
• Якщо потрібна максимальна швидкість для складних обчислень — використовуйте PyGMO.