Ця симуляція демонструє генетичний алгоритм — метод оптимізації, натхненний дарвінівською еволюцією. Популяція кандидатних розв'язків оцінюється функцією пристосованості, і найпристосованіші переважно схрещуються, аби породити наступне покоління. Симуляція працює у двох режимах: класична задача підбору рядка «Weasel» та неперервна оптимізація 2D-функції Растрігіна. Кожне покоління застосовує турнірний відбір, одноточкове схрещування та випадкову мутацію, а елітизм зберігає двох найкращих особин незмінними.
Елементи керування дозволяють обрати режим і цільовий рядок, задати розмір популяції (від 20 до 200 особин), відрегулювати рівень мутації (від 1 до 30 відсотків) і змінити швидкість симуляції. Жива панель показує номер покоління, найкращу та середню пристосованість, різноманітність і поточний найкращий рядок. Генетичні алгоритми застосовуються в реальних інженерних задачах, як-от проектування антен, складання розкладів та оптимізація аеродинамічних форм, де простір пошуку завеликий для повного перебору.
Що таке генетичний алгоритм?
Генетичний алгоритм — це техніка пошуку та оптимізації, що імітує природний відбір. Вона підтримує популяцію кандидатних розв'язків, оцінює кожен функцією пристосованості й багаторазово схрещує найкращих за допомогою схрещування та мутації. За багато поколінь популяція схиляється до збіжності у напрямку розв'язків із високою пристосованістю.
Що робить режим String Evolution (Weasel)?
Він еволюціонує випадковий рядок літер до цільової фрази, за замовчуванням METHINKS IT IS LIKE A WEASEL. Пристосованість — це просто частка позицій символів, що збігаються з ціллю. Це відтворює знамениту програму «Weasel» Річарда Докінза, яка ілюструє, як накопичувальний відбір досягає цілі значно швидше за сліпе випадкове перетасування.
Що таке функція Растрігіна, яку використовує режим Landscape?
Функція Растрігіна — це стандартний тестовий випадок оптимізації, визначений на 2D-сітці від мінус п'яти до п'яти по кожній осі. Вона має єдиний глобальний оптимум у початку координат, оточений багатьма оманливими локальними оптимумами, розташованими в регулярній ґратці. Її горбиста поверхня робить її складним еталоном для демонстрації того, як популяція уникає пастки.
Щоб обрати батька, алгоритм випадково бере п'ять особин із популяції та залишає ту, що має найвищу пристосованість. Повторення цього процесу надає перевагу пристосованішим особинам, але водночас дає слабшим випадковий шанс, що допомагає підтримувати різноманітність. Тиск відбору зростає з розміром турніру, який у цій симуляції фіксований на п'яти.
Схрещування поєднує двох батьків у нащадка. У режимі рядка воно використовує одну випадкову точку розрізу, беручи початок від одного батька, а решту — від іншого. Потім мутація випадково замінює символи з імовірністю, що дорівнює рівню мутації. У режимі ландшафту нащадок — це зважена суміш координат батьків плюс невелике випадкове тремтіння, масштабоване рівнем мутації.
Рівень мутації, який регулюється від 1 до 30 відсотків, задає, як часто кожен ген випадково змінюється під час створення нащадків. Низькі значення змушують популяцію швидко сходитися, але ризикують застрягти в локальному оптимумі. Високі значення додають більше різноманітності й допомагають вибратися з пасток, але надмірна мутація перетворює пошук на неефективне випадкове блукання.
Це називається елітизмом. Дві особини з найвищою пристосованістю копіюються безпосередньо в наступне покоління без схрещування чи мутації. Елітизм гарантує, що знайдений досі найкращий розв'язок ніколи не втрачається, тож крива найкращої пристосованості ніколи не спадає. Решта місць заповнюється відбором, схрещуванням і мутацією.
У режимі рядка різноманітність вимірюється як середня кількість різних символів, що з'являються на кожній позиції в усій популяції. Висока різноманітність на початку означає, що популяція все ще широко досліджує простір; у міру збіжності до цілі різноманітність падає до одиниці, що вказує, що більшість особин тепер мають однакові літери.
Це достовірна модель основного механізму — відбору, що діє на спадкову мінливість, — але вона навмисно спрощена. Реальна еволюція не має фіксованої цілі, глобальної функції пристосованості й має значно багатшу генетику. Задача «Weasel» зокрема є навчальною ілюстрацією накопичувального відбору, а не твердженням про те, як еволюціонують організми.
Їх застосовують усюди, де простір пошуку величезний, а градієнти недоступні або ненадійні, зокрема у проектуванні літаків та антен, складанні заводських і часових розкладів, компонуванні схем, налаштуванні гіперпараметрів машинного навчання та оптимізації фінансових стратегій. NASA знамените тим, що використовувало еволюціоновані конструкції антен для космічних апаратів із незвичними, але дуже ефективними формами.
Спостерігайте, як еволюція вирішує задачу оптимізації: популяція потенційних розв'язків «схрещується» та «мутує» — кожне покоління стає трохи кращим. Принцип природного відбору у дії.
Генетичний алгоритм імітує еволюцію: відбір (виживають найкращі рішення), схрещування (поєднання двох рішень) і мутація (випадкова зміна). Після багатьох поколінь алгоритм знаходить майже оптимальне рішення.
Натисніть «Старт», щоб запустити еволюцію. Регулюйте розмір популяції, ймовірність мутації та кількість поколінь. Спостерігайте за кривою пристосованості та найкращим розв'язком у реальному часі.
Генетичні алгоритми вже використовувалися для проектування антен NASA (супутник ST5), оптимізації авіаційних маршрутів та розвитку тактик у відеоіграх. У 1997 р. вони розробили принципово нові конструкції антен, які люди-інженери ніколи б не придумали самі.