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

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

Він еволюціонує випадковий рядок літер у напрямку цільової фрази, за замовчуванням METHINKS IT IS LIKE A WEASEL. Пристосованість — це просто частка позицій символів, що збігаються з ціллю. Це відтворює знамениту програму Weasel Річарда Докінза, яка ілюструє, що кумулятивний відбір досягає цілі значно швидше за сліпе випадкове перемішування.

Функція Растригіна — стандартний тестовий приклад оптимізації, визначений на 2D-сітці від мінус п'яти до п'яти по кожній осі. Вона має єдиний глобальний оптимум у початку координат, оточений численними оманливими локальними оптимумами, розташованими в регулярній ґратці. Її горбиста поверхня робить її складним еталоном для демонстрації того, як популяція уникає застрягання.

Щоб обрати батька, алгоритм випадково вибирає п'ять особин із популяції та залишає ту, що має найвищу пристосованість. Повторення цього процесу надає перевагу пристосованішим особинам, водночас лишаючи слабшим випадковий шанс, що допомагає підтримувати різноманітність. Тиск відбору зростає з розміром турніру, який у цій симуляції фіксований на п'яти.

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

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

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

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

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

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