Алгоритм пошуку множини рішень, оптимальних за Парето і Слейтером, за інформаційно-аналітичної підтримки процесів системи інформаційної безпеки

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Алгоритм пошуку множини рішень, оптимальних за Парето і Слейтером, за інформаційно-аналітичної підтримки процесів системи інформаційної безпеки

Зибін Сергій Вікторович

Зибін Сергій Вікторович, доктор технічних наук, доцент, Національний Авіаційний університет м. Київ, Україна

Статтю присвячено розробці алгоритму звуження множини Парето-оптимальних рішень в досить вузький набір альтернатив, призначених для остаточного вибору особою, яка приймає рішення.

Розроблений алгоритм не має принципових обмежень на розмірність задачі, використання дозволяє істотно знизити розмірність розглянутих задач, забезпечуючи тим самим умови для застосування інших методів, ефективних для значно менших множин альтернатив. Машинні експерименти засвідчили, що запропонований у статті алгоритм, який є, з точки зору гарантованої оцінки складності обчислень, не гіршим від деяких аналогів, розроблених для кількісних критеріїв зазвичай значно ефективніший у сенсі необхідного числа кроків за великої кількості альтернатив. Крім того, він із мінімальною трудомісткістю для особи, яка ухвалює рішення, автоматично дозволяє досить сильно звужувати безліч Парето-оптимальних альтернатив за відсутності інформації про нерівноцінність критеріїв і не позбавляє при цьому особу, яка ухвалює рішення, свободи вибору.

Ключові слова: інформаційна безпека, автоматизована інформаційна система, захист інформації, система підтримки прийняття рішень, багатокритеріальна оптимізація, система управління, моделювання процесів, інформаційний вплив, управлінське рішення, комплексна система захисту інформації.

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

Разработанный алгоритм не имеет принципиальных ограничений на размерность задачи, использование позволяет существенно снизить размерность рассматриваемых задач, обеспечивая тем самым условия для применения других методов, эффективных для значительно меньших множеств альтернатив. Машинные эксперименты показали, что предложенный в статье алгоритм, который является с точки зрения гарантированной оценки сложности вычислений, не худшим от некоторых аналогов, разработанных для количественных критериев, как правило, значительно эффективнее в смысле необходимого числа шагов при большом количестве альтернатив. Кроме того, он с минимальной трудоемкостью для лица, принимающего решения, автоматически позволяет достаточно сильно сужать множество Парето-оптимальных альтернатив при отсутствии информации о неравноценности критериев, не лишая при этом лицо, принимающее решения, свободы выбора.

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

Zybin Serhii, D. Sci. (Engineering), Associate Professor, National Aviation University, Kyiv, Ukraine,

THE SEARCH ALGORITHM FOR SET SOLUTIONS, OPTIMAL ONES ACCORDING TO PARETO AND SLATER, WITH INFORMATION AND ANALYTICAL SUPPORT OF THE INFORMATION SECURITY SYSTEM PROCESSES

Getting rid of qualitative criteria and moving to a task with only quantitative criteria in order to use well-developed various decision-making methods are often not provided with objective information. This allows us to transform the general model of decision-making in terms of order structures into a more partial model in topological terms of the degree closeness

The problems that arise when evaluating and optimizing alternatives are due to the person's limited ability to process information when making a decision. Therefore, we need such structuring of the goal-oriented process for a compromise choice of variant so that the person can use the intermediate results of the decision and to show their knowledge on the basis of the proper construction of the human-machine technology for the decision-making.

This paper is devoted to the development of an algorithm for narrowing the set of pareto-optimal solutions to a narrow set of alternatives, which are intended for the final choice by the decision maker.

As a result, an algorithm for pre-optimizing the initial set of alternatives (finding Pareto and Slater optimal solutions) was developed based on partial generalized rankings. In this case, the algorithms for finding solutions that are optimal for Pareto and Slater differ only by changing the procedures for transferring alternatives in the rankings on the corresponding steps of the algorithms, as well as certain conditions. Both algorithms complete the work in one go and stop for a finite number of steps.

The developed algorithm has no fundamental restrictions on the dimension of the problem. Using this algorithm can significantly reduce the dimension of the considered problems. This provides the conditions for applying other methods that are effective for much smaller number of alternatives. Experiments have shown that the proposed algorithm, which is from the point of view of the guaranteed estimation of complexity calculations not worse than some analogues, which were developed for quantitative criteria. Moreover, as a rule, much more effective in the sense of the required number of steps with a large number of alternatives. In addition, it minimizes the complexity of the set of pareto-optimal alternatives in the absence of information on the inequality of criteria and does not deprive the decision-maker of the choice.

