Генетичні алгоритми

Генетичний алгоритм (англ. genetic algorithm) — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію.

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

"Батьком-засновником" генетичних алгоритмів вважається Джон Голланд (англ. John Holland), книга якого "Адаптація в природних і штучних системах" (англ. Adaptation in Natural and Artificial Systems) є фундаментальною в цій сфері досліджень.

Генетичні алгоритми є новим напрямком у алгоритміці. Вони здатні не тільки вирішувати і скорочувати перебір у складних завданнях, але й легко адаптуватися до зміни проблеми.

Схема генетичного алгоритму:

• Генерація випадкового початкового стану
  Перше покоління створюється з довільно вибраних рішень (хромосом). Це відрізняється від стандартних методів, коли початковий стан завжди одне й те саме.
• Обчислення коефіцієнта пристасованності (fitness)
  Кожному рішенню (хромосомі) зіставляється якесь чисельне значення, яке залежить від його близькості до відповіді.
• Відтворення
  Хромосоми, що мають високий рівень пристасованності (fitness), потрапляють до нащадків (які потім можуть мутувати) з більшою ймовірністю. Нащадок, результат злиття 'батька' і 'матері', є комбінацією їх ген. Цей процес називається 'кроссіннговер' (crossing over).
• Наступне покоління
  Якщо нове покоління містить рішення, досить близьке до відповіді, то задача вирішена. У протилежному випадку воно проходить через той же процес. Це продовжується до досягнення рішення.