Теоретическая часть. Генетические алгоритмы (ГА) являются направлением искусственного интеллекта, моделирующим биологическую эволюцию и использующие её принципы и терминологию

Генетические алгоритмы (ГА) являются направлением искусственного интеллекта, моделирующим биологическую эволюцию и использующие её принципы и терминологию, такие как процессы отбора (в ходе которого наиболее жизнеспособные виды сохраняются в то время, как более слабые исчезают), воспроизводства, понятия популяции и жизнеспособности. Генетический алгоритм принимает каждую анализируемую единицу популяции и каждого соответствующего члена популяции как шифровку потенциального решения интересующей проблемы. Традиционно этими шифровками (или генотипами) считаются двоичные строки (0, 1, 0, 1, …). Генотипы могут быть интерпретироваться различными способами, в зависимости от природы задачи. Эволюция в популяции генотипов осуществляется посредством процесса псевдоестественного отбора с использованием псевдогенетических операторов. ГА являются вероятностным методом направленного поиска. Поиск может быть рассмотрен как итерационная программа, применяемая с целью создания лучших инди­видов с помощью таких операторов, как селекция, скрещивание (рекомбина­ция) и мутация (см. рис.3).

Переход к новому поколению

Рис. 3. Схема функционирования генетического алгоритма

Стратегии мутации и скрещивания различны. Мутация основывается на слу­чае. Результат даже одного шага мутации всегда непредсказуем. Результат скрещивания менее случаен, поскольку при этом скрещиваются только стро­ки, находящиеся в одной популяции. При этом поиск с помощью скрещива­ния приводит к сходимости популяции и способен локализовать оптимум без применения мутации только при достаточно большом размере популяции.

Эти операторы обычно являются статическими, т. е. их параметры и вероят­ность использования фиксированы в начале и остаются постоянными до за­вершения работы алгоритма.