Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция №2

Бинарный код грея (БКГ)

БКГ наиболее широко применяется для кодирования генетической информации о компонентах вектора параметров

БКГ записывается в виде целочисленного вектора:

, (1)

где ,

- количество двоичных разрядов (бит)

С помощью БКГ можно закодировать целое число из интервала:

Мощность: ,

Если компоненты вектора x изменяются в интервалах:

(2)

то БКГ вида (1) можно декодировать в значение компонента x_i вектора x с помощью следующей формулы:

, (3)

где - целое число, в которое декодируется БКГ вида (1).

Рассмотрим процесс декодирования хромосом, представленных БКГ с m=4, в вектор вещественных параметров , компоненты которого изменяются в интервалах:

(4)

Таблица 1 воспроизводит в полном объеме процедуру декодирования . Таким образом БКГ позволяет аппроксимировать непрерывный бит X, заданный параметрами (4), дискретной сеткой 15x15. Для того, чтобы повысить точность аппроксимации X, необходимо увеличить разрядность m БКГ.

В данном случае для того, чтобы при декодировании получить числа с точностью до 3 знака после десятичной точки, необходимо по оси x₂ закодировать 4000 целых чисел: m=12.

Таблица 1.

Геометрическая интерпретация БКГ: ,

После этого полагаем и обходим куб в обратном порядке.

Из таблицы 1 хорошо видно, почему БКГ имеет преимущества по сравнению с обычным двоичным кодом, который при некотором стечении обстоятельств приводит процесс поиска оптимума в тупик.

В качестве примера рассмотрим любые 3 расположенные подряд строки из таблицы 1, например, .

Предположим, хромосома, соответствующая , принадлежит оптимальному вектору x, являющемуся решением некоторой оптимизационной задачи, а лучшая ТТО из текущей популяции, содержит хромосому из строки, соответствующей . Такая ситуация благоприятна для обоих кодов. Достаточно выполнить одну операцию замены 0 на 1 в 4-ом разряде хромосомы и решение будет найдено.

Иной случай получается, если лучшая ТТО содержит хромосому из строки, соответственно . Для БКГ эта ситуация аналогична предыдущей: замена 0 на 1 в 3-м разряде опять приведет к оптимальному решению. В то же время для двоичного кода необходимо выполнить 2 операции: заменить 1 на 0 в 3-м разряде, и 0 на 1 в 4-ом разряде.

Выполнив лишь одну замену в двоичном коде, мы перескочим либо в , либо в .

Иначе говоря, если использовать геометрическую интерпретацию, то БКГ гарантирует, что две соседние принадлежащие одному ряду вершины гиперкуба K^m, на котором осуществляется поиск, всегда декодируется в две ближайшие точки оси вещественных чисел, отстающие друг от друга на одну дискрету точности. Двоичный код подобным свойством не обладает.

Декодирование может быть выполнено, по формуле, приведенной для МКГ. Однако для БКГ существует более изящный алгоритм декодирования.

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

Шаг 0. Полагаем

Шаг 1. Определяем – количество нулевых разрядов, расположенных в левее _. Полагаем _.

Шаг 2. Если , то вычисляем . Переходим к шагу 4. Иначе переходим к шагу 3.

Шаг 3.

Шаг 4.

Шаг 5. . Если , то переходим к шагу 1. Иначе переходим к шагу 6.

Шаг 6. Вычисляем .

Шаг 7. STOP

Пример 1. .

K=1; d₁=0; ρ₁=1.

l₁=(-1)¹⁺¹(2^4-1+1-1)1=15

K=2; z₂=0 => l₂=0.

K=3; d₃=1; ρ₃=3-1=2

l₃=(-1)²⁺¹(2^4-3+1-1)1=(-1)3=-3

K=4; z₄=0 => l₄=0.

l=15-3=12.

Пример 2. .

K=1; d₁=0; ρ₁=1-0=1.

l₁=(-1)¹⁺¹(2^4-1+1-1)1=15

K=2; d₂=0; ρ₂=2-0=2.

l₂=(-1)²⁺¹(2^4-2+1-1)1=(-1)7=-7

K=3; d₃=0; ρ₃=3-0=3.

l₃=(-1)³⁺¹(2^4-3+1-1)1=3

K=4; d₄=0; ρ₄=4-0=4.

l₄=(-1)⁴⁺¹(2^4-4+1-1)1=(-1)1=-1

l=15-7+3-1=10

Пример 3.

K=1; d₁=0; ρ₁=1-0=1.

l₁=(-1)¹⁺¹(2^5-1+1-1)1=31

K=2; d₂=0; ρ₂=2-0=2.

l₂=(-1)²⁺¹(2^5-2+1-1)1=(-1)15=-15

K=3; z₃=0 => l₃=0.

K=4; z₄=0 => l₄=0.

K=5; z₅=0 => l₅=0.

l=31-15=16.

Пример 4. .

K=1; d₁=0; ρ₁=1-0=1.

l₁=(-1)¹⁺¹(2^5-1+1-1)1=31

K=2; d₂=0; ρ₂=2-0=2.

l₂=(-1)²⁺¹(2^5-2+1-1)1=(-1)15=-15

K=3; d₃=0; ρ₃=3-0=3.

l₃=(-1)³⁺¹(2^5-3+1-1)1=7

K=4; d₄=0; ρ₄=4-0=4.

l₄=(-1)⁴⁺¹(2^5-4+1-1)1=(-1)3=-3

K=4; d₅=0; ρ₅=5-0=5.

l₅=(-1)⁵⁺¹(2^5-5+1-1)1=1

l=31-15+7-3+1=21

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

,

Где а остаток от деления на

Пример 1

Пример 2

Алгоритм перевода БКГ в двоичный код

Пример 3

Пример 4

Другая форма записи алгоритма перевода БКГ в двоичный код

Оценка приспособленности ТТО

Решается оптимизационная задача:

Определить .

Пусть сгенерирована начальная популяция ТТО

Каждая ТТО представляет собой битовую строку: в битовой строке закодирована информация о векторе параметров .

БКГ БКГ

Оценка приспособленности (пригодность) ТТО осуществляется в несколько этапов.

Шаг 1. Декодирование ТТО

,

т. е. .

Шаг 2. Для всех проверяется выполнение условия

(1*)

Обозначим - количество точек , в которых выполняется условие (1*), сформируем функцию вида:

(2*)

Функция обладает следующими свойствами:

1. Если , то . Это означает, что в точке функция достигает своего минимального значния относительно текущей позиции . Другими словами, точка является «лучшей» в популяции .

2. Если , то это означает, что в точке функция достигает своего максимального значения относительно текущей позиции . То есть точка является «худшей» в популяции .

3. Если , то . Таким образом в «лучшей» точке популяции принимает свое максимальное значение , равное 1. В худшей точке популяции принимает свое максимальное значение , равное . Здесь q – параметр, влияющий на скорость сходимости генетического алгоритма к оптимуму.

Формирование из текущей популяции ТТО массива родителей

На этом этапе выполняются следующие операции.

1. Построение интервала для определения вероятности выбора ТТО в родителе. Используются следующие рекуррентные соотношения:

Далее полагаем . Геометрически это означает:

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов лекций