Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2014
Hauptverfasser:	Парасюк, И.Н., Костукевич, Ф.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2014
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Программно-технические комплексы
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/115770
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия / И.Н. Парасюк, Ф.В. Костукевич // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 138-150. — Бібліогр.: 16 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-115770
record_format	dspace
spelling	irk-123456789-1157702017-04-13T03:02:40Z Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия Парасюк, И.Н. Костукевич, Ф.В. Программно-технические комплексы Предложены основы математического обеспечения для исследования состояний сложных систем методами вероятностного вывода на базе нечетких сетевых моделей доверия и их расширений. Введены понятия нечетких потенциалов и операций над ними, разработан математический аппарат двухэтапного точного вероятностного вывода, процедура оценивания и прогнозирования состояний исследуемой системы, описаны архитектурные аспекты компьютерной реализации соответствующей информационной технологии. Запропоновано основи математичного забезпечення для дослідження станів складних систем методами ймовірнісного виведення на базі нечітких мережних моделей довіри та їх розширень. Введено поняття нечітких потенціалів та операцій над ними, розроблено математичний апарат двоетапного точного ймовірнісного виведення, процедуру оцінювання та прогнозування станів досліджуваної системи, описано архітектурні аспекти комп’ютерної реалізації відповідної інформаційної технології. We propose the fundamentals of the software for the analysis of states of complex systems by probabilistic inference methods based on belief fuzzy network models and their extensions. We introduce the concepts of fuzzy potentials and operations over them, develop mathematical tools of two-phase exact probabilistic inference and the procedure for evaluating and predicting the states of the system under study, and describe the architectural aspects of the computer implementation of the relevant information technology. 2014 Article Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия / И.Н. Парасюк, Ф.В. Костукевич // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 138-150. — Бібліогр.: 16 назв. — рос. http://dspace.nbuv.gov.ua/handle/123456789/115770 519.9:681.3 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Программно-технические комплексы Программно-технические комплексы
spellingShingle	Программно-технические комплексы Программно-технические комплексы Парасюк, И.Н. Костукевич, Ф.В. Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия Кибернетика и системный анализ
description	Предложены основы математического обеспечения для исследования состояний сложных систем методами вероятностного вывода на базе нечетких сетевых моделей доверия и их расширений. Введены понятия нечетких потенциалов и операций над ними, разработан математический аппарат двухэтапного точного вероятностного вывода, процедура оценивания и прогнозирования состояний исследуемой системы, описаны архитектурные аспекты компьютерной реализации соответствующей информационной технологии.
format	Article
author	Парасюк, И.Н. Костукевич, Ф.В.
author_facet	Парасюк, И.Н. Костукевич, Ф.В.
author_sort	Парасюк, И.Н.
title	Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия
title_short	Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия
title_full	Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия
title_fullStr	Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия
title_full_unstemmed	Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия
title_sort	математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2014
topic_facet	Программно-технические комплексы
url	http://dspace.nbuv.gov.ua/handle/123456789/115770
citation_txt	Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия / И.Н. Парасюк, Ф.В. Костукевич // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 138-150. — Бібліогр.: 16 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT parasûkin matematičeskoeobespečeniedlâissledovaniâsostoânijsložnyhsistemvusloviâhneopredelennostinaosnovaniinečetkihsetevyhmodelejdoveriâ AT kostukevičfv matematičeskoeobespečeniedlâissledovaniâsostoânijsložnyhsistemvusloviâhneopredelennostinaosnovaniinečetkihsetevyhmodelejdoveriâ
first_indexed	2025-07-08T09:20:36Z
last_indexed	2025-07-08T09:20:36Z
_version_	1837069958819872768
fulltext	ÓÄÊ 519.9:681.3 È.Í. ÏÀÐÀÑÞÊ, Ô.Â. ÊÎÑÒÓÊÅÂÈ× ÌÀÒÅÌÀÒÈ×ÅÑÊÎÅ ÎÁÅÑÏÅ×ÅÍÈÅ ÄËß ÈÑÑËÅÄÎÂÀÍÈß ÑÎÑÒÎßÍÈÉ ÑËÎÆÍÛÕ ÑÈÑÒÅÌ Â ÓÑËÎÂÈßÕ ÍÅÎÏÐÅÄÅËÅÍÍÎÑÒÈ ÍÀ ÎÑÍÎÂÀÍÈÈ ÍÅ×ÅÒÊÈÕ ÑÅÒÅÂÛÕ ÌÎÄÅËÅÉ ÄÎÂÅÐÈß Àííîòàöèÿ. Ïðåäëîæåíû îñíîâû ìàòåìàòè÷åñêîãî îáåñïå÷åíèÿ äëÿ èññëåäîâàíèÿ ñîñòîÿ- íèé ñëîæíûõ ñèñòåì ìåòîäàìè âåðîÿòíîñòíîãî âûâîäà íà áàçå íå÷åòêèõ ñåòåâûõ ìîäåëåé äîâåðèÿ è èõ ðàñøèðåíèé. Ââåäåíû ïîíÿòèÿ íå÷åòêèõ ïîòåíöèàëîâ è îïåðàöèé íàä íèìè, ðàçðàáîòàí ìàòåìàòè÷åñêèé àïïàðàò äâóõýòàïíîãî òî÷íîãî âåðîÿòíîñòíîãî âûâîäà, ïðîöåäó- ðà îöåíèâàíèÿ è ïðîãíîçèðîâàíèÿ ñîñòîÿíèé èññëåäóåìîé ñèñòåìû, îïèñàíû àðõèòåêòóð- íûå àñïåêòû êîìïüþòåðíîé ðåàëèçàöèè ñîîòâåòñòâóþùåé èíôîðìàöèîííîé òåõíîëîãèè. Êëþ÷åâûå ñëîâà: íå÷åòêàÿ âåðîÿòíîñòü, íå÷åòêèé ïîòåíöèàë, ñåòåâûå ìîäåëè äîâåðèÿ, íå÷åòêèå áàéåñîâñêèå ñåòè, íå÷åòêèå äèàãðàììû âëèÿíèÿ, òðàíñôîðìàöèÿ ñåòåé, âåðîÿò- íîñòíûé âûâîä, óçëîâîå äåðåâî, èíôîðìàöèîííûå òåõíîëîãèè. ÂÂÅÄÅÍÈÅ Ñåòè äîâåðèÿ, èçâåñòíûå êàê áàéåñîâñêèå ñåòè (ÁÑ), à òàêæå ñòðóêòóðíî-ôóíê- öèîíàëüíûå ðàñøèðåíèÿ ýòèõ ìîäåëåé — äèàãðàììû âëèÿíèÿ (ÄÂ), ýôôåêòèâ- íî ïðèìåíÿþòñÿ äëÿ âåðîÿòíîñòíîãî ìîäåëèðîâàíèÿ ñîñòîÿíèé ñëîæíûõ ñèñ- òåì â óñëîâèÿõ íåîïðåäåëåííîñòè [1, 2]. Ïðè ýòîì ìîæíî ïîñòðîèòü áîëåå àäåêâàòíûå ìîäåëè èññëåäóåìûõ ñèñòåì, à òàêæå ïîëó÷èòü áîëåå èíôîðìàòèâ- íûå ðåçóëüòàòû ìîäåëèðîâàíèÿ, åñëè ê ðåøåíèþ ýòèõ ïðîáëåì äîïîëíèòåëüíî 138 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 © È.Í. Ïàðàñþê, Ô.Â. Êîñòóêåâè÷, 2014 ïðèâëå÷ü àïïàðàò òåîðèè íå÷åòêèõ ìíîæåñòâ [3]. Öåëü äàííîé ðàáîòû — îá- îáùèâ ðåçóëüòàòû èññëåäîâàíèé [4–7], ñ ó÷åòîì èçâåñòíûõ â ýòîé îáëàñòè äîñòèæåíèé [8–13] ñîçäàòü îñíîâû ìàòåìàòè÷åñêîãî îáåñïå÷åíèÿ äëÿ èçó÷åíèÿ ñîñòîÿíèé ñëîæíûõ ñèñòåì ìåòîäàìè òî÷íîãî âåðîÿòíîñòíîãî âûâîäà íà áàçå íå÷åòêèõ ñåòåâûõ ìîäåëåé äîâåðèÿ è èõ ðàñøèðåíèé. Â ÷àñòíîñòè, ïðè îöåíè- âàíèè âåðîÿòíîñòè ïåðåìåííûõ â íå÷åòêîì èçìåðåíèè ïîñðåäñòâîì íå÷åòêèõ (òîëåðàíòíûõ èëè óíèìîäàëüíûõ) ÷èñåë [3] â ðàáîòå ââåäåíî ïîíÿòèå íå÷åòêèõ âåðîÿòíîñòíûõ ïîòåíöèàëîâ è îïåðàöèè íàä íèìè, îñóùåñòâëåíà èìïëåìåíòà- öèÿ ýòèõ ïîíÿòèé â ìàòåìàòè÷åñêèé àïïàðàò äâóõýòàïíîãî òî÷íîãî âåðîÿòíîñò- íîãî âûâîäà, ïðîöåäóð îöåíèâàíèÿ è ïðîãíîçèðîâàíèÿ ñîñòîÿíèé èññëåäóåìûõ ñèñòåì, îïèñàíû íåêîòîðûå àñïåêòû êîìïüþòåðíîé ðåàëèçàöèè ñîîòâåòñòâóþ- ùåé èíôîðìàöèîííîé òåõíîëîãèè. ÍÅ×ÅÒÊÈÅ ÎÖÅÍÊÈ ÂÅÐÎßÒÍÎÑÒÅÉ È ÎÏÅÐÀÖÈÈ ÍÀÄ ÍÈÌÈ Ïîä íå÷åòêîé îöåíêîé âåðîÿòíîñòè P (äàëåå — íå÷åòêîé âåðîÿòíîñòüþ) áóäåì ïîíèìàòü íå÷åòêîå ÷èñëî Im( )P , îïðåäåëåííîå íà ÷åòêîì ïîäìíîæåñòâå óíè- âåðñàëüíîãî ìíîæåñòâà [0; 1], ïðè ýòîì �( )p è dom ( )� — åãî ôóíêöèÿ ïðè- íàäëåæíîñòè è îáëàñòü åå îïðåäåëåíèÿ ñîîòâåòñòâåííî. Ðåçóëüòàòîì îïåðàöèè � (ñëîæåíèÿ «�», óìíîæåíèÿ «�», âû÷èòàíèÿ «�») íå- ÷åòêèõ âåðîÿòíîñòåé P1 è P2 , çàäàííûõ �-ñå÷åíèÿìè [3] íå÷åòêèõ (òîëåðàíòíûõ èëè óíèìîäàëüíûõ) ÷èñåë, ÿâëÿåòñÿ íå÷åòêàÿ âåðîÿòíîñòü P3 : Im ( ) Im ( ) Im ( ) [ , ] [ , ] P P P a b a b3 1 2 0 1 1 1 2 2 � � � � � �� ñ ôóíêöèåé ïðèíàäëåæíîñòè � � �( ) sup min ( ( ), ( ))p p p p p p 3 1 1 2 2 3 1 2 � � � , ãäå p P1 1�dom (Im ( )), p P2 2�dom (Im ( )) , p P3 3�dom (Im ( )) . Äëÿ ðàíæèðîâàíèÿ íå÷åòêèõ âåðîÿòíîñòåé âûáðàí ìåòîä, îñíîâàííûé íà öåíòðå òÿæåñòè, ó÷èòûâàþùèé ïðèðîäó íå÷åòêîé âåðîÿòíîñòè Ð äëÿ êàæäîãî �-ñå÷åíèÿ [14], âû÷èñëÿåìûé ñëåäóþùèì îáðàçîì: m p p dp p dpP � � �� ( ) / ( ) ( ) ( )dom dom , ãäå �( )p — ôóíêöèÿ ïðèíàäëåæíîñòè íå÷åòêîãî ÷èñëà Im( )Ð . Ìàñøòàáèðîâàíèå íå÷åòêîé âåðîÿòíîñòè P1 ñ ïîìîùüþ íå÷åòêîé âåðîÿòíîñ- òè P2 — ýòî ïðîöåññ ïðåîáðàçîâàíèÿ íå÷åòêîé âåðîÿòíîñòè P1 â P3 ïî ôîðìóëå Im( ) Im ( ) Im( ) [ / , / ] [ , ] P P P a b a b3 1 2 0 1 1 1 2 2 � � �� ñ ôóíêöèåé ïðèíàäëåæíîñòè � �( ) ( / )p p p3 1 2� , p P1 1�dom (Im( )), p P2 2�dom (Im ( )), p P3 3�dom (Im ( )), çäåñü è äàëåå « » è «/» — ñèìâîëû íå÷åòêîãî è ÷åòêîãî äåëåíèÿ ñîîòâåòñòâåííî. Íå÷åòêèå âåðîÿòíîñòè Ð i n³ , , ,� 1 2 , íîðìàëèçóþòñÿ ïî ôîðìóëå Im( )Pi � � Im( ) Im( )P Pi , ïðè÷åì P Pi i n � � � � 1 1 (÷åòêàÿ åäèíèöà). ÍÅ×ÅÒÊÈÅ ÂÅÐÎßÒÍÎÑÒÍÛÅ ÏÎÒÅÍÖÈÀËÛ È ÎÏÅÐÀÖÈÈ ÍÀÄ ÍÈÌÈ Íå÷åòêèå âåðîÿòíîñòíûå ïîòåíöèàëû. Ðàñøèðåíèåì êëàññè÷åñêîãî ïîíÿòèÿ ðàñïðåäåëåíèÿ ÷åòêèõ âåðîÿòíîñòåé ÿâëÿåòñÿ ïîíÿòèå íå÷åòêîãî âåðîÿòíîñòíî- ãî ïîòåíöèàëà. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 139 Ïóñòü Õ X X X n� { , , , }1 2 — ìíîæåñòâî âåðîÿòíîñòíûõ ïåðåìåííûõ, îá- ëàñòü îïðåäåëåíèÿ êîòîðûõ åñòü ïîëíîå (èñ÷åðïûâàþùåå) ìíîæåñòâî âçàèìîèñ- êëþ÷àþùèõ ñîáûòèé. Äåêàðòîâî ïðîèçâåäåíèå îáëàñòåé îïðåäåëåíèé ïåðåìåííûõ ìíîæåñòâà Õ îáðàçóåò ïðîñòðàíñòâî åãî ñîñòîÿíèé dom ( )Õ , à õ Õ�dom ( ) — èí- ôîðìàöèîííîå ñîñòîÿíèå (äàëåå — ñîñòîÿíèå) àññîöèèðóåòñÿ ëèáî ñ óñëîâíî-çà- âèñèìûìè, ëèáî ñ ñîâìåñòíûìè ñîáûòèÿìè. Íå÷åòêèé âåðîÿòíîñòíûé ïîòåíöèàë (äàëåå, ãäå ýòî íå ïðèâîäèò ê äâóñìûñ- ëåííîñòè, — ïîòåíöèàë) — ýòî ôóíêöèÿ � : ( ) { }dom X Pi� ( , , ,i m� �1 2 � \| ( ) \| )dom X , ñòàâÿùàÿ â ñîîòâåòñòâèå êàæäîìó ñîñòîÿíèþ x X�dom ( ) ìíîæåñ- òâî íå÷åòêèõ âåðîÿòíîñòåé, dom dom( ) ( )� � X — îáëàñòü îïðåäåëåíèÿ ïîòåíöèà- ëà. Ïîòåíöèàë, îïðåäåëåííûé íàä ïðîñòðàíñòâîì ñîñòîÿíèé dom ( )X , îáû÷íî îá- îçíà÷àþò � X èëè �( )X . Åñëè ýëåìåíòû ïðîñòðàíñòâà ñîñòîÿíèé dom ( )X — ýòî óñëîâíî-çàâèñèìûå ñîñòîÿíèÿ, òî ïîòåíöèàë �( )X — ðàñïðåäåëåíèå óñëîâíûõ íå÷åòêèõ âåðîÿòíîñòåé, â ïðîòèâíîì ñëó÷àå îí îïðåäåëÿåò îáùåå ðàñïðåäåëåíèå íå÷åòêèõ âåðîÿòíîñòåé ïåðåìåííûõ ìíîæåñòâà Õ . Íàä íå÷åòêèìè âåðîÿòíîñòíûìè ïîòåíöèàëàìè, êàê è íàä ÷åòêèìè [6], îïðå- äåëåíû îïåðàöèè ñëîæåíèÿ, óìíîæåíèÿ, âû÷èòàíèÿ, ìàðãèíàëèçàöèè (ïðîåöèðî- âàíèÿ), ìàñøòàáèðîâàíèÿ è íîðìàëèçàöèè. Ïóñòü �1 è �2 — ïîòåíöèàëû, îïðåäåëåííûå íàä dom ( )Õ , Õ W , è dom ( )Y , Y W , ñîîòâåòñòâåííî, à z Õ Y� �dom ( ) , Õ Y W� (W — ìíîæåñòâî ïåðåìåí- íûõ), åñòü íåêîòîðîå ñîñòîÿíèå. Òîãäà ñóììà (ïðîèçâåäåíèå, ðàçíîñòü) ïîòåíöèà- ëîâ � �1 2� îïðåäåëÿåòñÿ ñóììîé (ïðîèçâåäåíèåì, ðàçíîñòüþ) íå÷åòêèõ âåðîÿò- íîñòåé äëÿ ñîîòâåòñòâóþùèõ ñîñòîÿíèé ïðîñòðàíñòâà dom ( )Õ Y� ñëåäóþùèì îáðàçîì: ( )( ) ( ) ( )� � � �1 2 1 2� � �z z zX Y , ãäå z X è zY — ïðîåêöèè z íà dom ( )Õ è dom ( )Y ñîîòâåòñòâåííî. Îòìåòèì, ÷òî ïåðåä ñëîæåíèåì (óìíîæåíèåì, âû÷èòàíèåì) ïîòåíöèàëîâ èõ îáëàñòè îïðåäåëåíèÿ ðàñøèðÿþòñÿ äî dom dom( ) ( )Z Õ Y� � , à ýëåìåíòàìè ýòèõ îáëàñ- òåé ñòàíîâÿòñÿ ñîñòîÿíèÿ z ïðîñòðàíñòâà dom ( )Z . Ïóñòü Õ — ìíîæåñòâî ïåðåìåííûõ, íàä êîòîðûìè îïðåäåëåí íå÷åòêèé âå- ðîÿòíîñòíûé ïîòåíöèàë �( )X , è ïóñòü W Õ . Òîãäà ðåçóëüòàò ìàðãèíàëèçàöèè �( )X íà W, îáîçíà÷àåìûé � �W X( ), áóäåò íå÷åòêèì âåðîÿòíîñòíûì ïîòåíöèà- ëîì, îïðåäåëåííûì íàä dom ( )W è âû÷èñëÿåìûì ïî îäíîé èç ôîðìóë � � � � � � � �W y X W WX W x y( ) ( ) ( , ) ( \ )dom , (1) � � � � � � �W y X W WX W x y( ) ( ) max ( , ) ( \ )dom , (2) ãäå ( , )x y XW �dom( ) . Îïåðàöèè ìàðãèíàëèçàöèè (1) è (2) ïîçâîëÿþò âû÷èñëèòü ïîòåíöèàë, îïðå- äåëåííûé íà ìíîæåñòâå, êîòîðîå ÿâëÿåòñÿ ïîäìíîæåñòâîì îáëàñòè îïðåäåëåíèÿ èñõîäíîãî ïîòåíöèàëà. Îíè èãðàþò âåñüìà âàæíóþ ðîëü â àëãîðèòìàõ ðàñïðîñ- òðàíåíèÿ äîâåðèÿ, â ÷àñòíîñòè, èñïîëüçóþòñÿ äëÿ âû÷èñëåíèÿ êîýôôèöèåíòà îá- íîâëåíèÿ äîâåðèÿ. Ëîêàëüíûå âû÷èñëåíèÿ ýòîãî êîýôôèöèåíòà ñ îïåðàöèåé sum-ìàðãèíàëèçàöèè ïîòåíöèàëîâ ïîçâîëÿþò íàõîäèòü àïîñòåðèîðíîå ðàñïðåäå- ëåíèå îòäåëüíî äëÿ êàæäîé ïåðåìåííîé âåðîÿòíîñòíîé ìîäåëè, à ñ îïåðàöèåé max-ìàðãèíàëèçàöèè — âû÷èñëèòü ýëåìåíò ïðîñòðàíñòâà ñîñòîÿíèé, èìåþùèé íàèáîëüøóþ íå÷åòêóþ âåðîÿòíîñòü, îäíîâðåìåííî äëÿ âñåõ ïåðåìåííûõ âåðîÿò- íîñòíîé ìîäåëè èëè ïîëó÷èòü îïòèìàëüíîå ðåøåíèå äëÿ ìîäåëè ïðèíÿòèÿ ðåøåíèé. 140 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 Ìàñøòàáèðîâàíèå ïîòåíöèàëîâ îñóùåñòâëÿåòñÿ òàê: ( )( ) ( ) ( ), ( ) , � � � � � 1 2 1 2 2 0 0 � �� z z z zX Y Yåñëè ãäå z X è zY ÿâëÿþòñÿ ïðîåêöèÿìè z íà dom ( )Õ è dom ( )Y ñîîòâåòñòâåííî. Íîðìàëèçàöèÿ ïîòåíöèàëà âûïîëíÿåòñÿ ñëåäóþùèì îáðàçîì: � � � �( ( )) ( ) ( ) ( ) X X x x X � � � dom . Ïîòåíöèàëû ðåøåíèé è îöåíêà ïîëåçíîñòè. Ïîòåíöèàë ðåøåíèÿ � — ýòî ñòðóêòóðíîå îáúåäèíåíèå íå÷åòêîãî âåðîÿòíîñòíîãî ïîòåíöèàëà �( , )X D è íå÷åòêîãî ïîòåíöèàëà ïîëåçíîñòè u X D( , ) : � �� { }( , ), ( , )X D u X D , ãäå X è D ñîîòâåòñòâåí- íî ìíîæåñòâà âåðîÿòíîñòíûõ ïåðåìåííûõ è ïåðåìåííûõ-ðåøåíèé, Z X D� � . Ïî- òåíöèàë ïîëåçíîñòè u — ýòî íå÷åòêèé ïîòåíöèàë, ñâÿçàííûé ñ ïåðåìåííîé-ðåøåíèåì (èëè åå ñëåäñòâèÿìè) è îöåíèâàþùèé ïîëåçíîñòü ïðèíèìàåìîãî ðåøåíèÿ. Îáùàÿ ïî- ëåçíîñòü ïðèíÿòûõ ðåøåíèé îöåíèâàåòñÿ ñóììîé êîíå÷íîãî ÷èñëà ëîêàëüíûõ ïîòåí- öèàëîâ ïîëåçíîñòè, ò.å. u X D u Zi i i k ( , ) ( )� � � 1 . Ïðîñòðàíñòâî dom ( )Z³ ñîñòîèò èç ñî- ñòîÿíèé òàêèõ ïîäìíîæåñòâ ïðîñòðàíñòâà dom dom( ) ( , )Z X D� , íà êîòîðûõ îïðå- äåëåíû ëîêàëüíûå ïîòåíöèàëû ïîëåçíîñòè u³ . Ïðîèçâåäåíèå � �1 2� ïîòåíöèàëîâ ðåøåíèé � �1 1 1� ( , )u è � �2 2 2� ( , )u , îïðåäåëåííûõ íàä dom ( )Z2 è dom ( )Z Z1 2� ñîîòâåòcòâåííî, âû÷èñëÿåòñÿ ñ ïî- ìîùüþ óìíîæåíèÿ è ñëîæåíèÿ íå÷åòêèõ âåðîÿòíîñòåé äëÿ ñîîòâåòñòâóþùèõ ñî- ñòîÿíèé èç dom ( )Z Z1 2� ïî ôîðìóëå � � � �1 2 1 2 1 2� � � �( ) ( ( ) ( ), ( ) ( ))Z Z Z u Z u Z , ãäå Z Z Z� �1 2 è õîòÿ áû îäèí èç ïîòåíöèàëîâ �1 èëè � 2 îïðåäåëåí (èëè ìîæåò áûòü ïðèâåäåí ê ýòîìó) íà dom ( )Z . Ìàñøòàáèðîâàíèåì ïîòåíöèàëà ðåøåíèé � �( ) ( ( ), ( ))Z Z u Z� , îïðåäåëåííîãî íàä dom ( )Z ñ ïîìîùüþ ïîòåíöèàëà ðåøåíèé � �( ) ( ( ), ( ))W W u W� , ÿâëÿåòñÿ ïî- òåíöèàë ðåøåíèé � * ( )Z , W Z , âû÷èñëÿåìûé ñ ïîìîùüþ ìàñøòàáèðîâàíèÿ è âû÷èòàíèÿ íå÷åòêèõ âåðîÿòíîñòåé äëÿ ñîîòâåòñòâóþùèõ ñîñòîÿíèé ïî ôîðìóëå � � � � � * ( ) ( ) ( ) ( ( ) ( ), ( ) ( ))Z Z W Z W u Z u W� � � , ãäå � �( ) ( )Z W � 0, åñëè �( )W � 0, à �( )W ïðè íåîáõîäèìîñòè ðàñøèðÿeòñÿ, ÷òî- áû èìåòü îáëàñòü îïðåäåëåíèÿ dom ( )Z äî âûïîëíåíèÿ ìàñøòàáèðîâàíèÿ. Îïåðàöèè ìàðãèíàëèçàöèè ïîòåíöèàëà ðåøåíèé ó÷èòûâàþò ñòðóêòóðó äàí- íîãî ïîòåíöèàëà. Ïóñòü ìíîæåñòâî ïåðåìåííûõ, íàä êîòîðûìè îïðåäåëåí ïîòåí- öèàë ðåøåíèé, óäîâëåòâîðÿåò óñëîâèþ W Z è ïóñòü � �( ) ( ( ), ( ))Z Z u Z� . Òîãäà ðåçóëüòàòîì sum-ìàðãèíàëèçàöèè �( )Z íà W áóäåò ïîòåíöèàë � �W Z( ), îïðåäåëåííûé íàä W è âû÷èñëÿåìûé ïî ôîðìóëå � � � � � � � � � �� W W W W y Z W WZ Z z y u z y u z y( ) ( ), ( , ) ( , ) ( , dom( \ ) ) y Z W� � � � �� dom( \ ) , ãäå ( , )z y ZW �dom ( ) . Òàêèì îáðàçîì, âåðîÿòíîñòíàÿ ÷àñòü ïîòåíöèàëà ðåøå- íèÿ ìàðãèíàëèçóåòñÿ îáû÷íûì ñïîñîáîì, òîãäà êàê îöåíêà ïîëåçíîñòè ìàðãè- íàëèçóåòñÿ ñ ïîìîùüþ âû÷èñëåíèÿ öåíòðà òÿæåñòè íå÷åòêèõ ïàðàìåòðîâ. Ðå- çóëüòàòîì max-ìàðãèíàëèçàöèè � �( ) ( ( ), ( ))Z Z u Z� íà W Z åñòü ïîòåíöèàë � �W Z( ) , îïðåäåëåííûé íàä W è âû÷èñëÿåìûé ïî ôîðìóëå � � � � � � � �� W W W WZ z y u z y z y( ) ( ( , ), ( )( , ) ( , )), ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 141 â äðóãèõ ñëó÷àÿõ, ãäå y� ìàêñèìèçèðóåò ( )( , )� � u z yW äëÿ êàæäîé ïðîåêöèè ñîñòîÿíèÿ y Z W�dom( \ ) , ò.å. y u z y y Z W W � � � �arg max ( )( , ) ( \ )dom � , z WW �dom ( ). Íîðìàëèçàöèÿ ñîñòàâíîãî ïîòåíöèàëà ðåøåíèÿ � Z âûïîëíÿåòñÿ ñ ïîìîùüþ íîðìàëèçàöèè êàæäîé åãî ÷àñòè: � � � � �( ( )) ( ( )), ( ( ))Z Z u Z� { }. ÂÅÐÎßÒÍÎÑÒÍÛÉ ÂÛÂÎÄ ÍÀ ÍÅ×ÅÒÊÈÕ ÑÅÒÅÂÛÕ ÌÎÄÅËßÕ ÄÎÂÅÐÈß Â îáùåì ñëó÷àå öåëü çàäà÷ âåðîÿòíîñòíîãî âûâîäà, ðåøàåìûõ â ïðîöåññå ìî- äåëèðîâàíèÿ íà íå÷åòêèõ ñåòåâûõ ìîäåëÿõ äîâåðèÿ, — óñòàíîâèòü, êàê èçìå- íÿþòñÿ íå÷åòêèå âåðîÿòíîñòè ïåðåìåííûõ ìîäåëè, åñëè èçâåñòíî, ÷òî íåêîòî- ðûå èç íèõ íàõîäÿòñÿ â îïðåäåëåííûõ ñîñòîÿíèÿõ. Îðèãèíàëüíûé ïîäõîä è ýôôåêòèâíûå àëãîðèòìû ðåøåíèÿ ýòîé NP-ñëîæíîé çàäà÷è èçëîæåíû â [8, 9]. Îòìåòèì äâà ýòàïà â ýòîì ïîäõîäå: òðàíñôîðìàöèþ èñõîäíîé ñåòè â ñòðóêòó- ðó òèïà «óçëîâîå äåðåâî» è ðåøåíèå íà íåì çàäà÷ âåðîÿòíîñòíîãî âûâîäà. Íå÷åòêèå áàéåñîâñêèå ñåòè è äèàãðàììû äîâåðèÿ. Áàéåñîâñêàÿ ñåòü N X G� ( , , )� íàçûâàåòñÿ íå÷åòêîé (ðèñ. 1, à), åñëè îíà ñîñòîèò èç: — àöèêëè÷åñêîãî îðãðàôà G V E� ( , ) ñ óçëàìè V n� { , , }� �1 è äóãàìè E V V� � ; — ìíîæåñòâà âåðîÿòíîñòíûõ ïåðåìåííûõ X , êîòîðûå ïðåäñòàâëåíû âåðøè- íàìè ãðàôà G; — ìíîæåñòâà íå÷åòêèõ âåðîÿòíîñòíûõ ïîòåíöèàëîâ �� {� � �( \| ( )X X pa1 1 � � � � � �( \| ( )X X n npa }, ïðåäñòàâëÿþùèõ àïðèîðíîå ðàñïðåäåëåíèå íå÷åòêèõ âåðî- ÿòíîñòåé (óñëîâíûõ èëè ìàðãèíàëüíûõ), çäåñü è äàëåå X pa( )� — ìíîæåñòâî ðî- äèòåëüñêèõ ïåðåìåííûõ äëÿ ïîäìíîæåñòâà ïåðåìåííûõ X X� � . Íå÷åòêàÿ ÄÂ (ÍÄÂ) — îäíî èç ñòðóêòóðíî-ôóíêöèîíàëüíûõ ðàñøèðåíèé íå÷åòêèõ ÁÑ (ÍÁÑ). Ôîðìàëüíî ÄÂ N X G U� ( , , , )� íàçûâàåòñÿ íå÷åòêîé, åñëè â åå îñíîâå ëåæèò íå÷åòêàÿ ÁÑ, äîïîëíåííàÿ ñëåäóþùèìè ýëåìåíòàìè: — ìíîæåñòâîì ïåðåìåííûõ ðåøåíèé D òàêèõ, ÷òî Z X D� � ïðåäñòàâëåíû âåðøèíàìè â G; — ìíîæåñòâîì ôóíêöèé ïîëåçíîñòè U , ñîäåðæàùèì ïî îäíîìó íå÷åòêîìó ïîòåíöèàëó ïîëåçíîñòè u X pa( )( )� äëÿ êàæäîãî óçëà â ïîäìíîæåñòâå îöåíî÷íûõ óçëîâ V VU � . Â íàñòîÿùåé ñòàòüå ðàññìîòðåíû ïåðåìåííûå ÍÁÑ è ÍÄÂ ñ äèñêðåòíûìè çíà÷åíèÿìè. Ãðàôè÷åñêè âåðøèíû ÄÂ èçîáðàæàþòñÿ â âèäå êðóãà (âåðîÿòíîñòíàÿ âåðøèíà), ïðÿìîóãîëüíèêà (âåðøèíà-ðåøåíèå) è ðîìáà (âåðøèíà — îöåíêà ïîëåçíîñòè èëè ðèñêà, ñîîòâåòñòâóþùàÿ ïîòåíöèàëó ïîëåçíîñòè). Ôóíêöèîíàëüíûå äóãè (çàêàí÷èâà- þùèåñÿ â âåðøèíàõ-îöåíêàõ) ïîêàçûâàþò âëèÿíèå ñîñòîÿíèé âåðîÿòíîñòíûõ âåðøèí 142 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 A B G I K C D FE L Ðèñ. 1. Ïðèìåðû ãðàôîâûõ ìîäåëåé ÍÁÑ (à) è ÍÄÂ (á) BA C GE D F D2 D1V1 K D3 V2 à á è âåðøèí-ðåøåíèé íà îöåíêó ïðèíèìàåìîãî ðåøåíèÿ. Èíôîðìàöèîííûå äóãè (çàêàí÷èâàþùèåñÿ â âåðøèíå-ðåøåíèè) óêàçûâàþò, ÷òî ðåøåíèå â êîíöå äóãè ïðèíèìà- åòñÿ íà îñíîâå ðàíåå èçâåñòíûõ ñîñòîÿíèé âñåõ âåðøèí â íà÷àëå ñîîòâåòñòâóþùèõ äóã. Óçëîâûå äåðåâüÿ è ìåòîäû èõ ïîñòðîåíèÿ. Íàèáîëåå ïðèíöèïèàëüíûé è ñëîæíûé øàã â ïðîöåññàõ òðàíñôîðìàöèè ÷åòêèõ èëè íå÷åòêèõ ñåòåé äîâåðèÿ — òðèàíãóëÿöèÿ ïåðâè÷íî ïðåîáðàçîâàííîãî ãðàôà (ìîðàëüíîãî ãðàôà). Ñîáñòâåííî ïîýòîìó ðàçðàáîòêà ýôôåêòèâíûõ àëãîðèòìîâ òðèàíãóëÿöèè, â òîì ÷èñëå ýâðèñ- òè÷åñêèõ, ïðè ïîñòðîåíèè èíòåëëåêòóàëüíûõ ñèñòåì, îñíîâàííûõ íà ãðàôîâûõ ìî- äåëÿõ, ÿâëÿåòñÿ ïî-ïðåæíåìó âåñüìà àêòóàëüíîé è íåòðèâèàëüíîé çàäà÷åé è â äàí- íîé ñòàòüå åé óäåëåíî îñîáîå âíèìàíèå. Äëÿ ñòðîãîñòè èçëîæåíèÿ è îäíîçíà÷íîãî ïîíèìàíèÿ ïðåæäå, ÷åì îïèñàòü ïðåäëîæåííûé àëãîðèòì òðàíñôîðìàöèè, ïðèâåäåì ñîãëàñíî [5] îïðåäåëåíèÿ íå- êîòîðûõ êëþ÷åâûõ ïîíÿòèé. Ãðàô G m íàçûâàåòñÿ ìîðàëüíûì, à ïðîöåññ åãî ñîçäàíèÿ — ìîðàëèçàöèåé, êîãäà îí ïîëó÷åí èç âõîäíîãî àöèêëè÷åñêîãî îðãðàôà ïîñëå âûïîëíåíèÿ ñëåäóþ- ùèõ äåéñòâèé: åñëè óçåë èìååò íåñêîëüêî ðîäèòåëüñêèõ óçëîâ, òîãäà âñå îíè ïî- ïàðíî ñîåäèíÿþòñÿ ðåáðàìè, ò.å. ðîäèòåëüñêèå óçëû «æåíÿòñÿ»; âñå äóãè âõîäíî- ãî ãðàôà çàìåíÿþòñÿ ðåáðàìè. Êëèêîé ÑU , çàäàííîé íàä ïîäìíîæåñòâîì âåðøèí U V , íàçûâàåòñÿ òàêîå ïîäìíîæåñòâî âåðøèí, â êîòîðîì îíè îáðàçóþò ïîëíûé ïîäãðàô ãðàôà G m . Ñåïàðàòîðîì S AB , ÿâëÿþùèìñÿ íàãðóçêîé äëÿ ðåáðà ìåæäó êëèêàìè ÑÀ è ÑÂ , íàçûâàåòñÿ êëèêà, çàäàííàÿ ïåðåñå÷åíèåì êëèê S Ñ ÑAB À Â� � . Äåðåâî íàçûâàåòñÿ óçëîâûì èëè ñîåäèíèòåëüíûì, åñëè åãî âåðøèíû — ýòî êëèêè è äëÿ ëþáûõ äâóõ êëèê: ÑÀ è ÑÂ , Ñ ÑÀ Â� , âûïîëíÿþòñÿ óñëîâèÿ Ñ ÑÀ Â� è Ñ ÑÂ À� , à òàêæå íà ïóòè ìåæäó ëþáîé ïàðîé êëèê ÑÀ è ÑÂ îáúåäè- íåíèå âñåõ ñåïàðàòîðîâ ñîäåðæèò ïåðåñå÷åíèå Ñ ÑÀ Â� . Óçëîâîå äåðåâî íàçûâàåòñÿ ñòðîãèì, åñëè îíî èìååò õîòÿ áû îäíó âåðøè- íó R, îòëè÷íóþ îò äðóãèõ âåðøèí è íàçûâàåìóþ ñòðîãèì êîðíåì, äëÿ êîòîðîé êàæäàÿ ïàðà ñìåæíûõ êëèê ÑÀ è ÑÂ â ýòîì äåðåâå (ãäå ÑÀ íàõîäèòñÿ áëèæå ê R, ÷åì ÑÂ ) èìååò ñëåäóþùåå ñâîéñòâî: ýëåìåíòû êëèêè ÑÂ ÷àñòè÷íî óïîðÿäî÷åíû òàê, ÷òî ýëåìåíòû ñåïàðàòîðà S AB ïðåäøåñòâóþò ýëåìåíòàì Ñ ÑÂ À\ . Ýòî ñâîé- ñòâî ãàðàíòèðóåò, ÷òî ìàêñèìàëüíî îæèäàåìàÿ ïîëåçíîñòü áóäåò ïîëó÷åíà ïîñëå ïðèìåíåíèÿ ê äåðåâó àëãîðèòìà ðàñïðîñòðàíåíèÿ äîâåðèÿ. ×àñòè÷íûé ïîðÿäîê íà ìíîæåñòâå âåðøèí íà÷àëüíîãî ãðàôà óñòàíàâëèâàåòñÿ âî âðåìÿ ïðîöåññà ïðå- îáðàçîâàíèÿ íà÷àëüíîãî ãðàôà â óçëîâîå äåðåâî. Êàæäàÿ âåðøèíà óçëîâîãî äåðå- âà ïîëó÷àåò èìÿ â ïðîöåññå ñîçäàíèÿ ñîîòâåòñòâóþùåé êëèêè. Ãðàô íàçûâàåòñÿ õîðäàëüíûì, åñëè â íåì êàæäûé öèêë ñ äëèíîé áîëåå 3 èìååò õîðäó. Ïîñêîëüêó ëþáîé ïðîñòîé öèêë â õîðäàëüíîì ãðàôå ÿâëÿåòñÿ òðåó- ãîëüíèêîì, òàêîé ãðàô åùå íàçûâàþò òðèàíãóëèðîâàííûì, à ïðîöåññ åãî ïîëó÷å- íèÿ — òðèàíãóëÿöèåé [5]. Òàêèì îáðàçîì, äëÿ ïðåîáðàçîâàíèÿ èñõîäíîãî ãðàôà G â êëàñòåðíîå äåðåâî íóæíî âûïîëíèòü ñëåäóþùóþ ïîñëåäîâàòåëüíîñòü òðàíñôîðìàöèé [1, 2, 5], à èìåííî îñóùåñòâèòü ìîðàëèçàöèþ ãðàôà G, ñîçäàâ ìîðàëüíûé ãðàô G m , òðèàí- ãóëÿöèþ ìîðàëüíîãî ãðàôà G m , ñîçäàâ õîðäàëüíûé ãðàô G H è äåêîìïîçèöèþ õîðäàëüíîãî ãðàôà íà êëèêè, à òàêæå ñîçäàòü ìíîæåñòâî ñåïàðàòîðîâ è, ñîåäèíèâ èìè êëèêè, îáðàçîâàòü óçëîâîå äåðåâî. Ðàññìîòðèì ïåðå÷èñëåííûå ýòàïû òðàíñôîðìàöèè íà ïðèìåðàõ ÍÁÑ è ÍÄÂ (ñì. ðèñ. 1). Äëÿ ïîñòðîåíèÿ ìîðàëüíîãî ãðàôà èç ÍÄÂ íåîáõîäèìî âûïîëíèòü ñëåäó- þùèå øàãè: 1) â ñîîòâåòñòâèè ñ âðåìåííûì ïîðÿäêîì ðàññìîòðåíèÿ âåðøèí-ðåøåíèé �, çàäàííîì äëÿ ÍÄÂ, äëÿ êàæäîé âåðøèíû-ðåøåíèÿ Di ñîçäàòü ìíîæåñòâî âåðîÿò- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 143 íîñòíûõ âåðøèí I i , íàçûâàåìîå èíôîðìàöèîííûì, ñîñòîÿùåå èç ðîäèòåëüñêèõ âåðøèí äëÿ Di ; 2) óäàëèòü ññûëêè, óêàçûâàþùèå íà âåðøèíû-ðåøåíèÿ; 3) äîáàâèòü ðåáðà äëÿ êàæäîé ïàðû óçëîâ ñ îáùèì ðåáåíêîì (â òîì ÷èñëå, åñëè îáùèé óçåë ÿâëÿåòñÿ âåðøèíîé-îöåíêîé); 4) çàìåíèòü äóãè ðåáðàìè; 5) èçúÿòü âåðøèíû-îöåíêè. Ïîñêîëüêó âåðøèíû-îöåíêè ìîãóò ïîðîæäàòü ìîðàëüíûå ðåáðà, ñëåäîâà- òåëüíî, âàæíî èõ óäàëÿòü ïîñëå ìîðàëèçàöèè. Äëÿ ÍÁÑ, ãäå ñóùåñòâóþò âåðøè- íû îäíîãî òèïà — âåðîÿòíîñòíîãî, âûïîëíÿþòñÿ òîëüêî øàãè 3 è 4. Â îñíîâå àëãîðèòìà òðèàíãóëÿöèè ìîðàëüíîãî ãðàôà ëåæèò èäåÿ ýëèìèíàöèè âåðøèíû (óäàëåíèå ïî îïðåäåëåííîìó ïðàâèëó) èç ãðàôà G m . Âî âðåìÿ ýëèìèíà- öèè âåðøèíà ìîðàëüíîãî ãðàôà G m óäàëÿåòñÿ, à ñàì ãðàô äîïîëíÿåòñÿ ðåáðàìè, êîòîðûå ïîïàðíî ñîåäèíÿþò âñå âåðøèíû, ñìåæíûå ñ óäàëÿåìîé. Òàêèå ðåáðà íà- çûâàþò õîðäàëüíûìè. Àëãîðèòì òðèàíãóëÿöèè ìîðàëüíîãî ãðàôà, ïîëó÷åííîãî èç ÍÄÂ, ïðåäóñìàòðèâàåò ïîñëåäîâàòåëüíóþ ýëèìèíàöèþ âåðøèí â ñîîòâåòñòâèè ñ âðåìåííûì ïîðÿäêîì �, ò.å. ñîîòâåòñòâóåò ïîñëåäîâàòåëüíîñòè èíôîðìàöèîííûõ ìíîæåñòâ è âåðøèí-ðåøåíèé I D I D D Ih h h h� � 1 1 1 0, , , , , , , ãäå 1 h n . Êà÷åñòâî è âðåìÿ ïðîâåäåíèÿ òðèàíãóëÿöèè ñóùåñòâåííî çàâèñÿò îò ýâðèñ- òè÷åñêîãî êðèòåðèÿ c( )� , ñ ïîìîùüþ êîòîðîãî îïðåäåëÿåòñÿ ïîðÿäîê ýëèìèíà- öèè âåðøèí. Êðèòåðèåì c( )� [1], íå çàâèñÿùèì îò èíòåðïðåòàöèè ñëó÷àéíûõ âå- ëè÷èí, ÿâëÿåòñÿ âûáîð âåðøèíû òàêèì îáðàçîì, ÷òîáû ÷èñëî äîïîëíèòåëüíûõ ðåáåð, êîòîðûå íåîáõîäèìî äîáàâèòü â ãðàô ïîñëå óäàëåíèÿ âåðøèíû, áûëî ìè- íèìàëüíûì. Òàêîé êðèòåðèé c( )� ïîçâîëÿåò ïîëó÷èòü õîðäàëüíûé ãðàô äëÿ ïðî- èçâîëüíîãî ìîðàëüíîãî ãðàôà. Ñîãëàñíî [10] îöåíêà âðåìåíè âûïîëíåíèÿ àëãî- ðèòìà òðèàíãóëÿöèè (íà îñíîâå ýëèìèíàöèè âåðøèíû) ñ ó÷åòîì ïðèìåíåíèÿ êðè- òåðèÿ c( )� , ò.å. çàâèñèìîñòü êîëè÷åñòâà îïåðàöèé â àëãîðèòìå îò n — êîëè÷åñòâà âåðøèí â ãðàôå, ðàâíà O n( )3 . Â ïðåäëîæåííîì ìîäèôèöèðîâàííîì àëãîðèòìå òðèàíãóëÿöèè èñïîëüçóþò- ñÿ ñëåäóþùèå îáîçíà÷åíèÿ: ne( )� — ìíîæåñòâî âåðøèí, ñìåæíûõ c âåðøèíîé � ; K� — ñâÿçíûé ïîäãðàô ãðàôà G m , ãäå K ne� � �� ( ); List( )K — ñïèñîê âñåõ K� , ò.å. List( ) { \| }K K Vi i� �� ; F� — êîëè÷åñòâî äîïîëíèòåëüíûõ ðåáåð, äîïîëíÿþ- ùèõ K� äî êëèêè Ñ� ; c K( )� — êðèòåðèé äëÿ âûáîðà K� , êîòîðîìó ñîîòâåòñòâóåò ìèíèìàëüíîå F� èëè íàèìåíüøåå ïðîñòðàíñòâî ñîñòîÿíèé âåðøèí, âõîäÿùèõ â åãî ñîñòàâ, â ñëó÷àå ðàâåíñòâà; k — ñðåäíåå êîëè÷åñòâî ðåáåð, èíöèäåíòíûõ âåðøèíàì â ãðàôå G m . Ìîäèôèöèðîâàííûé àëãîðèòì òðèàíãóëÿöèè (íà îñíîâå ýëèìèíèðîâàíèÿ âåðøèí) ñîñòîèò èç ïîäãîòîâèòåëüíûõ äåéñòâèé (ïðåïðîöåññèíãà) è îñíîâíîãî àëãîðèòìà. Àëãîðèòì ïðåïðîöåññèíãà. 1. Äëÿ êàæäîé âåðøèíû G m âû÷èñëèòü K� , F� , äîáàâèòü K� â ñïèñîê List( )K . 2. Îòñîðòèðîâàòü ñïèñîê List( )K . Ìîäèôèöèðîâàííûé àëãîðèòì òðèàíãóëÿöèè. 1. Âñå âåðøèíû íåíóìåðîâàíû, ñ÷åò÷èê âåðøèí ³ n� è ñ÷åò÷èê èíôîðìàöè- îííûõ ìíîæåñòâ j h� �1. 2. Ïîêà ñóùåñòâóþò íåíóìåðîâàííûå âåðøèíû: 2.1. Åñëè ñóùåñòâóåò I j �!, òî âûáðàòü èç List( )K òàêîå K� , ÷òî âåðîÿò- íîñòíàÿ âåðøèíà � �I j è âûïîëíÿåòñÿ êðèòåðèé ñ K( )� , èíà÷å âûáðàòü âåðøè- íó-ðåøåíèå � � �D j 1 è óìåíüøèòü j íà åäèíèöó. 2.2. Îòìåòèòü âûáðàííóþ âåðøèíó íîìåðîì ³, ò.å. � �i � . 2.3. Ñîçäàòü êëèêó Ñ³ , ñîñòîÿùóþ èç � i è åå íåíóìåðîâàííûõ ñîñåäåé. 144 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 2.4. Óäàëèòü K� èç ñïèñêà List( )K è óìåíüøèòü ³ íà åäèíèöó. 2.5. Ïîâòîðèòü äëÿ êàæäîãî äîïîëíèòåëüíîãî ðåáðà F s t� � ( , ): 2.5.1. Äîáàâèòü ðåáðî ( , )s t â Ks, âû÷èñëèòü Fs. 2.5.2. Äîáàâèòü ðåáðî ( , )s t â Kt , âû÷èñëèòü Ft . 2.5.3. Äëÿ êàæäîé âåðøèíû r ne s� ( ): åñëè t Kr� , òî äîáàâèòü ðåáðî ( , )s t â Kr , âû÷èñëèòü Fr . 2.5.4. Äëÿ êàæäîé âåðøèíû r ne t� ( ): åñëè s Kr� , òî äîáàâèòü ðåáðî ( , )s t â Kr , âû÷èñëèòü Fr ; 2.6. Óäàëèòü ñòàðûå ýëåìåíòû K K Ks t r, , èç ñïèñêà List( )K . 2.7. Âñòàâèòü, ñîõðàíÿÿ ñïèñîê List( )K îòñîðòèðîâàííûì, íîâûå ýëåìåíòû K K Ks t r, , . Ñ êàæäîé êëèêîé óçëîâîãî äåðåâà ñâÿçàí ëèíåéíûé ñïèñîê ListName, ýëå- ìåíòàìè êîòîðîãî ÿâëÿþòñÿ íàèìåíîâàíèÿ âåðøèí íà÷àëüíîãî ãðàôà (íîìåð âåð- øèíû, ïîëó÷åííûé ïîñëå òðàíñôîðìàöèè íà÷àëüíîãî ãðàôà â óçëîâîå äåðåâî, è ñòðîêîâîå èìÿ âåðøèíû), âõîäÿùèõ â ñîñòàâ ñîîòâåòñòâóþùåé êëèêè. Àëãîðèòìè÷åñêè äëÿ èìåíîâàíèÿ êëèêè óçëîâîãî äåðåâà (ïîñëå âûïîëíåíèÿ àë- ãîðèòìà òðèàíãóëÿöèè) íóæíî: 1) óïîðÿäî÷èòü ñïèñîê ListName ïî óáûâàíèþ íîìåðîâ âåðøèí; 2) èäåíòèôèêàòîðó êëèêè ïðèñâîèòü íîìåð ïåðâîé âåðøèíû èç ñïèñêà ListName, êîòîðûé ÿâëÿåòñÿ óíèêàëüíûì, ÷òî ñëåäóåò èç àëãîðèòìà òðèàíãóëÿöèè; 3) ñîçäàòü ñòðîêîâîå èìÿ êëèêè êàê ðåçóëüòàò êîíêàòåíàöèè ñòðîêîâûõ èìåí èç ñïèñêà ListName. Îòìåòèì, ÷òî âû÷èñëèòåëüíàÿ ñëîæíîñòü ìîäèôèöèðîâàííîãî àëãîðèòìà òðèàíãóëÿöèè âñåãäà íèæå ñëîæíîñòè îðèãèíàëüíîãî àëãîðèòìà O n( )3 ñ àíàëî- ãè÷íûì êðèòåðèåì c( )� [1]. Äëÿ òðèàíãóëÿöèè ìîðàëüíîãî ãðàôà, ïîëó÷åííîãî èç ÍÁÑ, ïðèìåíÿåòñÿ àëãîðèòì òðèàíãóëÿöèè, ïðèâåäåííûé âûøå, â êîòîðîì íåò øàãà ñ âûáîðîì âåðøèíû-ðåøåíèÿ. Ìíîæåñòâî êëèê, ñîçäàííûõ íà ýòàïå òðèàíãóëÿöèè ìîðàëüíîãî ãðàôà, ïî- ðîæäàåò óçëîâîå äåðåâî ñ ïîìîùüþ ñëåäóþùåãî àëãîðèòìà (çäåñü è äàëåå îïåðà- öèÿ «èìÿ " âûðàæåíèå» îáîçíà÷àåò íàèìåíîâàíèå ðåçóëüòàòà, ïîëó÷åííîãî â õîäå âû÷èñëåíèÿ âûðàæåíèÿ): 1. Ñîçäàòü â ñîîòâåòñòâèè ñ ïîðÿäêîì ýëèìèíàöèè âåðøèí ïîäïîñëåäîâà- òåëüíîñòü Ñ � ( , , , )Ñ Ñ Ñn1 2 ; i n" — ñ÷åò÷èê êëèê èç ïîñëåäîâàòåëüíîñòè Ñ . 2. Ïîâòîðèòü äëÿ êàæäîé êëèêè Ci , i n�1 2, , ,� : 2.1. Ñîçäàòü ìíîæåñòâî ñåïàðàòîðîâ S C Cij i j" � , ãäå j i� �1 2 1, , , . 2.2. Ñðåäè ñîçäàííûõ ñåïàðàòîðîâ âûáðàòü ñåïàðàòîð S iq , êîòîðûé ñîäåð- æèò íàèáîëüøåå êîëè÷åñòâî âåðøèí. 2.3. Ñîåäèíèòü êëèêè C Ci q� . Â ïîëó÷åííîì óçëîâîì äåðåâå óäàëÿþòñÿ êëèêè, êîòîðûå ÿâëÿþòñÿ ïîäìíî- æåñòâàìè äðóãèõ êëèê. Êîðåíü óçëîâîãî (ñòðîãîãî) äåðåâà, ïîñòðîåííîãî íà îñíîâå ÍÄÂ, — êëèêà ñ íàèìåíüøèì íîìåðîì, à óçëîâîãî äåðåâà, ïîëó÷åííîãî íà îñíîâå ÍÁÑ, — ïðîèçâîëüíàÿ êëèêà â íåì. Íà ðèñ. 2 ïîêàçàíî ñòðîãîå óçëîâîå äåðåâî äëÿ ÍÁÑ è ÍÄÂ (ñì. ðèñ. 1). ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 145 I D E G B G D A B K G I B C A G D F B KL G I K G D B E I G B G D A K G I K B Ðèñ. 2. Ñòðîãîå óçëîâîå äåðåâî, ïîëó÷åííîå äëÿ ÍÁÑ (à) è ÍÄÂ (á) D2D1AB FD2B D2B F CED2AD1 FB GD3FB GF GDBKGD4F GB à á ÀËÃÎÐÈÒÌÛ ÐÀÑÏÐÎÑÒÐÀÍÅÍÈß ÄÎÂÅÐÈß Âñå ìíîãîîáðàçèå ðåøàåìûõ çàäà÷ âåðîÿòíîñòíîãî âûâîäà íà ÍÁÑ ìîæíî ñôîðìèðîâàòü â âèäå ñëåäóþùèõ òèïîâ çàïðîñîâ [1]: 1) âû÷èñëèòü àïîñòåðèîðíîå ðàñïðåäåëåíèå íå÷åòêèõ âåðîÿòíîñòåé äëÿ êàæäîé ïåðåìåííîé ÍÁÑ ñ ó÷åòîì ñâèäåòåëüñòâ (ïåðåìåííûõ ñ èçâåñòíûìè ñîñòîÿíèÿìè); 2) âû÷èñëèòü íàèáîëåå âåðîÿòíîå îáùåå ñîñòîÿíèå âñåõ ïåðåìåííûõ ñåòåâîé ìîäåëè, êîòîðîå íàèëó÷øèì îáðàçîì îáúÿñíÿåò íàëè÷èå ñâèäåòåëüñòâ. Çàäà÷è ëîãèêî-âåðîÿòíîñòíîãî âûâîäà íà ÍÄÂ ñâîäÿòñÿ ê îïòèìèçàöèîííîé çàäà÷å ïîèñêà îïòèìàëüíîãî ðåøåíèÿ ñ ó÷åòîì ñîñòîÿíèé ïåðåìåííûõ. Îòâåòîì íà ýòè çàïðîñû ÿâëÿåòñÿ ðåçóëüòàò ïðèìåíåíèÿ àëãîðèòìà ðàñïðîñòðàíåíèÿ äîâå- ðèÿ (ÀÐÄ), èñïîëüçóþùèé óçëîâîå äåðåâî â êà÷åñòâå èñõîäíîé ñòðóêòóðû. Â îñíîâó ÀÐÄ ïîëîæåíû àðõèòåêòóðíûå ïðèíöèïû [9, 11, 12], îäíàêî íåêî- òîðîå ïðåäïî÷òåíèå [13] îòäàíî àðõèòåêòóðå HUGIN [12]. Îáùèì ïðèíöèïîì ýòèõ àðõèòåêòóð åñòü ñõåìà äâóõýòàïíîãî âû÷èñëåíèÿ: ïåðâûé ýòàï — íàêîïëå- íèå ñâèäåòåëüñòâ, è âòîðîé — èõ ðàñïðîñòðàíåíèå. Ôóíêöèîíèðîâàíèå ÀÐÄ íà- ÷èíàåòñÿ ñ âûáîðà êîðíÿ R â óçëîâîì äåðåâå: äëÿ äåðåâà, ïîñòðîåííîãî íà îñíîâå ÍÁÑ, êîðåíü — ïðîèçâîëüíàÿ êëèêà; äëÿ äåðåâà, ïîñòðîåííîãî íà îñíîâå ÍÄÂ, — êëèêà, ñîäåðæàùàÿ ïåðåìåííóþ ñ íàèìåíüøèì íîìåðîì â ýëèìèíàöèîííîé ïîñëå- äîâàòåëüíîñòè #. Ïîòåíöèàë êàæäîé êëèêè èíèöèàëèçèðóåòñÿ ëèáî ïðîèçâåäåíèåì ïîòåíöèàëîâ, îáëàñòè îïðåäåëåíèÿ êîòîðûõ ÿâëÿþòñÿ ïîäìíîæåñòâàìè êëèêè, ëèáî îáúåäèíåíèåì òàêèõ ïîòåíöèàëîâ â ìíîæåñòâî. Â ïîñëåäíåì ñëó÷àå èõ ïðîèçâåäå- íèÿ âû÷èñëÿþòñÿ âî âðåìÿ âûïîëíåíèÿ ÀÐÄ. Ïîñëå âûáîðà êîðíÿ â óçëîâîì äåðåâå îñóùåñòâëÿþòñÿ ðåêóðñèâíûå âû÷èñëåíèÿ îò ëèñòüåâ äåðåâà ê êîðíþ (ýòàï íàêîïëå- íèÿ ñâèäåòåëüñòâ) è îò êîðíÿ ê ëèñòüÿì äåðåâà (ýòàï ðàñïðîñòðàíåíèÿ ñâèäåòåëüñòâ). Ïðèìåíÿÿ ðåêóðñèâíîå îïèñàíèå ýòàïîâ âû÷èñëåíèé, íàêîïëåíèå ñâèäåòåëüñòâ ìîæíî ðåàëèçîâàòü ñ ïîìîùüþ àëãîðèòìà ïîèñêà â «ãëóáèíó» [15], à ðàñïðîñòðàíåíèå — àë- ãîðèòìà ïîèñêà â «øèðèíó» [15]. Âûïîëíåíèå ÀÐÄ îñóùåñòâëÿåòñÿ êàê äëÿ ñåòåâîé ìîäåëè ñ àïðèîðíûìè ÷èñëîâûìè ïàðàìåòðàìè, òàê è ïðè íàëè÷èè ñâèäåòåëüñòâ (àïîñòåðèîðíûé âûâîä). Â ïîñëåäíåì ñëó÷àå èçìåíÿþòñÿ òîëüêî îöåíêè ñîñòîÿíèé, ïîðÿäîê âûïîëíåíèÿ ÀÐÄ îñòàåòñÿ ïðåæíèì. Îòìåòèì, ÷òî ÀÐÄ äëÿ ÍÄÂ îñóùåñòâëÿåòñÿ òîëüêî äëÿ ñáîðà ñâèäåòåëüñòâ ñ ó÷åòîì âðåìåííîãî ïîðÿäêà � ïðèíÿòèÿ ðåøåíèé äëÿ ÍÄÂ è ïîëó÷åííîé äëÿ íåå ýëèìèíàöèîííîé ïîñëåäîâàòåëüíîñòè #. Ðåçóëüòàòîì ïðèìåíåíèÿ ÀÐÄ ê ÍÄÂ ÿâëÿåòñÿ îïòèìàëüíàÿ ïîëèòèêà ïðèíÿòèÿ ðåøåíèé. Îáùèé ôóíêöèîíàëüíî-àðõèòåêòóðíûé ïðèíöèï ÀÐÄ — íàëè÷èå êëþ÷åâîãî ìå- õàíèçìà (ïðîöåäóðû) îáíîâëåíèÿ äîâåðèÿ (ïåðåäà÷è ñîîáùåíèÿ), àêòèâíî èñïîëüçóþ- ùåãîñÿ íà îáîèõ ýòàïàõ äëÿ îáíîâëåíèÿ íå÷åòêèõ ïîòåíöèàëîâ íà îñíîâå ïîòåíöèàëîâ ñìåæíûõ êëèê. Ïðèíöèïèàëüíîå îòëè÷èå àðõèòåêòóðû HUGIN îò äâóõ äðóãèõ àðõèòåêòóð ñ âû÷èñëèòåëüíîé òî÷êè çðåíèÿ ñîñòîèò â òîì, ÷òî äëÿ ïåðåäà÷è ñîîáùåíèÿ âûïîëíÿåòñÿ îïåðàöèÿ äåëåíèÿ íå÷åòêèõ ïîòåíöèàëîâ, îïðåäåëåííûõ íàä ñåïàðàòîðàìè óçëîâîãî äåðåâà. Ðàññìîòðèì ïðîöåäóðó ïåðåäà÷è ñîîáùåíèÿ íà ïðèìåðå óçëîâîãî äåðåâà (ðèñ. 3, á). Ïóñòü ïðîöåäóðà ìàðãèíàëèçàöèè ïîòåíöèàëà � �Y X( ), ãäå Y X , dom dom( ) ( )� � X . Ïåðåäà÷à ñîîáùåíèÿ îò êëèêè Ñ X Y1 � { , } ê êëèêå Ñ Y W2 � { , } âûïîëíÿåòñÿ c ïî- ìîùüþ ñëåäóþùåãî àëãîðèòìà. 1. Âû÷èñëèòü ìàðãèíàëüíîå ðàñïðåäåëåíèå � � * ( ) ( )Y CY" � 1 . 2. Âû÷èñëèòü êîýôôèöèåíò îáíîâëåíèÿ äîâåðèÿ � � � * * ( ) ( ) ( ) Y Y Y " , ãäå �( )Y — íå÷åòêèé ïîòåíöèàë ñåïàðàòîðà S Y� { }, �( )Y $1. 146 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 Ðèñ. 3. Ïðîñòàÿ ÍÁÑ (à) è ñî- îòâåòñòâóþùåå åé óçëîâîå äåðåâî (á) X Y W XY Y YW à á 3. Âû÷èñëèòü îáíîâëåííûé ïîòåíöèàë êëèêè � � �new ( ) ( ) ( )C C Y2 2" � . Ïåðåäà÷à ñîîáùåíèÿ â îáðàòíîì ïîðÿäêå — îò êëèêè Ñ Y W2 � { , } ê êëèêå Ñ X Y1 � { , } âûïîëíÿåòñÿ àíàëîãè÷íî. 1. Âû÷èñëèòü ìàðãèíàëüíîå ðàñïðåäåëåíèå � � * ( ) ( )Y CY" � new 2 . 2. Âû÷èñëèòü êîýôôèöèåíò îáíîâëåíèÿ äîâåðèÿ � � � * ( ) ( ) ( ) Y Y Y " . 3. Âû÷èñëèòü îáíîâëåííûé ïîòåíöèàë êëèêè � � �new ( ) ( ) ( )*C C Y2 2" � . Â ðåçóëüòàòå ïðîâåäåííûõ âû÷èñëåíèé ìàðãèíàëüíîå ðàñïðåäåëåíèå íå÷åò- êèõ âåðîÿòíîñòåé äëÿ Õ îïðåäåëÿåòñÿ íà îñíîâå ðàñïðåäåëåíèÿ ñîâìåñòíûõ íå- ÷åòêèõ âåðîÿòíîñòåé � ( )C1 , äëÿ W — íà îñíîâå � * ( )C2 , äëÿ Y — íà îñíîâå � * ( )C1 , � * ( )C2 èëè � ** ( )Y . Åñëè � �Y X( ) — îïåðàöèÿ sum-ìàðãèíàëèçàöèè, òî ðåçóëüòàòîì ïðèìåíåíèÿ ÀÐÄ ê ÍÁÑ èëè ÍÄÂ áóäåò îòâåò íà ïåðâûé òèï çàïðî- ñà. Åñëè � �Y X( ) — îïåðàöèÿ max-ìàðãèíàëèçàöèè, òî ðåçóëüòàòîì ïðèìåíåíèÿ ÀÐÄ ê ÍÁÑ áóäåò îòâåò íà âòîðîé òèï çàïðîñà. Ïðîöåäóðà ïåðåäà÷è ñîîáùåíèÿ îñíîâàíà íà äâóõ îïåðàöèÿõ ñ íå÷åòêèìè ïî- òåíöèàëàìè: óìíîæåíèå è ìàðãèíàëèçàöèÿ ïîòåíöèàëîâ. ×òîáû óâåëè÷èòü ýôôåê- òèâíîñòü âûïîëíåíèÿ ìàðãèíàëèçàöèè ïîòåíöèàëà êëèêè, ïðèìåíÿþòñÿ ðàçëè÷íûå ýâðèñòè÷åñêèå ïîäõîäû, îïèñàííûå, íàïðèìåð, â [7]. Â íàñòîÿùåé ðàáîòå äëÿ ýòîé öåëè ïðåäëîæåí ìîäèôèöèðîâàííûé îáîáùåííûé àëãîðèòì ýëèìèíàöèè âåðøè- íû, èñïîëüçóþùèé ìîäèôèöèðîâàííûé àëãîðèòì òðèàíãóëÿöèè è ïðèìåíÿåìûé êàê ê ÍÁÑ, òàê è ê ÍÄÂ. Ïðè ýòîì ââåäåíû ñëåäóþùèå îáîçíà÷åíèÿ: �— îáúåäè- íåíèå ìíîæåñòâ íå÷åòêèõ âåðîÿòíîñòíûõ ïîòåíöèàëîâ è ïîòåíöèàëîâ ïîëåçíîñ- òåé, îïðåäåëåííûõ íàä êëèêîé Ñ, ñîñòîÿùåé èç n âåðøèí; Z — ìíîæåñòâî ïåðå- ìåííûõ, äëÿ êîòîðûõ âû÷èñëÿåòñÿ ìàðãèíàëüíîå ðàñïðåäåëåíèå íå÷åòêèõ âåðî- ÿòíîñòåé; G( )� — ãðàô, ñîîòâåòñòâóþùèé ðàñïðåäåëåíèþ îáùèõ íå÷åòêèõ âåðîÿòíîñòåé � � � ( )C u u � � � % � � � , ãäå � — âåðîÿòíîñòíûå ñîñòàâíûå, u — îöåíî÷- íûå ñîñòàâíûå ïîòåíöèàëà-ðåøåíèé. Ïðèâåäåì ìîäèôèöèðîâàííûé îáîáùåííûé àëãîðèòì ýëèìèíàöèè âåðøèíû. 1. Äëÿ êëèêè Ñ ñîçäàòü ãðàô G( )� . 2. Âûïîëíèòü ìîðàëèçàöèþ ãðàôà, ÷òîáû ñîçäàòü ìîðàëüíûé ãðàô G m ( )� . 3. Âûïîëíèòü ìîäèôèöèðîâàííûé àëãîðèòì òðèàíãóëÿöèè ãðàôà G m ( )� : ðå- çóëüòàò — ýëèìèíàöèîííûé ïîðÿäîê . 4. Óïîðÿäî÷èòü â # âåðîÿòíîñòíûå ïåðåìåííûå â ãðàíèöàõ èíôîðìàöèîí- íûõ ìíîæåñòâ, êîòîðûì îíè ïðèíàäëåæàò, â ñîîòâåòñòâèè ñ ïîðÿäêîì ïîëó÷èòü íîâûé ïîðÿäîê &# . 5. Âû÷èñëèòü îöåíî÷íûé ïîòåíöèàë êëèêè Ñ u u C u : " � � � . 6. Ïîâòîðèòü äëÿ êàæäîé ïåðåìåííîé Y C Z� \ â ñîîòâåòñòâèè ñ ïîðÿäêîì &# : 6.1. Ñîçäàòü ìíîæåñòâî ïîòåíöèàëîâ �Y CY u� � �{ \| ( ) }� �dom . 6.2. Âû÷èñëèòü, åñëè Y âåðîÿòíîñòíàÿ ïåðåìåííàÿ, � � � Y C y Y u" � �� %� �dom(Y) , èíà÷å (åñëè Y — ïåðåìåííàÿ-ðåøåíèå) � � � Y y Y C Y u" � � � %max � . 6.3. Èçìåíèòü ìíîæåñòâî ïîòåíöèàëîâ � � �" �\ { }Y Y� . 7. Âû÷èñëèòü ìàðãèíàëüíûé ïîòåíöèàë � � � ( )Z " � % � . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 147 Ïîñêîëüêó ÍÁÑ ñîäåðæàò òîëüêî âåðîÿòíîñòíûå âåðøèíû, ïðèâåäåííûé âûøå àëãîðèòì ïðèìåíÿåòñÿ ê íèì ñ òàêèìè óïðîùåíèÿìè: — îòñóòñòâóþò øàãè 4 è 5; — øàã 6 âûïîëíÿåòñÿ òîëüêî â ñîîòâåòñòâèè ñ ýëèìèíàöèîííûì ïîðÿäêîì , ïîëó÷åííûì íà øàãå 3; — íà øàãå 6.1 ñîçäàåòñÿ ìíîæåñòâî òîëüêî èç âåðîÿòíîñòíûõ ïîòåíöèàëîâ; — øàã 6.2 âûïîëíÿåò âû÷èñëåíèå äëÿ âåðîÿòíîñòíîãî ïîòåíöèàëà ïî ôîðìó- ëå � � � Y y Y " �� %� �dom Y)( . Îïèñàííûé ïîõîä ÿâëÿåòñÿ âûñîêî ýôôåêòèâíûì óæå â òîì ñëó÷àå, êîãäà êëè- êè óçëîâîãî äåðåâà èíèöèàëèçèðóþòñÿ áîëåå ÷åì òðåìÿ íå÷åòêèìè ïîòåíöèàëàìè. ÀÐÕÈÒÅÊÒÓÐÍÛÅ ÀÑÏÅÊÒÛ ÈÍÔÎÐÌÀÖÈÎÍÍÎÉ ÒÅÕÍÎËÎÃÈÈ ÂÅÐÎßÒÍÎÑÒÍÎÃÎ ÌÎÄÅËÈÐÎÂÀÍÈß ÑÎÑÒÎßÍÈß ÑËÎÆÍÛÕ ÑÈÑÒÅÌ ÍÀ ÁÀÇÅ ÍÅ×ÅÒÊÈÕ ÑÅÒÅÂÛÕ ÌÎÄÅËÅÉ Äëÿ àâòîìàòèçàöèè ýòàïîâ ìîäåëèðîâàíèÿ íà ÍÁÑ è ÍÄÂ äàëåå ïðåäëîæåíà ïîñëîéíàÿ àðõèòåêòóðà ïðîãðàììíîé ñèñòåìû (òàáë. 1). Ìåõàíèçì îáìåíà äàí- íûìè ìåæäó êîìïîíåíòàìè ñèñòåìû ñïðîåêòèðîâàí ñîãëàñíî ìîäåëüíî-îðèåí- òèðîâàííîìó ïîäõîäó è ðåàëèçóåòñÿ ñ ïîìîùüþ îáìåíà ìåòàäàííûìè ìåæäó ïîäñèñòåìàìè. Òàêèì îáðàçîì, ñòðóêòóðà êëàññîâ ñèñòåìû äåëèòñÿ íà ÷åòûðå ñëîÿ: îñíîâà, ðåñóðñ, ìåõàíèçì âûâîäà, óïðàâëåíèå. Îñíîâà ñîñòîèò èç êëàññîâ, ïîääåðæèâàþùèõ ñïåöèôèêàöèþ áàçîâûõ ñòðóê- òóðíûõ ýëåìåíòîâ, êîòîðûå èñïîëüçóþòñÿ êëàññàìè âåðõíèõ óðîâíåé. Â ýòîò ñëîé âõîäÿò êëàññû, ïðåäñòàâëÿþùèå âåðøèíû, äóãè, ðåáðà îðãðàôà è óçëîâîãî äåðåâà, íå÷åòêèå âåðîÿòíîñòíûå ïîòåíöèàëû âåðøèí, èíäåêñû ñîñòîÿíèé â ïî- òåíöèàëàõ è âåêòîðû êëþ÷åé äëÿ óñòàíîâëåíèÿ ñîîòâåòñòâèÿ ìåæäó îáëàñòÿìè îïðåäåëåíèÿ ïåðåìíîæàåìûõ ïîòåíöèàëîâ. Ðåñóðñ ñîñòîèò èç êëàññîâ, ïðåäíàçíà÷åííûõ äëÿ îïèñàíèÿ èíôîðìàöèîííûõ èñòî÷íèêîâ, ïðåäñòàâëåííûõ â ôîðìàòå ñòàíäàðòà PMML, èñïîëüçóþùèì XML-ôîðìàò äëÿ îïèñàíèÿ ìîäåëåé äàííûõ, è áàçû äàííûõ, ðîáîòà ñ êîòîðîé îðãàíèçóåòñÿ ñðåäñòâàìè òåõíîëîãèè ADO. Â ïðîöåññå âûçîâà ìåòîäà çàïèñè ÍÁÑ èëè ÍÄÂ ïðîâåðÿþòñÿ ñîîòâåòñòâóþùèå íàñòðîéêè íà íåîáõîäèìîñòü èçìå- íåíèÿ âíóòðåííåãî ôîðìàòà äàííûõ ñèñòåìû â ôîðìàò, èñïîëüçóåìûé âíåøíåé ñèñòåìîé. Ïåðåä èçìåíåíèåì ôîðìàòà íàä äàííûìè âûïîëíÿåòñÿ ðÿä òðàíñôîð- ìàöèé: äåôàççèôèêàöèÿ, íîðìàëèçàöèÿ, îòîáðàæåíèå äèñêðåòíûõ çíà÷åíèé èç îäíîé øêàëû â äðóãóþ. Â ïðîöåññå ñ÷èòûâàíèÿ ÍÁÑ èëè ÍÄÂ âûïîëíÿåòñÿ îá- ðàòíîå èçìåíåíèå ôîðìàòîâ è ïðîâåðêà íà íåîáõîäèìîñòü òðàíñôîðìàöèè äàí- íûõ — äèñêðåòèçàöèè, ôàççèôèêàöèè [16], íîðìàëèçàöèè, îòîáðàæåíèÿ äèñêðåò- íûõ çíà÷åíèé èç îäíîé øêàëû â äðóãóþ. Ìåõàíèçì âûâîäà ñîñòîèò èç òðàíñôîðìàöèè, àëãîðèòìà, èíôîðìàöèîííîé âèçóàëèçàöèè. Ýòîò ñëîé ÿâëÿåòñÿ îñíîâíîé ÷àñòüþ áèçíåñ-ëîãèêè ñèñòåìû, ïîý- 148 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 Ò à á ë è ö à 1. Ïîñëîéíàÿ àðõèòåêòóðà ïðîãðàììíîé ñèñòåìû Ñëîé Ôóíêöèè àðõèòåêòóðíûõ ñëîåâ ïðîãðàììíîé ñèñòåìû Óïðàâëåíèå Ñîçäàíèå, ÷òåíèå, çàïèñü ÍÁÑ èëè ÍÄÂ Ìåõàíèçì âûâîäà Òðàíñôîðìàöèÿ (ìîäåëü, íàñòðîéêà) Àëãîðèòìû ðàñïðîñòðàíåíèÿ äîâåðèÿ Èíôîðìàöèîííàÿ âèçóàëèçàöèÿ Ðåñóðñ XML-ðåñóðñ Áàçà äàííûõ (òåõíîëîãèÿ ÀDÎ) Îñíîâà Âåðøèíû îðãðàôà è óçëîâîãî äåðåâà Äóãè ÍÁÑ, ÍÄÂ, ðåáðà óçëîâîãî äåðåâà Ñåïàðàòîðû óçëîâîãî äåðåâà Ïîòåíöèàëû òîìó êàæäàÿ åãî ñîñòàâëÿþùàÿ èìååò ñëîæíóþ ñòðóêòóðó. Êëàññû, êîòîðûå ïðè- íàäëåæàò òðàíñôîðìàöèè, êîíöåïòóàëüíî îáúåäèíÿþò äâå îáëàñòè: ìîäåëü è íà- ñòðîéêó. Ïåðâàÿ ñîñòîèò èç êëàññîâ, ïðåäñòàâëÿþùèõ ìåòàäàííûå, êîòîðûå îïè- ñûâàþò íàáîð âõîäíûõ àòðèáóòîâ äëÿ ïîñòðîåíèÿ ãðàôà, ïðîöåäóðû åãî êîíñòðóèðîâàíèÿ, ðåçóëüòàò ñîîòâåòñòâóþùåãî ýòàïà òðàíñôîðìàöèè, ïðîöåäóðû ïðîâåðêè êîððåêòíîñòè ìîäåëè. Îñíîâíûì êëàññîì ïàêåòà àëãîðèòì ÿâëÿåòñÿ ÀÐÄ, ñîäåðæàùèé îïèñàíèå ïðîöåäóðû ðàñïðîñòðàíåíèÿ äîâåðèÿ â óçëîâîå äåðå- âî. Èñïîëüçóÿ íàñòðîéêè, çàäàííûå ïîëüçîâàòåëåì (âèä ìàðãèíàëèçàöèè, íàëè÷èå ñâèäåòåëüñòâ), âûïîëíÿåòñÿ àëãîðèòì âåðîÿòíîñòíîãî âûâîäà. Ê èíôîðìàöèîííîé âèçóàëèçàöèè ïðèíàäëåæàò ñëåäóþùèå êëàññû: — ïðåäñòàâëÿþùèå ìåòàäàííûå äëÿ âèçóàëèçàöèè ÍÁÑ, ÍÄÂ, óçëîâîãî äå- ðåâà, òàáëèö ïîòåíöèàëîâ è ðåçóëüòàòîâ âû÷èñëåíèé â âèäå äèàãðàìì; — îïèñûâàþùèå âõîäíûå ïàðàìåòðû âèçóàëèçàöèè; — ñïåöèôèöèðóþùèå ïðîöåäóðó âèçóàëèçàöèè èçîáðàæåíèÿ ÍÁÑ, ÍÄÂ è óçëîâîãî äåðåâà. Ãðàôè÷åñêèé èíòåðôåéñ ñèñòåìû ïîçâîëÿåò ïîëüçîâàòåëþ ñîçäàâàòü è âíî- ñèòü èçìåíåíèÿ â ñòðóêòóðó ÍÁÑ, ÍÄÂ è çíà÷åíèÿ íå÷åòêèõ âåðîÿòíîñòíûõ ïî- òåíöèàëîâ âðó÷íóþ èëè äëÿ àâòîìàòè÷åñêîãî ïîñòðîåíèÿ ñîåäèíÿòüñÿ ñ èñòî÷íè- êîì äàííûõ (â òîì ÷èñëå ñ îòäàëåííûì), êîòîðûé ñîäåðæèò èíôîðìàöèþ î ñî- çäàííîé ðàíåå ÍÁÑ èëè ÍÄÂ. Ñ ïîìîùüþ èíòåðôåéñà ñèñòåìû ïîëüçîâàòåëü èìååò âîçìîæíîñòü ïåðåñìîòðåòü, êàê èçìåíÿþòñÿ çíà÷åíèÿ íå÷åòêèõ ïîòåíöèà- ëîâ íà êàæäîì ýòàïå âåðîÿòíîñòíîãî âûâîäà íà ÍÁÑ èëè ÍÄÂ. Óïðàâëåíèå ñîñòîèò èç êëàññîâ, ñïåöèôèöèðóþùèõ ïðîöåññû êîíòðîëÿ çà çàãðóçêîé, ñîõðàíåíèåì è âíåñåíèåì èçìåíåíèé â ñòðóêòóðó è ÷èñëîâûå ïàðà- ìåòðû ÍÁÑ èëè ÍÄÂ. Â ýòîò ñëîé âêëþ÷åíû îáúåêòû, êîòîðûå íà îñíîâå òåõíî- ëîãèè ADO óñòàíàâëèâàþò ñîåäèíåíèå ñ èñòî÷íèêîì äàííûõ, ïîëó÷àþò â îòâåò íà ñîçäàííûé ïîëüçîâàòåëåì çàïðîñ äàííûå äëÿ ïîñòðîåíèÿ ÍÁÑ èëè ÍÄÂ. Â ðåçóëüòàòå ñèñòåìà ïîëó÷àåò óíèâåðñàëüíûé äîñòóï (â òîì ÷èñëå è îòäàëåí- íûé) ê èñòî÷íèêàì, êîòîðûå ñîäåðæàò èíôîðìàöèþ î ÍÁÑ èëè ÍÄÂ. Â ñîîòâåòñòâèè ñ ïðèâåäåííîé àðõèòåêòóðîé ïðîãðàììíàÿ ñèñòåìà ñîâìåùà- åò ðÿä îáúåêòíî-îðèåíòèðîâàííûõ ïîäñèñòåì, êàæäàÿ èç êîòîðûõ ÿâëÿåòñÿ ñà- ìîñòîÿòåëüíîé óíèâåðñàëüíîé ïðîãðàììíîé åäèíèöåé è ïðåäíàçíà÷åíà äëÿ àâòî- ìàòèçàöèè îòäåëüíûõ ýòàïîâ òðàíñôîðìàöèè è âûïîëíåíèÿ ÀÐÄ. ÇÀÊËÞ×ÅÍÈÅ Â ñòàòüå îïèñàíî ïîñòðîåíèå íîâûõ íå÷åòêèõ ñåòåâûõ ìîäåëåé è íà èõ îñíîâå ïðîãðàììíî-àëãîðèòìè÷åñêèõ ñðåäñòâ ìîäåëèðîâàíèÿ ñîñòîÿíèé ñëîæíûõ ñèñ- òåì, â ÷àñòíîñòè, íîâîãî (ìîäèôèöèðîâàííîãî) àëãîðèòìà òðàíñôîðìàöèè íå÷åò- êèõ áàéåñîâñêèõ ñåòåé è äèàãðàìì âëèÿíèÿ â óçëîâîå äåðåâî, èñïîëüçóþùåãî äîïîëíèòåëüíûå ñòðóêòóðû äàííûõ è ýôôåêòèâíûå àëãîðèòìû ñîðòèðîâêè äëÿ óñêîðåíèÿ ïðîöåññà ïîñòðîåíèÿ óçëîâîãî äåðåâà. Ýòîò àëãîðèòì ïðèìåíåí äëÿ ìîäèôèêàöèè àëãîðèòìà ìàðãèíàëèçàöèè íà îñíîâå ýëèìèíàöèè ïåðåìåííîé. Ïîñòðîåí òàêæå àëãîðèòì ìîäåëèðîâàíèÿ ðàñïðîñòðàíåíèÿ âåðîÿòíîñòåé, ïîçâîëÿþùèé âû÷èñëÿòü àïîñòåðèîðíûå îöåíêè ñîñòîÿíèé è íàèáîëåå âåðîÿò- íîñòíûå èíôîðìàöèîííûå ñîñòîÿíèÿ ñëîæíûõ ñèñòåì íà îñíîâå ðàçìûòûõ çíà- íèé î ïðåäìåòíîé îáëàñòè ïóòåì èñïîëüçîâàíèÿ íå÷åòêèõ âåðîÿòíîñòíûõ ïîòåí- öèàëîâ. Äëÿ âû÷èñëåíèÿ îöåíîê äîâåðèÿ ïðåäñòàâëÿåòñÿ âîçìîæíîñòü èñïîëüçî- âàòü àëüòåðíàòèâíûå ñòðàòåãèè âûâîäà, ÷òî ïîçâîëÿåò ñðàâíèâàòü èõ ðåçóëüòàòû äëÿ ðàçíûõ ìîäåëåé îäíîãî ïðîöåññà èëè ñèñòåìû. Ïîñòðîåííûé àëãîðèòì âû- ïîëíÿåòñÿ êîððåêòíî è òðåáóåò ìåíüøèõ çàòðàò âû÷èñëèòåëüíûõ ðåñóðñîâ ïî ñðàâíåíèþ ñ ïðèìåíåíèåì àíàëîãè÷íûõ àëãîðèòìîâ ðàñïðîñòðàíåíèÿ äîâåðèÿ. Ïðèìå÷àòåëüíî, ÷òî îñíîâíûå ñâîéñòâà àëãîðèòìîâ, ðàçðàáîòàííûõ äëÿ íå÷åòêèõ áàéåñîâñêèõ ñåòåé, ïðèñóùè äëÿ íå÷åòêèõ äèàãðàìì âëèÿíèé. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 149 Ïðåäñòàâëåííûå òåîðåòè÷åñêèå ðåçóëüòàòû ñëóæàò ìåòîäîëîãè÷åñêîé áàçîé ïðè ïîñòðîåíèè ñîîòâåòñòâóþùåé íå÷åòêîé èíôîðìàöèîííîé òåõíîëîãèè ìîäå- ëèðîâàíèÿ ñîñòîÿíèé ñëîæíûõ ñèñòåì â óñëîâèÿõ íåîïðåäåëåííîñòè è ðàçìûòîñ- òè ïðè÷èííî-ñëåäñòâåííûõ ñâÿçåé. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. P r o b a b i l i s t i c networks and expert systems / R.G. Ñowell, A.P. Dawid, D.J. Spiegelhalter, S.L. Lauritzen. — New York: Springer-Verlag, 1999. — 321 p. 2. K j a e r u l f f U . B . , M a d s e n A . L . Bayesian networks and influence diagrams. — S.l.: Springer Science+Business Media, LLC, 2008. — 318 p. 3. Ç à ä å Ë . À . Îñíîâû íîâîãî ïîäõîäà ê àíàëèçó ñëîæíûõ ñèñòåì è ïðîöåññîâ ïðèíÿòèÿ ðåøå- íèé // Ìàòåìàòèêà ñåãîäíÿ (ñá. ñòàòåé, ïåð. ñ àíãë.). — Ì.: Çíàíèå, 1974. — Ñ. 5–48. 4. Â å ð ¸ â ê à Î . Â . , Ï à ð à ñ þ ê È . Í . Î ðàñïðîñòðàíåíèè âåðîÿòíîñòåé â íå÷åòêèõ áàéåñîâ- ñêèõ ñåòÿõ ñ íåäåòåðìèíèðîâàííûìè ñîñòîÿíèÿìè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2008. — ¹ 6. — Ñ. 153–169. 5. Ï à ð à ñ þ ê È . Í . , Ê î ñ ò ó ê å â è ÷ Ô . Â . Ìåòîäû òðàíñôîðìàöèè áàéåñîâñêîé ñåòè äëÿ ïî- ñòðîåíèÿ óçëîâîãî äåðåâà è èõ ìîäèôèêàöèÿ // Êîìïüþòåðíàÿ ìàòåìàòèêà. — Ê.: Èí-ò êèáåð- íåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, 2008. — ¹ 1. — C. 70–80. 6. Ï à ð à ñ þ ê È . Í . , Ê î ñ ò ó ê å â è ÷ Ô . Â . Íå÷åòêèå ïîòåíöèàëû è âîïðîñû èõ ïðèìåíåíèÿ â àëãîðèòìàõ ðàñïðîñòðàíåíèÿ äîâåðèÿ íà áàéåñîâñêèõ ñåòÿõ // Òàì æå. — 2009. — ¹ 1. — Ñ. 67–75. 7. Ï à ð à ñ þ ê È . Í . , Ê î ñ ò ó ê å â è ÷ Ô . Â . Îá îäíîì ýôôåêòèâíîì àëãîðèòìå ðàñïðîñòðàíå- íèÿ âåðîÿòíîñòåé â íå÷åòêèõ áàéåñîâñêèõ ñåòÿõ äîâåðèÿ // Òàì æå. — 2010. — ¹ 2. — Ñ. 102–112. 8. P e a r l J . Probabilistic reasoning in intelligent systems: networks of plausible inference. — San Mateo: Morgan Kaufmann, 1991. — 552 p. 9. L a u r i t z e n S . L . , S p i e g e l h a l t e r D . J . Local computations with probabilities on graphical structures and their application to expert systems // J. Royal Statist. Soc. Ser.B. — 1988. — 50, N 2. — P. 157–224. 10. H e g g e r n e s P . Minimal triangulations of graphs: A survey // Discrete math. — 2006. — 306, Iss. 3. — P. 297–317. 11. Sh e n o y P . P . , S h a f e r G . Axioms for probability and belief-function propagation // Uncer- tainty in Artif. Intellig. — 1990. — 4. — P. 169–198. 12. J e n s e n F . , L a u r i t z e n S . , O l e s e n K . Bayesian updating in causal probabilistic networks by local computations // SIAM J. Comp. — 1990. — N 4. — P. 269–282. 13. L e p a r V . , S h e n o y P . A comparison of Lauritzen–Spiegelhalter, Hugin and Shenoy–Shafer architectures for computing marginals of probability distributions / Ed. G. Cooper and S. Moral. — Proc. of the 14th Conf. on Uncertainty in Artificial Intelligence (UAI-98). — S.l.: Morgan Kaufmann, 1998. — P. 328–337. 14. D e t y n i e c k i M . , Y a g e r R . R . A note on ranking fuzzy numbers using a-weighted valuations // Intern. J Uncertainty, Fuzziness and Knowledge-Based Syst. — 2000. — 8. — P. 573–591. 15. Ê î ð ì å í Ò . , Ë å é ç å ð ñ î í × . , Ð è â å ñ ò Ð . Àëãîðèòìû: ïîñòðîåíèå è àíàëèç / Ïåð. ñ àíãë. ïîä ðåä. À. Øåíÿ. — Ì.: ÌÖÍÌÎ:ÁÈÍÎÌ. Ëàá. çíàíèé, 2004. — 960 ñ. 16. Ï ð è ê ë à ä í û å íå÷åòêèå ñèñòåìû / Ïåð. ñ ÿïîí. Ê. Àñàè, Ä. Âàòàäà, Ñ. Èâàè è äð. ïîä ðåä. Ò. Òýðàíî, Ê. Àñàè, Ì. Ñóãåíî. — Ì.: Ìèð, 1993. — 368 ñ. Ïîñòóïèëà 27.05.2013 150 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1

Математическое обеспечение для исследования состояний сложных систем в условиях неопределенности на основании нечетких сетевых моделей доверия

Institution

Ähnliche Einträge