Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

SEVERAL ASPECTS OF INCREASING OF THE EFFECTIVENESS OF THE MAKING DECISIONS BY INTELLIGENT SYSTEMS USING FUZZY INFERENCE

Dolinina O.N. 1 Shvarts A.Y. 1
1 Yury Gagarin State Technical University of Saratov
Рассмотрены продукционные базы знаний экспертных систем, использующих нечеткий вывод. Приведен сравнительный анализ различных подходов и алгоритмов принятия решений на основе нечеткой логики. Описанные методы нечеткого вывода могут быть выполнены параллельно на нескольких вычислительных узлах, что может значительно снизить временные затраты на принятие решений в интеллектуальных системах. Для повышения эффективности параллельных вычислений при принятии решения предлагается построение графа зависимостей правил в базе знаний и зависимостей лингвистических переменных в правилах. Обработка правил и переменных предполагает предварительное разбиение на группы. На основе сформированных групп выполнения правил и дефаззификации лингвистических переменных планируется повысить эффективность процесса принятия решений за счет применения параллельных вычислений в пределах каждой группы, что актуально для баз знаний большой размерности.
There are considered rule-based expert systems using fuzzy inference. Comparative analysis of different approaches and algorithms of making decisions on the base of fuzzy logic is given. Described methods can be processed on several computational nodes in parallel what can reduce time of making decision by intellectual systems. Building of graph of the dependence of the rules and the graph of dependence of the linguistic variables are suggested. Rules and variables should be divided into groups previously. On the base of the developed groups of rules and defuzzification of the linguistic variables it is planned to increase the effectiveness of the decision making with using of parallel calculations for each group what is considered to be an actual problem for the large dimension knowledge bases.
expert systems
fuzzy inference
increasing of the effectiveness of the making decisions
algorithms of the building of the rules’ dependence
1. Dolinina O.N., Antropov P.G., Kuz’min A.K., Shvarc A.Ju. Ispol’zovanie intellektual’nyh sistem dlja diagnostiki neispravnostej gazoperekachivajushhih agregatov // Sovremennye problemy nauki i obrazovanija. 2013. no. 6; URL: http://www.science-education.ru/113-11252 (data obrashhenija: 23.12.2013).
2. Jang J.-S. R., ANFIS: Adaptive-Network-Based Fuzzy Inference System // IEEE Transactions on Systems & Cybernetics, vol. 23, pp. 665–685, 1993.
3. Larsen P.M., Industrial Applications Of Fuzzy Logic Control // International Journal Of Man-Machine Studies, Vol. 12, pp. 3–10, 1980.
4. Mamdani E.H., Assilian S., An Experiment In Linguistic Synthesis With Fuzzy Logic Controller // International Journal Of Man-Machine Studies, Vol. 7, no. 1, рp. 1–13, 1975.
5. Mizumoto M., Fuzzy controls under various fuzzy reasoning methods // Information Science, Vol. 45, pp. 129–151, 1988.
6. Seki H., Mizumoto M., On the Equivalence Conditions of Fuzzy Inference Methods – Part 1: Basic Concept and Definition // IEEE Transactions on Fuzzy Systems, Vol. 9, no. 6, pp. 1097–1106, 2011.
7. Sugeno M. On stability of fuzzy systems expressed by fuzzy rules with singleton consequents // IEEE Transactions on Fuzzy Systems, Vol. 7, no. 2, pp. 201–224, 1999.
8. Tsukamoto Y., An Approach To Fuzzy Reasoning Method // Gupta M.M. Et Al (Eds.), Advances In Fuzzy Set Theory And Applications, pp. 137–149, 1979.
9. Takagi T., Sugeno M., Fuzzy Identification Of Systems And Its Applications To Modeling And Control // IEEE Transactions On Systems, Man, And Cybernetics, Vol. 15, no. 1, pp. 116–132, 1985.
10. Yubazaki N., Yi J., Hirota K., SIRMs (Single Input Rule Modules) connected fuzzy inference model // Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 1, no. 1, pp. 23–30, 1997.
11. Zadeh L.A., Fuzzy Sets // Information and Control, Vol. 8, pp. 338–353, 1965.
12. Zadeh L.A., The Concept Of A Linguistic Variable And Its Application To Approximate Reasoning // Information Sciences, Vol. 8, pp. 199–249, 301–357; Vol. 9, pp. 43–80, 1975.

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

