Кодирование информации и формирование популяции

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

Невыполнение этого условия может привести как к увеличению времени эволюционного поиска, так и к невозможности найти решение поставленной задачи.

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

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

Рис. 5.2. Пример целочисленного кодирования

Как правило, считают, что каждому параметру соответствует свой ген. Таким образом, можно также сказать, что хромосома на рис. 5.2 состоит из 4-х 10-разрядных генов. Несмотря на то, что каждый параметр закодирован в хромосоме целым числом (в виде двоичной последовательности), ему могут быть поставлены в соответствие и вещественные числа. Ниже представлен один из вариантов прямого и обратного преобразования «целочисленный ген → вещественное число».

Если известен диапазон [x_min ; x_max], в пределах которого лежит значение параметра и m – разрядность гена, то этот диапазон разбивают на 2^m равных отрезков, и каждому отрезку соответствует определенное значение гена. При этом для перевода значений из закодированного значения в дробные применяют следующие формулы:

,

,

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

Например, если искомое значение параметра лежит в промежутке [1; 2] и каждый ген кодируется 16 разрядами, то, если содержимое гена равно ABCD₁₆ = 43981₁₀, то соответствующее дробное значение равно:

r = 43981 * (2 – 1)/(2¹⁶ – 1) + 1 = 0,6711 + 1 = 1,6711.

Если же декодированное значение равно 1,3275, то соответствующий ген после обратного преобразования будет содержать (с округлением в меньшую сторону):

g = (1,3275 – 1)(2¹⁶ – 1) / (2 – 1) = 0,3275 * 65535 = 21462,7125 » 21462₁₀ = 0101 0011 1101 0110₂.

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

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

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

i = 0;

ПОКА (i < РАЗМЕР_ПОПУЛЯЦИИ) {

j = 0;

ПОКА (j < ЧИСЛО_ГЕНОВ) {

ОСОБЬ[i].ГЕН[j] = СЛУЧАЙНАЯ_ВЕЛИЧИНА;

j = j+1;

}

i = i+1;

}