Генети́ческий алгори́тм

Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
История
«Отцом-основателем» генетических алгоритмов считается Джон Холланд (en:John Henry Holland), книга которого «Адаптация в естественных и искусственных системах» (1975)[1] является основополагающим трудом в этой области исследований. Ему же принадлежит доказательство теоремы схем.
Описание алгоритма
Схема работы генетического алгоритма
Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов. Где каждый ген может быть битом, числом или неким другим объектом. В классичеких реализация ГА, предпологается что генотип имеет фиксированную длинну. Однако существуют вариации ГА свободные от этого ограничения.
Некотором, обычно случайным образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип им описываемый решает поставленную задачу.