Модели и методы решения нечетких задач дискретной оптимизации в диагностических информационных технологиях

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2005
Hauptverfasser:	Сергиенко, И.В., Парасюк, И.Н., Каспшицкая, М.Ф.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2005
Schlagworte:	Теоретичні та прикладні проблеми і методи системного аналізу
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/13804
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:	Модели и методы решения нечетких задач дискретной оптимизации в диагностических информационных технологиях / И.В. Сергиенко, И.Н. Парасюк, М.Ф. Каспшицкая // Систем. дослідж. та інформ. технології. — 2005. — № 2. — С. 7-22. — Бібліогр.: 22 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-13804
record_format	dspace
spelling	irk-123456789-138042010-12-07T16:43:07Z Модели и методы решения нечетких задач дискретной оптимизации в диагностических информационных технологиях Сергиенко, И.В. Парасюк, И.Н. Каспшицкая, М.Ф. Теоретичні та прикладні проблеми і методи системного аналізу Рассмотрены методы дискретной оптимизациии моделей практически важных задач (покрытия, выбора и классификации), возникающих в процессе проектирования и функционирования диагностических информационных технологий в нечетком пространстве. Приведены общие и конкретные постановки задач указанных типов, предложены методы их решения. Рассмотрен подход к определению весовых коэффициентов для построения аддитивных целевых и ограничивающих функционалов на основе метода анализа иерархий Т. Саати. The paper considers discrete optimization methods for a number of models of practically important covering, choice and clusterization problems appearing in designing and operation of diagnostic information technologies in fuzzy space. General and specific statements of such problems are given and solution methods are considered for them. On the basis of the T. Saati hierarchy analysis method, an approach is also proposed for calculation of weight coefficients for creation of additive objerlive and constraining functionals. Розглянуто методи дискретної оптимізації моделей практично важливих задач (покриття, вибору та класифікації), які виникають у процесі проектування та функціонування діагностичних інформаційних технологій в нечіткому просторі. Наведено загальні та конкретні постановки задач зазначених типів, запропоновано методи їх рішення. Розглянуто підхід до визначення вагових коефіцієнтів для побудови адитивних цільових та обмежуючих функціоналів на базі методу аналізу ієрархій Т. Сааті. 2005 Article Модели и методы решения нечетких задач дискретной оптимизации в диагностических информационных технологиях / И.В. Сергиенко, И.Н. Парасюк, М.Ф. Каспшицкая // Систем. дослідж. та інформ. технології. — 2005. — № 2. — С. 7-22. — Бібліогр.: 22 назв. — рос. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/13804 519.9 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	2005
topic_facet	Теоретичні та прикладні проблеми і методи системного аналізу
url	http://dspace.nbuv.gov.ua/handle/123456789/13804
citation_txt	Модели и методы решения нечетких задач дискретной оптимизации в диагностических информационных технологиях / И.В. Сергиенко, И.Н. Парасюк, М.Ф. Каспшицкая // Систем. дослідж. та інформ. технології. — 2005. — № 2. — С. 7-22. — Бібліогр.: 22 назв. — рос.
work_keys_str_mv	AT sergienkoiv modeliimetodyrešeniânečetkihzadačdiskretnojoptimizaciivdiagnostičeskihinformacionnyhtehnologiâh AT parasûkin modeliimetodyrešeniânečetkihzadačdiskretnojoptimizaciivdiagnostičeskihinformacionnyhtehnologiâh AT kaspšickaâmf modeliimetodyrešeniânečetkihzadačdiskretnojoptimizaciivdiagnostičeskihinformacionnyhtehnologiâh
first_indexed	2025-07-02T15:35:02Z
last_indexed	2025-07-02T15:35:02Z
_version_	1836549934027898880
fulltext	 Сергиенко И.В., Парасюк И.Н., Каспшицкая М.Ф., 2005 Системні дослідження та інформаційні технології, 2005, № 2 7 TIДC ТЕОРЕТИЧНІ ТА ПРИКЛАДНІ ПРОБЛЕМИ І МЕТОДИ СИСТЕМНОГО АНАЛІЗУ УДК 519.9 МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ НЕЧЕТКИХ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ В ДИАГНОСТИЧЕСКИХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЯХ И.В. СЕРГИЕНКО, И.Н. ПАРАСЮК, М.Ф. КАСПШИЦКАЯ Рассмотрены методы дискретной оптимизациии моделей практически важных задач (покрытия, выбора и классификации), возникающих в процессе проекти- рования и функционирования диагностических информационных технологий в нечетком пространстве. Приведены общие и конкретные постановки задач указанных типов, предложены методы их решения. Рассмотрен подход к опре- делению весовых коэффициентов для построения аддитивных целевых и огра- ничивающих функционалов на основе метода анализа иерархий Т. Саати. ВВЕДЕНИЕ Среди новейших технологий, играющих роль движущей силы в эволюции общества, пожалуй, наиболее важными являются информационные техноло- гии, где в роли технологических средств используется широкий спектр средств связи, компьютерная техника и соответствующее программное обеспечение, а основным сырьем и изделием — информация, лавинообраз- ный рост которой имеет необратимый характер. Большой интерес представляют интеллектуальные информационные технологии. Наряду с рутинными операциями получения, накопления (скла- дирования), поиска и управления информационными потоками они при- меняются для поддержки наиболее наукоемких процессов (собственно изго- товления информационной продукции). К числу таких применений относится компьютеризация интеллектуальных методов вывода диагнозов на базе накопленных знаний экспертов и симптомов-свидетельств о теку- щем состоянии исследуемой системы. Для решения этой важной задачи используется множество подходов, исходящих из определенных предста- влений о системе и ее состояниях и базирующихся на методах соответству- ющих теорий. В настоящей статье основное внимание уделено методам решения раз- личных дискретных оптимизационных задач, возникающих в процессе проектирования и функционирования диагностических информационных технологий. При этом предполагается, что такие технологии будут функци- онировать в нечетком информационном пространстве, т.е. данные и знания, на основании которых осуществляется логический вывод, имеют так назы- Сергиенко И.В., Парасюк И.Н., Каспшицкая М.Ф. ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 8 ваемый нечеткий (размытый) характер, что заставляет по-новому взглянуть на возникающие оптимизационные проблемы, их модели и методы решения. Уместно отметить, что методы решения этих и подобных задач в точечном (четком) информационном пространстве достаточно хорошо изучены. Од- нако каждая задача значительно усложняется, если одна или несколько ве- личин, входящих в ее условие, имеют размытую природу, т. е. являются ве- личинами нечеткими [1]. Это касается как моделей задач, так и способов их решения [2–4]. Представляется, что опыт, накопленный авторами при фор- мализации и решении отдельных классов задач дискретной оптимизации в нечетком информационном пространстве, позволит глубже понять пробле- мы компьютеризации решения таких задач и будет полезен при решении задач из других областей знаний. Основные понятия общего характера. Размытое число [1] будем по- нимать как подмножество числовой оси R , имеющее функцию принадлеж- ности 1][0,: →Rv , где R — множество действительных чисел. Обозначим множество всех таких функций ( )1][0,:)( →= RR vvF . Нормальные нечет- кие числа — это такие числа, что 1)(max = ∈ xv Rx , )()( RFxv ∈ . Носителем нечеткого числа а есть некоторое подмножество R⊂Ωa , если ( )0)( >=Ω xvxa , ax Ω∈∀ . Расширенная бинарная арифметическая опера- ция ∗~ над нечеткими числами CBA ,, , определенными функциями прина- длежности )(,, RFvvv CyA ∈ , R∈∀ zyx ,, , представляется в общем виде [3] ( ))()()(~ * yvxvzvBAC BAC yxz ∧=⇔∗= = ∨ , а расширенная операция min этих чисел определяется выражением ( ))()(),(min ),min( yvxvBA BAyxz C ∧ = ∨= , где ∗~ — одна из расширенных бинарных арифметических операций: ⊕ — суммирования, Θ — вычитания,  — умножения и ÷ — деления; ∨, ∧ — операции соответственно max и min. Например, расширенная бинарная операция сложения имеет вид ( ))()()( yvxvzvBAC BAC yxz ∧=⇔⊕= += ∨ . При построении функций принадлежности размытых величин (нечет- ких чисел) существенным является также понятие нечеткого интервала, ко- торый обычно описывается S -подобными функциями [5]. Oптимизационные задачи, возникающие в процессе логического вывода. В этом случае точнее говорить о логико-оптимизационном выводе. Содержательно суть такого вывода состоит в решении определенной, как правило, многокритериальной, оптимизационной задачи (или задач) в ин- формационном пространстве, которое задано априори или получено на пре- дыдущем этапе в результате применения методов логического вывода. В качестве таких задач чаще всего выступают задачи оптимального покры- тия, состоящие в том, что в заданном множестве элементов нужно найти оптимальное (в смысле определенных критериев) подмножество. Модели и методы решения нечетких задач дискретной оптимизации … Системні дослідження та інформаційні технології, 2005, № 2 9 Итак, пусть )( Ooo ii ∈ — некоторые операции; )( Sss jj ∈ — механи- змы, выполняющие операции из O ; ijα — «ресурс» операции io на меха- низме js ; ijβ — «цена» единицы «ресурса» операции io на механизме js ; jγ — «стоимость» механизма js ; ni ,...,1= ; mj ,...,1= ; OO ⊆0 — некото- рое интересующее нас подмножество операций. Приведем несколько моделей задач покрытия, использующих эту ин- формацию. Необходимо определить: 1. Подмножество механизмов SS ⊆* такое, чтобы соответствующее им подмножество операций O «покрывало» все операции подмножества 0O , т.е. OO ⊆0 , ∑ ∈∀ > 0 Ss ij j α , 0Ooi ∈∀ . (1) 2. Подмножество SS ⊆* минимальной мощности при условии (1). 3. Подмножество SS ⊆* минимальной стоимости ∑ ∈∀ =Γ Ss j j γ при ус- ловии (1). 4. Множество SS ⊆ минимальной стоимости Γ при условии (1) и ∑ ∈∀ ∈∀≤ * ,, 0 Ss iiijij j COoCβα — const. (2) 5. Множество SS ⊆* минимальной мощности при условиях (1) и (2). Из методологических соображений конспективно рассмотрим способы решения задач 1–5 в их четких постановках, т.е. в так называемом четком информационном пространстве. Входные данные для их решения могут быть представлены в виде матриц неотрицательных чисел mn jiijA , 1, = = α , mn jiijB , 1, = = β , (3) вектора стоимости механизмов },...,,{ 21 mγγγγ =  и вектора констант огра- ничений },...,,{ 21 nCCCC = . Задача 1 имеет, вообще говоря, множество решений. Решения задач 2 и 3 существуют, если существует решение задачи 1 при тех же самых ис- ходных данных. Множеством допустимых решений задач 4 и 5 будет неко- торое множество VUW = , где U — совокупность подмножеств множес- тва S , которые удовлетворяют условию (2) относительно операций из множества 0O , а V — совокупность подмножеств множества S , которые удовлетворяют неравенству (1) (т.е. V — множество решений задачи 1). Множество U не является пустым, если хотя бы для одного 0 * Oo i ∈ 0min *** >− ∈ ijijiSs C j βα . Множество V будет непустым, если для каждой опе- Сергиенко И.В., Парасюк И.Н., Каспшицкая М.Ф. ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 10 рации 0Ooi ∈ среди механизмов Ssi ∈ обнаружится хотя бы один такой, который ее выполняет. В противном случае задача теряет смысл относите- льно множества 0O , хотя, вообще говоря, может иметь решение относите- льно другого множества OO ⊆′ . Если для всех элементов 0Ooi ∈ выпол- няется условие 0 1 >∑ = m j ijα , то задача 1 имеет хотя бы одно решение. В противном случае, когда 0 1 0 =∑ = m j ji α для некоторой операции 0 0 Oo i ∈ , то в множестве S нет ни одного механизма, который выполняет операцию 0i o . Итак, допустим, что для всех операций, которые входят в множество О0, выполняется условие 0 1 >∑ = m j ijα , 0Ooi ∈∀ . (4) Для нахождения множества решений задачи 1 упорядочим множества S и 0O произвольными способами. В множество S включим последова- тельно механизмы: первым возьмем механизм, выполняющий первую опе- рацию в упорядоченном множестве 0O ; вторым — механизм, выполняю- щий вторую операцию, и т.д., пока не будут исчерпаны все операции из множества 0O . Поскольку количество вариантов упорядочений множества 0O равняется !\|\| 0O , а количество упорядочений множества S равняется !m , то общее количество теоретически возможных вариантов решения ограничено сверху числом !! 0nm , где \|\| 00 On = . Если какой-то из механиз- мов повторяется, то в решение он включается только один раз. Задача 2 является оптимизационной задачей на множестве решений за- дачи 1 и, как вытекает из сказанного выше, при достаточно больших m и 0n ее трудно решить методом полного перебора. Такими же задачами явля- ются и задачи 3–5. Поэтому для их решения целесообразно применить уни- версальный метод, который легко можно было бы модифицировать для лю- бой из задач данного класса или его видоизменения. Один из таких методов — метод градиентного типа (вектора спада, изученный и достаточ- но апробированный на классе комбинаторных оптимизационных задач [6, 7]). Общая схема этого метода в случае дискретного пространства X описана в работе [6]. Прежде чем рассмотреть эти задачи в нечетком информационном про- странстве, приведем общую задачу оптимизации на множестве SM — мно- жестве всех подмножеств множества S . Она состоит в следующем: определить такой элемент SMx ∈ , который дает экстремум функции )(xf на некотором подмножестве SMG ⊆ , т. е. )(ext)( * xfxf SMGx ⊆∈ = . (5) Модели и методы решения нечетких задач дискретной оптимизации … Системні дослідження та інформаційні технології, 2005, № 2 11 Как видно из приведенных выше формулировок, задачи 2–5 являются частными случаями задачи (5), а решения задачи 1 — элементами множест- ва G [8]. Предположим, что на множестве SM (или его подмножестве G ) зада- но размытое множество SM (или его подмножество G ) с помощью соот- ветствующих функций принадлежности [3,4,9]. Например, пусть требование покрытия множества 0O не является строгим, т.е. часть операций из мно- жества 0O менее важна с учетом некоторой дополнительной информации и, следовательно, может остаться невыполненной множеством механизмов SS ⊆0 . Эту дополнительную информацию предоставляет функция принад- лежности )( ioω , где 0Ooi ∈∀ . Таким образом, функцией принадлежности ω на множестве 0O определено размытое множество 0 ωO . Функции прина- длежности могут быть заданы в различном представлении [9]. Для опреде- ленности будем считать, что функции принадлежности ω заданы в числовой форме. В этих предположениях рассмотрим варианты размытых формулировок задач 1–5. Задача 1`. Определить подмножество механизмов SS ⊆0 такое, чтобы функции принадлежности )( ii oω , 0Ooi ∈ , 0Ss j ∈ удовлетворяли условию iiiij Oo Ω≥ΩΩ≥ ,,)( ω — const 00 , SsOo ji ∈∀∈∀ , (6) где )( ij oω , iΩ — размытые числа; O — размытое число нуль; ≥ — так называемая операция расширенного сравнения (размытые числа 21 αα ≥ , если их функции принадлежности )()( 21 xx µµ ≥ , Rx∈ ). Задача 1``. Определить множество механизмов SS ⊆0 такое, чтобы для всех )( ij oω удовлетворялись условия ( ) 1),( ijiij Tor ≤Ωω , 0Ooi ∈∀ , 0Ssi ∈∀ , (7) ( ) 2, ii TOr ≤Ω , 0Ooi ∈∀ , (8) где r — расширенная метрика Хемминга, вычисляемая по формуле ∫ ∞ ∞− −= dxxxr )()(),( 2121 µµαα ; (9) 21, iij TT — четкие числа (константы); )(1 xµ — функция принадлежности раз- мытого числа 1α ; )(2 xµ — функция принадлежности размытого числа 2α . Видно, что задачи 1` и 1`` отличаются одна от другой способом сравне- ния нечетких чисел. Условие (6) требует, чтобы ( ) ( )xxo iij ,),( Ω≥νωµ для всех R∈x , 0S∈is . Здесь, как и в задаче 1``, ( )xoij ),(ωµ , ( )xi ,Ων — функ- Сергиенко И.В., Парасюк И.Н., Каспшицкая М.Ф. ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 12 ции принадлежности размытых чисел )( ij oω , iΩ , соответственно, R∈x . Что касается условий (7), (8), то они являются более слабыми, чем усло- вия (6). Задача 1```. Пусть задано множество размытых чисел iδ , \|\|,...,2,1 0Oi = . Определить подмножество механизмов SS ⊆0 такое, чтобы соответствующее им множество операций O включало множество опера- ций 0O (т. е. выполнялось условие (1)), причем ∑ ∈ ∈∀>⊗⊕ Ss iijj j OoO 00 ,αδ , O — размытое число нуль, (10) где ⊗⊕ , — операции соответственно расширенного суммирования и умно- жения. Задачи 1`–1``` могут быть приближенно разрешимы модификацией приведенного в работе [8] способа решения задачи 1 с учетом свойств раз- мытых чисел и их функций принадлежности. Покажем это на примере зада- чи 1`: • строим, как это сделано при решении задачи 1, множество 0 1S , удов- летворяющее условию (1); • проверяем, выполняются ли на множестве 0 1S условия (6). Если да, то 0 1S является решением задачи 1`. Иначе строим окрестность точки 0 1S , выбираем в ней точку 0 2S , удовлетворяющую условию (1), в которой есть меньше нарушений условий (6), чем в 0 1S , и т.д., пока не придем к решению 0S , удовлетворяющему условию (1) и имеющему в окрестности заданного радиуса наименьшее количество нарушений условий (6). Это множество принимаем за приближенное решение задачи 1`. Размытые постановки оптимизационных задач 2–5 могут определять несколько факторов или даже их совокупность: размытость пространства SM , целевых и ограничительных функций, определенных размытостью чи- словых коэффициентов. Особенностью размытых задач 1` – 5` является то, что SM (множество подмножеств множества S ) в общем случае не является размытым. Это дает возможность пользоваться методом вектора спада с метрикой =),( 21 σσr )(\)( 2121 σσσσ ∩∪= , где SM∈21,σσ [8]. Если же в в некоторой задаче SM является размытым множеством, то для применения названного метода необходимо указать метрику ),( 21 xxR для элементов Sx M∈1 , Sx M∈2 . Это может быть, в частности, метрика, предложенная в работе [10]. Нечеткий вариант задачи 2 (задача 2`) представим в таком виде: определить множество SS ⊆ почти минимальной мощности при условии, что множество операций O , соответствующее множеству S , со- держит заданное множество операций 0O Модели и методы решения нечетких задач дискретной оптимизации … Системні дослідження та інформаційні технології, 2005, № 2 13 0 OO ⊆ , ∑ ∈∀ ∈∀> 0,0 Ss iij j o Oα . (11) Нечеткость этой оптимизационной задачи следует из определения це- левой функции в лингвистическом виде. Переход к числовому представле- нию функции сопряжен с заданием на множестве R действительных поло- жительных чисел функции принадлежности )()( ανµ += xx , (12) где ν — функция заданного вида, например, S -подобная [10], а α — неко- торый задаваемый числовой параметр (либо число, либо интервал, в кото- ром допускается изменение значений целевой функции). Итак, пусть на множестве положительных целых чисел задана функция принадлежности )(xµ , в частности, в виде (12). В процессе решения задачи 2 с помощью указанного выше итерационного метода в окрестности )(ζρL , SM∈ζ получим ряд целых чисел, определяющих мощность подмножества SSk ⊆ , удовлетворяющих условию (11) и принадлежащих окрестности )(ζρL . При этом необходимо учесть также информацию, задаваемую через функцию принадлежности )(xµ , и ряд чисел kkxxx ξξξ === ,...,, 1100 , )( 0ξξ ρLk ∈∀ c такими функциями принадлежности (характеристическими функциями [9]):    ≠ = = . , )( при0 при1 i i xx xx xiµ Находим теперь среди ix , ki ,...,1,0= то число i x , которое дает )()(min 10 xx ik µµ − <≤ . Это число i x будет локальным размытым решением рассматриваемой задачи в окрестности )( 0ξρL . Приняв i x в качестве цен- тра окрестности, продолжаем итерационный процесс до выполнения усло- вия его окончания. В результате получаем приближенное нечеткое решение задачи. Уместно заметить, что информация, которую предоставляет функция принадлежности, и информация, полученная из четких данных, предпо- лагаются «равноправными». Если такое «равноправие» сомнительно, то не- обходимо провести дополнительные исследования. Задачи выбора оптимальных решений в множестве альтернатив возникают при проектировании и применении диагностических информаци- онных технологий, в частности, в процессе логико-оптимизационного выво- да диагноза исследуемых систем. В качестве примера модели такой задачи для простоты выберем хорошо изученную (например, в работе [10]) задачу, представляющую практический интерес. Формально суть этой задачи со- стоит в следующем. Пусть каждому объекту множества q ii 1}{ == AA поставлена в соответст- вие последовательность параметров-характеристик { }niiii dddt ,...,, 21= . Та- Сергиенко И.В., Парасюк И.Н., Каспшицкая М.Ф. ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 14 ким образом, ценность объектов может быть охарактеризована матрицей qn ijijd , 1, = =T . Задача формулируется так: найти такой объект AA i ∈ , который обес- печивает ∑ =∈         − n j ji j jAA d a i 1 2 1min δ (13) при 1 1 =∑ = n j jδ , 0≠jid , 01 ≥≥ jδ , nj ,...,2,1= ; qi ,...,2,1= , где jij da , — идеальное (для данного клиента) и текущее фактическое значение j -й ха- рактеристики объекта; jδ — весовые коэффициенты соответствующих ха- рактеристик. Метод решения этой задачи в четкой постановке очевиден: для каждого qi ,...,1= вычислить суммы ∑ =         −= n j ji j ji d a f 1 2 1δ и выбрать тот объект i A , для которого сумма if примет минимальное значение. Размытую постановку задачи (13) рассмотрим в предположении, что ja — размытые числа, характеризуемые функциями принадлежности )(xv j , представленными определенным способом (пусть для определеннос- ти в виде некоторой S -подобной функции S ). Т.е. можно считать, что каж- дая из величин ja jα относится к размытому интервалу, определяемому дейст- вительными числами , jγ , а функции принадлежности =)(xv j ),,( jjxS γα= . В предположении, что в суммах if jδэлементы , jid — за- данные четкие числа, ja — нечеткие числа, носители которых [ ])2()1( , jj αα заданы, if будет нечетким числом — расширенной суммой ⊕ нечетких чи- сел 2 1        − ji j j d a δ с носителями                   −        −= 2)2(2)1( 1,1 ji j j ji j jji d a d a l δδ , nj ,...,1= . Обозначив )(xjiω функцию принадлежности нечетких чисел 2 1        − ji j j d a δ , вычисление функции принадлежности )(xiµ размытого числа if согласно [11] будет осуществляться так: qinjxxx jjji n j xx i n j j ,...,1,,...,1,,)()( 1 1 ==∈      = = = ∧ ∑ = ∨ Rωµ . (14) Модели и методы решения нечетких задач дискретной оптимизации … Системні дослідження та інформаційні технології, 2005, № 2 15 Учитывая, что jδ , jid , l — четкие величины, имеем =)(xjiω                 −= 2 1 ji jji d xv δ . Тогда согласно (14) для вычисления )(xiµ можно ис- пользовать выражение R∈                           −= = = ∧ ∑ = ∨ i ji j jji n j xx i x d x vx n k k ,1)( 2 1 1 δµ . (15) Таким образом, для нечетких чисел if , qi ,...,2,1= функции принад- лежности )(xiµ определяются формулой (15), а функция принадлежности расширенной операции min этих чисел, т.е. )(min xii µ , вычисляется как R∈      = == ∧∨ iii q ixx xxx i i ,)()( 1min µµ . (16) Вообще говоря, функция )(xµ не совпадает ни с одной из функций )(xiµ . Поэтому для определения номера i , соответствующего решению задачи (13) в нечеткой постановке, нужно среди )(xiµ обнаружить ту функ- цию, которая на множестве R будет наиболее близкой к функции )(xµ в определенном смысле, например ту, которая обеспечит минимум величины )()(max xx i Rx µµ − ∈ , qi ,...,2,1= . Задачу (13) можно представить и несколько иначе, например, считая, что величины ja неизвестны и для их определения предоставлена нечеткая информация в лингвистическом виде. Пусть экспертные оценки величин jid заданы в виде лингвистических термов высокого порядка, рекуррентно определяемых через термы низшего порядка, которые могут быть построе- ны на основе вербально-графических оценок экспертов. В этом случае мо- жет оказаться полезным метод семантических дифференциалов Осгуда. Применительно к задаче 13, следуя этому методу, границы интервала [ ]jj DD , изменения величин ja вычисляются по формулам jiij dD min= , ji i j dD max= , qi ,...,2,1= , nj ,...,2,1= . Чтобы оценить, насколько концы каждого интервала обладают свойством ja можно воспользоваться, напри- мер, экспертным методом. Это могут быть нормированные оценки ( )jDµ , ( )jDµ , т. е. принадлежащие интервалу ]1,0[ . Таким образом, можно полу- чить ряд дискретных значений функции принадлежности размытой величи- ны ja . Для числовой идентификации лингвистических термов можно вос- пользоваться модификацией вербально-графического метода [10]. В предположении, что оценки, соответствующие лингвистическим термам, нормированы, каждое из нечетких чисел ja , nj ,...,2,1= определя- Сергиенко И.В., Парасюк И.Н., Каспшицкая М.Ф. ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 16 ется совокупностью q дискретных значений функции принадлежности )(xjµ при jidx = , qi ,...,2,1= . Для получения аналитического выражения )(xjµ нужно аппроксими- ровать эту функцию, что можно сделать одним из известных способов: гра- фически с помощью лекал, сплайн-функциями, полиномами порядка 1−q , полиномами Чебышева и т.п. [12]. При полиномиальной аппроксимации )(xv j функции принадлежности )(xjµ могут быть нарушены условия нор- мированности. В этом случае в качестве функции принадлежности размы- той величины ja , nj ,...,1= , примем функцию )(xv j , R∈x      > ≤≤ = <∀ ∀ ∀ .xvх х хxv j j j j ,xv ,xv xv 0): : :),( (,0 1)(,1 1)(0 )( (17) Из определения функции )(xv j следует, что она, вообще говоря, может принимать значение, равное 1, в нескольких точках (даже на континууме), а также быть субнормальной ( 1)( <xv j ). Отметим, что функция принадлеж- ности )(xv j может лишь приближенно описывать размытое число, и к поня- тию «приближенность» мы обратились лишь в процессе решения задачи (аппроксимации), а размытость характерна уже для самой природы рас- смотренной задачи. Таким образом, возникает необходимость исследовать вопрос оценки точности приближения размытого решения. Задачи классификации. В информационных технологиях диагностики задачи классификации сложноструктурированной информации возникают повсеместно — не только непосредственно в процессе поиска наиболее аде- кватного диагноза, но и на различных этапах проектирования их компо- нентов. Например, хорошо проведенная классификация баз знаний такой технологии позволяет использовать более эффективные стратегии выбора актуальных симптомов. Задачи размытой классификации в данной работе представлены общей комбинаторной оптимизационной моделью как задачи на разбиениях и вы- борках. Такой подход позволил предложить, в частности, и новые методы их решения. Итак, рассмотрим постановку проблемы в общем виде. Пусть каждый элемент ia множества A может быть охарактеризован кортежем iE , кото- рый состоит из m упорядоченных элементов. Каждый из них отображает оценку ijα элемента ia согласно критерию je . В случае, если ijα — числа, iE является вектором. Таким образом, информация об оценке множества A согласно критериям множества E может быть записана в виде таблицы ∆ (матрицы в случае числовых значений ijα ): 1, n m jiijα = =∆ . Большинство критериев множества { }n ii 1== EE не предоставляет коли- чественных значений характеристикам ijα , а только лингвистические. Модели и методы решения нечетких задач дискретной оптимизации … Системні дослідження та інформаційні технології, 2005, № 2 17 В этом случае целесообразно лингвистические значения характеристик вы- разить в виде размытых чисел, используя разработанные для этого методы [14,15], в частности, упомянутый выше модифицированный метод Осгуда [10]. Пользуясь информацией, представленной в таблице ∆ , в предположе- нии, что сформулирована целевая функция, нужно ответить на ряд практи- ческих вопросов: каким элементам множества A дать преимущество? Как оптимально упорядочить или классифицировать множество A ? Чтобы по- лучить научно обоснованные ответы на эти и другие подобные вопросы, обратимся к общей постановке задачи и ее исследованию. Определим некоторые понятия. Под разбиением множества A на N классов понимаем такую совокупность подмножеств AA ⊂k , что AA = =  N k k 1 , причем 1≠N . Если последнее равенство дополнить условием ∅=∩ rk AA при rk ≠ , Nrk ,...,1, = , то будем говорить о разбиении мно- жества на кластеры. Для оценок «близости» элементов некоторого множества { }u ssb 1==B вводится понятие метрики ),( ps bbρ , B∈ps bb , . При этом диаметром мно- жества B является величина ),(max)( , ps Bbb bb ps ρ ∈∀ =BD , а величина =)(Bd ),(min , psbb bb ps ρ B∈∀ = — внутренним диаметром этого множества. При рассмотрении задач в нечетком информационном пространстве будем считать, что элементы ijα таблицы ∆ являются, в общем случае, размытыми числами, функции принадлежности которых задаются априори, а метрика определяется выражением ∑ = ∈∈ −== m j kj Rx ij Rx kiik xvxvEE kjij1 )(maxarg)(maxarg),(ρρ . Рассмотрим два типа задач: Тип 1. Оптимально, согласно некоторому критерию, разбить множест- во A на N классов при заданных ограничивающих условиях. Тип 2. Разбить множество A на минимальное количество классов при заданных ограничивающих условиях. Сначала рассмотрим случай, когда в задачах типа 1 и 2 требуется нулевое пересечение классов, т.е. нужно найти разбиение множества A на кластеры. Задачи типа 1. Известно, что основная кластерная задача, состоящая в определении раз- биения множества A на N непустых множеств-кластеров, удовлетворяю- щих некоторому критерию оптимальности и условиям однородности внутри кластера, может быть представлена как задача математического программи- рования (оптимизационная задача на комбинаторном пространстве разбие- ний). Большинство методов, предложенных для решения таких задач, не универсальны, так как существенно связаны с конкретными данными и ме- рой их определенности. Сергиенко И.В., Парасюк И.Н., Каспшицкая М.Ф. ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 18 Уточним исходную информацию, общую для задач указанных выше типов, а именно: множество элементов n iiaA 1== , множество их признаков (критериев) m jjeE 1= = и матрица (таблица) 1, n m jiij = =∆ α оценок элемен- тов ia ( ni ,...,2,1= ) согласно критериям je ( mj ,...,2,1= ); ijα — действите- льные числа (четкие или нечеткие). Итак, суть задач типа 1 и 2 состоит в разбиении множества A на клас- сы при выполнении некоторого заданного комплекса условий U , которые могут содержать требование оптимальности некоторой величины. Задачи типа 2. • Разбить множество A на минимальное количество классов (класте- ров) при условии DDS ≤ , где SD — диаметр кластера SA ; D — некото- рая заданная числовая величина. • Разбить множество A на минимальное количество классов (класте- ров) при условии δ≤− SS dD , где SS dD , — диаметр и внутренний диа- метр кластера δ;SA — заданная величина. Суть этой задачи состоит в по- строении классов с ограниченной концентрацией, и возникает она, в частности, при планировании застроек. • Разбить множество A на минимальное количество классов AA ⊆S таких, чтобы некоторая функция )( pF удовлетворяла определенным услови- ям U . Здесь P∈p — элемент множества P всех возможных разбиений множества A , а для вычисления значений функции F может понадобиться дополнительная информация, отличная от той, которая находится в матрице ∆ . В общем, задачи типа 2 отличаются от задач типа 1 содержанием кри- терия оптимизации: в задачах типа 2 — это количество элементов разбиения (классов). В задачах типа 1 критерием оптимизации служит некоторая дру- гая функция F , для построения которой, как уже упоминалось выше, может потребоваться дополнительная информация. В работе [13] предложены эвристические и итерационные алгоритмы решения задач классификации как оптимизационных задач вида )(extr)( * xFxF XGx <∈ = , (18) где X — метрическое пространство; )(xF — числовой функционал, опре- деленный на этом пространстве. Для построения целевых функционалов могут быть использованы раз- личные подходы. Так, если Ap Nx ∈= ),...,,( 21 ζζζ , ),...,,( \|\|21 iii i i aaa ζζ = и ка- ждому i i a1 согласно таблице ∆ соответствует кортеж i liE , \|\|,...,1 iil ζ= , то функционал ( )∑ = ∈ = p i i t i l aa EExF itl1 , 1 ,max)( ρ ζ (19) может служить мерой однородности разбиения x . Модели и методы решения нечетких задач дискретной оптимизации … Системні дослідження та інформаційні технології, 2005, № 2 19 При построении целевых функционалов можно использовать также по- нятие меры сходства — неотрицательную действительнозначную функцию ijji aa σσ =),( , удовлетворяющую требованиям 1),()2;,1),(0)1 =≠<≤ jijiji aaaaaa σσ ; 3) ),(),( ijji aaaa σσ = . Основываясь на мерах сходства, целевой функционал примет вид ( )∑ = ′ ∈′ = m i pppp EExF i1 ,2 ,min)( ρ ζ . (20) Используя формулу среднего расстояния между кластерами ji ζζ , ∑ ∑ ∈ ∈ = i jja a jijiji EED ζ ζ ζζρζζ 1 /),(),( , приходим к функционалу ∑∑ = = = \|\| 1 \|\| 1 3 ),()( x i x j jiDxF ζζ . Функционалы )(),(),( 321 xFxFxF применимы как в случае четких, так и нечетких величин, составляющих таблицу ∆ . Приведем еще функционал )(4 xF , имеющий смысл только в случае, если элементы таблицы ∆ есть размытые числа. Экстремум функционалу 4F дает разбиение, которое имеет наименьший показатель размытости (ана- лог понятия энтропии Шеннона) и для кластера xi ∈ζ определяется так: ( ) ( )∑ = −= \|\| 1)( )()( ln)( i ii ik ikiki aa ζ ζζ µµζδ . (21) При вычислении функционала )(4 xF может использоваться показатель размытости (21), например, функционал )(4 xF согласно физическому со- держанию задачи может принимать вид )(max)(1 4 i xi xF ζδ ζ ∈∀ = , (22) ∑ ∈ = x i i x xF ζ ζδ )( \|\| 1)(2 4 , (23)         = ∑ ∈x i i x xF ζ ζδ )( \|\| 1)( 23 4 . (24) Приведем некоторые разъяснения на случай, когда значениями целево- го функционала )(xF задачи являются размытые числа. Для задач типа 2 цель — минимальное количество классов. В случае размытой трактовки этой цели физическое содержание ее можно сформулировать как «почти минимальное количество классов». При более строгом определении целево- го функционала следует задать вид функции принадлежности искомого раз- мытого числа, например, это может быть сплайн-функция с заданной вели- Сергиенко И.В., Парасюк И.Н., Каспшицкая М.Ф. ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 20 чиной носителя. Таким образом, из окрестности выбирается несколько «наилучших» точек. В дальнейшем они служат центрами вспомогательных окрестностей, объединение которых будет использовано для выбора «луч- ших» точек. Может сложиться впечатление, что на протяжении итерацион- ного процесса количество «лучших» точек будет возрастать неограниченно. Однако этого не случится, поскольку на заданной в условии задачи длине носителя может поместиться только ограниченное количество точек, абс- циссы которых целые числа. При такой формулировке цели задачи («почти минимальное число классов») величины, которые образуют таблицу ∆ , мо- гут быть как четкими, так и размытыми. В последнем случае имеет смысл понятие размытой величины второго рода в применении к решению задачи. Подобная ситуация возникает в задачах типа 1, если целевой функционал определяется размытыми числами. Обратим внимание на то, что функционалы 3 4 2 4 1 4321 ,,,,, FFFFFF , употребляемые как целевые в одной задаче, в другой — могут входить в со- став ограничивающих условий. Например, имеет смысл задача: определить минимум целевого функционала )(1 xF (19) при условии δ≤)(1 4 xF , где δ — заданное число. Относительно ограничивающих и целевых функционалов следует от- метить, что они для своего определения зачастую требуют дополнительной информации, не содержащейся в таблице ∆ . Например, это может быть ин- формация, о взаимной совместимости или несовместимости отдельных свойств элементов. Такую информацию удобно записать в виде квадратной матрицы mm jiij , 1, = = γΓ , где ijγ — коэффициенты совместимости — четкие или размытые числа (последнее более соответствует физическому смыслу этих величин), определенные следующим образом: 0<− ijγ , если свойства ji ee , несовместимы (антагонистичны); 00 =ijγ , если свойства ji ee , индифферентны; 0>+ ijγ , если свойства ji ee , совместимы (усиливают друг друга). По информации, содержащейся в матрице Γ , можно построить функ- ционал разбиения ∑ ∑ ∑ = ∈ = = \|\| 1 1 5 )()( x k a m j ij ki xxF ζ γ , общая сумма коэффициентов несовместимости которого не превышает за- данного числа. Важно, что при решении рассмотренных выше задач элементы множе- ства S признаков (критериев), как правило, не являются равноправными, что следует учитывать при построении целевого функционала и ограничи- тельных функций. Одним из возможных подходов к учету такого случая, на наш взгляд, является построение иерархии признаков, например, по аналогии с тем, как Модели и методы решения нечетких задач дискретной оптимизации … Системні дослідження та інформаційні технології, 2005, № 2 21 это делается в методе анализа иерархий [15], путем попарного сравнения признаков и присвоения локальных преимуществ в численном или лингвис- тическом виде. Затем, в предположении, что каждому такому сравнению признаков (критериев) из множества S поставлена в соответствие некоторая величина локального приоритета ijγ , \|\|,...,2,1, Sji = (c учетом свойства об- ратной симметричности в случае числовых значений ijγ равны ijγ 1 ), для числовых характеристик попарных сравнений получаем матрицу 111 11 1 21 2 21 112     nn n n γγ γ γ γγ =Γ . Для определения обобщенных приоритетов признаков целесообразно использовать значения собственного вектора матрицы Γ . Это следует из того, что уравнение, определяющее собственный вектор матрицы Γ , и со- ответствующее ему значение λ находятся из уравнения xx λ=Γ , и, следо- вательно, матрицу Γ естественно характеризовать ее собственным векто- ром. Невырожденность матрицы Γ предполагается изначально. Правда, вы- числение собственных векторов может потребовать довольно много време- ни. Поэтому можно воспользоваться более простым приемом — вычислени- ем геометрического среднего, а именно, перемножением элементов в каждой строке и извлечением корня m -й степени. Полученный таким обра- зом столбец нормализуется делением каждого числа на сумму всех чисел. Имеются и другие способы использования матрицы Γ для определения приоритетов, например, [15, 16]. Отметим, что описанными способами можно получить значения весо- вых коэффициентов jδ в формуле (13) так же, как и в других аналогичных случаях [17–20]. ЗАКЛЮЧЕНИЕ Рассмотренные модели далеко не исчерпывают всего спектра оптимизаци- онных задач, возникающих на пути проектирования и функционирования диагностических информационных технологий, а ряд важных и интересных вопросов заслуживает более глубокого исследования, например, общие про- блемы устойчивости (стабильности) решений задач рассмотренного класса и их зависимость от числового параметра [8, 10, 13, 18, 21], проблемы точно- сти полученных решений и построение соответствующих систем алгорит- мического и программного обеспечения в нечетком информационном про- странстве [6, 22]. Сергиенко И.В., Парасюк И.Н., Каспшицкая М.Ф. ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 22 ЛИТЕРАТУРА 1. Zadeh L.A. Fuzzy Probabilities and Their Role Decision Analysis // Proc. of. IFAC Symp. «Theory and Appl. Of Digital Control». — New Delhi: IFAC, 1982. — P. 15–21. 2. Нечеткие множества в моделях управления и искусственного интеллекта / Под ред. Д.А. Поспелова. — М.: Наука, 1986. — 396 с. 3. Обработка нечеткой информации в системах принятия решений / А.Н. Борисов, А.В. Алексеев, Г.В. Меркурьева и др. — М.: Радио и связь, 1989. — 304 с. 4. Прикладные нечеткие системы: Пер. с япон. / Под ред. Т. Тэрано, К. Асан, М. Сугэно. — М.: Мир,1993. — 366 с. 5. Нечеткие множества и теория возможностей / Под ред. Г. Ягера — М: Радио и связь, 1986. — 408 с. 6. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. — Киев: Наук. думка, 1985. — 384 с. 7. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. — Киев: Наук. думка, 1981. — 287 с. 8. Каспшицкая М.Ф., Парасюк И.Н. Об одном классе задач оптимального покры- тия в нечеткой постановке // Компьютерная математика. — 2002. — № 2. — C. 93–105. 9. Слепцов А.И., Тищук Т.А. Метод расчета характеристик операций в задаче не- четкого планирования и управления //Кибернетика и системный анализ. — 2003. — № 3. — C. 58–71. 10. Сергиенко И.В., Парасюк И.Н., Каспшицкая М.Ф. Об одной нечеткой задаче многопараметрического выбора оптимальных решений // Кибернетика и системный анализ. — 2003. —№ 2. — С. 3–14. 11. Mizumoto M., Tanaka K. Algebraic properties of fussy numbers. — Jn: Proc. IEEE Int. Conf. «Cybernetics and Society». — 1976. — Р. 559–563. 12. Березин И.С., Жидков Н.П. Методы вычислений. Т. 1. — М: Гос. изд.физ.-мат. лит., 1959. — 464 с. 13. Каспшицкая М.Ф., Парасюк И.Н. О некоторых классах размытых задач клас- сификации: формализация, методы решения // Компьютерная математи- ка. — 2004. — №1. — С. 73–90. 14. Руа Б. Классификация и выбор при наличии нескольких критериев (метод ELECTRE) // Вопросы анализа и процедуры принятия решений: Сб. пере- водов. — М.: Мир, 1976. — С. 80–107. 15. Саати Т., Кернс К. Аналитическое планирование. Организация систем: Пер. с англ. — М.: Радио и связь, 1991. — 224 с. 16. Кофман А. Введение в теорию нечетких множеств. — М.: Радио и связь, 1982. — 432 с. 17. Заде Л. Понятие лингвистической переменной и его применение к понятию приближенных решений. — М.: Мир, 1976. — 165 с. 18. Гвишиани Н.Д., Агаян С.М., Богоутдинов Ш.Р. Математические методы геоин- форматики. I. Новый подход к кластеризации // Кибернетика и системный анализ. — 2002. — № 2. — С. 104–122. 19. Каспшицкая М.Ф., Сергиенко И.В., Стиранка А.И. Некоторые свойства дискре- тных размытых множеств // ЖВМ и МФ. — 1990. — № 7. — С. 1107–1112. 20. Dubois D. and Prade H.. Operations on Fuzzy Numbers // Int. 7. Systems Sci, 1978. — 9, № 6. — Р. 613 – 626. 21. Василевич Л.Ф. Анализ чувствительности и стабильности нечетких систем // Кибернетика и системный анализ. — 1998. — № 1. — С. 166–1 22. Парасюк И.Н., Сергиенко И.В. Пакеты программ анализа данных: Технология разработки. — М: Финансы и статистика, 1988. — 160 с. 72. Поступила 08.07.2004 МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ НЕЧЕТКИХ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ В ДИАГНОСТИЧЕСКИХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЯХ И.В. СЕРГИЕНКО, И.Н. ПАРАСЮК, М.Ф. КАСПШИЦКАЯ ВВЕДЕНИЕ Задачи типа 1. Задачи типа 2. Заключение

Модели и методы решения нечетких задач дискретной оптимизации в диагностических информационных технологиях

Institution

Ähnliche Einträge