Генетичні алгоритми: Еволюція як оптимізація

Пошук, одягнений як еволюція

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

Кротовка: найпростіший можливий приклад

Програма Річарда Даукінса "Кротовка" (1986 року) є найпростішим ілюстративним випадком: еволюціонувати випадковий ланцюг символів до фіксованої цільової фрази (його приклад: METHINKS IT IS LIKE A WEASEL) виключно за допомогою мутації та відбору одного найбільш пристосованого рядка поколіннями, без схрещування. Її метою було не те, що це точно моделює реальну біологію — воно націлене на відому фіксовану фразу, яку справжня еволюція ніколи не робить — а зробити одне очевидне речі: накопичений відбір малих випадкових змін значно швидше збігається, ніж просто шанс. Абсолютно випадковий 28-символьний ланцюг, що відповідає цільовій фразі символ за символом, має ймовірність приблизно (1/27)^2 * 28 — астрономічно неправдоподібно з'явитися одним випадковим ударом — але Кротовка зазвичай збігається протягом кількох десятків поколінь, оскільки кожне покоління зберігає будь-який покращення, який виникла мутація, замість того щоб починати з нуля.

Rastrigin: ландшафт пристойності, сповнений пасток

Другий режим на цій сторінці оптимізує 2D функцію Rastrigin, яка є стандартним бенчмарком у дослідженні оптимізації, саме тому вона складна в певному, добре зрозумілому вигляді:

f(x, y) = 20 + x^2 + y^2 - 10*cos(2*pi*x) - 10*cos(2*pi*y) // глобальний мінімум: f(0, 0) = 0 // але сповнений регулярно розташованими локальними мінімумами поблизу Квадратичний член x^2 + y^2 створює один гладкий глобальний чаші, центрований в точці початку координат, а косинусні члени проникають регулярною сіткою локальних мінімумів у цю чашу — ландшафт, на який простий алгоритм підкорення куту майже миттєво застрягає, оскільки рух у напрямку найближчого схилу зазвичай призводить до потрапляння в неправильну локальну яму замість справжнього мінімума в точці початку координат. Популяційно-орієнтований пошук генетичного алгоритму, а також здатність мутації робити стрибок більшим за одну локальну чашу, спеціально розроблені для перевірки таких ландшафтів.

f(x, y) = 20 + x^2 + y^2 - 10*cos(2*pi*x) - 10*cos(2*pi*y)
// global minimum: f(0, 0) = 0
// but riddled with regularly-spaced local minima nearby

Вибір, кросування, мутація — три оператори

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

Кросування об’єднує геноми двох батьків — для рядка ‘Weasel’, точка зрізу розрізає кожного батька та міняє хвости; для Rastrigin, координати (x, y) можуть бути змішані або усереднені. Мутація потім незначно змінює нащадків незалежно від батьків — низький, але не нульовий рівень мутації є тим, що запобігає передчасній деградації популяції на один локальний оптимум і втраті здатності досліджувати.

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

loop each generation:
  evaluate fitness(individual) for every individual
  new_population = []
  while new_population not full:
    parent1 = tournament_select(population)
    parent2 = tournament_select(population)
    child   = crossover(parent1, parent2)
    child   = mutate(child, rate)
    new_population.push(child)
  population = new_population

Frequently asked questions

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

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