Часть 1. Кодирование переменных. Преобразование в двоичный код

Генетические алгоритмы либо сами используются для решения задач оптимизации, либо сама задача, решаемая с помощью данного инструмента, сводится к оптимизационной. Причём оптимизация должна быть многомерной, иначе нет никакого смысла использовать такой сложный метод. Решение любой задачи оптимизации – это вектор значений оптимизируемых переменных, обеспечивающих наилучшую величину некоторого критерия.

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

Поскольку в генетических алгоритмах вещественного кодирования гены – это вещественные значения оптимизируемых переменных, их дополнительное кодирование не требуется, а размер генотипа определяется количеством оптимизируемых переменных.

В бинарном генетическом алгоритме для представления переменной в виде хромосомы необходимо задаться областью её допустимых значений и требуемой точностью вычислений. Устанавливают максимально и минимально возможные значения X min,Xmax, принимаемые каждой переменной, и требуемую точность вычисления каждой переменной по генетическому алгоритму e. Тогда количество возможных разнообразных значений (nб), которые может принимать данная переменная, составит:

(1)

Обратите внимание, диапазон изменения и точность каждой переменной могут отличаться от остальных, поэтому величина nб будет, в общем случае, различной для каждой переменной.

Количество бинарных генов (nг), которыми может быть закодирована одна переменная (размер хромосомы), представляет собой округлённый в сторону ближайшего большего целого числа логарифм nб по основанию 2:

(2)

Из-за округления количество возможных вариантов значений переменной будет немного больше рассчитанного по формуле (1). Фактическая точность вычисления переменной, таким образом, составит:

(3)

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

Далее необходимо сопоставить вещественные значения переменных с соответствующим им двоичным представлением. Принимают, что левая граница области допустимых значений соответствует двоичному коду с нулями во всех позициях, тогда пересчитанная правая граница – коду со всеми единицами. Таким образом, числа в указанной двоичной последовательности будут соответствовать расставленным в порядке возрастания от 0 до (XmaxXmin) с шагом вещественным значениям X(10), соответствующим значениям оптимизируемой переменной (X) в требуемых по условию задачи пределах [Xmin, Xmax]. Значения X(10) получают стандартным преобразованием из двоичного кода в десятичный. Истинное значение оптимизируемой переменной определяется по соотношению:

(4)

Критерий оптимизации (приспособленность особи) оценивается по значениям переменных, приведённых к их естественной форме по последней формуле.

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


Если у вас есть статья, заметка или обзор, которыми вы хотите поделиться с аудиторией нашего сайта, присылайте информацию на: neuronus.com@yandex.ru.
Гость, оставишь комментарий?
Имя:*
E-Mail:


Последние комментарии
Почему космос не имеет начала и конца: комментарии учёных
Земля находится трёх слонах, которые стоят на черепахе
Судьба ледокола «Арктика» остается неопределенной после повреждения одного из двигателей
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Сообщение о покупке водородной яхты Билом Гейтсом оказалось ложным
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Для чего динозавру абдараинуру такой необычный хвост
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Получены самые детальные снимки поверхности Солнца
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Мы в социальных сетях
Статистика
1  
Всего статей 2459
2  
Всего комментариев 886
0  
Пользователей 176