Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,118

АЛГОРИТМ СТРУКТУРНО-ПАРАМЕТРИЧЕСКОГО СИНТЕЗА КОМПЛЕКСА ИНЖЕНЕРНО-ТЕХНИЧЕСКИХ СРЕДСТВ СИСТЕМЫ ФИЗИЧЕСКОЙ ЗАЩИТЫ ПРОМЫШЛЕННОГО ОБЪЕКТА

Беседин И.И. 1
1 Академия ФСО России
В статье разработан алгоритм с вычислительной сложностью полиномиального класса для совместного решения задач по нахождению рациональных структуры и состава (плана установки) инженерно-технических средств охраны комплекса инженерно-технических средств системы физической защиты промышленного объекта. Алгоритм основан на численном решении сформированной условной оптимизационной задачи по критерию максимум рентабельности синтезируемой системы и обладает высокой надежностью и гарантированной сходимостью. С целью снижения вычислительной сложности в заданный критерий введены дополнительные ограничения на идемпотентность и целочисленность переменных, определяющие возможность преобразования (погружения) исходной задачи дискретной оптимизации в нелинейную. Применение разработанного алгоритма структурно-параметрического синтеза позволяет повысить рентабельность проектируемого комплекса инженерно-технических средств охраны системы физической защиты промышленного объекта в среднем на величину порядка 1,213 раз по сравнению с существующими последовательными решениями.
алгоритм
структурно-параметрический синтез
система физической защиты
1. Алаухов С.Ф. Концепция безопасности и принципы создания систем физической защиты важных промышленных объектов / С.Ф. Алаухов, В.Я. Коцеруба. – ФГУП «НИКИРЭТ», 2005.
2. Архипов Н.С. Алгоритм распределения однородных непрерывных ограниченных ресурсов на основе решения задачи условной оптимизации по критерию минимума моментов инерции / Н.С. Архипов, И.С. Полянский, В.А. Хомаза // Телекоммуникации. – 2011. – № 11. – С. 8–13.
3. Балк М.Б. Геометрия масс / М.Б. Балк, В.Г. Болтянский. – М.: Наука. Гл. ред. физ.-мат. лит., 1987.– 160 с.
4. Васильев Ф.П. Численные методы решения экстремальных задач. – М.: Наука, 1980. – 520 с.
5. Гантмахер Ф.Р. Теория матриц. – 4-е изд. – М.: Наука. Гл. ред. физ.-мат. лит. – 1988. – 552 с.
6. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 с.
7. Ковалев М.М. Дискретная оптимизация (целочисленное программирование). – Минск: Изд-во БГУ, 1977. – 192 с.
8. Алгоритмы: построение и анализ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн: пер. с англ. И.В. Красикова, В.Н. Романова, Н.А. Ореховой / Под ред. И. В. Красикова. – 2-е изд. – М.: Издательский дом «Вильямс», 2005. – 1296 с.
9. Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу, К. Стайглиц / под ред. И.А. Маховой. – М.: Мир, 1985. – 510 с.
10. Полянский И.С. Анализ методов повышения эффективности комплекса инженерно-технических средств системы физической защиты промышленного объекта / И.С. Полянский, И.И. Беседин // Наука XXI века: проблемы и перспективы: международная научно-практическая конференция. – Уфа, 2013. – С. 109–114.
11. Полянский И.С. Математическая модель комплекса инженерно-технических средств системы физической защиты объекта охраны / И.С. Полянский, И.И. Беседин, Б.Л. Панин // Фундаментальные исследования. – 2013. – № 6 (часть 6). – С. 1359–1365.
12. Полянский И.С. Алгоритм распределения неоднородных дискретных ограниченных ресурсов в системе физической защиты / И.С. Полянский, И.И. Беседин // Информационные системы и технологии. – 2013. – № 4 (78) июль-август. – С. 10–18.

Согласно [1], основным этапом проектирования современных систем физической защиты (СФЗ) является стадия концептуального проектирования СФЗ промышленного объекта. При этом одной из главных задач концептуального проектирования выступает обоснование и выбор рациональных структуры и состава разрабатываемого комплекса инженерно-технических средств (КИТС) СФЗ промышленного объекта, по сути определяющих решение задач по нахождению [10]:

