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

Из биологии известно, что любой организм может быть представлен своим фенотипом, который фактически определяет, чем является объект в реальном мире, и генотипом, который содержит всю информацию об объекте на уровне хромосомного набора. При этом каждый ген, то есть элемент информации генотипа, имеет свое отражение в фенотипе. Таким образом, для решения задач необходимо представить каждый признак объекта в форме, подходящей для использования в генетическом алгоритме. Все дальнейшее функционирование механизмов генетического алгоритма производится на уровне генотипа, позволяя обойтись без информации о внутренней структуре объекта, что и обуславливает его широкое применение в самых разных задачах.

В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака. Для кодирования ген в бинарной реализации генетического алгоритма часто используют код Грея (см. пример в таб.3).

Таблица 3. Пример фенотипа

После определения фенотипа генетический алгоритм функционирует по следующей схеме действий (рис. 15).

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

1. Формирование начальной популяции.

2. Оценка особей популяции.

3. Отбор (селекция).

4. Скрещивание.

5. Мутация.

6. Формирование новой популяции.

7. Если популяция не сошлась, то 2, иначе – останов (прекращение функционирования генетического алгоритма).

Формирование начальной популяции

Стандартный генетический алгоритм начинает свою работу с формирования начальной популяции — конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью простых приближенных алгоритмов. Выбор начальной популяции не имеет значения для сходимости процесса, однако формирование "хорошей" начальной популяции (например, из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума. Если отсутствуют предположения о местоположении глобального оптимума, то индивиды из начальной популяции желательно распределить равномерно по всему пространству поиска решения.

Популяция инициируется в начальный момент времени t=0 и состоит из k особей, каждая из которых представляет возможное решение рассматриваемой проблемы. Особь представляет собой одну или несколько хромосом (обычно одну). Хромосома состоит из ген, - т.е. это битовая строка (хромосомы не ограничены бинарным представлением, есть реализации генетического алгоритма, построенные на векторах вещественных чисел). Гены располагаются в различных позициях хромосомы, и принимают значения, называемые аллелями.