Сравнение нечётких интервалов LR-типа при автоматизированном проектировании функционально распределённых систем обработки данных

ПРИБОРОСТРОЕНИЕ

УДК 658.512.0)1.56

В. В. РОДИОНОВ

СРАВНЕНИЕ НЕЧЁТКИХ ИНТЕРВАЛОВ ЬЯ- ГИПА ПРИ АВТОМАТИЗИРОВАННОМ ПРОЕКТИРОВАНИИ ФУНКЦИОНАЛЬНО РАСПРЕДЕЛЁННЫХ СИСТЕМ ОБРАБОТКИ ДАННЫХ

Обосновывается необходимость использования нечётких величин при проектировании функционально распределённых систем обработки данных, целесообразность аппроксимации этих величии на основе нечётких интервалов ЬЛ-типа. Рассматривается краткая классификация методов сравнения нечётких интервалов, применимость, достоинства и недостатки отдельных методов. Описывается теоретическая основа и практическая реализация четырёх взаимодополняющих показателей сравнения при использовании трёх различных функций Ь и /?. Приводятся краткие сведения о

САПР, созданной в рамках предлагаемых подходов.

При проектировании функционально распределённых систем обработки данных (ФР СОД) одной из основных задач является нахождение оптимального баланса между программной и аппаратной реализацией функций класса задач, решаемых системой. Хотя выбор способа реализации может быть сделан на основе экспертных оценок, однако при большом количестве функций и достаточно жёстких критериях найденное решение будет не оптимальным, а в лучшем случае приемлемым. В современных условиях практически любая сложная разработка сопровождается моделированием, позволяющим, в частности, производить выбор оптимальных проектных решений на самых ранних стадиях. Характерной особенностью реальных систем, которую следует учитывать при разработке моделей, является принципиальная неопределенность значений их параметров [6]. Поэтому результаты моделирования на основе «точных» данных малоприменимы на практике.

Любая модель или теория может быть обобщена и «приближена к реальности» при помощи средств теории нечётких множеств [3]. Это не единственный способ учёта неопределённое™. Однако строгое применение вероятностных моделей часто затруднено ввиду недостатка информации о распределении вероятностей конкретных параметров, а с интервальными величинами можно работать и в рамках теории нечётких множеств. По этим причинам автоматизированное проектирование ФР СОД с использованием нечётких величин наиболее целесообразно.

Для многих применений достаточно ЬЯ-аппроксимашш нечётких множеств в рамках теории нечётких интервалов (НИ) [2, 5]. НИ занимает промежуточное положение между' чётким интервалом и нечётким множеством, обладая преимуществами тех и других: ядро НИ. может содержать наиболее

© В. В. Родионов, 2005

правдоподобные значения, тогда как функции Ь и К задают характер изменения возможностей для оставшихся значений. Для функций формы НИ (Ь и К) выбрана функция тах(0,1 — хр). Предусмотрено три

типа изменения возможностей за пределами ядра НИ: линейный (нормальный) (р = 1), ниже среднего

(ри выше среднего (р= 2). Линейный тип

.2

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

Помимо алгебраических операций, приводящих к преобразованиям НИ, в задачах оптимизации, использующий целевые функции и ограничения на основе НИ, крайне важны операции сравнения НИ. Этот вопрос в литературе до сих пор освещён крайне слабо или в лучшем агучае поверхностно [1].

Наиболее универсальны методы сравнения НИ, основанные на а-уровневом разложении НИ [1]. Дополнительным преимуществом этих методов служит то, что они могут опираться на хорошо разработанный аппарат сравнения чётких интервалов. В качестве представителя этой группы методов в [1] описан теоретико-вероятностный подход, позволяющий определить вероятность, с которой один интервал больше другого, а также вероятность их равенства. Однако ЬИ-аппроксимация НИ делает а-уровневое представление избыточным.

Качественные методы предназначены для выяснения характера отношений между НИ (равенства, большинства или меньшинства), базируясь в основном на анализе графических интерпретаций НИ. Од-

нако эти методы не способны ответить на вопрос, насколько, например, один НИ больше другого, и сильно зависят от вида анализируемых НИ.

Для выяснения степени неравенства можно использовать количественные методы, к числу которых относят расстояние Хемминга, расстояние Евклида и др. [4]. Расстояние Хемминга, для НИ М и N

П

равное p(N,M) = ]Г| juN(x, ) |, зависит

