- •Сборник методических указаний к лабораторным работам
- •Лабораторная работа №1 оценка эффективности цсио
- •Цели и задачи самостоятельной работы:
- •Теоретические сведения.
- •Порядок выполнения работы
- •Содержание отчета
- •Контрольные вопросы:
- •Лабораторная работа №2 графовая трактовка задачи оптимизации
- •Цели и задачи самостоятельной работы:
- •2. Теоретические сведения.
- •Порядок выполнения работы
- •Содержание отчета
- •Контрольные вопросы:
- •Лабораторная работа №3 транспортная система цсио с коммутацией каналов
- •Цели и задачи самостоятельной работы:
- •Теоретические сведения.
- •Порядок выполнения работы
- •Содержание отчета
- •Контрольные вопросы:
- •Лабораторная работа №4 пакетная транспортная система
- •Цели и задачи самостоятельной работы:
- •Теоретические сведения.
- •Порядок выполнения работы
- •Содержание отчета
- •Контрольные вопросы:
- •Лабораторная работа №5 гибридная транспортная система
- •Цели и задачи самостоятельной работы:
- •Теоретические сведения.
- •Порядок выполнения работы
- •Содержание отчета
- •Контрольные вопросы:
- •Лабораторная работа №6 макромодель сети связи
- •Цели и задачи самостоятельной работы:
- •Теоретические сведения.
- •Компоненты макромодели
- •Порядок выполнения работы
- •Содержание отчета
- •Контрольные вопросы:
- •Лабораторная работа №7 модель расчета смешанных (приоритетных) потоков
- •Цели и задачи самостоятельной работы:
- •Теоретические сведения.
- •Порядок выполнения работы
- •Содержание отчета
- •Контрольные вопросы:
- •Лабораторная работа №8 использование нелинейного программирования для оптимизации цсио (метод штрафных функций)
- •Цели и задачи самостоятельной работы:
- •Теоретические сведения.
- •Порядок выполнения работы
- •Содержание отчета
- •Контрольные вопросы:
- •Лабораторная работа №9 прикладные структурно-сетевые задачи оптимизации цсио. Поиск минимально необходимых производительности и пропускной способности
- •Цели и задачи самостоятельной работы:
- •Теоретические сведения.
- •Порядок выполнения работы
- •Содержание отчета
- •Контрольные вопросы:
Порядок выполнения работы
Изучить теоретические положения;
Составить алгоритм и фрагмент программы решения задачи на языке Паскаль
Ответить на контрольные вопросы;
Оформить отчет.
Содержание отчета
Номер и название работы;
Цели и задачи работы;
Конспект теоретических сведений;
Ответы на контрольные вопросы;
Результаты и выводы.
Контрольные вопросы:
В каком виде традиционно задается характеристика информационной потребности пользователя?
Чему соответствует хр=0?
Какой поток возникает при распределении пакетов данных в ЦСИО?
На какие две компоненты распадается транзитный трафик УК r-й ступени иерархии?
Каков физический смысл коэффициента ?
Лабораторная работа №8 использование нелинейного программирования для оптимизации цсио (метод штрафных функций)
Цели и задачи самостоятельной работы:
Ознакомление с применением метода штрафных функций. Приобретение навыков использования нелинейного программирования для оптимизации ЦСИО.
Теоретические сведения.
В качестве изоморфного формального обобщения однокритериальных ССЗ, формулируемых на базе макромодели ЦСИО, используется запись задачи нелинейного программирования
минимизировать (8.1)
при ограничениях
Требуется выбрать (синтезировать) алгоритм, позволяющий в пространстве RN построить конечную последовательность точек X(j)=0,1,...,Т, которая приводит к наилучшему решению X*.
При выборе метода оптимизации принимают во внимание следующие факторы: свойства минимизируемой функции (степень гладкости, сложность вычисления целевой функции, функций-ограничений и их производных), скорость сходимости, общий объем вычислений, устойчивость метода по отношению к погрешностям, область сходимости, требуемый объем памяти.
Базовая ССЗ и ее модификации, за исключением субзадачи РП, по классификационным канонам относятся к задачам смешанного математического программирования. Целесообразно провести регуляризацию задачи, т.е. свести переменные к одному типу, например к целочисленному. Это допустимо, так как с достаточной для практики точностью поиск по переменным может вестись с шагом 0,001—0,01, а вместо пропускных способностей можно оперировать целочисленными переменными, обозначающими их тип. В этом случае наиболее выгодным становится применение методов штрафных функций (МШФ), поскольку структура ограничений, их линейность или нелинейность, гладкость или негладкость не играют принципиальной роли при решении задачи минимизации. Кроме того, МШФ не требует, чтобы начальная точка принадлежала допустимой области.
Упрощение задачи, решаемой МШФ, достигается за счет усложнения исходной целевой функции (ЦФ), которая заменяется обобщенной ЦФ F(X,h), учитывающей критерий оптимизации и все функции-ограничения:
(8.2)
где — функция вектора X, причем , если ограничения выполнены (т.е. точка находится внутри допустимой области или на ее границе), и — в противном случае; P(h) — монотонно возрастающая функция переменной h.
Использование обобщенных ЦФ делает возможным применение хорошо развитого аппарата минимизации без учета ограничений, более простого, чем методы условного минимума. Поведение F(X, h) в допустимой области совпадает с П(Х), а вне допустимой определяется штрафным членом , который быстро возрастает с удалением точки X от допустимой области. Процесс минимизации сводится к решению последовательности задач безусловной минимизации для различных значений h. Рассматривается некоторая (в общем случае неограниченная) последовательность {hk} положительных чисел. Для h1>0 отыскивается безусловный минимум функции F(X, h1), который обозначается X(h1) и используется как начальное приближение при поиске безусловного локального минимума F(X, h2), где h2>h1. Процесс повторяется для h3,h4,... Поскольку для бесконечно возрастающей последовательности локальные минимумы приближаются к допустимой области (далекие от допустимой области минимумы погашаются за счет скорости роста штрафной функции), последовательность {hk} сходится к оптимальному решению X*. Существует много разновидностей штрафных функций (ШФ). При дискретных параметрах X=(x1, x2,..., хп) рекомендуется использовать дискретную модификацию МШФ, основанную на обобщенном критерии оптимальности вида,
(8.3)
где I(Х) — непрерывная барьерная функция; — штрафные параметры; I(Xd)—дискретная барьерная функция, обладающая свойством
(8.4)
Управление в процессе оптимизации параметром r способствует “выкатыванию” точки в допустимую область без учета условия дискретности, а изменением параметра накладывают штраф за несовпадение оптимизируемой точки с узлом целочисленной решетки.
В качестве (8.4) может быть использована функция , непрерывная в точках дискретности для всех вместе со своими первыми производными:
(8.5)
где qj — преобразованная переменная Xj,
qj=(xj – zjl)/(zjv - zjl),
zjl ,zjv — все соседние дискретные точки по отношению к xj.
Максимальное значение каждого слагаемого в (8.5) равно единице. В общем случае функции (8.3) и (8.5) многоэкстремальные с двумя типами локальных оптимумов. Одни соответствуют допустимому, но не оптимальному решению, а другие — недопустимым значениям параметров. Процесс поиска сводится к решению последовательности задач безусловной минимизации для различных комбинаций параметров и rk (k — номер оптимизационного цикла). Если достигнут локальный оптимум, то значение rk увеличивают, а уменьшают. При этом наклон гиперповерхности ШФ (8.3) увеличивается и очередное решение задачи безусловной минимизации дает новую точку X. Для достижения хорошей точности результата на этом же оптимизационном цикле rk уменьшают, а увеличивают и решают очередную задачу безусловной минимизации. После проведения достаточного числа этих шагов, именуемых “процедурой огибания локальных экстремумов, не являющихся глобальными”, удается найти точку дискретной области с лучшим значением обобщенного критерия оптимальности. Указанная процедура дает хорошие результаты как на тестовых примерах, так и в практических расчетах. При неблагоприятной геометрии допустимой области число циклов не превышает шести.
Для решения непрерывных ССЗ рекомендуется применение ШФ, рассчитанных на невыпуклый случай:
(8.6)
где т0 — число ограничений; h, — параметры МШФ, h>0, ; [•]+ —функция ; — функции-ограничения, приведенные к неравенству вида .
Формула (8.6) обладает определенной инерционностью, не позволяющей алгоритму “застревать” в первом найденном локальном минимуме. Это важно, поскольку для иерархических ЦСИО не удается показать выпуклость свертки (8.6). Практика показывает, что решение задачи (8.6) достигается за число циклов, не превышающее 4, например для hk, принимающих значения 1, 102, 104, 106. Эффективность МШФ существенно зависит от класса используемых алгоритмов безусловной минимизации. Практика показывает, что ШФ (8.6) пригодна и для дискретных ССЗ. В качестве метода безусловной минимизации используется комбинация алгоритмов локального и глобального поиска, например шагового алгоритма парных проб (ШАП) [87] и метода случайного поиска с уменьшением интервала поиска (СПУИП).
Согласно ШАП, из произвольной точки Хj делается шаг по 1-й координате . Он засчитывается, если . После неудачного шага делается двойной в противоположном направлении, и он засчитывается, если . В противном случае система возвращается в исходную точку Хj и производится смещение по другим координатам. После остановки ШАП, что соответствует нахождению локального экстремума или “застреванию” системы в “овраге”, производится уменьшение шага поиска Х. По достижении минимального значения шага поиска Х= 1 производится передача управления СПУИП.
В рекуррентной форме СПУИП записывается следующим образом:
(8.7)
где — единичный случайный вектор, равномерно распределенный по всем направлениям пространства оптимизируемых параметров.
Согласно (8.7), шаг в случайном направлении считается неудачным, если значение F(Xj) не уменьшается. В противном случае система смещается в точку Хj и управление передается ШАП. По достижении заданного объема выборки производится уменьшение параметра Х, что соответствует уменьшению области поиска, т.е. происходит локализация экстремума.
Таким образом, ШАП непосредственно осуществляет поиск локального минимума, а СПУИП — “выпрыгивание” из точки локального минимума в зону притяжения другого минимума.
Для решения ССЗ в непрерывной постановке используется метод сопряженных градиентов Флетчера—Ривса, близкий по скорости сходимости к ньютоновским методам, но не требующий вычислений вторых производных.
Сравнение поисковых характеристик методов безусловной минимизации на дискретной ЗОС показало, что метод Флетчера—Ривса быстрее заканчивает оптимизацию по сравнению с комбинированным методом. Однако необходимость дискретизации полученных решений и вносимая при этом погрешность являются недостатками подобного способа минимизации.
Решение ССЗ в многокритериальной постановке на макромодели может быть доведено до получения наиболее характерных точек множества Парето либо участка этой зависимости, либо единственного решения.
Исходя из предпосылок подхода “эффективность—стоимость”, число критериев векторной задачи может быть снижено до одного-двух—приведенных затрат П(Х) и одного из показателей качества обслуживания пользователей ЦСИО, например средней сквозной задержки пакета данных, при одновременном переводе остальных показателей в разряд ограничений. Решение двухкритериальной задачи в настоящее время не является проблемным и сводится к последовательности скалярных задач минимизации П(Х) для различных численных значений i-гo ограничения [90]. Аналогичный прием применим и для оптимизации ЦСИО с различными методами коммутации, повышения достоверности и т.п.
Для получения единственного глобально оптимального решения достаточно эффективной оказывается модель справедливого компромисса, основанная на мультипликативной свертке частных критериев. Предполагается, что все они являются минимизируемыми (максимизируемыми).
Для графической интерпретации результатов решения многокритериальных задач используются графы Кивиата.