Организация экспертных систем продукционного типа на локальнопараллельных нечетких алгоритмах

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

После этого проверяется, удовлетворяет ли хромо -сома-ребенок нашему условию- если нет, слагаемое возвращается хромосоме-родителю, а в хромосому-ребенок направляется следующее слагаемое. Таким образом, выполняется вся схема, пока не переберутся все гены хромосомы-родителя. Если оптимальный вариант не найден, начинается постановка генов — попарно. И снова до тех пор, пока не произойдет полный перебор всех генов. Если оптимальный вариант снова не найден, начинаем передавать по три гена. И так до тех пор, пока не найдется вариант, удовлетворяющий оптимальному критерию (17).
Таким образом, после нахождения полинома Колмогорова-Габора оптимальной длины, удовлетворяющего условию (17), мы выполняем проверку данного полинома, для выбранной альтернативы подставляя частные критерии. В нашем случае получается полином следующей длины:
Pi = kj + k2 + кз + k4 + kjk2 + kjk^. (19) Отсюда полезность альтернатив:
R3 = 2,9375 — R4 = 2,75 — R2 = 2,265- R5 = 1,892- Ri = 1,267.
Полезность альтернативы R3 максимальна, следовательно, остальные альтернативы действительно хуже, и задача решена правильно.
УДК 539. 87
ОРГАНИЗАЦИЯ ЭКСПЕРТНЫХ СИСТЕМ ПРОДУКЦИОННОГО ТИПА НА ЛОКАЛЬНОПАРАЛЛЕЛЬНЫХ НЕЧЕТКИХ АЛГОРИТМАХ
МИХАЛЬ О.Ф. __________________________
Рассматриваются принципы организации нечеткой экспертной системы (ЭС) продукционного типа на локально-параллельных (ЛП) алгоритмах. ЭС содержит каналы взаимодействия с оператором и объектом управления, поддерживает четыре режима: базовое обучение, адаптация, автономная подстройка и рабочий. Показывается, что перспективной областью применения ЛП алгоритмических решений могут стать интеллектуальные распределенные сетевые ЭС с децентрализованным использованием и обновлением знаний.
Интеллектуализация компьютерных систем, применяемых в управлении, разворачивается преимущественно в двух направлениях: описание объектов и явлений предметной области на основе аппарата нечеткой логики (НЛ) [1] и использование экспертных знаний (ЭЗ). Перспективным является пересечение указанных направлений-нечеткие экспертные системы (ЭС) [2] - по следующей причине. Носителем Э З есть человек, непрерывная циклическая познавательная деятельность которого (ги-
5. Выводы
Результаты исследований показали, что применение новой методики с использованием генетических алгоритмов дает ощутимый выигрыш во времени и качестве показателей, а также является более наглядным для ЛПР, нежели другие методы.
Литература: 1. Эйкофф П. Основы идентификации систем управления. М.: Мир, 1975. 238с. 2. Овезгелъдыев А. О., Петров Э. Г., Петров К. Э. Синтез и идентификация моделей многофакторного оценивания и оптимизации. К.: Наук. думка, 2002. 161 с. 3. Овезгелъдыев А. О., Петров К. Э. Компараторная идентификация параметров линейных моделей многофакторного оценивания // Радиоэлектроника и информатика. 1998. № 2(03). С. 41−43. 4. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970. 124с. 5. Курейчик В. М Генетические алгоритмы. Состояние. Проблемы. Перспективы. Таганрог, 1999. 6. Ротштейн А. П. Интеллектуальные технологии идентификации. Винница: «Универсум-Винница», 1999. 320с.
Поступила в редколлегию 03. 12. 2002
Петров Эдуард Георгиевич, д-р техн. наук, профессор, зав. кафедрой системотехники ХНУРЭ. Научные интересы: математическое моделирование, теория принятия решений. Адрес: Украина, 61 166, Харьков, пр. Ленина, 14, тел. 40−93−06.
Булавин Дмитрий Алексеевич, аспирант кафедры системотехники ХНУРЭ. Научные интересы: теория принятия решений, генетические алгоритмы. Увлечения: футбол, музыка, история. Адрес: Украина, 61 166, Харьков, ул. Ленина, 3, кв. 20, тел. 45−38−87, e-mail: dimetroid@yandex. ru.
потеза — эксперимент — обобщение — новая гипотеза) априорно предполагает на любом этапе неполноту и последовательное уточнение ЭЗ, а следовательно, их нечеткость. Поэтому представление ЭЗ средствами НЛ включает минимум промежуточных преобразований и вносит в них минимум искажений, что необходимо для достижения адекватного поведения ЭС в предметной области. Важной характеристикой при технической реализации НЛ систем является быстродействие. Его повышение диктуется потребностями предметной области и достигается либо аппаратно, специализированными средствами обработки — нечеткими процессорами- либо алгоритмически, в частности, использованием принципа локалъной параллелъности (ЛП) [3]. Основные ЛП-алгоритмы НЛ описаны в [3,4]. Функционирование Э С включает два фундаментальных процесса: приобретение и исполъзование ЭЗ. Процесс использования ЭЗ реализуется в ЭС, в частности, в составе системы управления. ЭС при этом в основных чертах функционально аналогичны блоку обработки в цепи обратной связи. Элементы организации подобных нечетких структур на ЛП-алгоритмах описаны в [5,6].
Цель настоящей работы-описание организации на ЛП-алгоритмах нечеткой ЭС, реализующей оба процесса: приобретение и использование ЭЗ, включая согласование вновь приобретенных ЭЗ со старыми. Описание приводится применительно к ЭС продукционного типа.
РИ, 2003, № 1
93
Экспертные системы
Как область исследовательской и инженерно-технической деятельности, ЭС пересекаются с системами управления, технической диагностики, распознавания образов (ситуаций) и обучающими системами. Разграничительным признаком является базируемость на ЭЗ. ЭС различаются по используемому механизму представления знаний [7]: связки вида объект-атрибут-значение- продукционные правила if (A)-then (B), где A — антецедентная (условная), B — консеквентная (заключительная) часть- фреймы- семантические сети и др. Границы между механизмами ЭС зачастую оказываются размытыми: фреймы могут рассматриваться как обобщения связок. В рамках продукционных правил получило развитие НЛ-ответвление ЭС- развиваются гибридные направления: продукционно-фреймовые, фреймово-продукционные, сети фреймов и др. [7]. В связи с использованием представления нечетких ЭЗ с применением лингвистических переменных (ЛгП) представляют интерес ЭС продукционного типа. Данная модель наиболее распространена [7] и интенсивно «ассимилирует» с другими моделями- поэтому реализация ее на Л П-алгоритмах перспективна, как направление развития, так и для комбинированных структур.
Важными составляющими ЭС (рис. 1) являются: база знаний (БЗ), механизм вывода (МВ), модуль пополнения знаний (МПЗ), адаптер технического устройства (АТУ), интерфейс оператора (ИО). Оператор (Оп) и техническое устройство (ТУ) с точки зрения ЭС являются объектами внешней среды — предметной области, для работы с которой предназначена ЭС. Для взаимодействия с ТУ АТУ включает датчики (Д): для снятия выходных характеристик ТУ и устройства управления (УУ), для выдачи воздействий на ТУ. Взаимодействие ИО-Оп может быть представлено аналогично взаимодействию АТУ-ТУ: ИО включает средства ввода (Вв) и вывода (Выв) информации для оператора. В обоих случаях имеются контуры обратной связи, замыкающиеся через I и II уровни ЭС:
ТУ ^ Д ^ II ^ I ^ II ^ УУ ^ ТУ ,
Оп ^ Вв ^ II ^ I ^ II ^ Выв ^ Оп.
Рис. 1. Четырехуровневая структурная схема ЭС
МПЗ предназначен преимущественно для приобретения знаний, а МВ — для их использования.
Взаимодействие между ними включает выдвижение и проверку гипотез, запрос и получение новых данных. Оп либо ТУ преобладают во взаимодействии с ЭС в зависимости от этапа работы или способа применения ЭС.
Структуру взаимодействия ЭС со средой целесообразно рассматривать как состоящую из четырех функциональных слоев: уровня БЗ (I) — уровня взаимодействия с БЗ (II), куда входят МПЗ и МВ- уровня взаимодействия с внешней средой (III), включающего ИО и АТУ- внешней среды (IV) — Оп и ТУ. Работа Э С предполагает циклическую передачу управления (состояния активности) снизу вверх и сверху вниз:
… ^ IV ^ III ^ II ^ I ^ II ^ III ^ IV ^ III ^…
Восходящий фрагмент (IV ^ … ^ I) соответствует получению и обработке информации внешней среды, нисходящий (IV ^… ^ I) — принятию решений и выработке рекомендаций или управляющих воздействий. При этом, как отмечалось, реализуется два процесса: приобретение и использование знаний, которые, с учетом симметрии структуры рис. 1, могут быть интерпретированы как 4 режима работы ЭС (рис. 2): базовое обучение (БО), адаптация (А), автономная подстройка (АП) и рабочий режим (РР). Режимы Б О и, А осуществляются с участием оператора- АП и РР-автономно, при взаимодействии ЭС с ТУ. Режим Б О соответствует заполнению пустой ЭС информацией «с нуля" — А — корректировке работы ЭС оператором в период опытной эксплуатации- АП-подстройке параметров МВ в соответствии с корректировками, внесенными оператором- РР — отлаженному состоянию при штатной эксплуатации ЭС. При ориентации ЭС на управление ТУ, после прохождения режима БО, режимы, А и АП должны чередоваться, пока оператор не придет к выводу, что ЭС адекватно себя ведет в предметной области. После этого ЭС продолжительное время используется в режиме РР, пока оператор не обнаружит несоответствий в ее работе, требующих новых корректировок — чередующихся периодов, А и АП (рис. 3, а).
Базовое обучение (БО)
Адапттщия (А)
БЗ БЗ
t
мпзН мпзИ МВ
ГГЖ ГГ t ж t
ИО I I ИО 1 1
* t t я
Оп On
Автономная Рабочий
подстройка (АГГ режим (РР)
БЗ БЗ
t
лшзИ MB Н мв
t ж t Z3ZSS ГГ
| | АТУ | | АТУ
* t * я
ТУ ТУ
Рис. 2. Режимы работы ЭС
94
РИ, 2003, № 1
Существенным моментом взаимодействия с оператором является способ применения ЭС: ее решения могут носить управляющий или рекомендательный характер. ЭС в рабочем управляющем режиме взаимодействует непосредственно с ТУ и мало чем отличается от системы управления. ЭС в рабочем рекомендательном режиме управляет ТУ не непосредственно, а через оператора. Оператор учитывает рекомендации ЭС, но независимо контролирует работу ТУ, принимает решения (возможно, с привлечением дополнительных данных) и выдает управляющие воздействия. С точки зрения ЭС, оператор реализует функции УУ- с точки зрения оператора, ЭС есть система поддержки принятия решений (СППР). С любой точки зрения оператор является дополнительным интеллектуальным звеном в цепи управления, в силу чего он наделен определенными функциями управления. При этом соотношение между перечисленными четырьмя режимами существенно зависит от способа применения ЭС- в частности, рекомендующая ЭС может чередовать режимы, А и АП (рис. 3, б).
Рис. 3. Управляющий (а) и рекомендательный (б) способы применения ЭС
Нечеткие экспертные системы
ЭЗ в нечетких ЭС хранятся в нечеткой форме [1], в виде ЛгП и наборов решающих правил (РП). ЛгП содержат наборы суждений относительно объектов и процессов предметной области, РП определяют продукционный процесс — логический вывод на основе суждений, представленных средствами ЛгП. ТУ (предметная область ЭС при использовании знаний) имеет nвыходных (A, AjAn) и m входных (Aj, A2,…, Aj,…, An) параметров. Выходные параметры Aj контролируются датчиками Д (цепь ТУ ^ Д ^ АТУ ^…), входные Bjj регулируются с помощью УУ (… ^ АТУ ^ УУ ^ ТУ). Аналогично, Оп (предметная область ЭС при приобретении знаний), с точки зрения ЭС, обладает выходными и входными характеристиками. Выходные параметры (инструкции оператора) контролируются через Вв (цепь Оп ^ Вв ^ ИО ^…), входные (информация для оператора) — регулируются с помощью Выв (… ^ ИО ^ Выв ^ Оп).
Параметрам соответствуют ЛгП (для упрощения, применены одинаковые обозначения), каждая из которых состоит из к термов:
РИ, 2003, № 1
Ai -{ai1, ai2,…, aip,…, aik }, Bj -{bjb bj2,…, bjq ,-., b jk } (первый индекс-номер параметра, второй — номер терма). Термы представляют собой наборы значений (профили) функций принадлежности (ФП), определенные на множествах значений соответствующих параметров и принимающие значения на интервале [0,1]: aip = Hip (Ai) — bjq = нjq (Bj) — Hip (Ai), H jq (Bj) є [0,1]. Профили Ф П представляют собой часть ЭЗ и хранятся в БЗ. Конфигурации профилей ФП строятся разработчиком ЭС, например по результатам интервьюирования эксперта-человека. Другая часть ЭЗ содержится в РП, в которых выходные (Ai) параметры находятся в антецедентной части, а входные (Bj) в — консеквентной:
if ((A (i1) = a (i1)(p1)) and (A (i2) = a (i2)(p2))), then (B (j1) = b (j1)(q1)), где (Л),(/2) є {1,2,…, n}, (j1),(j2) є {1,2,…, m} ,
(p1), (p2), (q1) є {1,2,…, k}, and — нечеткое логическое «И» [1]. Легко видеть, что для полного описания — указания реакции ЭС Bj при всех возможных комбинациях термов выходных параметров Ai -требуется не более mkn РП.
Рис. 4. Дерево нечетких решений
В реальных системах, при управлении конкретными ТУ, не все комбинации выходных параметров являются возможными (имеют физический смысл). Соответственно, набор из mkn РП обладает избыточностью. Кроме того, существуют определенные трудности с обеспечением быстродействия системы при больших наборах РП [7]. Поэтому используется подход на основе дерева нечетких решений (ДНР), при котором набор РП ограничивается только реально применяемыми. Процесс перебора при этом автоматически упорядочивается (оптимизируется) в соответствии с процедурой принятия решений. Разумеется, система должна допускать последовательное рассмотрение выходных параметров Ai в детерминированном порядке, т. е. для
95
нее должна существовать эффективная последовательная процедура принятия решений. На рис. 4 такая процедура представлена в виде (n- 1)-уровне-вого ДНР. Сигналы с датчиков Д (значения выходных параметров) поступают на блоки A — An, где сопоставляются с термами соответствующих ЛгП и преобразуются в нечеткую форму. Продукции осуществляются последовательно, в порядке возрастания номера уровня. На первом уровне сопоставляются параметры, А и A2, на h-м — результат работы (h-l)-ra уровня ((h-^-я нечеткая продукция) и (h+ 1)-й параметр А^+. Результатом каждой из продукций может быть значение промежуточной ЛгП, передаваемое на следующий уровень, или (и) значения входных параметров Bj, подаваемых через УУ на ТУ.
Аналогично, не все корректирующие воздействия Оп могут иметь смысл. В частности, нецелесообразно корректировать одновременно выходные и входные характеристики, связанные общим РП (т.е. в антецедентную и консеквентную части РП), так как такие корректировки могут быть взаимно компенсирующимися. Поэтому процесс приобретения знаний (режим А), реализованный на принципах НЛ (с ЛгП и РП, описывающими подстройку ЭЗ), также эффективен при применении ДНР.
Конкретная расстановка входов параметров Bj по выходам ДНР (конкретная конфигурация ДНР) определяется набором РП, т. е. в конечном счете предметной областью (ТУ или Оп). На рис. 4 представлено не полное ДНР, а только одна из основных его ветвей, включающая рассмотрение полного набора выходных параметров Aj. В случае ДНР для режима, А имеют место по крайней мере две группы основных ветвей: для условных и заключительных частей РП. Кроме основных ветвей, ДНР может содержать неосновные, в которых решения принимаются по сокращенным наборам параметров. Естественно, при попадании на неосновную ветвь решение принимается быстрее- поэтому при конструировании ДНР должна преобладать тенденция к «раскущению»: стремление к построению коротких ветвей.
Сокращение числа работающих РП происходит из-за того, что на каждый уровень приходит несколько (не более s- s & lt- kh — h — номер рассматриваемого уровня- 1& lt-h<-m-1) ветвей ДНР с предыдущего уровня. На h-м уровне к g-й (g є {1,2,…, s}) пришедшей ветке подключаются не все к РП, соответствующих термам a (h+1)b -& gt- a (h+1)k выходного параметра A (h+1), а только те из них, которые указываются экспертом при разработке ЭС. При работе ЭС в каждом цикле (при каждом прохождении от корня ДНР к его вершине) рассматриваются не все имеющиеся РП, а только те из них, которые оказываются на пути: дают ненулевые значения результирующей ФП. Разумеется, цена ускорения работы ЭС — введение промежуточных ЛгП (не более (n-2) на каждой ветви):
A (1a2& gt- A (… л3),•••, A (.. A (h-1)), A (… лh),•••, A (.. A (n-1))
(применена рекуррентная индексация: A (… Ah) обозначает A ((_A (h1))Ah)). Это увеличивает объем работы при разработке ЭС, но на практике нормализует процесс интервьюирования эксперта-чело-века и упрощает верификацию ЭС. Кроме того, снимается проблема доказательства существования эффективной последовательной процедуры принятия решений: эмпирически оптимальная процедура предлагается экспертом-человеком в процессе интервьюирования.
Рассмотренная структура — ДНР — характерна для подмножества ЭС, реализующего РР. Как отмечалось, ЭС с фиксированным набором знаний реализует функции СППР. В ней режимы БО, А и АП всецело вынесены в этап разработки. Режим Б О на текущем этапе развития технологии ЭС не включает нечеткой алгоритмизации. БО не разграничивается четко с фазой проектирования ЭС: включает определение ЛгП, формирование профилей ФП, установку РП, что осуществляется разработчиком или оператором исключительно средствами ИО. Создание интеллектуального интерфейса, способного самостоятельно осуществлять БО (т.е. изначально умеющего осваивать новую предметную область «без преподавателя»), является гранью, отделяющей в настоящее время человеческий интеллект от машинного. Обсуждение данного вопроса выходит за границы настоящей работы.
Кроме Р Р, нечеткая алгоритмическая часть имеется в режимах, А и АП. Как отмечалось, режим, А включает корректировку ЭЗ, находящихся в БЗ, с участием оператора. Режим А П предполагает автоматическое согласование корректировок с ранее полученными знаниями. Оператор — специалист в предметной области, но не специалист в нечетких ЭС. В связи с этим перспективное требование к ИО — понятия, с которыми работает оператор, должны быть сформулированы в терминах предметной области. Опишем вариант организации режимов, А и АП для случая корректировки ЛгП, удовлетворяющий этому требованию.
Выше рассмотрено ТУ, имеющее n выходных (A1 — An) и m входных (B1 — Bm) параметров, каждый из которых описывается ЛгП, включающей к термов. Каждый терм представляет собой профиль ФП. Система проще в организации и выше по быстродействию, если профили ФП имеют унифицированный вид [8]: характеризуются фиксированным набором параметров р. В этом случае суммарно имеется (m+n)kp параметров, полностью описывающих набор ЛгП данного ТУ. По каждому из параметров в режиме, А должна быть обеспечена регулировка, поэтому требуется (m+n)kp регулировочных ЛгП.
Рассмотрим организацию регулировочных ЛгП и принципы работы с ними на примере корректировки термов управляющей ЛгП с профилями ФП трапецеидальной формы. Пусть при перекрытии значений параметра Aj: {ац, aj2,…, ajpajk} соРИ, 2003, № 1
96
блюдается следующее правило: промежуток между ближайшими точками нижних оснований к-й и (к+2)-й трапеций равен верхнему основанию (к+1)-й трапеции (/ - номер параметра, к — номер терма в порядке возрастания величины Aj). Данное правило соответствует практике построения ЛгП: оно обеспечивает полное и не более чем двукратное перекрытие всей области значений параметра Aj.
Пусть корректируемыми параметрами являются ширина и местоположение профиля ФП при соблюдении неизменных наклонов фронтов и правила перекрытия значений параметра Aj, что эквивалентно управлению раздельным перемещением фронтов. В табл. 1 представлена система обозначений для команд управления выходным параметром Aj при двух градациях величины управляющего воздействия. Пример вербальной интерпретации
обозначений: ajk -I — «слабо уменьшить ширину
профиля ФП смещением правого фронта». Правило перекрытия значений выражается тождествами:
Т ajk = aj (k, Т ajk = aj (k-1) ^ ^ aik = aj (k-1), Т ajk = aj (k-1).
Таблица 1
Левый фронт Правый фронт
Сильно увеличить ^ ajk ajk ^
Слабо увеличить ^ ajk ajk ї
Слабо уменьшить ^ ajk ajk 4-
Сильно уменьшить W ajk ajk w
Рис. 5 иллюстрирует корректировку выходного параметра At при одной градации управляющего воздействия.
Рис. 5. Корректировка выходного параметра At
Представлена ЛгП Aj, содержащая 4 терма в исходном состоянии Aj: {aji, aj2, ajj, aj4} (а) и после двух вариантов (б и в) корректировки из исходного
состояния: Aj: {aji,…, a^} (уменьшение ширины
смещением левого фронта) и Ajj: {ajjaj4} (увеличение ширины смещением правого фронта). Пунктиром показаны предельные положения смещения левого (для Aj) и правого (для Ajj) фронтов, которыми ограничены возможности корректировки термов. Если, например, требуется расширить (к+1)-й терм влево так, что правая граница к-го терма сместится больше чем на ширину к-го терма, то сначала должна быть смещена влево левая граница к-го терма.
Рис. 6. Алгоритм согласования перемещения фронтов ФП термов
Таким образом, корректировка должна включать дополнительные проверки, как показано на блок-схеме рис. 6, для смещения левого фронта (^ aj (k +1)). Команды ajk і, t ajk, ajk t и aj (k+1) ^ соответствуют рекуррентному запуску аналогичной процедуры, с последующим возвратом в исходную. Аналогично выглядит блок-схема для процедуры смещения правого фронта ФП (команда aj (k+1) ^). Рекурсивный вызов команд смещения фронтов может быть многократным: например, команда aj2 t (смещение правого фронта, рис. 5, в) повлечет за собой команды і ajj, ajj t и і aj4
(смещение левого фронта aj4 и перемещение впра-
II j4
во ФП aj3). Могут накладываться дополнительные ограничения в связи с характером предметной области, но характер процедур в целом и рекуррентное вложение при выполнении смещений фронтов сохраняются.
РИ, 2003, № 1
97
Представленный пример включает ФП и РП. ФП, которая задает возможность проведения регулировки по каждому из фронтов, определяется пределами перемещения фронтов и может изменяться в процессе регулировки. В связи с этим регулировочная Ф П строится по управляющим Ф П непосредственно при проведении регулировки. РП, представленные на рис. 6 блоками 3 и 4, определяют последовательность проведения корректировок, затрагивающих несколько соседних ФП. В рассмотренном примере регулировочная ФП — четкая (при смещении фронта деформируется единственная соседняя ФП), что является частным случаем. Введением нечетких регулировочных Ф П несложно обеспечить «дальнодействие» между фронтами: разномасштабную деформацию и смещение нескольких соседних ФП в направлении смещения данного фронта. Алгоритмическая реализация подобной процедуры требует отдельного обсуждения.
(символом ф обозначена конкатенация). В результате масштабирования Дд = M * рд (где M = (2q -1) — m — число битов, выделяемых под хранение одного значения ФП- q є (1,2,3,…) — случай q =1 соответствует четкому множеству), 0 & lt- Дд (ai) & lt- M. Аппроксимация целочисленными значениями в интервале [0, M] с равномерным шагом M/(p-1) дает следующие (M+1) градаций значений ФП: Дд (ai) = 0, Дд (a2) = M/(p-1), Дд (аз) = 2M /(p-1), …, Дд (ai) = (i-1)M /(p-1) v. v Дд (ap) = M. Таким образом, каждый из сегментов обеспечивает передачу 2q градаций значения ФП. Величина q может быть выбрана с учетом требований точности системы. При конкатенации р-кратно уменьшается объем адресуемой памяти [3] и пропорционально сокращается число циклов выборки значений ФП.
Как отмечалось, рассмотренная процедура охватывает работу двух режимов: А (включает взаимодействие с оператором) и АП (приведение старых знаний в соответствие с вновь приобретенными). Блоки 1 и 2 (см. рис. 6), а также блок генерации сообщения оператору о завершении корректировки (не показан) относятся в режиму А- блоки 3 — 10 и все рекурсивно подключаемые процедуры составляют режим АП. Взаимодействуя с оператором, ЭС последовательно проходит режимы: … ^ А ^ АП ^ А ^… (см. рис. 3, б). При этом регулировочное воздействие оператора затрагивает несколько управляющих ФП, что отрабатывается в режиме АП. Реальная Э С обычно предоставляет оператору инструментарий, перекрывающий полный набор корректируемых параметров термов ЛгП предметной области. Инструменты соответствуют термам не взаимно -однозначно, но допускают взаимовлияние (как и в случае со смещением фронтов), отрабатываемое в режиме АП (согласование новых приобретенных знаний со старыми). Соответствующие затраты ресурсов могут быть существенно сокращены при реализации нечетких ЭС с использованием принципа локальной параллельности.
Локально-параллельные нечеткие экспертные системы
Традиционная последовательная схема программной реализации нечетких операций предполагает хранение значений ФП в виде массивов чисел. Процедура обработки включает поэлементный перебор массивов, вследствие чего продолжительность обработки возрастает пропорционально числу хранимых значений ФП. Значения Ф П при ЛП представлении нечеткой информации хранятся и обрабатываются не по одному, а в виде конкатенаций из р q-битовых сегментов pq& lt-r, где r — разрядность вычислительного устройства, на котором реализуется ЛП-алгоритм [3,4]. Для этого значения ФП масштабируются (рд ^рд), целочисленно аппроксимируются (Дд ^ Дд) и конкатенируются, образуя регистровое представление (РгП):
(Мд) R =Мд (a1) (c)Дд (a2) ©… (c)Дд (ap)
ЛП-алгоритм операции НЛ (®) [3,4] представляет собой специальным образом подобранную последовательность арифметических, поразрядных логических и сдвиговых регистровыхопераций, про -изводимых над конкатенациями д и Bj операндов ag и b, g=1,2,…, k, как над обычными числами, в результате которых получается число C, которое может быть интерпретировано как конкатенация (ф) результатов cg НЛ операций, проведенных над операндами Cg = aig ® bjg независимо:
Arian& gt-"-' ai*} ^АГаа®… ®аЛ^
ВРЪА.
Как отмечалось, в нечетких ЭС принцип ЛП применяется в режимах А, АП и РР. Рассмотрим особенности ЛП алгоритмической реализации каждого из режимов.
За исключением ДНР (см. рис. 4), основные моменты РР рассмотрены в [6]. ЛП-реализация ДНР предполагает определенную специфику. Рассмотрим первый уровень. Термы Ta1g ЛгП д1 и Ta2g ЛгП д2 (g=1,2,…, k) в ЛП представлении имеют вид наборов РгП:
Ta1g = Ma1g (ЛД © Ma1g (x12) ©… © Ma1g (x1g) ,
Ta2g = Ma2g (x21) ® Ma2g (x22) ©… ® Ma2g (x2g) ,
где X11,., X1g и X11,., X1g — дискретные отсчеты значений параметров областей определения ЛгП д1 и д2, соответственно. Полагается, что выходные параметры ТУ, соответствующие ЛгП д1 и д2, снимаются с Д в виде дискретных значений с точностью в пределах дискретизации областей определения ЛгП. После преобразований (не являю-
98
РИ, 2003, № 1
щихся частью рассматриваемых алгоритмов) значения выходных параметров приобретают вид РгП:. (00. 0)(11. 1)(00. 0)(00. 0). (показан фрагмент, сегменты в двоичном представлении для наглядности выделены скобками). Размеры сегментов выходных параметров Л и A2 совпадают с размерами соответствующих сегментов РгП термов Tag и Tq2g, g=1,2,…, к. Положение единственного единичного сегмента соответствует значению (отсчету), снятому с Д. Далее по каждой из ЛгП значение параметра сопоставляется с термами: AT1g = A1andTa1g, AT2g = A2andTa2g (and — нечеткое логическое «И»). При этом из профилей ФП термов Taig и Та2g вырезаются сегменты, соответствующие единичным сегментам Ai и A2. Остальные части обнуляются. Затем проверяется наличие ненулевых сегментов: ATig & gt- 0, ATig & gt- 0. Если AT1g & gt- 0 или ATig & gt- 0, соответствующие РгП из дальнейшего рассмотрения исключаются. Так, из полных наборов РгП формируются наборы ненулевых РгП, позволяющие сократить число реально используемых РП. В рассматриваемом случае каждая из ЛгП имеет к термов- полный набор РП (по каждому входному параметру ТУ либо промежуточному терму) содержит не более к РП. Если термы определены с перекрытием не более 2 (как в рассмотренном выше примере, рис. 5), по каждому входному параметру реально работает не более 4 РП. Ненулевые ATig и At2g попарно комбинируются между собой, задавая антецедентные части РП. По каждому из правил должно отыскиваться минимальное из значений ФП. Для сравнения фрагменты в ATig и At2g выравниваются по ненулевому фрагменту, после чего значение консеквентной части РП определяется как Л П нечеткое логическое «И» операндов антецедентной части: ATig and At2g = min (ATig, At2g).
ЛП-алгоритм выравнивания представлен в [6], ЛП нечеткого логического «И» — в [3].
Результатами работы РП могут быть значения входных параметров ТУ Bj (см. рис. 4, выход УУ1-го уровня) либо значения одного или нескольких термов промежуточной ЛгП (см. рис. 4, блок AiA2). Л П-алгоритмы поиска значений входных параметров Bj (нахождение масок (координат) центров тяжести термов входных ЛгП и поиск средневзве -шенных значений с масштабированием масок выровненными значениями) рассмотрены в [6]. ЛП обработка для промежуточной ЛгП несколько проще. Она предполагает только указание и масштабирование ненулевых термов. Полагается, что промежуточная ЛгП определена: имеется соответствующий набор из к термов
A1a2: {a (iA2)1, a (iA2)2 v, a (iA2)k}.
2
к РП подразделяются на к групп в соответствии с к термами ЛгП AiA2, соответствующими кразным консеквентным частям к РП. Как отмечалось, реально работают (дают ненулевые значения) не все
РИ, 2003, № 1
РП. Поэтому только некоторые из к групп дают ненулевые значения. Пусть кh -я — одна из таких группа и пусть на нее указывает l из к РП. Это значит, что терм a (lЛ2)kh є a1a2, кь є (1,2,…, к) становится ненулевым и масштабируется большим из значений, определяемых антецедентными частями l ненулевых РП, которые указывают на терм a (iA2)№. Масштабирование осуществляется в соответствии с результатом max-min-процедуры [2]:
(am and a2ji) or (a^ and a2j2) or …
… or (am and a2 ji) = max (min (apg, a2 jg)),
g=1,2,…, l, or — ЛП нечеткое логическое «ИЛИ ЛП алгоритмическая реализация подобной процедуры рассмотрена в [9], Л П нечеткого логического «ИЁИ» — в [3].
Режимы, А и АП рассмотрены выше как процедур -но-единый блок. Представленный пример (см. рис. 5 и 6) является весьма частным, но достаточно информативным, поэтому Л П реализацию режимов, А и АП рассмотрим на нем же.
Термы Taig (g=1,2,…, к) ЛгП Ai в ЛП представлении приобретают вид РгП:
Taig = Maig (Лі) ® Maig (x12) ®… ® Maig (x1g) ,
где xi,…, xig — дискретные отсчеты значений выходного параметра Ai ТУ. Частота следования отсчетов должна быть достаточной для исчерпывающего представления фронтов профилей термов. Практически это значит, что фронт должен содержать по крайней мере 2q отсчетов для передачи всех градаций значений ФП. Необходимость воспроизведения полного набора градаций очевидна: не представленные фронтом градации никогда не будут воспроизведены в системе при преобразовании информации- следовательно, в рамках точности системы они избыточны. Как отмечалось, каждый из отсчетов представлен в Taig q-разрядным сегментом.
Кроме терма Тaig, для ЛП корректировки требуется маска фронтов Taig, вид которой пояснен примером для случая p=12, q=2:
Taig = (00)(01)(10)(П)(П)(П)(П)(10)(01)(00)(00)(00), Faig = (11)(11)(11)(11)(00)(00)(11)(11)(11)(11)(00)(00).
Процедура получения Faig для заданного терма Taig в формальном описании на псевдокоде [10] выглядит следующим образом:
LP — Mask — of — Fronts (T)
1 M1 ^ T & quot-and"- E0
2 M2 ^ T & quot-xor"- E0
3 F ^ E0& quot- xor& quot- (M 1& quot-or"- M 2)
4 F ^ F & quot-or"- (F & gt->- nq)
5 F ^ F & quot-or"- (F & lt-<- nq)
99
Здесь «and», «or» и «xor» — побитовые логические операции- & lt-<- и & gt->- - поразрядный сдвиг влево и вправо- T — исходный терм, F — маска фронтов- M1 и M2 — промежуточные переменные- E0 — константа, содержащая единицы в pq младших разрядах [3]- n — число градаций величины управляющего воздействия (см. табл. 1) — q-разрядность сегмента. Легко видеть, что процедура LP-Mask-of-Fronts (T) присоединяет к каждому из фронтов по n верхних (соответствующих mA= 1) и n нижних (соответствующих mA=0) отсчетов (сегментов). Это позволяет далее модифицировать Taig средствами ЛП нечеткой логики, как показано в табл.2 для случая n=1.
Таблица 2
Команда Оператор
^ aik T ^ T or (F & lt-<- q)
^ aik T ^ T or (F & gt->- q)
aik ^ T ^ T or (F & gt->- q)
aik ^ T ^ T and (F & lt-<- q)
Изложенное в основном соответствует Л П алгоритмической реализации режима А. Режим А П предполагает дополнительное нахождение процедурой LP-Mask-of-Fronts (T) масок фронтов Fai (g -і) и Fai (g+1) для сопредельных термов Tai (g-1) и Tai (g +1). Далее при выполнении команд табл. 2 в соответствии с фиксированным набором правил (рис. 6) проверяются возможности сжатия сопредельных термов (блоки 3 и 6, рис. 6). Критерием невозможности является M1=0 (первая строка процедуры LP-Mask-of-Fronts (T) для Tai{g-1) и Tai (g +1)). В этом случае весь профиль сопредельного терма сдвигается: Tai (g _1) & lt-<- q или Tai (g +1) & gt->- q. При M1& gt-0 одним из операторов табл .2 смещается соответствующий фронт сопредельного терма.
Как отмечалось, четкий характер РП, применяемых в режиме АП, соответствует ограниченному взаимовлиянию термов. Расширенное взаимовлияние (введение «дальнодействия») возможно определением соответствующих ФП, аналогично промежуточным ЛгП в ДНР. Описание соответствующего алгоритма — предмет отдельного рассмотрения. Представленный материал показывает, что Л П реализация, по-видимому, не накладывает на такой алгоритм никаких фатальных ограничений.
Заключение
Ключевое преимущество ЛП-алгоритмов — экономное расходование вычислительных ресурсов: объемов памяти и времени обработки. При этом для их реализации не требуется специального аппаратного обеспечения. Перспективной областью применения ЛП-алгоритмов применительно к экспертным системам с продуктивным выводом могут стать интеллектуальные распределенные сетевые решения с децентрализованным использованием и обновлением знаний. Подобные системы приобретают особую актуальность в условиях быстро изменяющегося (лавинообразно расширяющегося) кибернетического информационного пространства.
Литература: 1. ЗадеЛ. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976. 2. Малышев Н. Г., Берштейн Л. С., Боженюк А. В. Нечеткие модели для экспертных систем в САПР. М.: Энергоатомиздат, 1991. 3. Михаль О. Ф, Руденко О. Г. Принцип локальной параллельности в задачах обработки нечеткой информации. Базовые операции / / Доповіді НАН України, 1999. № 8,. С. 71−75. 4. Михаль О. Ф., Руденко О. Г. Принцип локальной параллельности в задачах обработки нечеткой информации. Расширенный набор операций // Доповіді НАН України, 2000. № 1. С. 75 -78. 5. Михаль О. Ф., Руденко О. Г. Принцип локальной параллельности в задачах обработки нечеткой информации. Организация системы управления. // Доповіді НАН України, № 12, 1999. С. 103−107. 6. Михаль О. Ф, Руденко О. Г. Принципы организации систем нечеткого регулирования на однородных локально-параллельных алгоритмах // Управляющие системы и машины, 2001. № 3. С. 3−10. 7. Представление и использование знаний // Под ред. Х. Уэно, М. Исудзука. М.: Мир, 1989. 8. IEC 1131 -Programmable Controllers. Part 7 — Fuzzy Control Programming. Committee Draft CD 1.0 (Rel. 19 Jan 1997). 9. Михаль О. Ф. Локально-параллельный однородный алгоритм нечеткой дизъюнктивной суммы // Вестник ХГПУ. Вып. 128. Новые решения в современных технологиях. Харьков, 2000. С. 52−58. 10. Кормен Т, Лей-зерсон Ч, Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.
Поступила в редколлегию 23. 09. 2002
Рецензент: д-р техн. наук, проф. Руденко О. Г.
Михаль Олег Филиппович, канд. техн. наук, доцент кафедры ЭВМ ХНУРЭ. Научные интересы: нечеткие множества и их приложения: экспертные системы, распознавание образов, адаптивное регулирование, нечеткие сети Петри. Адрес: Украина, 61 137, Харьков, ул. Бакинская, 5, тел. 40−93−54, е-mail: mikhal@ kharkov. ukrtel. net.
100
РИ, 2003, № 1

ПоказатьСвернуть
Заполнить форму текущей работой