Вопрос 8: Бинарное и вещественное кодирование в генетическом алгоритме. Код Грея.

Зависимые вопросы

• Виды кроссовера в генетическом алгоритме
• Виды селекции в генетическом алгоритме
• Практика с бинарным кодированием
• Практика c вещественным кодированием

Типы кодирования

Хромосомы в генетическом алгоритме, как правило, представляются в виде бинарной строки или вещественным вектором. Если исходные данные задачи были представлены вещественными числами, то для работы алгоритма необходимо определить некоторую функцию кодирования и декодирования решений. Существует много способов кодирования решений. Рассмотрим некоторые из них:

• Вещественный
• Бинарный
• Код Грея

Исследования показали, что для большинства функций генетические алгоритмы будут работать лучше, если закодировать параметры в строку кодом Грея, а не прямым бинарным кодом. Это связано с тем, что соседние числа отличаются в значениях нескольких битов, к примеру, числа 7 и 8 различаются на 4 бита. Прямое бинарное кодирование добавляет дополнительные разрывы, что осложняет поиск. Младший разряд в последовательности чисел в коде Грея принимает значения 0 и 1, затем следующий старший разряд становится единичным и младший разряд принимает свои значения уже в обратном порядке (0, 1). Пример кодирования

Не уверен что это важно, но для ответы на вопросы подойдет

Алгоритм кодирования бинарного кода в код Грея

Коды Грея легко получаются из двоичных чисел путём побитовой операции «Исключающее ИЛИ» с тем же числом, сдвинутым вправо на один бит и в котором старший разряд заполняется нулём. Следовательно, i-й бит кода Грея $G_i$ выражается через биты двоичного кода $B_i$ следующим образом:

$G_i = B_i \bigoplus B_{i+1}$

Алгоритм декодирования кода Грея в бинарный код

Обратный алгоритм — преобразование кода Грея в двоичный код — можно выразить рекуррентной формулой:

$B_i = G_i \bigoplus B_{i+1}$

причём преобразование осуществляется побитно, начиная со старших разрядов, и значение $B_{i+1}$, используемое в формуле, вычисляется на предыдущем шаге алгоритма.