INVESTIGATION OF THE GENETIC ALGORITHM WITH AN ALTERNATIVE REPRESENTATION OF SOLUTIONS

Texto integral

Огромное число работ посвящено исследованию генетических алгоритмов. Традиционно исследователи рассматривают влияние вероятности мутации, размера популяции, способов селекции и др., легко на- ] страиваемые параметры алгоритма. Представление решений же, как правило, осуществляется кодированием в бинарную строку вещественных переменных с помощью традиционного бинарного кодирования или грей-кода. Целью данной работы было исследовать возможность применения в генетическом алгоритме альтернативных способов бинарного кодирования вещественных чисел. При проектировании генетического алгоритма выбор способа представления решений является определяющим. В зависимости от решаемой задачи составляют хромосомы решений из вещественных чисел, целых чисел, специальные алфавиты, используют порядковое представление, представление в виде «деревьев» и др. Стандартный генетический алгоритм использует в качестве хромосомы бинарный вектор. Представление хромосом определяется способом кодирования. Как правило, в генетическом алгоритме применяется двоичное представление хромосом. Оно основано на известном способе записи десятичных чисел в двоичной системе, где каждый бит двоичного кода соответствует очередной степени цифры 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 Математика, механика, информатика Таким образом, показана эффективность использования в генетическом алгоритме для решения задач оптимизации не только хорошо известных методов бинарного кодирования (прямой метод и грей-код), но и альтернативных способов. Особый интерес альтернативные способы кодирования представляют для гибридных генетических алгоритмов с локальным спуском. В данный момент проводятся исследования таких алгоритмов.

Sobre autores

Ilia Panfilov

Siberian State Aerospace University named after academician M. F. Reshetnev

Email: crook_80@mail.ru
Candidate of Engineering Science, associate professor, associate professor of System Analysis and Operations Research Department 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660014, Russian Federation

Ekaterina Bazanova

Siberian State Aerospace University named after academician M. F. Reshetnev

Email: bazanova_ekaterina@mail.ru
31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660014, Russian Federation

Evgeny Sopov

Siberian State Aerospace University named after academician M. F. Reshetnev

Email: crook_80@mail.ru
Candidate of Engineering Science, associate professor, associate professor of System Analysis and Operations Research Department 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660014, Russian Federation

Bibliografia

Arquivos suplementares