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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

В современных условиях бурного развития информационных технологий решение большинства задач, возникающих в различных областях науки и техники, связано с нахождением глобального оптимума (наилучшего решения) в общем случае невыпуклой, негладкой, многоэкстремальной целевой функции, численно характеризующей выбранный показатель качества (эффективности). Решение подобных задач предполагает использование специальных многоэкстремальных оптимизационных методов, определяющих некоторое правило перебора решений на равномерной/неравномерной сетке по детерминированному или случайному закону. В практике научных решений большое распространение получили алгоритмы глобальной оптимизации, основанные на эволюционных методах, - генетические алгоритмы. Для увеличения эффективности последних, особенно при решении многомерных многоэкстремальных задач, в ряде работ [1-3] предложена комбинация работы генетического алгоритма и некоторого классического градиентного метода локальной оптимизации. В рассматриваемой постановке гибридная генетическая оптимизация предполагает параллельную (раздельную) работу генетического и градиентного методов с постоянным сравнением на каждой k-й итерации лучшего решения с последующей передачей последнего (лидера и вектора лидеров из полученной популяции) на k+1-й итерации градиентному методу.

При этом, с учетом предложенных решений [1-3] и результатов их работы, особый интерес вызывают вопросы, связанные с непосредственным объединением генетических методов с известными методами локального поиска [4-6], а также методов статистического анализа [7] на этапе селекции новой популяции.

Градиентное обучение и прогнозирование при решении задач глобальной оптимизации.

Рассмотрим решение задачи нахождения глобального оптимума многомерной функции:

 (1)

где N определяет число переменных функции. При этом в общей постановке функция (1) может быть недифференцируема в некоторых точках, иметь точки разрыва первого и второго рода (может быть определена не для всех точек ). В связи с этим на существенное улучшение сходимости генетического метода при использовании только градиентного обучения особи-лидера популяции при случайном выборе начального приближения (первое поколение), очевидно, не всегда можно рассчитывать. Для увеличения скорости сходимости решения предлагается по выбранному методу локальной оптимизации [4] использовать градиентное обучение всех особей-лидеров с дополнительным применением моделей прогнозирования авторегрессии - скользящего среднего (ARMA) [7] выбранного порядка на этапе мутации популяции и скрещивания с использованием метода параболической интерполяции [5].

Для решения задачи (1) рассмотрим генетический алгоритм в вещественных кодах [8] RGA (real-coded genetic algoritms определяет представление генов особи в популяции в виде вещественного числа) с градиентным обучением и прогнозированием. Предпочтительность использования RGA кодирования заключается в простоте (с позиции минимизации вычислительных затрат) реализации процедуры кодирования/декодирования фенотипа особи в ее эквивалентный генотип, по сути определяющий перевод вещественного значения аргумента к безразмерному виду для интервала по правилу [8]:

где - границы области поиска глобального оптимума функции (1) по переменной .

Последовательность предлагаемого решения заключается в выполнении следующих действий:

1. Задание настраиваемых параметров алгоритма: n - размер популяции; - параметр кроссовера; k - количество привилегированных особей в популяции (особи-лидеры); - границы области поиска глобального оптимума функции (1) по переменной ; p и q - параметры, определяющие порядок модели ARMA(p, q); m = 1 - номер итерации алгоритма; M - предельно допустимое число итераций алгоритма; - первое поколение, определяющее начальное приближение итерационного алгоритма оптимизации функции (1).

2. Вычисление значений целевой функции (1) для j-х особей из полученной m-й итерации популяции.

3. Сортировка значений по возрастанию и выбор лучших особей из m-й популяции.

4. Генерация фенотипов и пары популяций родителей по правилу:

где - белый шум (случайная величина, распределенная по равномерному закону на интервале ); - случайная величина, распределенная по равномерному закону на интервале ; и - коэффициенты модели ARMA (авторегрессионные коэффициенты и коэффициенты скользящего среднего соответственно), определяемые по правилам, представленным в [7].

5. Скрещивание полученных пар популяций родителей с использованием метода параболической интерполяции [5]. В такой постановке фенотипы потомков с учетом [8] задаются отношениями:

где , , - значения целевой функции (1) для j-х особей, заданных соответствующими фенотипами популяций , , .

6. Градиентное обучение по выбранному оптимизационному алгоритму k первых особей-лидеров из сформированной на предыдущем шаге популяции потомков .

Например, в случае градиентного обучения по алгоритму Дэвидона-Флетчера-Пауэлла значения определятся по правилу [4]:

