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

Глобальная оптимизация - одна из наиболее актуальных и бурно развивающихся областей, так как число прикладных задач принятия решений, которые могут выражаться многоэкстремальными функциями, растет и развивается вычислительная техника. В большинстве таких задач недостаточно просто найти один из локальных минимумов, так как глобальный способен дать существенный выигрыш по сравнению с каким - либо другим.
При этом целевая функция и ограничения могут задаваться в форме черного ящика, то есть в виде некоторого вычислительного алгоритма, на вход которого подается аргумент, а на выходе значение функции, причем внутреннее устройство такого алгоритма может быть неизвестным или сложным с вычислительной точки зрения. Также может отсутствовать дифференцируемость функции. Вышеперечисленные свойства значительно усложняют поиск глобального оптимума, делают невозможным применение многих классических методов решения этой задачи [2, 3, 6, 9, 10].
Построение схем нахождения глобального оптимума, способных менять направление поиска в зависимости от текущей информации, возможно благодаря определенным априорным предположениям о характере рассматриваемой проблемы. Такие предположения играют ключевую роль при разработке быстрых алгоритмов глобального поиска и служат основным математическим инструментом для получения оценок глобального решения после остановки алгоритма [14].
Одним из естественных и важных (как в теоретическом, так и в прикладном отношениях) допущений о задаче глобальной оптимизации (1) является предположение об ограниченности относительных изменений целевой функции /(х), выраженное в формуле (2). Оно связано с тем, что отношения приращений функций к соответствующим приращениям
аргументов обычно не могут превышать некоего порога, определяемого ограниченной энергией изменений в системе, который может быть описан с использованием действительной положительной константы L. В таком случае функция f(x) называется липшицевой, а сама задача - задачей липшицевой глобальной оптимизации.
f* = f (x*) = min f(x), x G [a, b], (1)
|f(x‘) — f(x")| < L|x‘— x"|, Vx',x" G [a, b], 0 < L < ш, (2) где f* - значение искомого глобального минимума с координатой x*. На рисунке 1 показан пример липшицевой функции.

Рисунок 1 - Липшицевая функция

Рассмотрим задачу идентификации параметров [12, 18]. Пусть имеются некоторые экспериментальные данные из входных х1 и выходных у^ (/ = 1, п), где п - количество данных, а также математическая модель Р(х, 2), где х = (х1, .,хт) - входной вектор размерности т, 2 = (21, ...,2р) - вектор параметров размерности р. Тогда для того, чтобы модель Г(х,2) была адекватной, то есть чтобы мало отличалась от экспериментальных данных, составим квадратичную функцию невязки /(2):
n
l(A) = ^(F(xl,X)-y^2, (3)
¿ = 1
затем решим задачу:
1(Л) ^ min. (4)
Тогда набор параметров Л* = (Л1, _, Я.^), являющийся решением задачи (4), и будет являться оптимальным набором параметров для математической модели F(x,Л). Для решения задачи (4) часто применяются инструменты глобальной липшицевой оптимизации. Также эти методы применяются в задаче отыскания первого левого нуля в множестве сигналов [20].
Целью работы является построение алгоритма глобальной оптимизации липшицевой целевой функции с использованием нейронных сетей.
Задачи:
- изучить существующие алгоритмы глобальной оптимизации, их достоинства и недостатки;
- модифицировать алгоритм поиска глобального минимума, использующий нейросеть для оценки локальной константы Липшица;
- построить и обучить нейросеть для алгоритма глобальной минимизации;
- выполнить сравнение эффективности построенного алгоритма на тестовых функциях.

Купить

В ходе работы были решены следующие задачи:
1) изучены существующие алгоритмы глобальной оптимизации, их достоинства и недостатки. Рассмотрен алгоритм равномерного перебора точек, локальные методы оптимизации, в том числе градиентный спуск и классический метод решения задачи оптимизации с помощью производных, также рассмотрен метод решения задачи глобальной оптимизации с помощью априорно заданной константы Липшица;
2) модифицирован алгоритм поиска глобального минимума, использующий нейросеть для оценки локальной константы Липшица, описан способ получения истинной константы Липшица для обучения нейронной сети. Отличие алгоритма заключается лишь в способе оценки локальной константы Липшица;
3) построена и обучена нейросеть для алгоритма глобальной минимизации. Использовалась многослойная полносвязная нейронная сеть, так как хорошо подходит для задачи регрессии;
4) выполнено сравнение эффективности построенного алгоритма на тестовых функциях. Удалось добиться уменьшения отношения среднего числа вычислений функции в точках НС алгоритма к среднему числу вычислений функции в точках классического алгоритма НЛ на 16,5%.
Таким образом, все поставленные задачи полностью решены, а цель достигнута. В дальнейшем планируется доказать сходимость алгоритма теоретически.

Купить