#=1

от количества п выбранных чётких значений, поэтому предпочтительнее использовать относительное расстояние Хемминга, которое получается делением p{N,M) на п Однако расстояние Хемминга и другие несложные в вычислении показатели часто вступают в противоречие с интуитивным пониманием ситуации [1]. Так, в данном случае это скорее критерий вложенности одного НИ в другой.

Другой распространённый способ - сравнение репрезентативных чисел НИ, в частности, полученных при дефаззификации НИ (например, с помощью нахождения центра тяжести нечёткого числа [5]). Однако в пограничных случаях любое упрощение не может не сказаться на корректности результатов.

Наилучшие результаты даёт сочетание качественных и количественных методов с применением нескольких показателей сравнения [1], которые учитывают как характер пересечения НИ, так и взаимное расположение интервалов. В работе для сравнения НИ использованы четыре показателя неравенства, описанные в [2].

Для сравнения НИ М = (m,m,a,j3)LR и N = (п,п,у,cr)IR, где 772, /77 - границы ядра НИ, а,

[3 - коэффициенты нечеткости (КН), вводится ряд дополнительных множеств. Для НИ М это множества чисел, которые, возможно (с необходимостью), больше или равны значениям переменной,связанной с НИ М; они обозначаются соответственно [М; +оо) и (М; +оо) (рис. 1). Их функции принадлежности описываются следующим образом:

Н[м.ю) (= Пм ([w,+oо)) = sup рм (и) ,

//<><'

V(M. «о) (W) = Нм(( w,+co)) = inf 1- рм (и),

U<W

где Пм и Нк! - меры возможности и необходимости, заданные по распределешпо рм .

Точно так же определяются множества (-00; М] и (-со; М) - нечёткие множества чисел, возможно (с необходимостью), меньше, чем М.

и -------М [М; +оо) -----------(М; +со) R

Рис. 1. Соотношение множеств М,

[М ; +со).

Для определения большего из двух НИ М и N можно сравнивать множества М и [N; +со), {VI и (N; +оо), вычисляя по ФП ph{ возможность или необходимость нечётких событий [N; -н») и (N; +со).

Рассмотрим следующие показатели неравенства НИ.

1) Показатель PSE - Pos(Х>У) :

Пм ([N; + со)) = supmin(рм(и),supph,(v)) . (О

и v£n

Пусть X и У - переменные, имеющие области определения, ограниченные НИ М и N соответственно.

Тогда величину 17 Kf ([N; + со)) можно интерпретировать как возможность Pos(X > Y) того, что наибольшие значения, которые может принимать переменная X. будут больше или равны наименьшим значениям переменной Y.

2) Показатель PS - Pos(X > Y ) :

ITM

U v£f/

3)ПоказательNSE- Nec(X_>Y_):

HM

u v<u

Nec(X_>YJ - это необходимость того, что наименьшие значения, принимаемые переменной X, будут больше или равны наименьшим значениям переменной Y.

4) Показатель NS - Nec(X > Y):

IIм

il

Теоретико-множественные определения показателей, приведённые выше, неудобны для практических вычислений, а для LR-чисел являются избыточными. В [2] описаны формулы, являющиеся функциями от значений границ ядра и КН:

PSE — Pos

/3 + у

NSE = Nec

a + y

PS - Pos

J3 + 5

Л;£ - №с(Х_ > У) - тах((),ппп(1,

/77 — 77

)) -

а + 5

Формулы (5)-(8) не учитывают нелинейность функций формы Е и Я и дают точный результат лишь при сравнении трапециевидных интервалов. Получение точных значений при любых Ь и Я связано с нахождением координат точек пересечения левых и/или правых частей ФП двух сравниваемый НИ. На основе формул, предложенных в [2], и сравнительного анализа выражений (1)-(4), (5)-(8) нами были получены следующие уравнения:

РЗЕ = Роз(X > У) = К

(и-т' — т 77 — И

Р V — Л/ к У J

№Е = ЛТес(Х >У) = 1-Ь

Г N

777 — И

\

а

У

= Ь

/7 — II

\

РЭ = Роб(X > У) = Я

г

и — т

\

/3

= 1-Я

Г ~\ и ~ 77

/ \ 77? — и

\

/

8

\

а

и - 77

5

/

)

Должны быть рассмотрены все возможные соче-

-Р,- П

тания р^г и р^,. Таковых может быть 4-3 =36 (реально достаточно рассмотреть 28), пр!гчём в восьми случаях решаются уравнения четвёртой степени (методом Феррари). Очевидно, что сложность решения и программирования нескольких десятков уравнений несоизмерима с использованием формул (5)-(8), но это своего рода цена, которую пришлось заплатать за точность. Если графики функций Е или И для соответствующего показателя не имеют точки пересечения, то вместо результатов решения уравнений (9)-(12) используются формулы (5-8), где подобные ситуации предусмотрены.

Итоговое сравнение НИ М и N проводится следующим образом. Показатели РБЕ, .ШЕ, Р8, N8 вычисляются сначала для НИ М по сравнению с НИ 14, все полученные значения суммируются:

= РЗЕМ + Н8ЕМ + Р8м+№м . При помощи сравнения НИ N с НИ М вычисляется сумма 8*,. Если Бм >5а;, то НИ М больше НИ N. и наоборот. Причём разность АЗ =| Зм - 5^ |, Л? е [0,4] показывает

степень различности двух НИ: если - 0, то М = N , при р М и N не пересекаются. Поэтому можно предложить простой способ установления равенства двух НИ: «точное равенство», если

и «мягкое равенство», если | 8И |< £ , где £ > 0 - допустимая погрешность.

Описанная методика сравнения НИ реализована в рамках САПР ФР СОД, созданной в среде БефЫ. Было взято значение £ — 0,1 (2.5% от 4-х), достаточно

большое, чтобы влиять на результат, и достаточно малое, чтобы не вносить существенных искажений. При использовании линейных формул (5)-(8) откло-

~ Я* >

непие может составить более 20%, что равняется почти полному значению одного из четырёх показателей. Однако если один из сравниваемых НИ полностью входит в состав другого, то оба интервала будут признаны идентичными в любом случае, что вполне согласуется со здравым смыслом. В связи с этим становится особенно ясной неадекватность расстояния Хеммннга и других подобных показателей, которые, напротив, основаны именно на анализе включения одного НИ в другой.

Проведённые эксперименты показали, что при замене обычных числовых значений на НИ операции сравнения остаются полностью корректными, а практическое использование разработанной САПР позволяет получать оптимальные конфигурации систем обработки данных.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Дили гене кий, Н. В. Нечёткое моделирование и многокритериальная оптимизация производственных систем в условиях неопределенности: технология, экономика, экология / Н. В. Дилигенский, Л. Г. Дымова, П. В. Севастьянов.-- М.: Машиностроение-1, 2004.-401 с.

2. Дюбуа, Д. Теория возможностей. Приложение к представлению знаний в информатике / Д. Дюбуа,

А. Прад / пер. с фр. В. Б. Тарасова; под ред.

С. А. Орловского. - М.: Радио и связь, 1990.-286 с.

3. Заде, Л. А. Роль мягких вычислений и нечёткой логики в понимании, конструировании и развитии информационных/интеллектуальных систем // Новости искусственного интеллекта. - 2001.- №2-3.-С. 7-11.

4. Пивкин, В. Я. Нечёткие множества в системах управления: методическое пособие / В. Я. Пивкин,

Е. П. Бакулин, Д. И. Кореньков. - Новосибирск: Новосибирский государственный университет, 1997. — 52 с.

5. Прилуцкий, М. X. Многостадийные задачи распределения и упорядочения с нечёткими характеристиками [Электронный ресурс] // Электронный журнал «Исследовано в России». - 2001.- С. 1182-1189 // http://zhumal.ape.relam.ru

6. Шишкин. В. В., Родионов, В. В. Оптимальный выбор аппаратного или программного способа реализации функций для функционально распределённой системы обработки данных с использованием нечётко заданных критериев оценки // Труды междунар. науч,-техн. конф. «Интеллектуальные системы» и «Интеллектуальные САПР». В 3 Т. (Дивноморское, 3-10 сентября 2003 г.). - М.: Изд-во Физико-математической литературы. 2003. - Т. 1. - С. 137-140.

Родионов Виктор Викторович, ассистент кафедры ИВК УлГТУ.