Способы кодирования

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

Как правило, в хромосоме кодируются численные параметры решения. Для этого возможно использование целочисленного и вещественного кодирования.

Целочисленное кодирование

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

На рис. показан пример кодирования 4-х 10-разрядных параметров в 40 разрядной хромосоме. Как правило, считают, что каждому параметру соответствует свой ген. Таким образом, можно также сказать, что хромосома на рис. состоит из 4-х 10-разрядных генов.

Кодирование вещественных чисел

Несмотря на то, что каждый параметр закодирован в хромосоме целым числом, ему могут быть поставлены в соответствие и вещественные числа.

Если известен диапазон, в пределах которого лежит значение параметра, то этот диапазон разбивают на 2m отрезков, где m – разрядность гена, и каждому отрезку соответствует определенное значение гена.

При этом для перевода значений из закодированного значения в дробные применяют следующие формулы:

где r – вещественное (декодированное) значение параметра, g – целочисленное (закодированное) значение параметра, xmax и xmin – соответственно максимальное и минимальное допустимое значение декодированного параметра.

Часто бывает удобнее кодировать в гене не целое число, а вещественное. Это позволяет избавиться от операций кодирования/декодирования, используемых в целочисленном кодировании, а также увеличить точность найденного решения.

Пример вещественного кодирования