Генетические алгоритмы с вещественным кодированием

Авторы идеи вещественного кодирования ([Herrera, 1998], [Michalewich, 1995], [Wright, 1991]) отталкиваются от предположения, что двоичное представление хромосом влечет за собой определенные трудности при выполнении поиска в непрерывных пространствах, что, в свою очередь, приводит к большой размерности пространства поиска.

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

,

где N - количество разрядов для кодирования битовой строки. Чаще всего используются значения N = 8; 16; 32.

При увеличении N пространство поиска расширяется и становится огромным. В иностранных источниках по РГА часто приводится такой пример. Пусть для 100 переменных, изменяющихся в интервале [-500; 500], требуется найти минимум с точностью до шестого знака после запятой. В этом случае при использовании ГА с двоичным кодированием длина строки составит 3000 элементов, а пространство поиска - около 10 в степени 1000.

Для преодоления таких количественных проблем предлагается использовать вещественное представление признаков в хромосоме [14, 15, 16]. В этом случае гены (признаки) напрямую представляются в виде вещественных чисел, т.е. генотип объекта становится идентичным его фенотипу. Теперь точность искомого решения потенциально ограничена не количеством битовых разрядов для кодирования, а только точностью представления вещественных чисел компьютера, на котором реализуется вещественный ГА. В результате, возникает предположение, что вещественное кодирование в ГА позволит повысить точность найденных решений и скорость нахождения оптимального решения (из-за отсутствия процессов кодирования и декодирования хромосом на каждом шаге алгоритма). Для такого подхода, естественно не подходят стандартные генетические операторы. По этой причине были разработаны и исследованы специальные операторы. Наиболее полный их обзор приведен в [14].

Пусть C1=(c11, c21, . . ., cn1) и C2=(c12, c22, . . ., cn2) - две хромосомы, выбранные оператором селекции для проведения кроссовера.

. Плоский кроссовер (flat crossover). Потомок H=(h1, h2, . . ., hn), где hi - случайное число из интервала [ci1, ci2].

. Арифметический кроссовер (arithetical crossover). Создаются два потомка H1=(h11, h21, . . ., hn1) и H2=(h12, h22, . . ., hn2):

,

- константа.

. BLX-a кроссовер. Генерируется один потомок H=(h1, h2, . . ., hn), где hi - случайное число из интервала [cmin - D×a, cmax + D×a], cmax =max(ci1, ci2), cmin =min(ci1, ci2), D= cmax - cmin,

. Линейный кроссовер (linear crossover). Создаются три потомка, рассчитываемые по формулам:

На этапе селекции в линейном кроссовере выбираются две особи с наибольшими приспособленностями.

В качестве оператора мутации наибольшее распространение получили: случайная и неравномерная мутация Михалевича.

При случайной мутации ген, подлежащий изменению, принимает случайное значение из интервала своего изменения

В неравномерной мутации значение гена после оператора мутации рассчитывается по формуле: