Генетичні Алгоритми: Оптимізація за допомогою Симульованого Природного Відбору

Пошук шляхів шляхом імітації відбору, а не точного імітування біології

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

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

1. initialise a random population of N candidate solutions
2. evaluate fitness(individual) for every member
3. select parents, biased toward higher fitness
4. crossover: combine pairs of parents into offspring
5. mutate offspring with small probability
6. replace the population with the new generation
7. repeat from step 2 until fitness stops improving (or a target is reached)

Вибір: відбір тих, хто розмножується

Турнірний відбір є найпоширевшим методом на практиці: вибирають k індивідів випадково з популяції та дозволяють найбільш пристосована з цієї групи стати батьком/матір’ю, повторюючи це стільки разів, скільки потрібно батьків. Це недорогий метод, який не потребує сортування всієї популяції, а розмір турніруної групи k безпосередньо контролює відбірний тиск – k = 1 є чисто випадковим вибором (без жодного тиску), тоді як велике значення k наближається до завжди вибору одного найкращого індивіда, що швидко збігається, але ризикує втратити генетичну різноманітність занадто рано. Колесо-малюка (пропорційного фітнесу) відбір є класичною альтернативою, яка надає кожній індивідуальності шанс бути обраною пропорційно її показникові пристосованості, хоча він чутливий до масштабування показників пристосованості – один домінуючий індивід може витіснити решту популяції протягом кількох поколінь, якщо значення пристосованості спочатку не нормалізуються.

Перехрестя: комбінування, а не просто копіювання

Перехрестя поєднує дві батьківські геноми в нащадків, і ця рекомбінація – не лише мутації – дозволяє ГПЗ знаходити комбінації хороших підрозділів рішення, яких жодна з батьківських інструкцій не мала окремо. Перехрестя з однією точкою вибирає одну позицію розрізу та замінює все після неї між двома батьками; перехрестя з двома точками та рівномірне перехрестя незалежно обирають кожен ген з одного або іншого батька. Який план найкраще працює залежить від того, чи схильні близькі гени в кодуванні взаємодіяти – властивість, яка називається спарюванням – що саме пояснює вибір хорошої репрезентації для задачі (як кандидатне рішення кодується як хромосома) часто є найважливішим дизайнерським рішенням при застосуванні ГПЗ.

parent A:  1 0 1 1 | 0 0 1
parent B:  0 1 0 0 | 1 1 0
                    ^ crossover point

child:     1 0 1 1 | 1 1 0     (tail swapped from parent B)

Мутація: джерело генів, які не були в популяції

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

Простір пристосуваності та чому ГА добре підходять для негодних

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

Часті запитання

Спробуйте наживо

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