1) топологии, задающей расстановку и смежность между узлами комплекса (подступами к объекту N1, рубежами защиты N2 и охраняемыми зонами N3) с учетом ограничения на существование путей (доступа) от подступов до объекта к определенным зонам охраны;

2) плана установки на рубежах защиты различных инженерно-технических средств охраны (ИТСО).

Цель статьи заключается в разработке алгоритма структурно-параметрического синтеза КИТС СФЗ промышленного объекта. Необходимо отметить, что настоящая статья является продолжением работы [11], и полноценное понимание изложенных здесь результатов затруднительно без предварительного ознакомления с указанной публикацией.

Формальная постановка задачи синтеза

В [11] сформирована математическая модель КИТС СФЗ, позволяющая задать аналитическую зависимость между рентабельностью синтезируемого КИТС СФЗ (показателем эффективности) и структурно-функциональными свойствами, характеризующими: структуру, определяющую топологические связи между подступами к объекту, рубежами защиты и охраняемыми зонами; различные способы преодоления рубежей защиты; разнородность ИТСО по принципу действия, обеспечивающих разноэффективный уровень защиты рубежа от конкретных способов его преодоления; стоимость ИТСО; ограничение на допустимую стоимость устанавливаемых ИТСО, необходимых для решения задачи по нахождению рациональных топологий КИТС СФЗ и плана установки на рубежах защиты различных ИТСО. Согласно заданным в [11] представлениям, обобщенный критерий эффективности КИТС СФЗ определяется в виде

Eqn1.wmf (1)

где Eqn2.wmf – множество неотрицательных целых чисел: {0, 1, 2, ...}; Сp – суммарная стоимость ИТСО по их установки, эксплуатации и т.д.; Ψ(X, Y, T) – функция, преобразующая пространство матриц управляющих переменных, характеризующих топологическую структуру Eqn3.wmf, Eqn4.wmf и состав (план установки ИТСО) Eqn5.wmf, в выходной параметр – обратную величину суммарного вероятного уровня ущерба (риска) КИТС СФЗ. Матрицы управляющих переменных X и Y определяют «…соответствующие элементы матриц инцидентности для прямого Hin и обратного Hout потоков синтезируемой структуры СФЗ» [11]. Элементы матрицы T характеризуют количество устанавливаемых на i2-м рубеже защиты p-х типов ИТСО.

В общем виде сформированная задача синтеза (1) в [11] относится к классу задач дискретной оптимизации [7]. При этом в связи с различием областей определения значений элементов матриц управляющих переменных Eqn6.wmf, Eqn7.wmf и многомерностью оптимизируемой целевой функции (1) совместное решение задач структурного и параметрического синтеза КИТС СФЗ промышленного объекта за полиномиальное время с использованием известных подходов не представляется возможным, поскольку использование класса комбинаторных алгоритмов для решения подобных дискретных задач порождает значительную вычислительную сложность. Принципиальным результатом исследования таких задач является понятие полной задачи [9].

Последовательное решение задач по

1) нахождению рациональной структуры КИТС СФЗ на заданном исходном плане установки ИТСО T*, определяемой

Eqn8.wmf;

2) оптимизации плана установки ИТСО (параметров КИТС СФЗ) на рубежах защиты

Eqn9.wmf

с учетом найденной на первом этапе рациональной структуры, – теоретически обеспечивает существенное снижение вычислительных затрат.

Однако наряду с относительным уменьшением вычислительной сложности последовательное решение задач синтеза не позволяет:

1) определить точку

Eqn10.wmf,

соответствующую глобальному оптимуму целевой функции (1);

2) решить вопрос о корректности выбора исходного плана установки ИТСО T* на первом этапе решения задачи синтеза;

3) произвести решение задачи структурного и параметрического синтеза за полиномиальное время.

