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