Генетические алгоритмы либо сами используются для решения задач оптимизации, либо сама задача, решаемая с помощью данного инструмента, сводится к оптимизационной. Причём оптимизация должна быть многомерной, иначе нет никакого смысла использовать такой сложный метод. Решение любой задачи оптимизации – это вектор значений оптимизируемых переменных, обеспечивающих наилучшую величину некоторого критерия.
В зависимости от способа конечного кодирования хромосом различают два наиболее часто используемых вида алгоритмов. Бинарные генетические алгоритмы предусматривают представление генов в виде нулей или единиц. В генетических алгоритмах вещественного кодирования гены – вещественные числа. В то же время возможны и другие способы представления.
Поскольку в генетических алгоритмах вещественного кодирования гены – это вещественные значения оптимизируемых переменных, их дополнительное кодирование не требуется, а размер генотипа определяется количеством оптимизируемых переменных.
В бинарном генетическом алгоритме для представления переменной в виде хромосомы необходимо задаться областью её допустимых значений и требуемой точностью вычислений. Устанавливают максимально и минимально возможные значения X min,Xmax, принимаемые каждой переменной, и требуемую точность вычисления каждой переменной по генетическому алгоритму e. Тогда количество возможных разнообразных значений (nб), которые может принимать данная переменная, составит:
Обратите внимание, диапазон изменения и точность каждой переменной могут отличаться от остальных, поэтому величина nб будет, в общем случае, различной для каждой переменной.
Количество бинарных генов (nг), которыми может быть закодирована одна переменная (размер хромосомы), представляет собой округлённый в сторону ближайшего большего целого числа логарифм nб по основанию 2:
Из-за округления количество возможных вариантов значений переменной будет немного больше рассчитанного по формуле (1). Фактическая точность вычисления переменной, таким образом, составит:
Количество генов, кодирующих одну особь популяции, представляет собой сумму значений nг, рассчитанных для каждой переменной.
Далее необходимо сопоставить вещественные значения переменных с соответствующим им двоичным представлением. Принимают, что левая граница области допустимых значений соответствует двоичному коду с нулями во всех позициях, тогда пересчитанная правая граница – коду со всеми единицами. Таким образом, числа в указанной двоичной последовательности будут соответствовать расставленным в порядке возрастания от 0 до (Xmax – Xmin) с шагом вещественным значениям X(10), соответствующим значениям оптимизируемой переменной (X) в требуемых по условию задачи пределах [Xmin, Xmax]. Значения X(10) получают стандартным преобразованием из двоичного кода в десятичный. Истинное значение оптимизируемой переменной определяется по соотношению:
Критерий оптимизации (приспособленность особи) оценивается по значениям переменных, приведённых к их естественной форме по последней формуле.
По материалам учебного пособия:
Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.