Keywords: information security, automated information system, information protection, decision support system, multi-criteria optimization, control system, process modeling, information impact, control solution, integrated information security system.

Позбавлення від якісних критеріїв і перехід до задачі тільки з кількісними критеріями з метою використання добре розвинених різноманітних методів прийняття рішень часто не забезпечені об'єктивною інформацією, що дозволяє перетворити загальну модель прийняття рішень у термінах структур порядку на більш часткову модель у топологічних термінах міри близькості.

Проблеми, що постають при оцінюванні та оптимізації альтернатив, обумовлені обмеженими можливостями людини в обробці інформації при прийнятті рішення. Отже, необхідна така структуризація процесу цілеспрямованого вибору компромісного варіанту, щоб людина могла використовувати проміжні результати рішення і проявляти свої знання на основі належної організації людино-машинної технології прийняття рішень.

Статтю присвячено розробці алгоритму звуження множини парето-оптимальних рішень до досить вузького набору альтернатив, які призначені для остаточного вибору особою, яка приймає рішення.

Як наслідок, було розроблено алгоритм попередньої оптимізації початкової множини альтернатив (пошук рішень оптимальних за Парето і Слейтером) на основі частинних узагальнених ранжувань. При цьому алгоритми пошуку рішень оптимальних за Парето і Слейтером вирізняються тільки зміною процедур перенесення альтернативи в ранжуваннях на відповідних кроках алгоритмів, а також певними умовами. Обидва алгоритми завершують роботу за один прохід і зупиняються за кінцеве число кроків.

Розроблений алгоритм не має принципових обмежень на розмірність задачі, використання дозволяє істотно знизити розмірність розглянутих задач, забезпечуючи цим умови для застосування інших методів, ефективних для значно менших множин альтернатив. Машинні експерименти показали, що запропонований в статті алгоритм, який виступає, з точки зору гарантованої оцінки складності обчислень, не гіршим від деяких аналогів, розроблених для кількісних критеріїв, зазвичай значно ефективніший в сенсі необхідного числа кроків за великої кількості альтернатив. Крім того, він із мінімальною трудомісткістю для особи, що приймає рішення, автоматично дозволяє досить сильно звужувати множину парето-оптимальних альтернатив за відсутності інформації про нерівноцінність критеріїв і не позбавляє при цьому особу, яка приймає рішення щодо свободи вибору.

Підвищення якості і скорочення часу прийняття рішень при керуванні складними технічними та інформаційними системами різного призначення нині неможливе без інформаційно-аналітичної підтримки. Засоби інтелектуалізації процесів прийняття рішень є найбільш важливими і практично необхідними у сфері інформаційної безпеки держави та інформаційних технологій.

Багатокритеріальні задачі прийняття рішень зазвичай відносять до класу слабкоструктурованих [1, 2], оскільки частина інформації, необхідної для повного й однозначного вирішення задачі відсутня. При цьому багатокритеріальний характер завдань ускладнюється тим, що кількість альтернативних рішень часто є значним, і тому знайти рішення задачі важко без застосування ЕОМ [2]. Крім того, часто критерії оцінювання альтернатив є не кількісними, а якісними, причому останні зазвичай домінують.

Зведення зазначених завдань до оптимізаційних (тільки з кількісними критеріями і з заданими ваговими коефіцієнтами значущості), забезпечуючи можливість використання добре розвиненого математичного апарату скалярної оптимізації та деякі інші переваги, проте можуть привносити в постановку задачі завідомо неправдиву інформацію з непередбачуваними і, можливо, негативними наслідками. При цьому використовуються методи, зазвичай спрямовані на впровадження єдиної кількісної міри й максимізацію відповідного узагальненого (глобального, скалярного) критерію оптимальності, який часто ототожнюється з метою. Це може бути невірним, оскільки критерії характеризують мету лише побічно, іноді краще, іноді гірше, але завжди приблизно. Не задавши всіх необхідних обмежень, можна одночасно з максимізацією зазначеного узагальненого критерію (як єдиної функції корисності) отримати також непередбачені й небажані супутні ефекти. Крім того, ряд авторів, наприклад [3], відзначають, що якщо навіть вдається досягти єдиного оптимального рішення, воно може виявитися дуже “крихким”. Тобто незначні зміни, які в умовах завдання можуть призвести до вибору альтернатив, істотно різняться.

