Непосредственно двоичный код, как правило, всё-таки не используется для бинарного представления хромосомы. Это связано с тем, что минимально отличающиеся в вещественном представлении переменные в большинстве случаев имеют большие различия (во многих позициях генов) при их двоичном представлении. Рассмотрим это на примере.
Пусть оптимальное (минимальное) значение переменной x определяется критерием: R = (x – 7)2. Исходя из физического смысла задачи, xopt было предварительно локализовано в пределах [0, 15]. Требуется точность вычисления e = 1. С учётом соотношений (2, 3) из Части 1, переменная должна кодироваться четырьмя битами, а фактическая точность совпадает с требуемой. Представим все возможные значения переменных в десятичном (X) и двоичном (X(2)) выражениях в первых двух колонках табл. 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). Данная функция возвращает единицу, если нечётное количество бинарных аргументов также были единицами, в противном случае функция возвращает ноль.
Для представления двоичного кода в форме кода Грея требуется приписать к двоичной форме слева ноль. Тогда соответствующей формой кода Грея будет последовательность значений функции «Исключающее ИЛИ» для пар: нуля и первого гена исходной двоичной формы, первого и второго генов, второго и третьего и т. д. То есть, например, для случая преобразования двоичной последовательности (a1, b1, c1) в последовательность в форме кода Грея (a2, b2, c2) получим: a2 = XOR(0, a1); b2 = XOR(a1, b1); c2 = XOR(b1, c1).
Примеры соответствия бинарного представления в коде Грея (X(Г)) двоичным и десятичным значениям представлены в табл. 1. Из таблицы видно, что расстояние Хэмминга между представлениями чисел 7 и 8 в коде Грея минимально и равно 1: отличие имеет место лишь в четвёртом разряде.
Для преобразования из кода Грея в двоичную форму к исходному коду слева приписывается ноль. Тогда результирующей двоичной формой будет последовательность значений функции «Исключающее ИЛИ» для первых двух знаков расширенной последовательности, первых трёх, четырёх и т. д. Например, для преобразования кода Грея (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 – двоичные параметры, позволяющие учесть знаки перед экспонентой и её степени в формуле пересчёта значения переменной из двоичной формы в десятичную:
где φ – десятичное представление степени экспоненты, закодированной последовательностью a1, b1, ….
Данный способ кодирования существенным образом уменьшает размер хромосом, однако делает это в ущерб точности поиска оптимального решения, и высока вероятность пропуска глобального оптимума. Минимизировать отрицательный эффект данного ограничения возможно лишь за счёт использования двоичного представления дробной степени φ при экспоненте.
По материалам учебного пособия:
Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.