Кодирование переменных. Код Грея

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

Пусть оптимальное (минимальное) значение переменной x определяется критерием: R = (x – 7)2. Исходя из физического смысла задачи, xopt было предварительно локализовано в пределах [0, 15]. Требуется точность вычисления e = 1. С учётом соотношений (2, 3) из Части 1, переменная должна кодироваться четырьмя битами, а фактическая точность совпадает с требуемой. Представим все возможные значения переменных в десятичном (X) и двоичном (X(2)) выражениях в первых двух колонках табл. 1.

Таблица1

Соответствие значений переменной в десятичном, двоичном
представлениях и представлении в коде Грея

Варианты представления переменной Значение
приспособленности (R)
X X(2) X(Г)
0 0000 0000 49
1 0001 0001 36
2 0010 0011 25
3 0011 0010 16
4 0100 0110 9
5 0101 0111 4
6 0110 0101 1
7 0111 0100 0
8 1000 1100 1
9 1001 1101 4
10 1010 1111 9
11 1011 1110 16
12 1100 1010 25
13 1101 1011 36
14 1110 1001 49
15 1111 1000 64

Очевидно, оптимальным решением является xopt = 7. Таким образом, решая задачу с использованием переменных в десятичном выражении и находясь в точке x = 8, достаточно сделать единственный шаг длиной, равной фактической точности, чтобы достичь оптимального значения. Однако в двоичном выражении всё выглядит наоборот.

Расстояние Хэмминга – количество различающихся битов данных, являющееся мерой близости бинарных значений, в этом случае максимально возможно и равно 4: во всех четырёх позициях двоичных представлений 7 и 8 биты не совпадают. Это означает, что в принципе невозможно, имея значение x(2) = 1000, получить x(2) = 0111, применив любой из базовых операторов генетического алгоритма, и лишь при редчайшем стечении обстоятельств это возможно, если применить модифицированный генетический оператор. Следствие этого обстоятельства – резкое снижение эффективности поиска оптимального решения при приближении функции приспособленности к своему наилучшему значению.

Проблему решают переходом от двоичного к бинарному представлению переменных в форме кода Грея. Правила преобразования из двоичного кода в код Грея и обратно просты и основаны на использовании логической функции «Исключающее ИЛИ» (XOR). Данная функция возвращает единицу, если нечётное количество бинарных аргументов также были единицами, в противном случае функция возвращает ноль.

Правило 1.

Для представления двоичного кода в форме кода Грея требуется приписать к двоичной форме слева ноль. Тогда соответствующей формой кода Грея будет последовательность значений функции «Исключающее ИЛИ» для пар: нуля и первого гена исходной двоичной формы, первого и второго генов, второго и третьего и т. д. То есть, например, для случая преобразования двоичной последовательности (a1, b1, c1) в последовательность в форме кода Грея (a2, b2, c2) получим: a2 = XOR(0, a1); b2 = XOR(a1, b1); c2 = XOR(b1, c1).

Примеры соответствия бинарного представления в коде Грея (X(Г)) двоичным и десятичным значениям представлены в табл. 1. Из таблицы видно, что расстояние Хэмминга между представлениями чисел 7 и 8 в коде Грея минимально и равно 1: отличие имеет место лишь в четвёртом разряде.

Правило 2.

Для преобразования из кода Грея в двоичную форму к исходному коду слева приписывается ноль. Тогда результирующей двоичной формой будет последовательность значений функции «Исключающее ИЛИ» для первых двух знаков расширенной последовательности, первых трёх, четырёх и т. д. Например, для преобразования кода Грея (a1, b1, c1) в двоичную последовательность (a2, b2, c2) получим:a2 = XOR(0, a1);b2 = XOR(0, a1, b1); c2 = XOR(0, a1, b1, c1).

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

В соответствии с этим способом каждая переменная кодируется последовательностью: a, b, a1, b1, …, где a, b – двоичные параметры, позволяющие учесть знаки перед экспонентой и её степени в формуле пересчёта значения переменной из двоичной формы в десятичную:

(5) Кодирование переменных. Код Грея,

где φ – десятичное представление степени экспоненты, закодированной последовательностью a1, b1, ….

Данный способ кодирования существенным образом уменьшает размер хромосом, однако делает это в ущерб точности поиска оптимального решения, и высока вероятность пропуска глобального оптимума. Минимизировать отрицательный эффект данного ограничения возможно лишь за счёт использования двоичного представления дробной степени φ при экспоненте.

По материалам учебного пособия:
Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.