Генетичні алгоритми — Еволюційна оптимізація в інформатиці

1. Еволюційна метафора

Теорія еволюції Чарльза Дарвіна шляхом природного відбору описує, як популяції організмів змінюються з покоління в покоління: особини, краще пристосовані до середовища, виживають і успішніше розмножуються, передаючи свої ознаки нащадкам. Генетичні алгоритми (ГА), започатковані Джоном Холландом у 1970-х роках, перетворюють цей біологічний процес на обчислювальний фреймворк для розв'язання задач оптимізації та пошуку.

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

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

Уявлення простору пошуку як ландшафту пристосованості дуже наочне. Уявіть багатовимірну поверхню, де кожна точка відповідає кандидатному розв'язку, а її висота — пристосованості. Піки відповідають хорошим розв'язкам; долини — поганим. Завдання ГА — знайти найвищий пік, глобальний оптимум, не відвідуючи вичерпно кожну точку.

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

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

2. Селекція, кросовер і мутація

Три генетичні оператори рухають еволюцію в ГА. Разом селекція, кросовер і мутація визначають, як популяція змінюється від одного покоління до наступного.

Селекція

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

Турнірна селекція — найпоширеніший метод. Невелика група з k особин випадково вибирається з популяції, і перемагає найпристосованіша особина в цій групі. Значення k = 2 (бінарний турнір) дає помірний тиск відбору; більші турніри підвищують тиск і прискорюють збіжність, але ризикують передчасною збіжністю.

Рулеткова селекція (селекція, пропорційна до пристосованості) призначає кожній особині ймовірність вибору, пропорційну до її пристосованості. Уявіть колесо рулетки, де кожен сектор має розмір відповідно до пристосованості: пристосованіші особини займають більші сектори й мають більше шансів бути обраними. Цей метод може страждати, коли значення пристосованості сильно розрізняються — одна дуже пристосована особина може домінувати й швидко знизити різноманітність.

Кросовер

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

Одноточковий кросовер обирає одну точку розрізу вздовж хромосоми й обмінює хвости:

Рівномірний кросовер радикальніший: кожен ген у нащадка успадковується незалежно від одного з батьків з імовірністю 0,5. Це дає нащадків, які можуть суттєво відрізнятися від обох батьків, і особливо ефективний, коли корисні гени розкидані по хромосомі, а не зібрані в купку.

Кросовер зазвичай застосовується з імовірністю 0,6–0,9 на пару батьків. Якщо кросовер не відбувається, нащадки просто є копіями своїх батьків.

Мутація

Мутація вносить випадкові зміни в окремі хромосоми. У бінарних поданнях кожен біт незалежно інвертується з малою ймовірністю (зазвичай 0,001–0,05 на біт). У дійснозначних поданнях до значень генів додаються невеликі випадкові збурення — часто з гаусового розподілу.

Мутація виконує дві критично важливі функції: вона повертає генетичну різноманітність, яку могли розмити кросовер і селекція, і дає змогу алгоритму досліджувати ділянки простору пошуку, які наразі не займає жодна наявна особина. Без мутації алгоритм обмежений комбінуванням наявного генетичного матеріалу і ніколи не зможе вирватися з локального оптимуму, коли популяція вже до нього збіглася.

Елітизм

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

Типові гіперпараметри: розмір популяції 50–500; частота кросоверу 0,6–0,9; частота мутації 0,001–0,05 на ген; елітизм зберігає найкращі 1–5% особин.

3. Ландшафти пристосованості та збіжність

Концепція ландшафту пристосованості — запроваджена Сьюеллом Райтом у популяційній генетиці — дає інтуїтивне уявлення про те, що робить ГА. Кожна точка ландшафту відповідає одному кандидатному розв'язку, а її висота (пристосованість) показує, наскільки цей розв'язок хороший. Ефективне орієнтування в цьому ландшафті — головний виклик.

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

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

Підтримка різноманітності

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

• Розподіл пристосованості (нішування): особини в подібних ділянках простору пошуку конкурують передусім одна з одною. Пристосованість штрафується залежно від кількості подібних особин поблизу, запобігаючи домінуванню однієї ніші над популяцією. Кілька підпопуляцій можуть підтримуватися одночасно, кожна досліджуючи свій пік.
• Скупчення (crowding): нащадки заміщують найбільш подібну наявну особину, а не випадкову. Це рівномірніше розподіляє популяцію по ландшафту й запобігає надмірній експлуатації однієї ділянки.
• Острівна модель (паралельні ГА): кілька підпопуляцій еволюціонують незалежно й паралельно, з періодичною міграцією — особини переміщуються між островами через певні інтервали. Кожен острів може збігтися до свого локального оптимуму, а події міграції вносять свіжий генетичний матеріал, здатний зрушити популяції з локальних піків. Ця модель природно відповідає паралельним і розподіленим обчислювальним архітектурам.

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

4. Застосування та гібридні методи

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

Реальна інженерія

Проєктування антен: космічний апарат NASA ST-5, запущений у 2006 році, використовував антену, еволюціоновану ГА, яка перевершила за характеристиками будь-яку антену, спроєктовану людьми-інженерами. Еволюціонована антена мала нерегулярну, нелогічну на перший погляд форму, до якої жоден конструктор-людина не додумався б, проте вона відповідала всім вимогам місії з чудовими характеристиками. Це залишається одним із найвідоміших прикладів еволюційного проєктування в інженерії.

Оптимізація розкладів: цехове планування (розподіл робіт по верстатах в оптимальному порядку), складання розкладу занять в університеті, маршрутизація транспорту з часовими вікнами — це NP-складні комбінаторні задачі, де кількість можливих розв'язків астрономічно велика. ГА регулярно знаходять майже оптимальні розв'язки за прийнятний час, перевершуючи точні методи на великих задачах.

Машинне навчання

Пошук нейронних архітектур (NAS): AutoML від Google та подібні системи використовували еволюційні алгоритми для відкриття нових архітектур згорткових нейронних мереж. Еволюціоновані архітектури — такі як родина NASNet — перевершили спроєктовані вручну мережі на класифікації ImageNet, використовуючи менше параметрів. Еволюція дослідила архітектурні рішення (типи шарів, схеми з'єднань, гіперпараметри), які конструктори-люди не розглядали.

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

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

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

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

Схожі статті