Генерация начальной популяции

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

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

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

Для кодирования признаков можно использовать самый простой вариант — битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Но, к сожалению, такое кодирование не лишено недостатков. Основной недостаток заключается в том, что соседние числа отличаются в значениях нескольких битов, так, например числа 7 и 8 в битовом представлении различаются в 4-х позициях, что значительно увеличивает размер поискового пространства. Одним из решений данной проблемы является использование кода Грея (см. приложение А). И, наоборот, для того чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующие этим признакам, то есть генотип объекта. Операция определения фенотипа объекта по его генотипу называется операцией декодирования или роста, то есть мы выращиваем фенотип из генотипа.

Таким образом, для того чтобы инициализировать начальную популяцию, необходимо сначала определиться со способами кодирования особей. [3].