АДАПТАЦИЯ ПАРАМЕТРОВ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ОПТИМИЗАЦИИ СЛОЖНЫХ ФУНКЦИЙ
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И СИСТЕМЫ
УДК 519.816
И. Б. БОНДАРЕНКО, Е. А. КАЛЯЕВА, Д. Н. КОКШАРОВ
АДАПТАЦИЯ ПАРАМЕТРОВ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ОПТИМИЗАЦИИ СЛОЖНЫХ ФУНКЦИЙ
Исследовано влияние параметров разработанного генетического алгоритма на процесс оптимизации сложных функций. Показана взаимосвязь параметров при поиске глобального экстремума сложной функции. Даны рекомендации по использованию генетического алгоритма в подобных задачах.
Ключевые слова: генетический алгоритм, вещественное кодирование, пропорциональный отбор, глобальная оптимизация, тестовая функция, функция Растригина, функция Де Ионга, сложность алгоритма.
Генетические алгоритмы (ГА) относятся к методам эволюционного моделирования [1] и используются, наряду с методами нелинейного программирования и перебора, как для решения комбинаторных задач, так и для поиска глобального экстремума функций. В настоящей статье рассматривается концепция выбора основных параметров генетического алгоритма для оптимизации многомерных, мультимодальных функций и придания ему адаптирующих свойств.
Классический ГА базируется на следующих процедурах: отбор, скрещивание и мутация. Задачу оптимизации сложных функций произвольного вида выразим как
Qопт = extr(Q( X )), Q( X ) = Q(x1, x2,..., xn ) ,
(1)
где n — количество показателей функции качества Q(X) готовой системы. При вещественном кодировании хромосом и их пропорциональном отборе, т.е. когда
вероятность отбора хромосомы вычисляется с использованием функции [2]
pi
=
f
Nhr
(hri )
,
∑ f (hri )
i=1
(2)
где f(hri) — приспособленность i-й хромосомы; Nhr — количество хромосом или размер популяции, возникает следующая дилемма: как подобрать параметры ГА таким образом, чтобы,
во-первых, гарантированно найти решение задачи (1), а во-вторых, затратить на это меньше
времени.
Параметрами ГА являются:
— вероятность мутации (pм); — точность получения результата;
— количество итераций алгоритма или количество поколений (K);
— размер популяции (Nhr).
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 9
6 И. Б. Бондаренко, Е. А. Каляева, Д. Н. Кокшаров В работах, посвященных исследованиям генетического алгоритма [2, 3], авторы сходят-
ся во мнении, что вероятность мутации должна выбираться из диапазона 0,5—1 %. Так как два последних параметра в известных публикациях „оставлены без внимания“, то в настоящей статье именно их оценка и будет произведена. Необходимо отметить, что влияние обоих параметров на время вычислений прямо пропорционально.
В ходе исследований был разработан алгоритм, структурная схема которого приведена на рис. 1.
Начало
a, b, e, n, Nhr
Формирование начальных условий случайным образом
Вычисление коэффициентов
функции приспособленности
Отбор хромосом для родителей
Скрещивание
Вычисление коэффициентов
Выход
Да Есть решение? Нет Мутация
Рис. 1
Для исследования влияния параметров ГА на процесс поиска была выбрана тестовая функция Растригина [2]:
n
∑Q( X ) = 10n + {xi2 −10 cos(2πxi )}; i=1
(3)
xi ∈(а, b), а = – 5,12, b = 5,12.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 9
Адаптация параметров генетического алгоритма для оптимизации сложных функций
7
Наличие тригонометрической функции в выражении (3) приводит к образованию множества локальных экстремумов: см. рис. 2, где показана функция Растригина для n=2. Гло-
бальный экстремум будет находиться в точке xi = 0; i = 1, n .
z
yx
Рис. 2
На основе соотношения (2) и генетического алгоритма (см. рис. 1) была создана программа и исследована тестовая функция вида (3) для ряда значений параметров n и Nhr при точности е = 0,1 и pм = 0,1. Результаты тестирования представлены на рис. 3. (При значениях n, равных 3 и 5, графики сливаются с осью абсцисс.)
K⋅103
1000
800 600 n=7 400
n=9 n=11
200
0
5 30 60 90 120 150 180 250 400 550 700 850 1000 1300 1600 1900 Nhr
Рис. 3
Значение K>1200 тыс. было признано неудовлетворительным ввиду значительных вре-
менных затрат.
Для сравнения с предыдущим результатом была исследована сферическая функция или
тестовая функция Де Ионга 1 [2]
n
∑Q( X ) = xi2 , xi ∈ (−5,12; 5,12) , i=1
(4)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 9
8 И. Б. Бондаренко, Е. А. Каляева, Д. Н. Кокшаров
имеющая глобальный экстремум в той же точке, что и функция Растригина. Для тех же значений параметров, что и для функции (3), исследование сферической функции привело к результатам, представленным на рис. 4.
K⋅103
1000
800
600
400 n=11
200 n=7
n=9
0
5 30 60 90 120 150 180 250 400 550 700 Nhr Рис. 4
Исследования тестовых функций, схожих с функцией (4), например гиперэллипсоидной:
n
∑Q( X ) = ixi2 , xi ∈ (−5,12; 5,12) , i=1
(5)
или повернутой гиперэллипсоидной:
ni
Q(X ) = ∑∑
x
2 j
,
xi ∈ (−65, 536; 65, 536) ,
i=1 j=1
(6)
приводят к результатам, сходным с представленными на рис. 4.
При анализе рис. 3 и 4 возникает вопрос: что выгоднее — увеличивать число хромосом
в популяции или количество итераций ГА, т.е. число поколений? Для ответа на этот вопрос
была рассчитана сложность разработанного алгоритма:
O{4
Nhr
n+8
Nhr
+
N
2 hr
}
.
(7)
Ясно, что
lim(O{4 Nhr n + 8 Nhr + Nh2r }) → O{Nh2r }
(8)
при больших величинах Nhr. Следовательно, при увеличении числа хромосом, например, на величину w сложность
алгоритма согласно выражению (8) определяется как
O{(Nhr + w)2} ,
(9)
а при увеличении числа поколений — как
O{w Nh2r } .
(10)
Таким образом, так как сложность алгоритма, рассчитанная по выражению (10), с ростом w
возрастает быстрее, чем при расчете по формуле (9), то выгоднее увеличивать число хромосом.
Окончательно по результатам тестирования можно сделать следующие выводы.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 9
Адаптация параметров генетического алгоритма для оптимизации сложных функций
9
1. Если исследуемая функция многомерная и унимодальная (вида (4)—(6)), то для гарантированного нахождения ее экстремума необходимо, например, 100 тыс. поколений, состоящих из 5—400 хромосом для 3—11 переменных.
2. Если функция многомерная и мультимодальная, например вида (3), то необходимо уже 5—1800 хромосом для 3—11 переменных при том же количестве поколений.
3. Уменьшение числа поколений приводит к необходимости увеличения числа хромосом. При поиске выгоднее увеличивать число хромосом, чем число поколений, несмотря на увеличение размерности массивов и необходимость дополнительной оперативной памяти.
В заключение следует отметить, что результатом данного исследования являются рекомендации по использованию классического генетического алгоритма при поиске экстремума сложных функций. С учетом вышеизложенных аспектов алгоритм можно адаптировать к степени сложности оптимизируемой модели, что позволит повысить скорость решения подобных задач.
СПИСОК ЛИТЕРАТУРЫ
1. Бондаренко И. Б., Гатчин Ю. А., Соловьев Д. В. Интеллектуальная поддержка выработки оптимальных решений в САПР оптического производства // Тр. Междунар. науч.-техн. конф. „Интеллектуальные системы“ (AIS'08) и „Интеллектуальные САПР“ (CAD-2008). М.: Физматлит, 2008. Т. 1. С. 115—119.
2. Панченко Т. В. Генетические алгоритмы: Учеб. пособие / Под ред. Ю. Ю. Тарасевича. Астрахань: Изд. дом „Астраханский университет“, 2007. 87 с.
3. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы / Под ред. В. М. Курейчика. М.: ФИЗМАТЛИТ, 2006.
Игорь Борисович Бондаренко Екатерина Анатольевна Каляева Дмитрий Николаевич Кокшаров
Сведения об авторах — канд. техн. наук, доцент; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, кафедра проектирования компьютерных систем; E-mail: igorlitmo@rambler.ru — студентка; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра проектирования компьютерных систем; E-mail: kate4kina@list.ru — канд. техн. наук; ЗАО „НАВИС“, Санкт-Петербург; руководитель проекта; E-mail: drobifmo@yandex.ru
Рекомендована кафедрой проектирования компьютерных систем СПбГУ ИТМО
Поступила в редакцию 08.02.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 9
УДК 519.816
И. Б. БОНДАРЕНКО, Е. А. КАЛЯЕВА, Д. Н. КОКШАРОВ
АДАПТАЦИЯ ПАРАМЕТРОВ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ОПТИМИЗАЦИИ СЛОЖНЫХ ФУНКЦИЙ
Исследовано влияние параметров разработанного генетического алгоритма на процесс оптимизации сложных функций. Показана взаимосвязь параметров при поиске глобального экстремума сложной функции. Даны рекомендации по использованию генетического алгоритма в подобных задачах.
Ключевые слова: генетический алгоритм, вещественное кодирование, пропорциональный отбор, глобальная оптимизация, тестовая функция, функция Растригина, функция Де Ионга, сложность алгоритма.
Генетические алгоритмы (ГА) относятся к методам эволюционного моделирования [1] и используются, наряду с методами нелинейного программирования и перебора, как для решения комбинаторных задач, так и для поиска глобального экстремума функций. В настоящей статье рассматривается концепция выбора основных параметров генетического алгоритма для оптимизации многомерных, мультимодальных функций и придания ему адаптирующих свойств.
Классический ГА базируется на следующих процедурах: отбор, скрещивание и мутация. Задачу оптимизации сложных функций произвольного вида выразим как
Qопт = extr(Q( X )), Q( X ) = Q(x1, x2,..., xn ) ,
(1)
где n — количество показателей функции качества Q(X) готовой системы. При вещественном кодировании хромосом и их пропорциональном отборе, т.е. когда
вероятность отбора хромосомы вычисляется с использованием функции [2]
pi
=
f
Nhr
(hri )
,
∑ f (hri )
i=1
(2)
где f(hri) — приспособленность i-й хромосомы; Nhr — количество хромосом или размер популяции, возникает следующая дилемма: как подобрать параметры ГА таким образом, чтобы,
во-первых, гарантированно найти решение задачи (1), а во-вторых, затратить на это меньше
времени.
Параметрами ГА являются:
— вероятность мутации (pм); — точность получения результата;
— количество итераций алгоритма или количество поколений (K);
— размер популяции (Nhr).
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 9
6 И. Б. Бондаренко, Е. А. Каляева, Д. Н. Кокшаров В работах, посвященных исследованиям генетического алгоритма [2, 3], авторы сходят-
ся во мнении, что вероятность мутации должна выбираться из диапазона 0,5—1 %. Так как два последних параметра в известных публикациях „оставлены без внимания“, то в настоящей статье именно их оценка и будет произведена. Необходимо отметить, что влияние обоих параметров на время вычислений прямо пропорционально.
В ходе исследований был разработан алгоритм, структурная схема которого приведена на рис. 1.
Начало
a, b, e, n, Nhr
Формирование начальных условий случайным образом
Вычисление коэффициентов
функции приспособленности
Отбор хромосом для родителей
Скрещивание
Вычисление коэффициентов
Выход
Да Есть решение? Нет Мутация
Рис. 1
Для исследования влияния параметров ГА на процесс поиска была выбрана тестовая функция Растригина [2]:
n
∑Q( X ) = 10n + {xi2 −10 cos(2πxi )}; i=1
(3)
xi ∈(а, b), а = – 5,12, b = 5,12.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 9
Адаптация параметров генетического алгоритма для оптимизации сложных функций
7
Наличие тригонометрической функции в выражении (3) приводит к образованию множества локальных экстремумов: см. рис. 2, где показана функция Растригина для n=2. Гло-
бальный экстремум будет находиться в точке xi = 0; i = 1, n .
z
yx
Рис. 2
На основе соотношения (2) и генетического алгоритма (см. рис. 1) была создана программа и исследована тестовая функция вида (3) для ряда значений параметров n и Nhr при точности е = 0,1 и pм = 0,1. Результаты тестирования представлены на рис. 3. (При значениях n, равных 3 и 5, графики сливаются с осью абсцисс.)
K⋅103
1000
800 600 n=7 400
n=9 n=11
200
0
5 30 60 90 120 150 180 250 400 550 700 850 1000 1300 1600 1900 Nhr
Рис. 3
Значение K>1200 тыс. было признано неудовлетворительным ввиду значительных вре-
менных затрат.
Для сравнения с предыдущим результатом была исследована сферическая функция или
тестовая функция Де Ионга 1 [2]
n
∑Q( X ) = xi2 , xi ∈ (−5,12; 5,12) , i=1
(4)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 9
8 И. Б. Бондаренко, Е. А. Каляева, Д. Н. Кокшаров
имеющая глобальный экстремум в той же точке, что и функция Растригина. Для тех же значений параметров, что и для функции (3), исследование сферической функции привело к результатам, представленным на рис. 4.
K⋅103
1000
800
600
400 n=11
200 n=7
n=9
0
5 30 60 90 120 150 180 250 400 550 700 Nhr Рис. 4
Исследования тестовых функций, схожих с функцией (4), например гиперэллипсоидной:
n
∑Q( X ) = ixi2 , xi ∈ (−5,12; 5,12) , i=1
(5)
или повернутой гиперэллипсоидной:
ni
Q(X ) = ∑∑
x
2 j
,
xi ∈ (−65, 536; 65, 536) ,
i=1 j=1
(6)
приводят к результатам, сходным с представленными на рис. 4.
При анализе рис. 3 и 4 возникает вопрос: что выгоднее — увеличивать число хромосом
в популяции или количество итераций ГА, т.е. число поколений? Для ответа на этот вопрос
была рассчитана сложность разработанного алгоритма:
O{4
Nhr
n+8
Nhr
+
N
2 hr
}
.
(7)
Ясно, что
lim(O{4 Nhr n + 8 Nhr + Nh2r }) → O{Nh2r }
(8)
при больших величинах Nhr. Следовательно, при увеличении числа хромосом, например, на величину w сложность
алгоритма согласно выражению (8) определяется как
O{(Nhr + w)2} ,
(9)
а при увеличении числа поколений — как
O{w Nh2r } .
(10)
Таким образом, так как сложность алгоритма, рассчитанная по выражению (10), с ростом w
возрастает быстрее, чем при расчете по формуле (9), то выгоднее увеличивать число хромосом.
Окончательно по результатам тестирования можно сделать следующие выводы.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 9
Адаптация параметров генетического алгоритма для оптимизации сложных функций
9
1. Если исследуемая функция многомерная и унимодальная (вида (4)—(6)), то для гарантированного нахождения ее экстремума необходимо, например, 100 тыс. поколений, состоящих из 5—400 хромосом для 3—11 переменных.
2. Если функция многомерная и мультимодальная, например вида (3), то необходимо уже 5—1800 хромосом для 3—11 переменных при том же количестве поколений.
3. Уменьшение числа поколений приводит к необходимости увеличения числа хромосом. При поиске выгоднее увеличивать число хромосом, чем число поколений, несмотря на увеличение размерности массивов и необходимость дополнительной оперативной памяти.
В заключение следует отметить, что результатом данного исследования являются рекомендации по использованию классического генетического алгоритма при поиске экстремума сложных функций. С учетом вышеизложенных аспектов алгоритм можно адаптировать к степени сложности оптимизируемой модели, что позволит повысить скорость решения подобных задач.
СПИСОК ЛИТЕРАТУРЫ
1. Бондаренко И. Б., Гатчин Ю. А., Соловьев Д. В. Интеллектуальная поддержка выработки оптимальных решений в САПР оптического производства // Тр. Междунар. науч.-техн. конф. „Интеллектуальные системы“ (AIS'08) и „Интеллектуальные САПР“ (CAD-2008). М.: Физматлит, 2008. Т. 1. С. 115—119.
2. Панченко Т. В. Генетические алгоритмы: Учеб. пособие / Под ред. Ю. Ю. Тарасевича. Астрахань: Изд. дом „Астраханский университет“, 2007. 87 с.
3. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы / Под ред. В. М. Курейчика. М.: ФИЗМАТЛИТ, 2006.
Игорь Борисович Бондаренко Екатерина Анатольевна Каляева Дмитрий Николаевич Кокшаров
Сведения об авторах — канд. техн. наук, доцент; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, кафедра проектирования компьютерных систем; E-mail: igorlitmo@rambler.ru — студентка; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра проектирования компьютерных систем; E-mail: kate4kina@list.ru — канд. техн. наук; ЗАО „НАВИС“, Санкт-Петербург; руководитель проекта; E-mail: drobifmo@yandex.ru
Рекомендована кафедрой проектирования компьютерных систем СПбГУ ИТМО
Поступила в редакцию 08.02.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 9