Генетичні алгоритми (ГА) — це методи оптимізації та пошуку, натхненні біологічною еволюцією, які запропонував Джон Голланд у 1970-х роках. Популяція кандидатів-розв'язків (особин) кодується у вигляді хромосом — рядків бітів, чисел чи інших представлень — і еволюціонує через покоління за допомогою операторів, що імітують відбір, кросовер (рекомбінацію) та мутацію. На кожному поколінні особини оцінюються функцією пристосованості, і ті, що мають вищу пристосованість, з більшою ймовірністю розмножуються та передають свої "гени" наступному поколінню.
Еволюцію рухають три базові оператори. Відбір переважно копіює особин з високою пристосованістю (методами турнірного відбору, рулетки чи рангового відбору). Кросовер поєднує сегменти двох батьківських хромосом, утворюючи нащадків — за аналогією зі статевою рекомбінацією, — що дозволяє комбінувати вдалі "будівельні блоки" (схеми). Мутація випадково змінює окремі гени з невеликою ймовірністю, запобігаючи передчасній збіжності до локальних оптимумів і підтримуючи генетичну різноманітність. Взаємодія цих операторів дозволяє ГА досліджувати складні, розривні, багатомодальні ландшафти пристосованості, недоступні для градієнтних методів оптимізації.
Цей симулятор еволюціонує популяцію розв'язків у напрямку цілі, показуючи прогрес пристосованості з покоління в покоління, показники генетичної різноманітності та ландшафт пристосованості. Ви можете налаштувати розмір популяції, частоту кросоверу, частоту мутацій і тиск відбору, щоб спостерігати фазові переходи між дослідженням, що зберігає різноманітність, і експлуатацією, що максимізує пристосованість — центральним протиріччям еволюційних обчислень. ГА вже розв'язували задачі планування, проєктували антени, еволюціонували архітектури нейромереж і оптимізували молекули ліків.
Чим генетичний алгоритм відрізняється від градієнтного спуску?
Градієнтний спуск вимагає, щоб функція пристосованості (втрат) була диференційовною, і рухається до локальних оптимумів, рухаючись у напрямку градієнта. Він погано працює з розривними функціями, функціями з багатьма локальними мінімумами та задачами, де розв'язки не можна природно представити як неперервні вектори. Генетичні алгоритми не роблять жодних припущень про ландшафт пристосованості: вони здатні працювати з дискретними представленнями, розривними та зашумленими функціями, багатомодальними ландшафтами з багатьма локальними оптимумами. ГА одночасно досліджують багато областей простору пошуку завдяки популяції, жертвуючи ефективністю градієнтного спуску заради стійкості до складних ландшафтів.
Що таке теорема про схеми і чому вона важлива?
Теорема Голланда про схеми дає теоретичне пояснення того, чому ГА працюють. Схема — це шаблон, який відповідає підмножині хромосом (наприклад, 1**0* відповідає всім 5-бітним рядкам, що починаються з 1 і мають 0 у четвертій позиції). Теорема стверджує, що схеми з пристосованістю вищою за середню, короткою визначальною довжиною (біти розташовані близько один до одного) і низьким порядком (мало фіксованих бітів) отримують експоненційно зростаюче представлення з покоління в покоління. Ця гіпотеза будівельних блоків пропонує, що ГА неявно шукають і комбінують короткі, низького порядку, високопристосовані шаблони — будівельні блоки хороших розв'язків — хоча явного пошуку будівельних блоків у коді немає.
Що таке компроміс між дослідженням і експлуатацією в генетичних алгоритмах?
Дослідження означає пошук нових, ще не відвіданих областей простору розв'язків (підтримка різноманітності); експлуатація означає вдосконалення вже знайдених найкращих розв'язків (збіжність). Висока частота мутацій і низький тиск відбору посилюють дослідження; низька мутація і високий тиск відбору посилюють експлуатацію. Надмірна експлуатація спричиняє передчасну збіжність — популяція сходиться до локального оптимуму раніше, ніж знайдено глобальний. Надмірне дослідження заважає збіжності до будь-якого гарного розв'язку. Адаптивні ГА регулюють частоту мутацій на основі показників різноманітності, а техніки нішування (розподіл пристосованості, скупчення) підтримують кілька різноманітних підпопуляцій, що одночасно досліджують різні піки пристосованості.
Кросовер поєднує сегменти двох батьківських хромосом, потенційно створюючи нащадка з комбінацією вдалих рис кожного з батьків, якими жоден із них окремо не володів. У багатомодальному ландшафті дві особини, що перебувають на різних локальних оптимумах, можуть дати нащадка поблизу кращого оптимуму, недосяжного жодному з батьків самою лише мутацією. Це аналогічно статевому розмноженню в біології: рекомбінація перемішує генетичний матеріал, дозволяючи корисним мутаціям з різних ліній об'єднатися в одній особині — процес значно швидший, ніж очікування, поки всі мутації виникнуть в одній лінії. Ефективність кросоверу залежить від того, наскільки кодування відображає структуру задачі (навчання зчеплення генів).
ГА та споріднені еволюційні алгоритми досягли помітних інженерних успіхів: антена космічного апарата NASA ST5 була еволюціонована за допомогою ГА — вигнута дротяна форма, яку жоден інженер-людина не вигадав би, але яка перевершила традиційні конструкції. ГА оптимізували згортання білків, дизайн молекул ліків, компонування НВІС-схем, торгові стратегії на фінансових ринках та форми аеродинамічних профілів. Google AutoML використовує еволюційні методи для пошуку архітектур нейромереж. У дослідженні операцій ГА розв'язують задачі маршрутизації транспорту, планування робіт і складання розкладів — NP-складні задачі, недоступні точним методам у реальних масштабах.