Уникнути можливих помилок, пов'язаних із особливостями розглянутих задач, дозволяє методологія системного аналізу, відмінною рисою якої є облік факторів невизначеності і якісних суджень при виборі мети, розробці та обговоренні альтернатив. Тому теорія і практика прийняття рішень спираються на системний підхід і, зокрема, на його принцип “першої особи”, відповідно до якого переваги керівника або особи, що приймає рішення (ОПР), стали проголошуватися основою остаточного вибору [2-10]. Як вказується в [4], тим самим був зроблений принципово важливий крок, який урозріз з відомою методологією дослідження операцій полягав у відмові від нав'язування керівнику єдино можливого рішення багатокритеріальної задачі вибору. Системний аналіз є, по суті, об'єднанням загальної схеми системного підходу й методів оцінювання та порівняння багатокритеріальних альтернатив на основі суб'єктивних суджень і включає низку процедур [2]:

- визначити цілі та ресурси;

- визначити альтернативні вирішення задачі;

- порівняти між собою альтернативи;

- вибрати кращі альтернативи.

Аналіз робіт, у яких завдання вибору ставиться в будь-якому вигляді [3, 6, 7], засвідчує, що наведені процедури системного аналізу характерні для найрізноманітніших багатокритеріальних задач прийняття рішень і вимагають своєї технологічної (математичної і комп'ютерної) підтримки. За напрямом їх конкретизації можна виділити такі етапи:

Побудова множини можливих і допустимих альтернатив, тобто генерація альтернатив і відсів явно неприйнятних альтернатив, зокрема, що не мають жодного фізичного сенсу.

Формування часткових критеріїв, істотних для оцінки альтернатив.

Формалізація вихідних переваг експертів або оцінювання альтернатив (в кількісній формі або у формі відносин переваги).

Оптимізація альтернатив.

Прогнозування наслідків обраного рішення і власне прийняття рішення.

У статті розглядаються тільки етапи 3, 4 з урахуванням при цьому характерних особливостей і можливостей методів, які використовуються натепер для реалізації інших етапів. Велика кількість публікацій, присвячених науково-технологічної підтримки етапів 3, 4 [5, 9], свідчить про те, що ці етапи є в проблематиці багатокритеріального вибору найважливішими і базовими, а також про високу практичну значимість і актуальність теми.

Автор поділяє відому точку зору, що позбавлення від якісних критеріїв і перехід до задачі тільки за кількісними критеріями з метою використання добре розвинених різноманітних методів прийняття рішень часто не підкріплене об'єктивною інформацією, що дозволяє перетворити загальну модель прийняття рішень в термінах структур порядку на більш часткову модель в топологічних термінах міри близькості.

Аналіз проблем, що виникають при оцінюванні й оптимізації альтернатив, показує, що багато з них обумовлені обмеженими можливостями людини в обробленні інформації при прийнятті рішення [2, 5]. Отже, необхідна така структуризація процесу цілеспрямованого вибору компромісного варіанту, щоб людина могла використовувати проміжні результати рішення і проявляти свої знання на основі належної організації людино-машинної технології прийняття рішень.

Метою статті є розробка алгоритму пошуку множини рішень для оцінювання оптимальних за Парето і Слейтером й подальшої багатокритеріальної оптимізації альтернатив.

Індекс і використовується як ідентифікаційний номер альтернативи, а пц - номер альтернативи у, в ранжуванні S1. Під Xі (у ) = у j, у J будемо розуміти підмножину альтернатив (їх ідентифікаційних номерів), які розташовано в ранжуванні S1 між найкращою (першою) і альтернативою у (альтернатива у і, порядковий номер, який в ранжуванні S1 дорівнює 1, виступає найкращою альтернативою по j-му критерію), включаючи останні (тобто у 1 і у ). Причому якщо 3xk,k є1, n , и 3 j (=1, m для яких xkI]xi, тоді перед формуванням Xі (у ) може застосовуватися для у процедура 1 або процедура 2 і Xі (у ) буде включати, відповідно, або всю групу альтернатив, які еквівалентні у за j-м критерієм, або тільки альтернативу у із цієї групи. Відповідні множини позначаються для визначеності X/ (у ) и X2 (xi ).

Запропоновано пропозицію 1. Рішення

Це рішення з мінімальною кількістю альтернатив назвемо лідуючим: сума кількостей альтернатив, яким xr поступається в ранжуваннях, є мінімальною.

Пропозиція 2. Припустимо, що рішення x є X* виступають завжди оптимальними за Парето.

Доведення. Задаємо Xnap - множину оптимальних за Парето рішень у множині альтернатив X. Доведемо, що X њ Xnap . Припустимо протилежне xr є X , xr Ј Xnap. Оптимальне за Парето рішення x : x є Xnap існує тоді і тільки тоді, коли не існує х' є Хпар , такого, що V j = 1, m x'Rx & 3 j0 є 1, m x'P1 x .

У цьому разі, якщо xr Ј Xnap

Нехай J (відповідно J> ) - множина індексів j = 1, m таких, що xiI1xr (відповідно xiP]xr ); очевидно, що j = 1, m = J~ u J> і із (2) випливає, що J> Ф. Тоді з визначення процедури 2 випливає, що