Для уменьшения вычислительной сложности расширим класс используемых алгоритмов при решении общей задачи (1) структурно-параметрического синтеза. Другими словами, представим исходную комбинаторную задачу как общую задачу нелинейного программирования, т.е. по существу используем условный подход, идея которого указана в [6] и основана на полиномиальной сводимости языка Eqn11.wmf (Eqn12.wmf – алфавит языка L1) исходной дискретной оптимизационной задачи к языку Eqn13.wmf – непрерывной (¡ – множество вещественных чисел). Достаточным условием полиномиальной сводимости L1∞L2, согласно [6] является существование функции реализации такой сводимости Eqn14.wmf, удовлетворяющей условиям:

1. Существует детерминированная однолинейная машина Тьюринга, вычисляющая f с временной сложностью, ограниченной полиномом.

2. Для любого Eqn15.wmf, x ∈ L1 в том и только том случае, если f(x) ∈ L2.

Существенная важность понятия полиномиальной сводимости, необходимой для формирования полиномиального алгоритма структурно-параметрического синтеза КИТС СФЗ, следует из леммы, описанной и доказанной в [6]: «Лемма. Если L1∞L2, то из L2 ∈ P следует, что L1 ∈ P. (Эквивалентно утверждение: из L2 ∉ P следует, что L1 ∉ P)».

С этой целью определим функции f1(x) и f2(x), удовлетворяющие двум указанным условиям и реализующие полиномиальную сводимость Eqn16.wmf для элементов матриц управляющих переменных Eqn17.wmf и Eqn18.wmf, т.е. структурный синтез, и Eqn19.wmf для элементов матриц Eqn20.wmf, т.е. параметрический синтез.

Для задания функции f1(x), определяющей отображение Eqn16.wmf, используем свойство идемпотентности [7]: x2 = x, допускающее булевость переменной x (x = 0 или 1). Функцию f2(x), задающую отображение Eqn19.wmf, представим с помощью введения в исходную задачу (1) дополнительных целочисленных ограничений, записанных с помощью элементарных тригонометрических функций, к примеру [12], sin(π∙x) = 0.

Применение подобных представлений позволяет изменить класс исходной оптимизационной задачи (1) c дискретной на нелинейную и преобразовать формальную постановку структурно-параметрического синтеза КИТС СФЗ к виду

Eqn21.wmf (2)

с учетом ограничений [11]:

Eqn22.wmf (3)

Eqn23.wmf

Eqn24.wmf Eqn25.wmf (4)

и дополнительных ограничений на булевость и целочисленность переменных:

Eqn26.wmf Eqn27.wmf Eqn28.wmf (5)

Eqn29.wmf Eqn27.wmf Eqn28.wmf (6)

Eqn30.wmf Eqn31.wmf

Eqn32.wmf Eqn33.wmf (7)

В выражениях (3), (4) Eqn34.wmf – максимально допустимая стоимость ИТСО (установка, эксплуатация и т.д.); Eqn35.wmf – матрица достижимости для всех возможных путей кратности от 1 до R.

Таким образом, целочисленная задача (1) преобразована в общую задачу нелинейного программирования (2)–(7) путем введения дополнительных ограничений (5)–(7). Такая ситуация обусловливает возможность решения сформированной нелинейной задачи с использованием релаксационных градиентных методов [4] при минимальном количестве предположений. Однако многомерность оптимизируемой целевой функции, где число переменных определяется как 2∙M∙N + N2∙P (M и N – число ребер и вершин в исходном графе [11] соответственно), приводит к росту вычислительных затрат при решении задачи методами градиентной оптимизации первого порядка (градиентный спуск, наискорейший спуск, сопряженных градиентов Флетчера‒Ривса, Полока‒Райбера и др.). Повышение скорости сходимости алгоритма возможно обеспечить применением методов оптимизации второго порядка (Ньютона, Ньютона-Рафсона, Марквардта, Левенберга‒Марквардта и др.). Однако использование последних накладывает более жесткие требования на определение начальных приближений оптимизационного алгоритма. Это связано с тем, что методы второго порядка являются менее устойчивыми, чем, например, методы сопряженных градиентов, и имеют тенденцию «застревать» в локальных минимумах [4], а также требуют больших вычислительных затрат на единичной итерации, связанных с необходимостью вычисления матрицы вторых частных производных (матрицы Гессе) и ее обращения (псевдообращения) [4, 7]. С целью устранения указанного противоречия между высокой скоростью сходимости, достигаемой методами второго порядка, и устойчивостью, обеспечиваемой методами сопряженных градиентов, согласно [12] приведем сформированный критерий (2) с учетом положений теории геометрии центров масс [3] и представлений, заданных в [2], к виду