где определяется вектор-столбец матрицы; - матрица, аппроксимирующая матрицу направлений размера для j-й особи на m-м шаге алгоритма (обратную матрицу Гессе), которая определяется в [4] как:

где:

;

Е - единичная матрица; - вектор градиента целевой функции (1).

Величина на каждом шаге определяется из условия:

. (2)

Задача (2) решается численно гибридным методом одномерной безусловной оптимизации, пример реализации которого подробно рассмотрен в [5].

Из полученных значений и с выхода градиентного алгоритма формируется m+1-е поколение . Счетчик итераций увеличивается на единицу: m = m + 1.

7. Проверка выполнения условия остановки итерационного алгоритма. Например, наряду с очевидным условием алгоритм может быть остановлен в случае невыполнения неравенства:

и/или (3)

где - малая величина, определяющая погрешность работы алгоритма.

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

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

(4)

где (график функции при N = 2 представлен на рис. 1а);

(5)

где (график функции при N = 2 представлен на рис. 1б);

(6)

где (график функции при N = 2 представлен на рис. 1в);

(7)

где (график функции при N = 2 представлен на рис. 1г).

При определении глобального минимума функций (4) и (5) их размерности принимались N = 2 , N = 50 с заданной популяцией в 20 особей (n = 20), для которой определено 5 особей-лидеров (k = 5). Результаты расчетов фиксировались по запускам алгоритма с последующим усреднением итогового выходного значения. Скорость сходимости предложенной модификации алгоритма с градиентным обучением особей из формируемой популяции методами наискорейшего спуска, Полака-Райбера, Флетчера-Ривса, Дэвидона-Флетчера-Пауэлла (Д-Ф-П), Ньютона-Рафсона [4] оценивалась в сравнении: 1) с гибридным генетическим алгоритмом (ГГА) с градиентным обучением лидера (ГОЛ) [1]; 2) ГГА с градиентным обучением особей-лидеров в популяции (ГООЛ); 3) ГГА с градиентным обучением всех особей в популяции (ГООП). На рис. 2а - г представлены графики зависимости ошибки определения глобального минимума соответствующих целевых функций (4 - 7) при N = 2 методами ГГА с ГОЛ, ГООЛ и ГООП от числа итераций K.

Рис. 1. Графики многоэкстремальных тестовых функций: а - двухмерная функция (4); б - двухмерная функция (5); в - двухмерная функция (6); г - двухмерная функция (7)

Полученные результаты (рис. 2а - г) свидетельствуют о предпочтительности с позиции увеличения скорости сходимости градиентного обучения всех особей из формируемой популяции. Выигрыш в сходимости увеличивается с увеличением числа локальных экстремумов (рис. 2а, б) дифференцируемой целевой функции. При этом не всегда скорость сходимости самого градиентного метода влияет на скорость сходимости итогового ГГА (ГГА с ГООП методом наискорейшего спуска сходится быстрее, чем ГГА с ГООП методом Ньютона-Рафсона для функции (4)). Также увеличение числа локальных экстремумов (рис. 2в), а тем более появление у целевой функции изолированных экстремумов (рис.1г), приводит к существенному ухудшению скорости сходимости ГГА.

На рис. 3а - г представлены графики зависимости ошибки определения глобального минимума соответствующих целевых функций (4 - 7) при N = 2 методами ГГА с ГООП и ГА с предложенной модификацией с прогнозированием по модели ARMA(1, 1) от числа итераций K. Градиентное обучение в обоих случаях выполнено методом наискорейшего спуска. Из полученных результатов следует более высокая скорость сходимости предложенной модификации при меньших вычислительных затратах алгоритма в сравнении с решением по ГГА с ГООП на единичной итерации.

Рис. 2. Графики зависимости ошибки определения глобального минимума функций от числа итераций: а - двухмерная функция (4); б - двухмерная функция (5); в - двухмерная функция (6); г - двухмерная функция (7)

итерация минимум генетический