Среди интеллектуальных систем наибольшую популярность получили экспертные системы (ЭС), позволяющие хранить, накапливать и использовать экспертные знания с целью автоматизации принятия решений в различных областях. Ядром ЭС является база знаний, включающая механизм принятия решений. Необходимо отметить, что с момента появления первых экспертных систем в семидесятых годах двадцатого века до настоящего времени развитие экспертных систем прошло достаточно большой путь в смысле развития моделей представления знаний: от простейших продукционных моделей с детерминированными правилами вида до комбинации различных способов представления знаний, позволяющих учитывать особенности предметной области.

Представим базу нечетких правил в виде

(V, I, G, P, R), (1)

где V – универсальное множество лингвистических переменных системы; I – множество входных лингвистических переменных, I ⊂ V; G – множество выходных лингвистических переменных, G ⊂ V; P – множество промежуточных лингвистических переменных, P ⊂ V, I ∪ G ∪ P = V, I ∩ G = ∅, I ∩ P = ∅, P ∩ G = ∅; R – множество правил вида

<rj, uj> ЕСЛИ vj,1 есть tj,1 И…И dolinina01.wmf есть dolinina02.wmf ТО dolinina03.wmf есть dolinina04.wmf, (2)

где rj – уникальное имя правила; uj – лингвистическая степень уверенности в истинности правила rj; nj – количество лингвистических переменных, задействованных в правиле; dolinina05.wmf – входные лингвистические переменные для правила rj; их множество обозначим Gj; dolinina06.wmf – значения входных лингвистических переменных (термы) для правила rj; dolinina07.wmf – выходная лингвистическая переменная для правила rj; dolinina08.wmf – значение выходной лингвистической переменной для правила rj.

Чаще всего эксперт не может однозначно трактовать те ли иные факты и их влияние на принятие решения. Среди методов, позволяющих обрабатывать неточные знания, часто используется аппарат нечеткой логики, введенный в классических работах Заде [11,12]. Нечеткое множество A может быть представлено в виде

dolinina09.wmf (3)

где X – универсальное множество; x – элемент множества X; μA(x) – функция принадлежности.

Функция принадлежности μA(x) характеризует степень принадлежности каждого x ∈ X нечеткому множеству A, причем μ:X → [0, 1]. Таким образом, μA(x) принимает значение 1 в случае, если элемент x полностью включен во множество A, и значение 0 в случае, если элемент x не включен во множество A. Значения функции принадлежности, лежащие на интервале (0, 1), характеризуют нечетко включенные элементы.

Общая схема механизма принятия решений в ЭС, основанных на нечетком выводе, представлена на рисунке.

pic_1.wmf

Схема системы нечеткого логического вывода

В литературе описано несколько различных подходов и алгоритмов принятия решений с использованием нечеткого вывода. Стоит отметить, что каждый из описанных в литературе алгоритмов [3–10] отличается не только характером и последовательностью операций, выполняемых в ходе фаззификации, нечеткого логического вывода и дефаззификации, но и видом используемых нечетких правил.

Методы Мамдани, Ларсена, Цукамото и product-sum-gravity оперируют нечеткими правилами, вид которых наиболее близок образу представления знаний человеком. Следовательно, формирование базы правил экспертом в случае использования этих методов будет наименее трудозатратным.

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

Метод Цукамото накладывает требования к монотонности функций принадлежности выходных переменных, что во многих системах недопустимо.

Метод SIRMs требует при формировании базы правил группировать их в модули, кроме того, каждое правило должно содержать только одну входную переменную.

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

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

Для решения описанной проблемы предлагается метод определения очередности выполнения правил в базах правил с описанными выше особенностями.

На первом этапе сгенерируем матрицу зависимостей правил. Рассмотрим следующий алгоритм.

Алгоритм генерации матрицы зависимостей правил

Шаг 1. Инициализировать нулями квадратную матрицу DR размерностью |R|×|R| (где |R| – мощность множества R).

Шаг 2. Для каждого rj ∈ R выполнить Шаг 3.

Шаг 3. Для каждого rq ∈ R, rq ≠ rj выполнить Шаг 4.

Шаг 4. Если dolinina10.wmf, то DRj,q = 1 и DRq,j = –1.

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

Каждому правилу rj ∈ R поставим в соответствие значение функции ρ(rj), определяющее порядковый номер группы выполнения правил. Порядковый номер группы имеет следующий смысл: правило dolinina11.wmf не может быть выполнено раньше правила dolinina12.wmf, если dolinina13.wmf.

Алгоритм расчета функции ρ(rj), определяющей порядковый номер группы выполнения правил

Шаг 1. Инициализировать нулями множество RO, |RO| = |R|.

Шаг 2. j = 1.

Шаг 3. Если j ≤ |R|, то перейти к Шагу 4, иначе перейти к Шагу 10.

Шаг 4. i = 1.

