Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

1. Основные положения 
1.1. Базовые понятия 
Генети́ческий алгори́тм
(англ. 
genetic algorithm
) — это эвристический 
алгоритм поиска, используемый для решения задач оптимизации и 
моделирования путем последовательного подбора, комбинирования и 
вариации искомых параметров с использованием механизмов, 
напоминающих биологическую эволюцию. Является разновидностью 
эволюционных 
вычислений 
(англ. 
evolutionary 
computation
). 
Отличительной особенностью генетического алгоритма является акцент 
на использование оператора «скрещивания», который производит 
операцию 
рекомбинации 
решений-кандидатов, 
роль 
которой 
аналогична роли скрещивания в живой природе. «Отцом-основателем» 
генетических алгоритмов считается Джон Холланд (англ. 
John Holland
), 
книга которого «Адаптация в естественных и искусственных системах» 
(англ. 
Adaptation in Natural and Artificial Systems
) является 
основополагающим трудом в этой области исследований. 
При описании генетических алгоритмов используются определения, 
заимствованные из генетики. Например, речь идет о 
популяции особей, 
а 
в качестве базовых понятий применяются 
ген, хромосома, генотип, 
фенотип, аллель. 
Также используются соответствующие этим терминам 
определения из технического лексикона, в частности, 
цепь, двоичная 
последовательность, структура.
Популяция 
- это конечное множество 
особей.

---

А.Е. Кононюк Дискретно-непрерывная математика 
10 
Особи, 
входящие в популяцию, в генетических алгоритмах 
представляются хромосомами с закодированным в них множествами 
параметров задачи, 
т.е. решений, которые иначе называются 
точками в 
пространстве поиска (search points). 
В некоторых работах особи 
называются 
организмами.
Хромосомы 
(другие названия - 
цепочки 
или 
кодовые последо-
вательности) 
- это упорядоченные 
последовательности генов.
Ген 
(также называемый 
свойством, знаком 
или 
детектором) - 
это 
атомарный элемент 
генотипа, 
в частности, хромосомы.