Тоді із (3) і (4) можна вивести

Отримане протиріччя (див. (1)] доводить твердження.

Сформуємо множини Sr2 = \JX2 (xr ) (на базі множин Xі (xr ), до яких попередньо застосовано процедуру 2).

Пропозиція 3. Будемо вважати, що для будь-якої альтернативи xr є X*, Хпар -- Sr 2.

Доведення. Припустимо, що 3 xr є X*,3 у є Хпар у. Ј Sr2 (/ є 1,n І.Тоді із у Ј Sr2 за визначенням Sr2 випливає, що для V j = 1, m xt Ј X2 (xr ). Тому з урахуванням визначення процедури 2 можна стверджувати, що V j = 1, m xrR1xi. У цьому разі xr не може бути еквівалентним у за всіма частинними критеріями, тоді З j0 є 1, m xrP] у , т.е. у Ј Хпар , що суперечить первинному припущенню. Твердження доведено. Так само доводимо оптимальність за Слейтером.

Пропозиція 4. Припустимо, що для будь-якої альтернативи xr є X*, Хсл -- Sr1.

Доведення. Припустимо, що 3 xr є X*, 3у. є Хсл x. Ј Sr1 є 1,n).Тоді із у Ј Sr1 за визначенням Sr2 випливає, що для V j = 1, m у Ј X/ (xr ). Тому з урахуванням визначення процедури 1 можна стверджувати, що V j = 1, m xrR1xi. Тому у Ј Хсл, що суперечить первинному припущенню. Твердження доведено.

Випливаючи з (1), для будь-якого xr(xr є X*),що лідує, при формуванні Srl (і = 1,2) відсіюється найбільша кількість альтернатив, що не входять в множину оптимальних за Парето рішень. З урахуванням цієї особливості лідуючих рішень пропонуються такі алгоритми пошуку рішень оптимальних за Парето і Слейтером для часткових узагальнених ранжувань. При цьому через Xmax домовимося позначати множину таких альтернатив, що для кожної з них існує певний критерій Fj0, j0 є1, m , за яким ця альтернатива є найкращою і не має еквівалентів. Далі такі альтернативи називаються єдиними найкращими за частковими критеріями.

Етапи пошуку множини рішень оптимальних за Парето.

Пропозиція 5. Припустимо, що множина X" збігається з множиною Xnap для X.

Рис. 1. Блок-схема алгоритму пошуку рішень оптимальних за Парето

завершує доказ припущення, що множина X'" збігається з множиною Хсл всіх рішень оптимальних за Слейтером.

Блок-схема алгоритмів попередньої оптимізації початкової множини альтернатив (пошук рішень оптимальних за Парето і Слейтером) на основі частинних узагальнених ранжувань представлена на рис. 1. При цьому алгоритми пошуку рішень оптимальних за Парето і Слейтером відрізняються тільки за зміною процедур перенесення альтернативи в ранжуваннях на відповідних кроках алгоритмів, а також умовами (5) і (6). Обидва алгоритми завершують роботу за один прохід і зупиняються за кінцеве число кроків. Обчислювальна складність алгоритмів дорівнює

n * m + n + m + т + т',

де n - кількість альтернатив x є X, m - кількість критеріїв,

т - сума порядкових номерів в ранжуваннях S1, j = 1, m альтернативи xr є X*, яка використовується при формуванні Sr 2 (Sr1 ),

т' - сума порядкових номерів всіх альтернатив x є Sr2\(Xmax и X*) (x є Sr,\ (x ( и X' ')) , які перевіряються по умові (5 і 6).

При цьому цілком очевидно, що на кроці 5, при перевірці умови (5) ((6)) для альтернативи х, достатньо отримати перший порожній перетин X11 (x)n... n Xk (x) = (X 1 (x)n... n X2 (x) =), 2 < к < m для того, щоб зробити висновок, що x є Xnap (x є Xcn).Тому Т є сумою порядкових номерів всіх альтернатив x є Sr 2 \ (xmax и X) (x є Sri \ (Xmax и X* )) ранжуваннях S\..., Sk, 2 < к < m. Перші три складових у формулі витрат, що обчислюються, обумовлені кроками 1 та 2 алгоритмів.