Шаг 5. Если i ≤ |R|, то перейти к Шагу 6, иначе перейти к Шагу 8.

Шаг 6. Если DRj,i = –1, то перейти к Шагу 9.

Шаг 7. i = i + 1.

Шаг 8. roj = 1.

Шаг 9. j = j + 1. Перейти к шагу 3.

Шаг 10. j = 1, c = 0.

Шаг 11. Если j ≤ |R|, то перейти к Шагу 12, иначе перейти к Шагу 20.

Шаг 12. i = 1, m = 1.

Шаг 13. Если i ≤ |R|, то перейти к Шагу 14, иначе перейти к Шагу 17.

Шаг 14. Если DRj,i = –1, то перейти к Шагу 15, иначе перейти к Шагу 16.

Шаг 15. Если roi > m, то m = roi.

Шаг 16. i = i + 1. Перейти к Шагу 13.

Шаг 17. Если roj < m + 1, то c = 1.

Шаг 18. roj = m + 1.

Шаг 19. j = j + 1. Перейти к Шагу 11.

Шаг 20. Если c = 0, то перейти к Шагу 21, иначе перейти к Шагу 10.

Шаг 21. Для каждого rj: ρ(rj) = roj.

На основе полученных значений ρ(rj) формируются множества

RGm:rj ∈ RGm ⇔ ρ(rj) = m, dolinina14.wmf

где LR – количество групп выполнения правил.

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

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

Шаг 1. Инициализировать нулями квадратную матрицу DV размерностью |V|×|V|.

Шаг 2. Для каждого vk ∈ V выполнить Шаг 3.

Шаг 3. Для каждого vh ∈ V, vh ≠ vk выполнить Шаг 4.

Шаг 4. Для каждого rj ∈ R выполнить Шаг 5.

Шаг 5. Если vk ∈ Gj и dolinina15.wmf то DVk,h = 1 и DVh,k = –1.

Полученная матрица DV может быть интерпретирована как матрица смежности ориентированного графа зависимости лингвистических переменных.

Каждой лингвистической переменной vk ∈ V поставим в соответствие значение функции ρ(vk), определяющее порядковый номер группы дефаззификации переменной. Порядковый номер группы имеет следующий смысл: переменная dolinina16.wmf не может быть дефаззифицирована раньше переменной dolinina17.wmf, если dolinina18.wmf.

Алгоритм расчета функции ρ(vk), определяющей порядковый номер группы дефаззификации переменной

Шаг 1. Инициализировать нулями множество VO, |VO| = |V|.

Шаг 2. k = 1.

Шаг 3. Если k ≤ |V|, то перейти к Шагу 4, иначе перейти к Шагу 10.

Шаг 4. h = 1.

Шаг 5. Если h ≤ |V|, то перейти к Шагу 6, иначе перейти к Шагу 8.

Шаг 6. Если DVk,h = –1, то перейти к Шагу 9.

Шаг 7. h = h + 1.

Шаг 8. vok = 1.

Шаг 9. k = k + 1. Перейти к шагу 3.

Шаг 10. k = 1, c = 0.

Шаг 11. Если k ≤ |V|, то перейти к Шагу 12, иначе перейти к Шагу 20.

Шаг 12. h = 1, m = 1.

Шаг 13. Если h ≤ |V|, то перейти к Шагу 14, иначе перейти к Шагу 17.

Шаг 14. Если DVk,h = –1, то перейти к Шагу 15, иначе перейти к Шагу 16.

Шаг 15. Если voh > m, то m = voh.

Шаг 16. h = h + 1. Перейти к Шагу 13.

Шаг 17. Если vok < m + 1, то c = 1.

Шаг 18. vok = m + 1.

Шаг 19. k = k + 1. Перейти к Шагу 11.

Шаг 20. Если c = 0, то перейти к Шагу 21, иначе перейти к Шагу 10.

Шаг 21. Для каждого vk: ρ(vk) = vok.

На основе полученных значений ρ(vk) формируются множества

VGm:vk ∈ VGm ⇔ ρ(vk) = m, dolinina19.wmf,

где LV – количество групп выполнения переменных.

Подразумевается, что каждая переменная, для которой ρ(vk) = 1, является входной переменной (vk ∈ I) и не нуждается в дефаззификации.

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

Рецензенты:

Кушников В.А., д.т.н., профессор, ведущий научный сотрудник, зам. директора по научно-организационной работе, Институт проблем точной механики и управления РАН, г. Саратов;

Шульга Т.Э., д.т.н., зав. кафедрой «Прикладная информатика и программная инженерия», международный факультет прикладных информационных технологий, Саратовский государственный технический университет им. Гагарина Ю.А., г. Саратов.

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