ИСПОЛЬЗОВАНИЕ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМИЗАЦИИ ЦСИО (МЕТОД ШТРАФНЫХ ФУНКЦИЙ)

1. Цели и задачи самостоятельной работы:

Ознакомление с применением метода штрафных функций. Приобретение навыков использования нелинейного программирования для оптимизации ЦСИО.

1. Теоретические сведения.

В качестве изоморфного формального обобщения однокритериальных ССЗ, формулируемых на базе макромодели ЦСИО, используется запись задачи нелинейного программи­рования

минимизировать (8.1)

при ограничениях

Требуется выбрать (синтезировать) алгоритм, позволяю­щий в пространстве R^N построить конечную последователь­ность точек X^(j)=0,1,...,Т, которая приводит к наилучшему решению X*.

При выборе метода оптимизации принимают во внимание следующие факторы: свойства минимизируемой функции (степень гладкости, сложность вычисления целевой функции, функций-ограничений и их производных), скорость сходимос­ти, общий объем вычислений, устойчивость метода по отно­шению к погрешностям, область сходимости, требуемый объем памяти.

Базовая ССЗ и ее модификации, за исключением субза­дачи РП, по классификационным канонам относятся к зада­чам смешанного математического программирования. Целесообразно провести регуляризацию задачи, т.е. свести переменные к одному типу, например к целочисленному. Это допустимо, так как с достаточной для практики точностью поиск по переменным может вестись с шагом 0,001—0,01, а вместо пропускных способностей можно оперировать цело­численными переменными, обозначающими их тип. В этом случае наиболее выгодным становится применение методов штрафных функций (МШФ), поскольку структура ограниче­ний, их линейность или нелинейность, гладкость или неглад­кость не играют принципиальной роли при решении задачи минимизации. Кроме того, МШФ не требует, чтобы началь­ная точка принадлежала допустимой области.

Упрощение задачи, решаемой МШФ, достигается за счет усложнения исходной целевой функции (ЦФ), которая заме­няется обобщенной ЦФ F(X,h), учитывающей критерий оптимизации и все функции-ограничения:

(8.2)

где — функция вектора X, причем ,если огра­ничения выполнены (т.е. точка находится внутри допустимой области или на ее границе), и — в противном слу­чае; P(h) — монотонно возрастающая функция переменной h.

Использование обобщенных ЦФ делает возможным применение хорошо развитого аппарата минимизации без учета ограничений, более простого, чем методы условного минимума. Поведение F(X, h) в допустимой области совпадает с П(Х), а вне допустимой определяется штрафным членом , который быстро возрастает с удалением точки X от допустимой области. Процесс минимизации сводится к ре­шению последовательности задач безусловной минимизации для различных значений h. Рассматривается некоторая (в об­щем случае неограниченная) последовательность {h_k} поло­жительных чисел. Для h₁>0 отыскивается безусловный ми­нимум функции F(X, h₁), который обозначается X(h₁) и ис­пользуется как начальное приближение при поиске безуслов­ного локального минимума F(X, h₂), где h₂>h₁. Процесс повторяется для h₃,h₄,... Поскольку для бесконечно возрас­тающей последовательности локальные минимумы приближа­ются к допустимой области (далекие от допустимой области минимумы погашаются за счет скорости роста штрафной функции), последовательность {h_k} сходится к оптимальному решению X*. Существует много разновидностей штрафных функций (ШФ). При дискретных параметрах X=(x₁, x₂,..., х_п) рекомендуется использовать дискретную модификацию МШФ, основанную на обобщенном критерии оптимальности вида,

(8.3)

где I(Х) — непрерывная барьерная функция; — штраф­ные параметры; I(X^d)—дискретная барьерная функция, об­ладающая свойством

(8.4)

Управление в процессе оптимизации параметром r спо­собствует “выкатыванию” точки в допустимую область без учета условия дискретности, а изменением параметра на­кладывают штраф за несовпадение оптимизируемой точки с узлом целочисленной решетки.

В качестве (8.4) может быть использована функция , непрерывная в точках дискретности для всех вместе со своими первыми производными:

(8.5)

где q_j — преобразованная переменная X_j,

q_j=(x_j – z_jl)/(z_jv - z_jl),

z_jl ,z_jv — все соседние дискретные точки по отношению к x_j.

Максимальное значение каждого слагаемого в (8.5) рав­но единице. В общем случае функции (8.3) и (8.5) много­экстремальные с двумя типами локальных оптимумов. Одни соответствуют допустимому, но не оптимальному решению, а другие — недопустимым значениям параметров. Процесс поиска сводится к решению последовательности задач без­условной минимизации для различных комбинаций парамет­ров и r_k (k — номер оптимизационного цикла). Если до­стигнут локальный оптимум, то значение r_k увеличивают, а уменьшают. При этом наклон гиперповерхности ШФ (8.3) увеличивается и очередное решение задачи безусловной ми­нимизации дает новую точку X. Для достижения хорошей точности результата на этом же оптимизационном цикле r_k уменьшают, а увеличивают и решают очередную задачу безусловной минимизации. После проведения достаточного числа этих шагов, именуемых “процедурой огибания локаль­ных экстремумов, не являющихся глобальными”, удается найти точку дискретной области с лучшим значением обоб­щенного критерия оптимальности. Указанная процедура дает хорошие результаты как на тестовых примерах, так и в прак­тических расчетах. При неблагоприятной геометрии допусти­мой области число циклов не превышает шести.