Eqn36.wmf (8)

где Ω(X, Y, T) – векторная функция, обратная величине действительного риска размерности N, элементы которой задают вероятность защиты от угрозы i-х узлов КИТС СФЗ с учетом воздействий ИТСО (субъектов защиты) на злоумышленника (субъект угрозы) [11]; Eqn37.wmf – значимость i3-х охраняемых зон.

Сформированная целевая функция (8), отражающая критерий максимума моментов инерции, в соответствии с [2] позволяет повысить скорость сходимости алгоритма структурно-параметрического синтеза при использовании градиентных методов с переменной метрикой, обусловленное снижением ранга матрицы Гессе за счет увеличения линейной зависимости ее строк.

Алгоритм структурно-параметрического синтеза КИТС СФЗ

Ввиду многомерности оптимизируемой целевой функции (8); наличия большого числа ограничений, накладываемых на переменные; периодичности функций-ограничений, эффективность работы алгоритма существенно зависит от выбора начальных приближений. В этой связи поиск начальных приближений переменных {X*, Y*, T*} предлагается осуществить путем следующей поэтапной декомпозиции:

1) решить задачу параметрического синтеза для топологии, заданной полносвязным графом Eqn38.wmf;

2) на основе сформированного плана установки ИТСО определить структуру КИТС СФЗ Eqn39.wmf;

3) осуществить оптимизацию плана установки ИТСО Eqn40.wmf с учетом найденной рациональной структуры, что обусловливает необходимость разработки частных алгоритмов параметрического и структурного синтеза КИТС СФЗ промышленного объекта.

В общем виде задача параметрического синтеза КИТС СФЗ промышленного объекта сводится к нахождению оптимума целевой функции:

Eqn41.wmf (9)

с учетом ограничений (3), (7).

Максимизация сформированной целевой функции F1(T) с учетом ограничений в виде равенств и неравенств произведена на основе метода штрафных функций [4] путем сведения задачи условной максимизации к решению последовательности задач поиска безусловного максимума вспомогательной функции:

Eqn42.wmf

Eqn43.wmf, (10)

где P1(rk, T) – штрафная функция; rk – коэффициент штрафа.

На каждой k-й итерации осуществляется поиск точки с координатами Eqn44.wmf, доставляющей максимум вспомогательной функции f1(rk, T) при заданном параметре штрафа rk методом сопряженных градиентов с переменной метрикой Дэвидона–Флетчера–Пауэлла, стратегия которого подробно рассмотрена в [4].

Задача структурного синтеза КИТС СФЗ промышленного объекта сводится к нахождению оптимума целевой функции:

Eqn45.wmf (11)

с ограничениями (4)–(6).

Нахождение условного экстремума (11) выполнено по аналогии с решением задачи параметрического синтеза методом штрафных функций на каждой итерации штрафа [4], при этом безусловная вспомогательная целевая функция задана в виде

Eqn46.wmf

Eqn47.wmf (12)

с осуществлением решения безусловной задачи (13) на каждой k-й итерации штрафа методом Дэвидона–Флетчера–Пауэлла.

Решение задачи структурно-параметрического синтеза КИТС СФЗ, заданной в виде целевой функции (8) с учетом ограничений (3)–(7), выполнено методом штрафных функций, при этом вспомогательная функция задана в виде разности целевой Θ(X′, Y′, T) (8) и штрафной P(rk, X′, Y′, T) функций:

Eqn48.wmf

Eqn49.wmf (13)

Для оценки эффективности работы предложенного алгоритма проведен ряд вычислительных экспериментов, в ходе которых произведен анализ результативности разработанного алгоритма и вычислительной сложности. В связи с выбранным критерием эффективности КИТС СФЗ промышленного объекта (1), заданным по правилу «отношения максимума защищенности (минимум риска) и минимума стоимости», для оценки результативности решения определим рентабельности синтезируемого КИТС СФЗ промышленного объекта по алгоритмам:

