Як працюють генетичні алгоритми
Математичний природний відбір
Генетичний алгоритм — спосіб розв’язання задач, який використовує методи, схожі на механізми еволюції. Такий алгоритм застосовують, якщо кількість можливих рішень занадто велика, щоб їх протестувати. Розповідаємо, як влаштовані генетичні алгоритми та як вони покращують роботу нейромереж.
Математична еволюція
Алгоритм починається зі створення популяції — списку моделей. Завдання для ГА важливо побудувати так, щоб кожну модель можна було представити списком чисел — набором характеристик (генів). Спочатку їх задають випадковим чином. Список рішень називають популяцією. Найкращі моделі відбирають для створення наступної популяції. Це повторюється, поки не буде знайдено задовільний результат.
Щоб встановити, наскільки якісне рішення надає модель, використовують функцію пристосованості. Її найпростіші приклади — точність передбачення та F-score. Що краще рішення, то вища ймовірність вибору особини для створення наступної популяції.
Основні етапи
Після створення початкової популяції генетичні алгоритми проходять чотири стадії:
#1. Відбір
Суть відбору в тому, щоб обрати найефективніші моделі та передати їхні гени іншому поколінню. Пари особин (батьків) відбирають залежно від пристосованості. Кількість батьків може бути довільною, але однаковою для кожного наступного циклу.
Ключові методи добору — турнірний і ранговий.
- Ранговий
Популяцію розбивають на кілька груп (рангів). Ранги присвоюють залежно від функції пристосованості та пропорційно відбирають деяку частину особин із кожного рангу. - Турнірний
Випадковим чином відбирають кілька особин. Серед них визначають найкращу. Процес повторюється, поки проміжна популяція не буде заповнена.
Універсального методу відбору не існує. У кожного — свої переваги. Ранговий відбір дає змогу зберегти більшу різноманітність моделей. Турнірний метод зручний, якщо ми можемо тільки порівнювати моделі попарно, а не виражати функцію пристосованості числом. Він підходить, наприклад, для ігрових стратегій.
#2. Схрещування
На етапі схрещування відбувається обмін даними між батьківськими парами. У популяції вибирають пари батьків і перемішують фрагменти їхніх хромосом, отримуючи новий набір генів. Часто використовують одноточкове схрещування: визначають точку розрізу хромосом у батьків, а потім міняють їхні частини. Після обміну нові дані додають у популяцію.
#3. Мутація
Вона виникає рідко і випадковим чином змінює значення окремих генів. Наприклад, змінює 1 на 0.
Мутації допомагають розширити ділянку пошуку і зберегти різноманітність у популяції. Вони можуть і поліпшити, і погіршити пристосованість особини.
#4. Завершення алгоритму
Алгоритм закінчує процес, якщо створено популяцію, яка майже не відрізняється від минулої. Це не означає, що знайдене рішення ідеальне, але воно не поліпшуватиметься.
Генетичні алгоритми vs нейромережі
ГА добре працює із завданнями, де є великий набір обмежених, дискретних даних, і знаходить рішення швидше, ніж повний перебір. Data Scientist Мішель Берк задав ГА визначити зміст зашифрованого речення Genetic Algorithms are wild. Алгоритму потрібно було вибирати з усіх можливих комбінацій — 2753. Він мав 30 особин у популяції та відгадав на 51-му поколінні. Тобто перевірив 1530 комбінацій.
Генетичний алгоритм може знайти найкоротший шлях між точками. Тому він підходить для пошуку розв’язання NP-повних проблем (як проблема комівояжера). Наприклад, ГА задіюють для розрахунку траєкторії руху або створення маршрутів для GPS-систем.
Учені також використовували клітинні автомати на основі ГА для аналізу поширення COVID-19 у 40 країнах світу протягом різного часу.
Нейромережі ж краще справляються з безперервними даними. Вони підходять для завдань класифікації (розпізнавання зображень, розуміння мови). Також нейромережі застосовують для задач лінійної регресії — пошуку залежності між змінними.
Симбіоз ГА та нейромережі
Є приклади об’єднання ГА з нейромережею. За допомогою генетичних алгоритмів можна оптимізувати роботу моделі. Наприклад, підібрати гіперпараметри (ваги або функцію активації).
Але застосування генетичних алгоритмів для підбору вимагає багато часу та обчислювальної потужності. Наприклад, щоб навчити нейромережі перемагати реальних гравців у відеоіграх. У 2017 році команда OpenAI залучала генетичний алгоритм, щоб відібрати ігри ботів у Dota 2, які проводили успішні матчі. Потім ці дані використовували для навчання нейромережі.
