Исследование эффективности работы генетического алгоритма оптимизации с альтернативным представлением решений

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

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

Представление хромосом определяется способом кодирования. Как правило, в генетическом алгоритме применяется двоичное представление хромосом. Оно основано на известном способе записи десятичных чисел в двоичной системе, где каждый бит двоичного кода соответствует очередной степени цифры 2. Например, двоичная последовательность [10011] представляет собой код числа 19, поскольку 1*2⁴+0*2³+0*2²+1*2¹+1*2¹=19. Данный способ кодирования решений будем называть прямым бинарным кодом . Существует много способов бинарного кодирования решений, рассмотрим некоторые из них.

Код Грея – это бинарный код целого числа, такой, что для смежных целых чисел расстояние между их кодами в метрике Хемминга равно 1.

Стандартное рефлексивное грей-кодирование целого числа получается применением оператора исключающего ИЛИ, к стандартному бинарному кодированию целого числа и к тому же бинарному коду, смещенному на одну позицию вправо, последний бит отсекается.

Для многих практических задач код Грея оказывается более эффективным, чем бинарное кодирование [1]. Код Грея частично сохраняет структуру окрестностей пространства поиска в бинаризованном пространстве. В результате, грей-код не может образовать оптимумов больше, чем у исходной целевой функции. Более того, так как у текущей точки в коде Грея соседних точек больше, чем в дискретной целевой функции, то в пространстве поиска грей-кода число оптимумов обычно меньше. В противоположность, прямой бинарный код часто создает новые оп-тимумы, которых у исходной целевой функции не было [2].

Практически не встречается в научной литературе использование для генетического алгоритма бинарных кодов с переменной длиной. Значащие цифры начинаются со старшей ненулевой цифры, например, в числе 000001101 2 =1*2⁰+0*2¹+1*2²+1*2³+0*2⁴+0*…=13 это последние 4 цифры. Порядок числа определяется позицией старшей ненулевой цифры в записи числа. Как и при обычной записи в десятичной системе, он равен числу цифр в записи числа без предшествующих незначащих нулей. В данном примере порядок равен четырем. Методы этой группы являются трансформирующими и поточечными (т. е. могут применяться даже в том случае, когда длина блока с данными не задана).

Унарный код – это запись числа N , последовательность из N нулевых бит и одного единичного.

Гамма-коды Элиаса ( Elias γ-codes ). Данные коды формируются в зависимости от диапазона числа. Допустим, кодируется число n , тогда гамма-кодом Элиаса для числа n будет его обыкновенное бинарное представление без старшей единицы, дополненное слева унарным представлением числа (табл. 1).

Таблица 1

Гамма-коды Элиаса

Диапазон	Гамма-коды Элиаса*	Длина кода, бит
1	1	1
2…3	01x	3
4...7	001xx	5
8…15	0001xxx	7
16…31	00001xxxx	9
32...63	000001xxxxx	11

* Символами «х» обозначены биты мантиссы без старшей единицы.

Дельта-коды Элиаса (Elias δ-codes). Дельтакодами Элиаса называются гамма-коды, в которых унарная часть также закодирована гамма-кодами. То есть для получения дельта-кода нужно закодировать L (количество значащих битов в двоичном представлении числа n) с помощью гамма-кода Элиаса и дописать двоичное представление числа без старшей единицы (табл. 2).

Таблица 2 Дельта-коды Элиаса

Диапазон	Дельта-коды Элиаса*	Длина кода, бит
1	1	1
2...3	010x	4
4...7	011xx	5
8…15	00100xxx	8
16...31	00101xxxx	9
32...63	00110xxxxx	10

Единственное отличие между γ - и δ -кодами состоит в том, что в γ -кодах экспоненты записываются в унарном виде, а в δ -кодах к ним еще раз применяется γ -кодирование. Видно, что γ -коды первых 15 чисел короче δ -кодов, а γ -коды первых 31 числа не длиннее δ -кодов. То есть чем неравномернее распределение вероятностей, чем круче возрастает вероятность чисел при приближении их значения к нулю, тем выгоднее γ – коды по сравнению с δ -кодами [3].

Гамма-коды Левенштейна ( Levenstein γ-codes ). Данный код для числа n получается путем обращения последовательности битов в двоичной записи этого числа и добавления перед каждым битом, кроме последнего, флагового (flag bit) бита 0. Последним флаговым битом является бит 1, который совпадает с самым старшим битом в исходной двоичной записи числа n (табл. 3).

Таблица 3

Гамма-коды Левенштейна

n	Гамма-коды Левенштейна
1	1
5	01001
13	0100011
63	01010101011
129	010000000000001

Коды Голомба ( Golomb codes ). Код Голомба для n с заданным параметром m , дает соединение двух кодов: унарная запись числа q = n/m и кодированный остаток r от деления n/m :

Если m является степенью числа 2, то код остатка представляет собой двоичную запись числа r , размещённую в log 2 m битах;

Если m не является степенью 2, вычисляется число b = log 2 m .

