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

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

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

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

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

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

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

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

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

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

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

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

   0. В каком виде традиционно задается характеристика информационной потребности пользователя?

   1. Чему соответствует х_р=0?

   2. Какой поток возникает при распределении пакетов данных в ЦСИО?

   3. На какие две компоненты распадается транзитный трафик УК r-й ступени иерархии?

   4. Каков физический смысл коэффициента ?

Лабораторная работа №8 использование нелинейного программирования для оптимизации цсио (метод штрафных функций)

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

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

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

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

минимизировать (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]. Аналогичный прием применим и для оптимизации ЦСИО с различными ме­тодами коммутации, повышения достоверности и т.п.

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

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