Однако в целом увеличение скорости сходимости алгоритма не может определить однозначную оценку предпочтительности использования предложенной модификации ГГА. Для окончательной оценки эффективности (вычислительная сложность и скорость сходимости) предложенной модификации ГГА для представленных тестовых функций выполнен следующий итоговый вычислительный эксперимент. Время работы алгоритма при реализации в САПР Mathcad 15 ограничено 2 мин (120 с) для ЭВМ с параметрами: Intel(R) Core(TM) i7-3612QM CPU 2.10 GHz, ОЗУ 8Гб (досрочная остановка алгоритма осуществляется при выполнении условий (3) при ). Выходные данные: средние выборочные значения числа итераций алгоритма Nср, средняя выборочная ошибка определения экстремума целевой функции , среднее время работы алгоритма tср. Результаты указанного эксперимента для размерности целевых функций (4 - 7) N = 50 представлены в таблице. Наиболее удачные (с точки зрения точности оценки) реализации алгоритмов по минимизации тестовых функций выделены серым цветом. Решения, соответствующие наибольшему быстродействию, выделены жирным шрифтом.

Рис. 3. Графики зависимости ошибки определения глобального минимума функций от числа итераций: а - двухмерная функция (4); б - двухмерная функция (5); в - двухмерная функция (6); г - двухмерная функция (7)

Из полученных результатов следует, что применение предложенной модификации генетического алгоритма - градиентного обучения особей-лидеров с прогнозированием - для многомерных произвольных функций в сравнении с известными решениями обладает наибольшей предпочтительностью как с позиции скорости сходимости, так и с позиции минимизации вычислительных затрат. Среднее время, соответствующее нахождению глобального оптимума четвертой тестовой функции по предложенной модификации генетического метода, составляет 16 мин 39,907 с, в то время как ГА с ГООЛ определяет глобальный оптимум в среднем за 21 мин 53,481 с.

Таблица 1. Результаты минимизации функций (4 - 7) для N = 50

На основании полученных результатов можно заключить, что реализация алгоритмов глобальной оптимизации по предложенной модификации генетического метода в направлении объединения с известными методами локального поиска и статистического анализа позволяет повысить эффективность численного решения многомерных многоэкстремальных задач, в особенности связанных со структурно-параметрическим синтезом различных систем [9; 10]. При этом допускается содержание в целевой функции точек разрыва первого и второго рода. В рамках проведенных вычислительных экспериментов с позиции вычислительной сложности определена предпочтительность предварительного прогнозирования фенотипов родителей популяции с последующим скрещиванием по методу параболической интерполяции и градиентным обучением особей-лидеров в сформированной популяции.

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

1. Тененев В.А. Гибридный генетический алгоритм с дополнительным обучением лидера / В.А. Тененев, Н.Б. Паклин // Интеллектуальные системы в производстве. - 2003. - № 2. - С. 181-206.

2. Дмитриев С.В. Применение прямых методов оптимизации в гибридном генетическом алгоритме / С.В. Дмитриев, В.А. Тененев // Интеллектуальные системы в производстве. - 2005. - № 2. - С. 11-22.

3. Дмитриев С.В. Оптимизация многоэкстремальных функций с помощью гибридных генетических алгоритмов / С.В. Дмитриев, В.А. Тененев // Изв. Ин-та математики и информатики. Ижевск. - 2006. - № 2 (36). - С. 163-166.

4. Васильев Ф.П. Численные методы решения экстремальных задач / Ф.П. Васильев. - М.: Наука, 1980. - 520 с.

5. Полянский И.С. Метод одномерной безусловной оптимизации в задаче оценки развязки парциальных лучей многолучевой антенны зеркального типа / И.С. Полянский // Современные проблемы науки и образования. - 2012. - № 4.

6. Таха Хэмди А. Введение в исследование операций / Хэмди А. Таха. - М.: Вильямс, 2001. - 912 с.

7. Андерсон Т. Статистический анализ временных рядов / Т. Андерсон; пер. с англ. И.Г. Журбенко, В.П. Носко, под ред. Ю.К. Беляева. - М.: Мир, 1976. - 755 с.

8. Herrera F. Tackling real-coded genetic algorithms: operators and tools for the behaviour analysis / F. Herrera, M. Lozano, J.L. Verdegay // Artificial Intelligence Review. - 1998. - Vol. 12. - № 4. - P. 265-319.

9. Еременко В.Т. Методологические аспекты синтеза оптимальной древовидной структуры в системах сбора и обработки информации / В.Т. Еременко, И.С. Полянский, И.И. Беседин // Вестник компьютерных и информационных технологий. - 2013. - № 11. - С. 11-15.

10. Полянский И.С. Алгоритм распределения неоднородных дискретных ограниченных ресурсов в системе физической защиты / И.С. Полянский, И.И. Беседин // Информационные системы и технологии. - 2013. - № 4(78).

Размещено на Allbest.ru