Если r < 2 ^b - m , код остатка представляет собой двоичную запись числа r , размещённую в b –1 битах, иначе остаток r кодируется двоичной записью числа r < 2 ^b - m , размещённой в b битах (табл. 4).

Коды Райса ( Rice codes ). Код Райса для n с заданным параметром k дает соединение двух кодов: унарная запись числа q = n /2 ^k и кодированный остаток r от деления n /2 ^k , представляющий собой двоичную запись числа r , размещённую в k битах (табл. 5).

Таблица 4

Коды Голомба

n/m	1	2	3	4	5
0	0	00	00	000	000
1	10	01	010	001	001
2	110	100	011	010	010
3	1110	101	100	011	0110

Таблица 5

Коды Райса

n/m	1	2	3	4	5
0	0	000	0000	00000	000000
1	10	001	0001	00001	000001
2	110	010	0010	00010	000010
3	1110	011	0011	00011	000011

Стандартный генетический алгоритм работает с бинарными хромосомами с фиксированной длиной. В данной работе использовался модифицированный генетический алгоритм, в котором были реализованы операторы процентного скрещивания для хромосом с переменной длиной [4].

Исследование эффективности генетического алгоритма проводилось на задаче минимизации следующих тестовых функций: функция Розенброка, функция Шекеля, функция Растригина, функция Катнико-ва, функция Гриванка, функция Де Йонга. Количество независимых переменных изменялось от 2 до 4. Длина каждой переменной для генетического алгоритма с прямым бинарным и грей-кодированием была взята равной 10. Для генетического алгоритма с кодированием гамма- и дельта-кодами Элиасса, гамма-кодами Левенштейна, кодами Голомба и Райса длина каждой переменной из меняется от 1 до 15. Статистика набралась по 100 запускам алгоритма. Размер популяции – 50 индивидов. Число поколений – 50. Для оценки эффективности алгоритмов использовалась надежность. Надежность – процент успешных запусков (решение найдено) алгоритма от общего числа запусков. Результаты решения тестовых задач приведены в табл. 6.

Из табл. 6 видно, что наилучший результат показал алгоритм с кодированием решений с помощью кода Райса. Генетический алгоритм с прямым бинарным кодированием хорошо работает на простых задачах, когда допустимая область обладает удобными для оптимизации свойствами (большой размер, выпуклая и т. д.). Однако из полученных результатов можно сделать вывод, что для сложных задач безусловной оптимизации генетический алгоритм с кодом Райса дает более высокую эффективность.

Для оценки статистической значимости полученных результатов использовался критерий ANOVA. Критерий ANOVA представляет собой непараметрическую оценку Манна–Уитни при значимости α = 0,05. Сравнения проводились попарно для каждого алгоритма со всеми остальными, представленными в табл. 6. Метод ANONA позволил определить, что различия результатов сравнения алгоритмов статистически достоверны.

Таблица 6

Результаты решения тестовых задач

Функция Растригина
Способ кодирования	Прямой бинарный код	Код Грея	Гамма-коды Элиаса	Дельта-коды Элиаса	Гамма-коды Левенштейна	Коды Райса
Надежность	25	67	50	17	17	84
Функция Гриванка
Способ кодирования	Прямой бинарный код	Код Грея	Гамма-коды Элиаса	Дельта-коды Элиаса	Гамма-коды Левенштейна	Коды Райса
Надежность	25	75	50	17	17	84
Функция Катникова
Способ кодирования	Прямой бинарный код	Код Грея	Гамма-коды Элиаса	Дельта-коды Элиаса	Гамма-коды Левенштейна	Коды Райса
Надежность	75	84	67	17	84	100
Функция Шекеля
Способ кодирования	Прямой бинарный код	Код Грея	Гамма-коды Элиаса	Дельта-коды Элиаса	Гамма-коды Левенштейна	Коды Райса
Надежность	50	75	67	20	84	100
Функция Де Йонга
Способ кодирования	Прямой бинарный код	Код Грея	Гамма-коды Элиаса	Дельта-коды Элиаса	Гамма-коды Левенштейна	Коды Райса
Надежность	75	75	100	100	67	100
Функция Розенброка
Способ кодирования	Прямой бинарный код	Код Грея	Гамма-коды Элиаса	Дельта-коды Элиаса	Гамма-коды Левенштейна	Коды Райса
Надежность	59	84	50	34	50	84
Функция «Сомбреро»
Способ кодирования	Прямой бинарный код	Код Грея	Гамма-коды Элиаса	Дельта-коды Элиаса	Гамма-коды Левенштейна	Коды Райса
Надежность	75	84	50	17	50	100

Таким образом, показана эффективность использования в генетическом алгоритме для решения задач оптимизации не только хорошо известных методов бинарного кодирования (прямой метод и грей-код), но и альтернативных способов. Особый интерес альтернативные способы кодирования представляют для гибридных генетических алгоритмов с локальным спуском. В данный момент проводятся исследования таких алгоритмов.