Для решения непрерывных ССЗ рекомендуется примене­ние ШФ, рассчитанных на невыпуклый случай:

(8.6)

где т₀ — число ограничений; h, — параметры МШФ, h>0, ; [•]⁺ —функция ; — функции-ограничения, приведенные к неравенству вида .

Формула (8.6) обладает определенной инерционностью, не позволяющей алгоритму “застревать” в первом найденном локальном минимуме. Это важно, поскольку для иерархиче­ских ЦСИО не удается показать выпуклость свертки (8.6). Практика показывает, что решение задачи (8.6) достигается за число циклов, не превышающее 4, например для h_k, при­нимающих значения 1, 10², 10⁴, 10⁶. Эффективность МШФ существенно зависит от класса используемых алгоритмов безусловной минимизации. Практика показывает, что ШФ (8.6) пригодна и для дискретных ССЗ. В качестве метода безусловной минимизации используется комбинация алгорит­мов локального и глобального поиска, например шагового алгоритма парных проб (ШАП) [87] и метода случайного поиска с уменьшением интервала поиска (СПУИП).

Согласно ШАП, из произвольной точки Х^j делается шаг по 1-й координате . Он засчитывается, если . После неудачного шага делается двойной в противоположном направлении, и он засчитывается, если .В противном случае система возвращается в исходную точку Х^j и производится смещение по другим ко­ординатам. После остановки ШАП, что соответствует нахож­дению локального экстремума или “застреванию” системы в “овраге”, производится уменьшение шага поиска Х. По достижении минимального значения шага поиска Х= 1 про­изводится передача управления СПУИП.

В рекуррентной форме СПУИП записывается следующим образом:

(8.7)

где — единичный случайный вектор, равномер­но распределенный по всем направлениям пространства оптимизируемых параметров.

Согласно (8.7), шаг в случайном направлении счита­ется неудачным, если значение F(X^j) не уменьшается. В про­тивном случае система смещается в точку Х^j и управление передается ШАП. По достижении заданного объема выборки производится уменьшение параметра Х, что соответствует уменьшению области поиска, т.е. происходит локализация экстремума.

Таким образом, ШАП непосредственно осуществляет поиск локального минимума, а СПУИП — “выпрыгивание” из точ­ки локального минимума в зону притяжения другого мини­мума.

Для решения ССЗ в непрерывной постановке используется метод сопряженных градиентов Флетчера—Ривса, близ­кий по скорости сходимости к ньютоновским методам, но не требующий вычислений вторых производных.

Сравнение поисковых характеристик методов безусловной минимизации на дискретной ЗОС показало, что метод Флет­чера—Ривса быстрее заканчивает оптимизацию по сравнению с комбинированным методом. Однако необходимость дискре­тизации полученных решений и вносимая при этом погреш­ность являются недостатками подобного способа миними­зации.

Решение ССЗ в многокритериальной постановке на макро­модели может быть доведено до получения наиболее харак­терных точек множества Парето либо участка этой зависи­мости, либо единственного решения.

Исходя из предпосылок подхода “эффективность—стои­мость”, число критериев векторной задачи может быть сни­жено до одного-двух—приведенных затрат П(Х) и одного из показателей качества обслуживания пользователей ЦСИО, например средней сквозной задержки пакета данных, при одновременном переводе остальных показателей в разряд ограничений. Решение двухкритериальной задачи в настоя­щее время не является проблемным и сводится к последова­тельности скалярных задач минимизации П(Х) для различ­ных численных значений i-гo ограничения [90]. Аналогичный прием применим и для оптимизации ЦСИО с различными ме­тодами коммутации, повышения достоверности и т.п.

Для получения единственного глобально оптимального ре­шения достаточно эффективной оказывается модель справед­ливого компромисса, основанная на мультипликативной свертке частных критериев. Предполагается, что все они яв­ляются минимизируемыми (максимизируемыми).

Для графической интерпретации результатов решения мно­гокритериальных задач используются графы Кивиата.

1. Порядок выполнения работы

Изучить теоретические положения;

Составить алгоритм и фрагмент программы решения задачи на языке Паскаль

Ответить на контрольные вопросы;

Оформить отчет.

1. Содержание отчета

Номер и название работы;

Цели и задачи работы;

Конспект теоретических сведений;

Ответы на контрольные вопросы;

Результаты и выводы.

1. Контрольные вопросы:

Что используется в качестве изоморфного формального обобщения однокритериальных ССЗ, формулируемых на базе макромодели ЦСИО?

Какие факторы принимают во внимание при выборе метода оптимизации?

Что значит провести регуляризацию задачи?

За счет чего достигается упрощение задачи, решаемой МШФ?

Какие штрафные функции рекомендуют применять для решения непрерывных ССЗ?