ОПТИМИЗАЦИЯ ПАРАМЕТРОВ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ НА ОСНОВЕ КОМБИНИРОВАННОГО ИСПОЛЬЗОВАНИЯ АНАЛИТИЧЕСКИХ И ИМИТАЦИОННЫХ МОДЕЛЕЙ
61
УДК 519.248
С. В. КОКОРИН, Ю. И. РЫЖИКОВ
ОПТИМИЗАЦИЯ ПАРАМЕТРОВ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ НА ОСНОВЕ КОМБИНИРОВАННОГО ИСПОЛЬЗОВАНИЯ АНАЛИТИЧЕСКИХ И ИМИТАЦИОННЫХ МОДЕЛЕЙ
Рассматриваются методы оптимизации параметров сетей массового обслуживания, задаваемых с использованием как аналитических, так и имитационных моделей. Ключевые слова: имитационная модель, аналитическая модель, теория очередей, численная оптимизация с ограничениями, однородные системы и сети массового обслуживания.
Введение. Задача поиска оптимальных вероятностно-временных характеристик современных информационных систем (ИС) является весьма актуальной. ИС представляют собой сложные объекты, подверженные структурной динамике, поэтому для их моделирования необходимо создание совокупности моделей с различной степенью детализации.
Исследования показывают, что вопрос об оптимальном выборе характеристик ИС остается, как правило, за рамками постановки и решения классических задач анализа систем и сетей массового обслуживания (СМО) либо рассматривается применительно к простым моделям теории очередей, для которых существует аналитическое решение задач оптимизации, т.е. при экспоненциальном распределении времени обслуживания и интервалов между поступлениями заявок [1].
В настоящей статье предлагается использовать аналитические и имитационные модели (АМ, ИМ) теории очередей для ИС, описывающих рассматриваемую предметную область. По сравнению с существующими подходами исследуем более широкий класс моделей теории
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11
62 С. В. Кокорин, Ю. И. Рыжиков
очередей, допускающих произвольное распределение времени обслуживания в узлах сети в рамках задачи поиска ее оптимальных параметров.
Постановка задачи. Рассмотрим открытую однородную СМО, которая задается набо-
( )ром параметров a,n,{bi}iM=1, R , где a = (a1,…, am )T — первые m начальных моментов рас-
пределения интервалов между появлением заявок в источнике (выбираются в зависимости от
требуемой точности решения задачи); n = (n1,…, nM )T — количество каналов в каждом из M
узлов сети; bi = (bi1,…,bim )T — первые m начальных моментов распределения времени об-
служивания заявок, задаваемых независимо для каждого узла сети;
R=
rij
i, j=M +1 i, j=0
— матрица
стационарных вероятностей переходов между узлами сети. При рассмотрении СМО под нулевым узлом будем понимать источник заявок, а под узлом с индексом М+1 — сток сети. Два данных узла не являются частью сети и вводятся лишь для удобства обозначений. Представ-
ляющими интерес параметрами сети являются: ν =(ν1,…, νm )T — моменты распределения
времени пребывания заявок в сети и ρ =(ρ1,…,ρM )T — коэффициент загрузки для каждого
узла сети. Исследуем влияние структуры однородной сети на ее пропускную способность. В дан-
ном случае оптимизируемыми параметрами являются элементы матрицы R. В качестве целевых функций (ЦФ) выберем две, позволяющие количественно оценить такие аспекты, как эффективность и отказоустойчивость исследуемой СМО соответственно:
J1
=
ν1
(R)
→
min
R∈Ω
,
где Ω — множество допустимых значений элементов матрицы R;
∑ ∑J2
=
ρ(R)
= 1/
M
M
ρi2
i=1
(R)
−1/
M
2
⎛ ⎝⎜⎜
M
ρi
i=1
(
R
)
⎞2 ⎠⎟⎟
→
min
R∈Ω
.
ЦФ J1 можно интерпретировать как среднее время прохождения заявки через СМО, a
ЦФ J2 — как показатель равномерности распределения нагрузки между узлами сети.
M +1
Множество Ω содержит естественные ограничения: ∑ rij = 1 ∀i ∈{0,…, M + 1} [2]. j=0
В общем случае предполагается, что далеко не все узлы СМО связаны друг с другом, поэтому
для многих элементов матрицы R существует ограничение вида rij = 0. Предполагается так-
1
Источник
2
3
47 5 Сток
68
же, что имеется возможность выбирать не все элементы матрицы R. Модель сети с подобными ограничениями приведена на рисунке, где элементы матрицы R, которые могут принимать ненулевое значение, обозначены стрелками.
В дополнение к сказанному необходимо отметить, что можно задавать ограничения на элементы матрицы R следующим образом:
f ′(R) = I (R ∈ Ω′) f (R),
где f ( R) — некоторая целевая функция, I ( R) — индикатор принадлежности матрицы R
множеству Ω′ , которое задается произвольным образом и является подмножеством Ω .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11
Оптимизация параметров сетей массового обслуживания
63
Кроме того, примем, что:
— a ≤ rij ≤ A , где (a, A) — произвольные константы; при этом проверка согласован-
ности ограничений для различных rij не проводится; в случае когда данные ограничения не
выполняются, то с использованием предлагаемого в статье метода решение не может быть
найдено;
— b ≤ ρi ( R) ≤ B , где (b, B) — произвольные константы.
Введение перечисленных ограничений позволяет учесть факторы износа оборудования,
а также специфику различных транспортных путей между узлами, что в целом обеспечивает
возможность моделирования реальных ИС с учетом особенностей их функционирования.
Расчет характеристик сети. Известно, что в общем случае [2] численный расчет па-
раметров открытой СМО с учетом преобразования потоков заявок включает в себя сле-
дующие шаги.
Шаг 1. Аппроксимация входных данных по методу моментов с помощью экспоненциаль-
ного либо гиперэкспоненциального распределения в зависимости от особенностей модели.
Шаг 2. Задание начальных значений λi для потоков поступающих заявок. Данные потоки принимаются простейшими с интенсивностью, определяемой при решении системы
уравнений, описывающих условие баланса потоков:
M
∑λi = Λr0i + λ j rij , i = 1,…, M , j=1
где Λ — суммарная интенсивность потока заявок, поступающих от внешних источников.
Шаг 3. Проверка отсутствия перегрузки во всех узла сети: λibi1 / n (i) < 1. Коэффициен-
ты немарковости [2] входящих потоков для каждого узла на первой итерации полагаются рав-
ными ξ(i0) = 0, i = 1,…, M . Шаг 4. Решение поочередно для всех узлов следующих подзадач:
— оценка распределений временных интервалов между поступлением заявок в i-й узел
со всех узлов сети;
— суммирование полученных оценок распределений;
{ }— расчет новых коэффициентов немарковости
ξ(i k )
M
,
i=1
определение
невязки
∆(i k ) = ξ(i k ) − ξ(i k−1) для текущей итерации k;
— расчет узла как изолированной системы массового обслуживания;
— расчет оценки распределений интервалов потока заявок, выходящего из i-го узла;
Шаг
5.
Если
max
i∈{1,…,M
}
∆i
>
ε,
где
ε
—
заданный
порог
невязки,
возвращение
к
шагу 4.
Шаг 6. Расчет моментов распределения времени пребывания заявки в узлах при каждом
посещении.
Шаг 7. Расчет моментов распределения времени пребывания заявки в сети в целом.
Оценки характеристик рассматриваемого класса СМО также можно получить с помо-
щью имитационных моделей, однако в этом случае вычислительные затраты, связанные с по-
лучением окончательных решений, значительно возрастают по сравнению с подходом, ис-
пользующим аналитические модели.
Методы оптимизации параметров СМО. Для вычисления и оптимизации целевых
функций J1, J2 предлагается использовать метод глобального поиска — метод пси-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11
64 С. В. Кокорин, Ю. И. Рыжиков
преобразования [3] — и метод численной оптимизации без вычисления производных — метод главных осей Брента [4].
Метод пси-преобразования является методом поиска глобального экстремума целевой функции и не критичен к выбору начальной оценки. Однако для его реализации требуются значительные вычислительные ресурсы в том случае, если увеличивается размерность пространства оптимизируемых параметров. Для ЦФ J1 в качестве пси-функции была выбрана вероятностная мера множества точек, на котором пропускная способность сети выше заданного уровня, а для ЦФ J2 — вероятностная мера множества точек, на котором величина
ρ( R) меньше заданного положительного значения. В этом случае задача оптимизации пара-
метров СМО сводится к поиску решения уравнения с многими переменными (оптимизируемыми параметрами).
Рассмотрим алгоритм, реализующий метод пси-преобразования [3]. Шаг 1. Оценка разброса значений целевой функции методом случайных испытаний.
Шаг 2. Выбор множества значений уровней ν1 ( R) ≥ ζl , l ∈{1,…, L}, где L — заданное
количество уровней, а ζl — величины, определяемые по оценкам разброса целевой функции, полученным на шаге 1.
Шаг 3. Вычисление средних значений целевой функции для каждого уровня методом случайных испытаний:
Ψl = 1/ q ∑ (ν1 ( R(s) ) − ζl ), { }R(s):ν1(R(s) )≥ζl
где q — число испытаний, R(s) — матрица переходов при s-м испытании и l ∈{1,…, L}.
Шаг 4. Вычисление средних значений параметров элементов матрицы R для каждого уровня:
∑ ( )xijl = q / Ψl
( )ri(js) ν1 R(s) − ζl α ,
{ }R(s):ν1(R(s) )≥ζl
где α = [1; ∞] — параметр метода оптимизации.
Шаг 5. Параболическая аппроксимация и экстраполяция величин Ψl на уровень 0. Вследствие высокой вычислительной сложности метода пси-преобразования и его недостаточной точности при оптимизации ЦФ J1 и J2 при большой размерности СМО предлагается использовать метод главных осей Брента. Данный метод ориентирован на локальную оптимизацию функции многих переменных без вычисления производных. На практике метод эффективен при решении задач оптимизации структуры СМО, в том числе, и для случая, когда пространство параметров имеет большую размерность. Основным недостатком алгоритма, реализующего данный метод, является необходимость задания начальной оценки, которая должна быть вычислена отдельно для каждой конкретной задачи. Кроме того, необходимо задать два параметра — δ и ∆z : параметр δ определяет момент останова итерацион-
ного процесса, ∆z — максимальную длину шага алгоритма. Приведем шаги алгоритма, реализующего метод главных осей для вычисления целевых
функций J1 и J2 .
Шаг 1. Вычисление начальной оценки маирицы R(0) .
Шаг 2. Задание начальных направлений одномерного поиска: U 0 = (ui )(0) M (M +2) = I, i=1
где I — единичная матрица.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11
Оптимизация параметров сетей массового обслуживания
65
Шаг 3. Поиск оптимального значения ЦФ поочередно вдоль каждого направления методом золотого сечения с начальным интервалом 2∆z. Перенос текущих значений оптимальных параметров во вновь найденную точку, которую обозначим как R(k) .
Шаг 4. Вычисление величины ∆z = 2 ⋅ R(k ) − R(k−1) .
Шаг
5.
Исключение
вектора
uM(k
−1) (M
+2)
,
переход
к
матрице
направлений
следующего
ви-
( )да: U k =
R( k )
−
R( k −1) ,
u1( k
−1)
,
u2(k−1) ,…,
uM( k
−1) (M
+2)−1
.
Шаг 6. После полной смены направляющего набора векторов U M (M+2) обновление на-
бора полностью с замещением его ортогональной матрицей, аппроксимирующей гессиан целевой функции в текущей точке.
Шаг 7. Повтор шагов 3—6 до тех пор, пока абсолютная разность значений ЦФ на последовательных итерациях не станет меньше δ .
Выбор начальной оценки при реализации метода главных осей предлагается осуществлять с использованием модели сети Джексона [4], для которой существует аналитическое решение поставленной задачи.
Многоканальные узлы замещаются одноканальными с пропорционально увеличенной
интенсивностью времени обслуживания µ′ = 1/ bin (i). Экспоненциальное распределение вре-
мени обслуживания в каждом узле аппроксимируется с учетом первых моментов заданных распределений. Последовательный обход сети в ширину позволяет выбрать начальные оценки для каждого узла на основе решения следующей оптимизационной задачи:
∑M +1
j=1 µ′j
rij − rij λ j
→ min .
R∈Ω
Использование данного метода выбора начальных оценок эффективно (в вычислительном отношении) при небольшом числе каналов в узлах и малых значениях коэффициентов вариации времени обслуживания в узлах. В качестве альтернативы используется метод псипреобразования. Его реализация предпочтительнее для сетей, в которых закон распределения времени обслуживания значительно отличается от экспоненциального (например, равномерный закон распределения на отрезке или гамма-распределение с высокой вариацией.).
Сравнительный анализ начальных оценок матрицы R, полученных методом построения
сети Джексона и методом пси-преобразования для расчета оптимального значения ЦФ J1 , представлен в таблице, где K — количество итераций.
М
Метод Джексона
ν1(R)
K
Метод пси-преобразования
ν1(R)
K
J1
3 2,91
319 2,91
651 2,18
5 3,35
895 3,57
1293
3,19
8 4,9
6067
4,83
5419
4,53
13 7,02
21939
7,92
41345
6,57
21
9,05 212939
8,84
201323
8,64
Численные эксперименты. Для сравнения результатов, полученных с использованием аналитических и имитационных моделей СМО, рассмотрим простую сеть, состоящую из 8 узлов, расположенных в трех ярусах (см. рисунок). При варьировании элементов, входящих в матрицу R вероятностей переходов между узлами, можно получить одинаковые результаты как на АМ, так и на ИМ. По сравнению с численной оптимизацией на АМ процедура поиска параметров на ИМ отличается плохой сходимостью соответствующего локального метода, которая определяется тем, что при имитации целевые функции принимают случайные значения.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11
66 С. В. Кокорин, Ю. И. Рыжиков
Для уменьшения влияния данного фактора требуется увеличить число имитационных экспериментов, при этом высокая точность требуется только на последних шагах метода при малых значениях ∆z . Поэтому для повышения эффективности вычислений ЦФ на ИМ был реализован расчет с использованием метода Брента, при котором точность расчета целевой функции зависит от длины шага как q0 / ∆z.
Выводы. В задачах оптимизации характеристик СМО вопросы повышения эффективности соответствующих вычислительных процедур, связанных с расчетом ЦФ, приобретают особую актуальность. При этом использование ИМ в данных задачах требует значительного количества информационных и временных ресурсов. Кроме того, такое моделирование характеризуется невысокой точностью расчета экстремальных значений ЦФ вследствие статистических погрешностей имитации. Поэтому в данной ситуации целесообразен поиск аналогичных параметров СМО с использованием АМ, что обусловлено значительно меньшими затратами информационных ресурсов, сокращением общего времени на проведение соответствующих расчетов ЦФ, а сами значения рассматриваемых функций вычисляются с меньшими погрешностями.
Предложенный в настоящей статье оригинальный подход к разработке и реализации методов оптимизации параметров различных типов сетей массового обслуживания основан на комбинированном использовании методов глобальной и локальной оптимизации, при этом недостатки метода, базирующегося на имитационной модели, компенсируются достоинствами аналитического метода.
Исследования по данной тематике проводились при поддержке Российского фонда фундаментальных исследований (гранты 10-07-00311, 09-07-00066a, 09-07-11004, 08-0800346-a, 10-08-0906-a, 10-08-90027-Бел-а) и Отделения нанотехнологий и информационных технологий РАН (проект № О-2.3/03).
СПИСОК ЛИТЕРАТУРЫ
1. Bramson М. Stability of Queuing Networks [Электронный ресурс]: .
2. Рыжиков Ю. И. Машинные методы расчета систем массового обслуживания. Л.: ВИКИ им А. Ф. Можайского, 1979.
3. Чичинадзе В. К. Решение невыпуклых нелинейных задач оптимизации. Метод пси-преобразования. М.: Наука, 1983.
4. Brent R. P. Algorithms for Minimization without Derivatives. NJ: Prentice-Hall, Inc., 1973.
5. Охтилев М. Ю., Соколов Б. В., Юсупов Р. М. Интеллектуальные информационные технологии мониторинга и управления структурной динамикой сложных технических объектов. М.: Наука, 2006.
Сергей Владимирович Кокорин Юрий Иванович Рыжиков
Сведения об авторах — аспирант; СПИИРАН, лаборатория информационных технологий в
системном анализе и моделировании; E-mail: kokorins@rambler.ru — д-р техн. наук, профессор; СПИИРАН, лаборатория информационных
технологий в системном анализе и моделировании; E-mail: ryzhbox@yandex.ru
Рекомендована СПИИРАН
Поступила в редакцию 09.07.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11
УДК 519.248
С. В. КОКОРИН, Ю. И. РЫЖИКОВ
ОПТИМИЗАЦИЯ ПАРАМЕТРОВ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ НА ОСНОВЕ КОМБИНИРОВАННОГО ИСПОЛЬЗОВАНИЯ АНАЛИТИЧЕСКИХ И ИМИТАЦИОННЫХ МОДЕЛЕЙ
Рассматриваются методы оптимизации параметров сетей массового обслуживания, задаваемых с использованием как аналитических, так и имитационных моделей. Ключевые слова: имитационная модель, аналитическая модель, теория очередей, численная оптимизация с ограничениями, однородные системы и сети массового обслуживания.
Введение. Задача поиска оптимальных вероятностно-временных характеристик современных информационных систем (ИС) является весьма актуальной. ИС представляют собой сложные объекты, подверженные структурной динамике, поэтому для их моделирования необходимо создание совокупности моделей с различной степенью детализации.
Исследования показывают, что вопрос об оптимальном выборе характеристик ИС остается, как правило, за рамками постановки и решения классических задач анализа систем и сетей массового обслуживания (СМО) либо рассматривается применительно к простым моделям теории очередей, для которых существует аналитическое решение задач оптимизации, т.е. при экспоненциальном распределении времени обслуживания и интервалов между поступлениями заявок [1].
В настоящей статье предлагается использовать аналитические и имитационные модели (АМ, ИМ) теории очередей для ИС, описывающих рассматриваемую предметную область. По сравнению с существующими подходами исследуем более широкий класс моделей теории
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11
62 С. В. Кокорин, Ю. И. Рыжиков
очередей, допускающих произвольное распределение времени обслуживания в узлах сети в рамках задачи поиска ее оптимальных параметров.
Постановка задачи. Рассмотрим открытую однородную СМО, которая задается набо-
( )ром параметров a,n,{bi}iM=1, R , где a = (a1,…, am )T — первые m начальных моментов рас-
пределения интервалов между появлением заявок в источнике (выбираются в зависимости от
требуемой точности решения задачи); n = (n1,…, nM )T — количество каналов в каждом из M
узлов сети; bi = (bi1,…,bim )T — первые m начальных моментов распределения времени об-
служивания заявок, задаваемых независимо для каждого узла сети;
R=
rij
i, j=M +1 i, j=0
— матрица
стационарных вероятностей переходов между узлами сети. При рассмотрении СМО под нулевым узлом будем понимать источник заявок, а под узлом с индексом М+1 — сток сети. Два данных узла не являются частью сети и вводятся лишь для удобства обозначений. Представ-
ляющими интерес параметрами сети являются: ν =(ν1,…, νm )T — моменты распределения
времени пребывания заявок в сети и ρ =(ρ1,…,ρM )T — коэффициент загрузки для каждого
узла сети. Исследуем влияние структуры однородной сети на ее пропускную способность. В дан-
ном случае оптимизируемыми параметрами являются элементы матрицы R. В качестве целевых функций (ЦФ) выберем две, позволяющие количественно оценить такие аспекты, как эффективность и отказоустойчивость исследуемой СМО соответственно:
J1
=
ν1
(R)
→
min
R∈Ω
,
где Ω — множество допустимых значений элементов матрицы R;
∑ ∑J2
=
ρ(R)
= 1/
M
M
ρi2
i=1
(R)
−1/
M
2
⎛ ⎝⎜⎜
M
ρi
i=1
(
R
)
⎞2 ⎠⎟⎟
→
min
R∈Ω
.
ЦФ J1 можно интерпретировать как среднее время прохождения заявки через СМО, a
ЦФ J2 — как показатель равномерности распределения нагрузки между узлами сети.
M +1
Множество Ω содержит естественные ограничения: ∑ rij = 1 ∀i ∈{0,…, M + 1} [2]. j=0
В общем случае предполагается, что далеко не все узлы СМО связаны друг с другом, поэтому
для многих элементов матрицы R существует ограничение вида rij = 0. Предполагается так-
1
Источник
2
3
47 5 Сток
68
же, что имеется возможность выбирать не все элементы матрицы R. Модель сети с подобными ограничениями приведена на рисунке, где элементы матрицы R, которые могут принимать ненулевое значение, обозначены стрелками.
В дополнение к сказанному необходимо отметить, что можно задавать ограничения на элементы матрицы R следующим образом:
f ′(R) = I (R ∈ Ω′) f (R),
где f ( R) — некоторая целевая функция, I ( R) — индикатор принадлежности матрицы R
множеству Ω′ , которое задается произвольным образом и является подмножеством Ω .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11
Оптимизация параметров сетей массового обслуживания
63
Кроме того, примем, что:
— a ≤ rij ≤ A , где (a, A) — произвольные константы; при этом проверка согласован-
ности ограничений для различных rij не проводится; в случае когда данные ограничения не
выполняются, то с использованием предлагаемого в статье метода решение не может быть
найдено;
— b ≤ ρi ( R) ≤ B , где (b, B) — произвольные константы.
Введение перечисленных ограничений позволяет учесть факторы износа оборудования,
а также специфику различных транспортных путей между узлами, что в целом обеспечивает
возможность моделирования реальных ИС с учетом особенностей их функционирования.
Расчет характеристик сети. Известно, что в общем случае [2] численный расчет па-
раметров открытой СМО с учетом преобразования потоков заявок включает в себя сле-
дующие шаги.
Шаг 1. Аппроксимация входных данных по методу моментов с помощью экспоненциаль-
ного либо гиперэкспоненциального распределения в зависимости от особенностей модели.
Шаг 2. Задание начальных значений λi для потоков поступающих заявок. Данные потоки принимаются простейшими с интенсивностью, определяемой при решении системы
уравнений, описывающих условие баланса потоков:
M
∑λi = Λr0i + λ j rij , i = 1,…, M , j=1
где Λ — суммарная интенсивность потока заявок, поступающих от внешних источников.
Шаг 3. Проверка отсутствия перегрузки во всех узла сети: λibi1 / n (i) < 1. Коэффициен-
ты немарковости [2] входящих потоков для каждого узла на первой итерации полагаются рав-
ными ξ(i0) = 0, i = 1,…, M . Шаг 4. Решение поочередно для всех узлов следующих подзадач:
— оценка распределений временных интервалов между поступлением заявок в i-й узел
со всех узлов сети;
— суммирование полученных оценок распределений;
{ }— расчет новых коэффициентов немарковости
ξ(i k )
M
,
i=1
определение
невязки
∆(i k ) = ξ(i k ) − ξ(i k−1) для текущей итерации k;
— расчет узла как изолированной системы массового обслуживания;
— расчет оценки распределений интервалов потока заявок, выходящего из i-го узла;
Шаг
5.
Если
max
i∈{1,…,M
}
∆i
>
ε,
где
ε
—
заданный
порог
невязки,
возвращение
к
шагу 4.
Шаг 6. Расчет моментов распределения времени пребывания заявки в узлах при каждом
посещении.
Шаг 7. Расчет моментов распределения времени пребывания заявки в сети в целом.
Оценки характеристик рассматриваемого класса СМО также можно получить с помо-
щью имитационных моделей, однако в этом случае вычислительные затраты, связанные с по-
лучением окончательных решений, значительно возрастают по сравнению с подходом, ис-
пользующим аналитические модели.
Методы оптимизации параметров СМО. Для вычисления и оптимизации целевых
функций J1, J2 предлагается использовать метод глобального поиска — метод пси-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11
64 С. В. Кокорин, Ю. И. Рыжиков
преобразования [3] — и метод численной оптимизации без вычисления производных — метод главных осей Брента [4].
Метод пси-преобразования является методом поиска глобального экстремума целевой функции и не критичен к выбору начальной оценки. Однако для его реализации требуются значительные вычислительные ресурсы в том случае, если увеличивается размерность пространства оптимизируемых параметров. Для ЦФ J1 в качестве пси-функции была выбрана вероятностная мера множества точек, на котором пропускная способность сети выше заданного уровня, а для ЦФ J2 — вероятностная мера множества точек, на котором величина
ρ( R) меньше заданного положительного значения. В этом случае задача оптимизации пара-
метров СМО сводится к поиску решения уравнения с многими переменными (оптимизируемыми параметрами).
Рассмотрим алгоритм, реализующий метод пси-преобразования [3]. Шаг 1. Оценка разброса значений целевой функции методом случайных испытаний.
Шаг 2. Выбор множества значений уровней ν1 ( R) ≥ ζl , l ∈{1,…, L}, где L — заданное
количество уровней, а ζl — величины, определяемые по оценкам разброса целевой функции, полученным на шаге 1.
Шаг 3. Вычисление средних значений целевой функции для каждого уровня методом случайных испытаний:
Ψl = 1/ q ∑ (ν1 ( R(s) ) − ζl ), { }R(s):ν1(R(s) )≥ζl
где q — число испытаний, R(s) — матрица переходов при s-м испытании и l ∈{1,…, L}.
Шаг 4. Вычисление средних значений параметров элементов матрицы R для каждого уровня:
∑ ( )xijl = q / Ψl
( )ri(js) ν1 R(s) − ζl α ,
{ }R(s):ν1(R(s) )≥ζl
где α = [1; ∞] — параметр метода оптимизации.
Шаг 5. Параболическая аппроксимация и экстраполяция величин Ψl на уровень 0. Вследствие высокой вычислительной сложности метода пси-преобразования и его недостаточной точности при оптимизации ЦФ J1 и J2 при большой размерности СМО предлагается использовать метод главных осей Брента. Данный метод ориентирован на локальную оптимизацию функции многих переменных без вычисления производных. На практике метод эффективен при решении задач оптимизации структуры СМО, в том числе, и для случая, когда пространство параметров имеет большую размерность. Основным недостатком алгоритма, реализующего данный метод, является необходимость задания начальной оценки, которая должна быть вычислена отдельно для каждой конкретной задачи. Кроме того, необходимо задать два параметра — δ и ∆z : параметр δ определяет момент останова итерацион-
ного процесса, ∆z — максимальную длину шага алгоритма. Приведем шаги алгоритма, реализующего метод главных осей для вычисления целевых
функций J1 и J2 .
Шаг 1. Вычисление начальной оценки маирицы R(0) .
Шаг 2. Задание начальных направлений одномерного поиска: U 0 = (ui )(0) M (M +2) = I, i=1
где I — единичная матрица.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11
Оптимизация параметров сетей массового обслуживания
65
Шаг 3. Поиск оптимального значения ЦФ поочередно вдоль каждого направления методом золотого сечения с начальным интервалом 2∆z. Перенос текущих значений оптимальных параметров во вновь найденную точку, которую обозначим как R(k) .
Шаг 4. Вычисление величины ∆z = 2 ⋅ R(k ) − R(k−1) .
Шаг
5.
Исключение
вектора
uM(k
−1) (M
+2)
,
переход
к
матрице
направлений
следующего
ви-
( )да: U k =
R( k )
−
R( k −1) ,
u1( k
−1)
,
u2(k−1) ,…,
uM( k
−1) (M
+2)−1
.
Шаг 6. После полной смены направляющего набора векторов U M (M+2) обновление на-
бора полностью с замещением его ортогональной матрицей, аппроксимирующей гессиан целевой функции в текущей точке.
Шаг 7. Повтор шагов 3—6 до тех пор, пока абсолютная разность значений ЦФ на последовательных итерациях не станет меньше δ .
Выбор начальной оценки при реализации метода главных осей предлагается осуществлять с использованием модели сети Джексона [4], для которой существует аналитическое решение поставленной задачи.
Многоканальные узлы замещаются одноканальными с пропорционально увеличенной
интенсивностью времени обслуживания µ′ = 1/ bin (i). Экспоненциальное распределение вре-
мени обслуживания в каждом узле аппроксимируется с учетом первых моментов заданных распределений. Последовательный обход сети в ширину позволяет выбрать начальные оценки для каждого узла на основе решения следующей оптимизационной задачи:
∑M +1
j=1 µ′j
rij − rij λ j
→ min .
R∈Ω
Использование данного метода выбора начальных оценок эффективно (в вычислительном отношении) при небольшом числе каналов в узлах и малых значениях коэффициентов вариации времени обслуживания в узлах. В качестве альтернативы используется метод псипреобразования. Его реализация предпочтительнее для сетей, в которых закон распределения времени обслуживания значительно отличается от экспоненциального (например, равномерный закон распределения на отрезке или гамма-распределение с высокой вариацией.).
Сравнительный анализ начальных оценок матрицы R, полученных методом построения
сети Джексона и методом пси-преобразования для расчета оптимального значения ЦФ J1 , представлен в таблице, где K — количество итераций.
М
Метод Джексона
ν1(R)
K
Метод пси-преобразования
ν1(R)
K
J1
3 2,91
319 2,91
651 2,18
5 3,35
895 3,57
1293
3,19
8 4,9
6067
4,83
5419
4,53
13 7,02
21939
7,92
41345
6,57
21
9,05 212939
8,84
201323
8,64
Численные эксперименты. Для сравнения результатов, полученных с использованием аналитических и имитационных моделей СМО, рассмотрим простую сеть, состоящую из 8 узлов, расположенных в трех ярусах (см. рисунок). При варьировании элементов, входящих в матрицу R вероятностей переходов между узлами, можно получить одинаковые результаты как на АМ, так и на ИМ. По сравнению с численной оптимизацией на АМ процедура поиска параметров на ИМ отличается плохой сходимостью соответствующего локального метода, которая определяется тем, что при имитации целевые функции принимают случайные значения.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11
66 С. В. Кокорин, Ю. И. Рыжиков
Для уменьшения влияния данного фактора требуется увеличить число имитационных экспериментов, при этом высокая точность требуется только на последних шагах метода при малых значениях ∆z . Поэтому для повышения эффективности вычислений ЦФ на ИМ был реализован расчет с использованием метода Брента, при котором точность расчета целевой функции зависит от длины шага как q0 / ∆z.
Выводы. В задачах оптимизации характеристик СМО вопросы повышения эффективности соответствующих вычислительных процедур, связанных с расчетом ЦФ, приобретают особую актуальность. При этом использование ИМ в данных задачах требует значительного количества информационных и временных ресурсов. Кроме того, такое моделирование характеризуется невысокой точностью расчета экстремальных значений ЦФ вследствие статистических погрешностей имитации. Поэтому в данной ситуации целесообразен поиск аналогичных параметров СМО с использованием АМ, что обусловлено значительно меньшими затратами информационных ресурсов, сокращением общего времени на проведение соответствующих расчетов ЦФ, а сами значения рассматриваемых функций вычисляются с меньшими погрешностями.
Предложенный в настоящей статье оригинальный подход к разработке и реализации методов оптимизации параметров различных типов сетей массового обслуживания основан на комбинированном использовании методов глобальной и локальной оптимизации, при этом недостатки метода, базирующегося на имитационной модели, компенсируются достоинствами аналитического метода.
Исследования по данной тематике проводились при поддержке Российского фонда фундаментальных исследований (гранты 10-07-00311, 09-07-00066a, 09-07-11004, 08-0800346-a, 10-08-0906-a, 10-08-90027-Бел-а) и Отделения нанотехнологий и информационных технологий РАН (проект № О-2.3/03).
СПИСОК ЛИТЕРАТУРЫ
1. Bramson М. Stability of Queuing Networks [Электронный ресурс]: .
2. Рыжиков Ю. И. Машинные методы расчета систем массового обслуживания. Л.: ВИКИ им А. Ф. Можайского, 1979.
3. Чичинадзе В. К. Решение невыпуклых нелинейных задач оптимизации. Метод пси-преобразования. М.: Наука, 1983.
4. Brent R. P. Algorithms for Minimization without Derivatives. NJ: Prentice-Hall, Inc., 1973.
5. Охтилев М. Ю., Соколов Б. В., Юсупов Р. М. Интеллектуальные информационные технологии мониторинга и управления структурной динамикой сложных технических объектов. М.: Наука, 2006.
Сергей Владимирович Кокорин Юрий Иванович Рыжиков
Сведения об авторах — аспирант; СПИИРАН, лаборатория информационных технологий в
системном анализе и моделировании; E-mail: kokorins@rambler.ru — д-р техн. наук, профессор; СПИИРАН, лаборатория информационных
технологий в системном анализе и моделировании; E-mail: ryzhbox@yandex.ru
Рекомендована СПИИРАН
Поступила в редакцию 09.07.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 11