Автором пропонується використовувати алгоритм пошуку рішень для ранжирування альтернатив за обраними критеріями з метою пошуку оптимальної альтернативи. Цей метод вимагає комп'ютерної реалізації в вигляді системи підтримки прийняття рішень, який буде використовувати обчислювальні потужності для пошуку альтернатив, їх оцінювання та вибір ключових критеріїв для оптимізації, після чого зазначені відомості надходять у систему для подальшої обробки й використання.

Розроблений алгоритм не має принципових обмежень на розмірність задачі, використання дозволяє істотно знизити розмірність розглянутих задач, забезпечуючи тим самим умови для застосування інших методів, ефективних для значно менших множин альтернатив. Машинні експерименти показали, що запропонований у статті алгоритм, який є з точки зору гарантованої оцінки складності обчислень не гіршим від деяких аналогів, розроблених для кількісних критеріїв, як правило, значно ефективніший в сенсі необхідного числа кроків за великої кількості альтернатив. Крім того, він із мінімальною трудомісткістю для ОПР або автоматично дозволяють досить сильно звужувати множину парето-оптимальних альтернатив за цього ОПР свободи вибору.

Література

аглоритм інтелектуалізація множина

1. Simon H., Newell A. Heuristic problem solving: the next advance in operations research. Operations Research. 1958. Vol. 6.

2. Ларичев О.И. Наука и искусство принятия решений. М.: Наука, 1979. 200 с.

3. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа: учебник. 2-е изд. Томск, 1997. 396 с.

4. Ларичев О.И. Объективные модели и субъективные решения. М.: Наука, 1987. 143 с.

5. Ларичев О.И., Москович E.M. Качественные методы принятия решений. М.: Наука, 1996. 208 с.

6. Ларичев О.И. Теория и методы принятия решений. 2-е изд., перераб. и доп. М.: Логос, 2002. 392 с.

7. Саати Т. Принятия решений. Метод анализа иерархии. М.: Радио и связь, 1993. 278 с.

8. Keeney R.L. Value-Focused Thinking. A Path to Creative Decisionmaking. Harvard University, 1996. pp. 432.

9. K. Borcherding, D. von Winterfeldt, “The effect of varying value trees on multiattribute evaluations”, Acta Psychologica, vol. 68, no. 1-3, pp. 153-170, 1988.

10. Зибін С.В. Алгоритм ранжування альтернатив при інформаційно-аналітичній підтримці процесів формування системи інформаційної безпеки держави. Сучасна спеціальна техніка. K.: ДНДІ МВС України, 2017. № 3(50). С. 42-50.

References

1. Simon, H., Newell, A. (1958) Heuristic Problem Solving: the Next Advance in Operations Research. Operations Research.Vol. 6. [in English].

2. Larychev, O.I. (1979) Nauka i iskusstvo pryniatyia reshenyi. “Science and the Art of Decision Making”. M.: Nauka, 1979. 200 p. [in Russian].

3. Perehudov, F.I., Tarasenko, F.P. (1997) Osnovy systemnoho analyza. “Fundamentals of System Analysis”: textbook. 2-nd ed. Tomsk. 396 p. [in Russian].

4. Larychev, O.I. (1987) Obektyvnye modely i subektyvnye reshenyia. “Objective Models and Subjective Decisions”. М.: Nauka. 143 p. [in Russian].

5. Larychev, O.I., Moshkovych, E.M. (1996) Kachestvennye metody pryniatyia reshenyi. “Qualitative Decision-Making Methods”. M.: Nauka. 288 p. [in Russian].

6. Larychev, O.I. (2002) Teoryia i metody pryniatyia reshenyi. “Theory and Decision-Making Methods. 2-nd ed., revised and add. M.: Logos. 392 p.

7. Saaty, Т. (1993) Pryniatyia resheniy. Metod analyza yerarkhyi. “Decision Making. Hierarchy Analysis Method”. M.: Radio and Communications. 278 p.

8. Keeney, R. L. (1996) Value-Focused Thinking. A Path to Creative Decisionmaking. Harvard University. 432 p. [in English].

9. K. Borcherding, D. von Winterfeldt (1988). The Effect of Varying Value Trees on Multiattribute Evaluations. Acta Psychologica. Vol. 68. No 1-3. P. 153-170 [in English].

10. Zybin, S.V. (2017) Alhorytm ranzhuvannia alternatyv pry informatsiino-analitychnii pidtrymtsi protsesiv formuvannia systemy informatsiinoi bezpeky derzhavy. “Algorithm of Ranking Alternatives with Information-Analytical Support of the Processes of Formation of the State Information Security”. Modern Special Technique 3(50), 42-50 [in Ukrainian].

Размещено на Allbest.ru