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

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

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

1. Оптимізаційні задачі
   • Комбінаторна оптимізація: задача комівояжера, розклади, маршрутизація транспорту.
   • Інженерна оптимізація: підбір параметрів конструкцій, мінімізація ваги або вартості.
2. Планування та розклади
   • Складання навчальних або виробничих розкладів.
   • Розподіл ресурсів.
   • Оптимізація логістичних процесів.
3. Налаштування параметрів еволюційних моделей
   • Підбір гіперпараметрів моделей машинного навчання.
4. Робототехніка та керування
   • Еволюція стратегій руху роботів.
   • Оптимізація траєкторій.
   • Налаштування систем керування в складних середовищах.

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

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

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

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

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

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

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

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

Приклад Генетичного алгоритму

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

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

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

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

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

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

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

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

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

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

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

У стандартному генетичному алгоритмі, кросовер забезпечується випадковим вибором позиції в батьківській послідовності і обміном частин батьків. У цьому прикладі, точка перетину - між 3-м і 4-м пунктом списку.

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

Кодування не може бути просто списком міст в порядку, як вони були відвідані. Для цього створені інші методи кодування. Хоча ці методи не будуть створювати недійсні тури, вони не беруть до уваги той факт, що тур "ABCDEFG" такий же, як "GFEDCBA". Щоб вирішити цю проблему належним чином кросовер алгоритму повинен бути складніше.

Дане рішення зберігає посилання в обох напрямках для кожного туру. У наведеному вище прикладі про тури, новий батько 1 буде збережений як:

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

• Для Нащадку 1, вибір посилання буде у виборі серед Батька 2, а потім Батька 1.
• Для Нащадку 2, вибір складається з Батька 2 і Батька 1 з іншим набором посилань.

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

Зрештою, ГА зробить так, що всі рішення будуть ідентичними. Це не є ідеальним рішенням. Якщо всі особини в ГА стануть ідентичними, ГА не зможе покращити рішення. Є два способи обійти це. Перший полягає у використанні дуже великих початкових розмірів популяції, так, що ГА буде потрібно багато часу, щоб все особини стали ідентичними. Другий метод - мутація, коли випадкові нащадки мутують, створюючи новий унікальний тур.

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

Життя Конвея (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

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

Бібліотека складається з наступних модулів:

• Основний модуль, що містить імплементацію генетичного алгоритму.
• Модуль nn дозволяє створювати нейромережі.
• Gann оптимізує нейромережі з використанням генетичного алгоритму.
• Cnn призначений для створення згорткових нейромереж.
• Gacnn оптимізує згорткові нейромережі за допомогою генетичного алгоритму.

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

DEAP (Distributed Evolutionary Algorithms in Python) — "золотий стандарт" для еволюційних обчислень, обчислювальна платформа для швидкого прототипування та тестування ідей. Вона прагне зробити алгоритми явними, а структури даних прозорими. Ідеально гармоніює з механізмами паралелізації, такими як багатопроцесорність та SCOOP, має багато функцій для створення власних еволюційних рішень.