ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ РАБОТЫ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ОПТИМИЗАЦИИ С АЛЬТЕРНАТИВНЫМ ПРЕДСТАВЛЕНИЕМ РЕШЕНИЙ

Полный текст

Огромное число работ посвящено исследованию генетических алгоритмов. Традиционно исследователи рассматривают влияние вероятности мутации, размера популяции, способов селекции и др., легко на- ] страиваемые параметры алгоритма. Представление решений же, как правило, осуществляется кодированием в бинарную строку вещественных переменных с помощью традиционного бинарного кодирования или грей-кода. Целью данной работы было исследовать возможность применения в генетическом алгоритме альтернативных способов бинарного кодирования вещественных чисел. При проектировании генетического алгоритма выбор способа представления решений является определяющим. В зависимости от решаемой задачи составляют хромосомы решений из вещественных чисел, целых чисел, специальные алфавиты, используют порядковое представление, представление в виде «деревьев» и др. Стандартный генетический алгоритм использует в качестве хромосомы бинарный вектор. Представление хромосом определяется способом кодирования. Как правило, в генетическом алгоритме применяется двоичное представление хромосом. Оно основано на известном способе записи десятичных чисел в двоичной системе, где каждый бит двоичного кода соответствует очередной степени цифры 2. Например, двоичная последовательность [10011] представляет собой код числа 19, поскольку 1*24+0*23+0*22+1*21+1*21=19. Данный способ кодирования решений будем называть прямым бинарным кодом. Существует много способов бинарного кодирования решений, рассмотрим некоторые из них. Код Грея - это бинарный код целого числа, такой, что для смежных целых чисел расстояние между их кодами в метрике Хемминга равно 1. Стандартное рефлексивное грей-кодирование целого числа получается применением оператора исключающего ИЛИ, к стандартному бинарному кодированию целого числа и к тому же бинарному коду, смещенному на одну позицию вправо, последний бит отсекается. Для многих практических задач код Грея оказывается более эффективным, чем бинарное кодирование [1]. Код Грея частично сохраняет структуру окрестностей пространства поиска в бинаризованном пространстве. В результате, грей-код не может образовать оптимумов больше, чем у исходной целевой функции. Более того, так как у текущей точки в коде Грея соседних точек больше, чем в дискретной целевой функции, то в пространстве поиска грей-кода число оптимумов обычно меньше. В противоположность, прямой бинарный код часто создает новые оп-тимумы, которых у исходной целевой функции не было [2]. Практически не встречается в научной литературе использование для генетического алгоритма бинарных кодов с переменной длиной. Значащие цифры начинаются со старшей ненулевой цифры, например, в числе 0000011012=1*20+0*21+1*22+1*23+0*24+0*...=13 это последние 4 цифры. Порядок числа определяется позицией старшей ненулевой цифры в записи числа. Как и при обычной записи в десятичной системе, он равен числу цифр в записи числа без предшествующих незначащих нулей. В данном примере порядок равен четырем. Методы этой группы являются трансформирующими и поточечными (т. е. могут применяться даже в том случае, когда длина блока с данными не задана). Унарный код - это запись числа N, последовательность из N нулевых бит и одного единичного. Гамма-коды Элиаса (Elias γ-codes). Данные коды формируются в зависимости от диапазона числа. Допустим, кодируется число n, тогда гамма-кодом Элиаса для числа n будет его обыкновенное бинарное представление без старшей единицы, дополненное слева унарным представлением числа (табл. 1). Дельта-коды Элиаса (Elias δ-codes). Дельтакодами Элиаса называются гамма-коды, в которых унарная часть также закодирована гамма-кодами. То есть для получения дельта-кода нужно закодировать L (количество значащих битов в двоичном представлении числа n) с помощью гамма-кода Элиаса и дописать двоичное представление числа без старшей единицы (табл. 2). Таблица 2 Дельта-коды Элиаса Диапазон Дельта-коды Элиаса* Длина кода, бит 1 1 1 СП (N 010x 4 011xx 5 5 8 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, размещённую в log2m битах; Если m не является степенью 2, вычисляется число b = log2m. Если r < 2b-m, код остатка представляет собой двоичную запись числа r, размещённую в b-1 битах, иначе остаток r кодируется двоичной записью числа r < 2b-m, размещённой в b битах (табл. 4). Коды Райса (Rice codes). Код Райса для n с заданным параметром к дает соединение двух кодов: унарная запись числа q = n/2k и кодированный остаток r от деления n/2k, представляющий собой двоичную запись числа r, размещённую в к битах (табл. 5). Таблица 1 Гамма-коды Элиаса Диапазон Гамма-коды Элиаса* Длина кода, бит 1 1 1 3 2 01x 3 001xx 5 5 8 0001xxx 7 31 6 00001xxxx 9 32...63 000001xxxxx 11 * Символами «х» обозначены биты мантиссы без старшей единицы. 69 Вестник СибГАУ. N 4(50). 2013 Таблица 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 70 Математика, механика, информатика Таким образом, показана эффективность использования в генетическом алгоритме для решения задач оптимизации не только хорошо известных методов бинарного кодирования (прямой метод и грей-код), но и альтернативных способов. Особый интерес альтернативные способы кодирования представляют для гибридных генетических алгоритмов с локальным спуском. В данный момент проводятся исследования таких алгоритмов.

Об авторах

Илья Александрович Панфилов

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: crook_80@mail.ru
кандидат технических наук, доцент, доцент кафедры системного анализа и исследования операций Российская Федерация, 660014, Красноярск, просп. им. газ. «Красноярский рабочий», 31

Екатерина Петровна Базанова

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: bazanova_ekaterina@mail.ru
Российская Федерация, 660014, Красноярск, просп. им. газ. «Красноярский рабочий», 31

Евгений Александрович Сопов

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: crook_80@mail.ru
кандидат технических наук, доцент, доцент кафедры системного анализа и исследования операций Российская Федерация, 660014, Красноярск, просп. им. газ. «Красноярский рабочий», 31

Список литературы

Дополнительные файлы