1) параметрического синтеза, предложенного в [12];

2) последовательного параметрического и структурного синтеза;

3) раздельного синтеза по схеме «параметрический-структурный-параметрический синтез»;

4) структурно-параметрического синтеза в рамках проведения математико-алгоритмического эксперимента. В результате оценки получен график зависимости рентабельности синтезируемого по указанным алгоритмам КИТС СФЗ промышленного объекта от числа узлов, задающих максимальное количество рубежей защиты N2 (рисунок, а).

а pic_1.wmfб pic_2.wmf

Оценка эффективности разработанного алгоритма структурно-параметрического синтеза КИТС СФЗ, включающая определение: а – зависимости рентабельности синтезируемого КИТС СФЗ промышленного объекта от числа рубежей защиты N2; б – асимптотической оценки вычислительной сложности

В [8] для расчета вычислительной сложности используется «O оценка» сложности алгоритмов, определяющая функцию g(N) порядка роста времени работы алгоритма. Определение вычислительной сложности сформированных алгоритмов производилось путем их реализации на языке программирования С++ в интегрированной среде программирования CodeGear RAD Studio XE2 с последующим проведением ряда вычислительных экспериментов, определяющих время работы алгоритма на «наихудший случай» [8] для погрешности вычислений ε = 10–7 на ЭВМ с характеристиками: Intel(R) Xeon(TM) CPU 3.60 GHz, 3.60 GHz; 2 Gb ОЗУ; жесткий диск 200 Gb. Результаты экспериментов для разработанного алгоритма представлен на рисунке, б (N – общее количество элементов синтезируемого комплекса).

Выводы

Таким образом, разработанный алгоритм структурно-параметрического синтеза с учетом представлений, предложенных в [11], реализует совместное решение по нахождению рациональных топологической структуры и состава КИТС СФЗ. При этом совместное решение позволяет повысить рентабельность проектируемой системы в среднем на величину порядка 1,213 раз по сравнению с существующими последовательными решениями. В общем случае применение идемпотентных x2 = x и целочисленных sin(π∙x) = 0 ограничений в классе подобных задач синтеза позволяет осуществить преобразование комбинаторной постановки (1) в общую задачу нелинейного программирования (2). Представленные экспериментальные результаты по оценке вычислительной сложности (см. рисунок, б) разработанного алгоритма подтверждают, что предложенный в статье подход к решению задачи структурно-параметрического синтеза позволяет значительно снизить вычислительные затраты на поиск рациональных структуры и состава КИТС СФЗ. Следует отметить, что для решения подобных задач нелинейного программирования (2) с учетом ограничений (3)–(7) применение метода множителей Лагранжа [4] является нецелесообразным. Это объясняется тем, что введение дополнительных переменных, сводящих целевую функцию и ограничения в виде равенств и неравенств в общий полином Лагранжа, приводит к резкому увеличению числа переменных в итоговой безусловной оптимизационной задаче. Последнее обусловливает существенное повышение вычислительных затрат и определяет сложность процедуры поиска его начальных приближений. Такая ситуация обусловливает предпочтительность использования метода штрафных функций.

Рецензенты:

Архипов Н.С., д.т.н., доцент, сотрудник Академии СФО России, г. Орёл;

Иванов Б.Р., д.т.н., профессор, сотрудник Академии СФО России, г. Орёл.

Работа поступила в редакцию 23.08.2013.


Библиографическая ссылка

Беседин И.И. АЛГОРИТМ СТРУКТУРНО-ПАРАМЕТРИЧЕСКОГО СИНТЕЗА КОМПЛЕКСА ИНЖЕНЕРНО-ТЕХНИЧЕСКИХ СРЕДСТВ СИСТЕМЫ ФИЗИЧЕСКОЙ ЗАЩИТЫ ПРОМЫШЛЕННОГО ОБЪЕКТА // Фундаментальные исследования. – 2013. – № 10-3. – С. 489-494;
URL: http://fundamental-research.ru/ru/article/view?id=32305 (дата обращения: 19.12.2018).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252