Еволюція як оптимізація
У 1975 році інформатик Джон Голланд опублікував працю Adaptation in Natural and Artificial Systems ("Адаптація в природних і штучних системах"), заклавши теоретичний фундамент для генетичних алгоритмів. Його центральна ідея була елегантною: природний відбір — це алгоритм пошуку. Еволюція не слідує плану чи градієнту — вона підтримує популяцію кандидатних розв'язків, перевіряє кожен на відповідність середовищу й дозволяє найкращим розмножуватися, тоді як решта гине. З покоління в покоління цей сліпий процес знаходить надзвичайно витончені розв'язки надзвичайно складних задач.
Паралель із комп'ютерною оптимізацією пряма. Визначте функцію пристосованості — міру того, наскільки хороший будь-який заданий розв'язок. Почніть із випадкової популяції кандидатних розв'язків. Багаторазово відбирайте більш пристосованих особин для розмноження, комбінуйте їхній "генетичний матеріал", вносьте випадкові зміни й оцінюйте нове покоління. Повторюйте, доки не з'явиться достатньо хороший розв'язок.
Похідна не потрібна. Гладкий ландшафт не передбачається. Попереднє знання структури розв'язку не потрібне. Алгоритм шукає, пробуючи різні варіанти, зберігаючи те, що працює, і відкидаючи те, що не працює — так само, як чотири мільярди років біологічної еволюції породили все розмаїття життя на Землі.
Кодування розв'язків у вигляді хромосом
Перш ніж еволюція зможе працювати над задачею, задачу потрібно перекласти у форму, з якою еволюція може діяти. У біологічній еволюції хромосома — це послідовність нуклеотидів, що кодує інструкції для побудови організму. У генетичних алгоритмах хромосома — це рядок бітів, чисел або символів, що кодує кандидатний розв'язок.
Вибір кодування не тривіальний — він кардинально визначає, що алгоритм може знайти і як швидко він це знаходить. Розгляньмо задачу комівояжера: за списком міст знайти найкоротший маршрут, що відвідує кожне рівно один раз і повертається до початку. Природне кодування — це перестановка індексів міст: для п'яти міст хромосома може мати вигляд [3, 1, 4, 2, 5], тобто "відвідати місто 3, потім 1, потім 4, потім 2, потім 5". Функція пристосованості — просто обернена до загальної довжини маршруту: коротші маршрути мають вищу пристосованість.
Інші стилі кодування підходять для інших задач. Задачі неперервної оптимізації часто використовують хромосоми з дійсними значеннями. Архітектури нейронних мереж можна кодувати як рядки, що вказують розміри шарів і схеми з'єднань. Задачі планування кодують хромосоми як упорядковані списки завдань. У кожному випадку кодування має допускати змістовну рекомбінацію — змішування двох хороших розв'язків має мати реальний шанс дати ще один хороший розв'язок, а не випадковий шум.
Генетичні оператори
Еволюційний пошук рухають три операції:
- Відбір визначає, які особини отримують можливість розмножуватися. Ключове завдання — надати більш пристосованим особинам більше репродуктивних можливостей, повністю не усуваючи слабо пристосованих — зберігаючи різноманітність. Турнірний відбір випадково вибирає невелику групу й обирає найкращу; відбір методом рулетки присвоює кожній особині ймовірність, пропорційну її пристосованості. Обидва підходи балансують використання хороших розв'язків із дослідженням нових областей.
- Схрещування (рекомбінація) поєднує дві батьківські хромосоми, створюючи нащадка. У одноточковому схрещуванні випадкова позиція розділяє хромосому кожного з батьків, і нащадок отримує один сегмент від кожного. Двоточкове схрещування використовує дві точки розриву, обмінюючи середній сегмент. Рівномірне схрещування незалежно обирає кожен ген від одного з батьків із рівною ймовірністю. Схрещування — головний механізм поєднання корисних ознак, виявлених у різних особинах.
- Мутація випадково змінює окремі гени — перемикає біт, зміщує дійсне значення, обмінює два елементи в перестановці. Частоту мутацій тримають низькою (зазвичай 0,1–1% на ген за покоління), щоб не руйнувати хороші розв'язки, але достатньо високою, щоб підтримувати різноманітність і дозволяти популяції вибиратися з локальних оптимумів, з яких саме лише схрещування вибратися не може.
Разом ці три оператори реалізують паралельний пошук: уся популяція одночасно досліджує простір розв'язків, а інформація про хороші області передається через схрещування щопокоління.
Збіжність і різноманітність
Центральне протиріччя будь-якого генетичного алгоритму — це баланс між дослідженням і використанням. Популяція, що збігається надто швидко — коли всі особини стають майже ідентичними — застрягає в тому локальному оптимумі, який знайшла першим, і не може відкрити кращі розв'язки в інших частинах простору пошуку. Це називається передчасною збіжністю, і це найпоширеніша причина невдач генетичних алгоритмів.
Кілька технік допомагають підтримувати різноманітність. Розподіл пристосованості (fitness sharing) штрафує особини, надто схожі на інших у популяції, розподіляючи пошук по кількох піках ландшафту пристосованості. Острівні моделі запускають кілька підпопуляцій паралельно з періодичною міграцією між ними — кожен острів може збігатися незалежно, але мігранти запобігають повній ізоляції. Ніширування явно резервує місце в популяції для розв'язків із різних областей простору пошуку.
Правильний баланс залежить від задачі. Для задач із єдиним глобальним оптимумом на відносно гладкому ландшафті добре працює агресивний відбір і низька мутація. Для сильно мультимодальних задач із багатьма локальними оптимумами схожої пристосованості підтримка різноманітності критично важлива — мета полягає в тому, щоб картографувати весь ландшафт, а не просто піднятися на найближчий пагорб.
Спостерігайте за еволюцією популяцій у реальному часі: наш симулятор еволюційної теорії ігор дозволяє засіяти популяцію різними стратегіями й спостерігати за природним відбором — співпрацею, зрадою і всім, що між ними — упродовж поколінь. Динаміка збіжності й різноманітності стає видимою одразу.
Реальні застосування
Генетичні алгоритми знайшли розв'язки інженерних задач, які людям-конструкторам було б непросто знайти самостійно — а в деяких випадках навіть уявити:
- Еволюціонована антена NASA: для місії Space Technology 5 інженерам знадобилася компактна антена з певними характеристиками підсилення й імпедансу в кількох частотних діапазонах. Генетичний алгоритм еволюціонував антену, що виглядає як хаотично зігнутий дріт — вона не має явної симетрії чи інтуїтивно зрозумілої структури, проте перевершує звичайні конструкції за кожним цільовим показником. Інженери-люди, обмежені інтуїтивними уявленнями про те, як "повинна" виглядати антена, ніколи б її не знайшли.
- Пошук ліків: молекулярні структури можна кодувати як хромосоми й еволюціонувати в напрямку бажаних властивостей зв'язування, профілів токсичності та біодоступності. ГА використовують для дослідження величезного хімічного простору потенційних лікарських кандидатів значно ефективніше, ніж скринінг грубою силою.
- Планування екіпажів авіакомпаній: призначення тисяч членів екіпажу на рейси з дотриманням профспілкових правил, вимог щодо відпочинку та кваліфікацій — це NP-складна задача оптимізації. Генетичні алгоритми регулярно знаходять близькі до оптимальних розклади, що заощаджують авіакомпаніям мільйони доларів щороку.
- Пошук архітектур нейронних мереж: сучасні системи ШІ використовують еволюційні методи для автоматичного виявлення архітектур нейронних мереж — структури та зв'язності моделей глибокого навчання, — які перевершують вручну спроєктовані альтернативи.
Генетичні алгоритми проти інших методів оптимізації
Генетичні алгоритми не завжди правильний інструмент. Градієнтний спуск — робочий кінь машинного навчання — набагато швидший, коли ландшафт пристосованості гладкий і диференційовний, бо він може напряму слідувати градієнту до локального оптимуму. ГА потребують багатьох оцінок пристосованості й повільніші порівняно з ним у задачах, де застосовний числовий аналіз.
Але ГА розкриваються там, де градієнтні методи зазнають невдачі:
- Функція пристосованості недиференційовна — вона включає дискретні вибори, комбінаторну структуру або симуляцію.
- Ландшафт грубий — сповнений локальних оптимумів, у яких градієнтні методи застрягли б.
- Простір розв'язків змішаний неперервно-дискретний, що робить стандартні підходи на основі числового аналізу незручними.
- Задача настільки багатовимірна, що аналітичні методи непридатні.
Імітація відпалу (simulated annealing) розв'язує деякі з тих самих задач, що й ГА — вона може вибиратися з локальних оптимумів, іноді приймаючи гірші розв'язки, причому ймовірність цього зменшується з часом, як охолодження металу. Але вона працює з єдиним розв'язком, а не з популяцією, втрачаючи перевагу паралельного пошуку. Оптимізація роєм часток (particle swarm optimization) використовує популяцію, подібно до ГА, але оновлює розв'язки за допомогою векторів швидкості, а не генетичних операторів, і чудово підходить для задач неперервної оптимізації.
Тривкий урок генетичних алгоритмів полягає не в тому, що вони завжди перемагають — а в тому, що еволюція як алгоритм набагато загальніша й потужніша, ніж здається на перший погляд. Маючи лише функцію пристосованості й достатньо поколінь, вона здатна підкорити гори складності, які жодному інженерові не подужати самотужки.