автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Математическое и программное обеспечение систем управления базами знаний интеллектуальных систем прогнозирования

На правах рукописи

хг^^—

Пинчер Денис Владимирович

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

СИСТЕМ УПРАВЛЕНИЯ БАЗАМИ ЗНАНИЙ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ ПРОГНОЗИРОВАНИЯ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 7 МАМ 2012

о5043822

Тула 2012

Работа выполнена в ФГБОУ ВПО «Тульский государственный универси-

тет»

Научный руководитель:

доктор технических наук, профессор Токарев Вячеслав Леонидович

Официальные оппоненты:

Ведущая организация:

Изотов Виктор Николаевич доктор технических наук, профессор, Тульский филиал ФГБОУ ВПО «Российская академия народного хозяйства и государственной службы при президенте Российской Федерации», зав. каф. «Экономика и финансы»

Кузнецов Геннадий Васильевич кандидат физико-математических наук, доцент, Тульский филиал ВЗФЭИ, зав. каф. «Математика и информатика»

ФГБОУ ВПО «Юго-западный государственный университет»

Защита состоится «28» мая 2012 г. в ¿0 час. 00 мин. на заседании диссертационного совета Д 212.271.07 при ФГБОУ ВПО «Тульский государственный университет» (300600, г.Тула, проспект Ленина, 92, 9-101)

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Тульский государственный университет».

Автореферат разослан «27 » апреля 2012 г.

Учёный секретарь <С2Г> Данилкин диссертационного совета _____Фёдор Алексеевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Основными компонентами любой интеллектуальной системы (ИС) являются база знаний (БЗ) и система управления базами знаний (СУБЗ). База знаний представляет собой совокупность знаний о предметной области, а СУБЗ - программное средство, в котором реализована совокупность алгоритмов, обеспечивающих работу со знаниями - то есть, их получение, пополнение, обработку и интерпретацию. Эффективность работы любой интеллектуальной системы напрямую зависит от эффективности выполнения каждого из этих процессов. Потому вопросам разработки математического и программного обеспечения СУБЗ в составе интеллектуальных систем традиционно уделяется много внимания.

Значительный вклад в развитие математического аппарата СУБЗ в составе интеллектуальных систем и методов построения соответствующего программного обеспечения внесли отечественные учёные Д.А. Поспелов, Т.А. Гаврило-ва, В.Ф. Хорошевский, Б.З. Мильнер, В.М. Вагин, А.Л. Гапоненко и другие, а также ряд зарубежных учёных: К. Вииг, С. Осуга, Ю. Саэки, М. Исидзука, У. Букович, Р. Уильяме, Л. Прусак, Т. Давенпорт и др.

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

Следовательно, разработка методов построения математического и программного обеспечения систем управления базами знаний в составе интеллек-

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

Объектом исследования являются программные системы управления базами знаний в составе интеллектуальных систем прогнозирования.

Предметом исследования является математическое и программное обеспечение систем управления базами знаний.

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

В соответствии с указанной целью в диссертационной работе были поставлены следующие задачи:

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

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

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

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

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

Научная новизна работы заключается в разработке комплекса программных, языковых и интеллектуальных средств, с помощью которых реализуется создание и использование базы знаний, а именно:

1. Предложен язык представления знаний, отличающийся возможностью описания информации в виде последовательности пар «ситуация - действие противодействующей стороны» и позволяющий описывать стратегии ПС.

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

3. Предложена методика построения программного обеспечения систем управления базами знаний, основанная на использовании разработанного языка представления знаний и позволяющая создавать СУБЗ в составе интеллектуальных систем прогнозирования.

Достоверность научных результатов подтверждена результатами теоретических и экспериментальных исследований, полученными в ходе решения

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

Практическая значимость работы заключатся в следующем:

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

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

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

На защиту выносятся:

1. Язык представления знаний о возможных стратегиях ПС;

2. Алгоритмическое обеспечение интерпретатора данного языка;

3. Методика построения программного обеспечения СУБЗ, использующего разработанный язык программирования.

Апробация работы. Основные положения и результаты диссертационного исследования докладывались и обсуждались на научных конференциях и семинарах: 1. «Гагаринские чтения». XXXV международная молодёжная конференция, МАТИ, Москва, 2009г. 2. «Интеллектуальные и информационные системы-Материалы Всероссийской научно-технической конференции». Тульский государственный университет. - Тула, 2009 г. 3. «Актуальные вопросы развития современной науки, техники и технологий». II всероссийская заочная научно-практическая конференция, НИИРРР, Москва, 2010 г. 4. «Научное творчество XXI века». II всероссийская заочная научная конференция с международным участием, Научно-инновационный центр, Красноярск, 2010 г. 5. «Электронные средства и системы управления». VI международная научно-практическая конференция, ТУСУР, Томск, 2010 г. 6. «Аюуальные проблемы аппаратно-программного и информационного обеспечения науки, образования, культуры и бизнеса». Международная научно-практическая конференция, МГУПИ, Мо-ква, 2010 г. 7. «Актуальные вопросы современной техники и технологии» III ¡еждународная заочная конференция, Липецк, 2011 г.

Публикации. По теме диссертационного исследования опубликовано 12 ечатных работ, в том числе 6 статей и 6 докладов в сборниках трудов конфе-6лН™ ВКЛЮЧаЯ 5 публикаций в периодических изданиях, рекомендуемых

1 ф Для публикаций материалов кандидатских диссертаций.

Структура и объем работы. Диссертация состоит из введения, четырех тав, заключения, библиографического списка (102 наименований) и приложе-

ний. Основная часть диссертации содержит 131 страницу машинописного текста, включая 6 рисунков, 17 таблиц.

Основное содержание работы

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

Первая глава посвящена общим вопросам разработки математического и программного обеспечения систем управления базами знаний в интеллектуальных системах прогнозирования действий противодействующей стороны.

Показано, что важную роль при построении программного обеспечения СУБЗ в составе ИС указанного типа играет язык представления знаний, с помощью которого могут быть описаны знания и получено решение задачи прогнозирования действий ПС в результате их обработки.

Отмечено, что для описания знаний необходимо определить их основные особенности и выбрать модель их представления. Рассмотрены особенности представления знаний в интеллектуальных системах прогнозирования действий ПС. Показано, что основу БЗ интеллектуальных систем должны составлять знания о возможных стратегиях ПС. Определены особенности таких знаний: * 1) динамичность, 2) неоднородность, 3) нечеткость.

Рассмотрены существующие модели представления знаний: логическая, сетевая, фреймовая и продукционная. Доказано, что перечисленные модели не позволяют обеспечить требуемой эффективности СУБЗ для интеллектуальной системы указанного типа. Обоснована необходимость разработки модели представления знаний, позволяющей описывать стратегии ПС с учетом перечисленных особенностей.

Показано, что разработка программного обеспечения СУБЗ в составе ИС прогнозирования действий ПС должна включать в себя следующие этапы: 1) определение способа описания знаний о возможных стратегиях поведения ПС в различных ситуациях, 2) разработка подхода к построению баз знаний на основе анализа данных, описывающих результаты наблюдений за ПС, 3) разработка алгоритма обработки знаний, обеспечивающего решение задачи прогнозирования действий ПС в текущей ситуации.

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

тегий ПС и их процедурной обработки. Обоснована необходимость разработки языка представления знаний, позволяющего описывать и обрабатывать такие знания.

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

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

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

Вторая глава посвящена языку представления знаний и алгоритму построения базы знаний, используемому в его интерпретаторе.

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

Взаимодействие сторон относительно некоторой системы Р предложено представить в виде схемы, приведенной на рисунке:

Здесь и - ход первой стороны (1С), х - ход второй стороны (ПС, 2С); -действие третьей стороны (ЗС), я - состояние системы Р. Под ходом понимается какое-либо действие (информационное, физическое, экономическое и т.п.), способное повлиять на состояние системы в дискретный момент времени 1С и 2С преследуют противоположные цели (под целью 1С или 2С понимается некоторое выгодное для этого участника состояние системы Б), ЗС определяет правила взаимодействия.

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

F

Рис. 1. Взаимодействие сторон

sk+i=F(?k,uk+l,wM,xk+x\ (1)

sk eS,xke X,uke.U,wk<E.W,k = 1,2,...«,

где S — конечное множество возможных состояний системы F, а множества U, X, W — это соответственно множества возможных действий первой, второй и третьей сторон. Дискретный момент времени п соответствует достижению цели 1С или 2С.

Предложена и обоснована метрика Р^^'яс))' позволяющая оценивать близость рассматриваемого состояния sk цели ПС = s*nc). Показано, что выбор действий ПС в текущей ситуации в соответствии с осуществляемой этим участником стратегией может быть описан с помощью нечетких отноше-

I

ниГгвида:

8аС): (^Ч )' ("ш ),HDm (W*+i)) (**+I ) (2)

где Вк - нечеткое множество состояний системы F, объединенных по степени сходства расстояний p(sA,.s*/K:)), Сд+1, Dk+l - нечеткие множества действий

первой и третьей сторон, объединенных по степени сходства их влияния на выбор следующего действия ПС, Ек+1 нечеткое множество действий второй стороны, характеризующих способ движения ПС к цели. ne4(st), Hct+|(u£+i)> ^Dt+i^+i) и ~ это функции принадлежности соответственно мно-

жеств Вк, Ck+l, Dk+i и Ек+1.

Показано, что правила перехода системы F из состояния в состояние в (2С)

рамках стратегии g ' можно представить нечеткими отношениями вида:

huC) '■ къ ^ ("ы (WM )' )) (¿i+i)

а модели Mfc) каждой из стратегий g'2C) могут быть описаны отношениями:

А,(оС): ("Во (-?о). /V, ("1 )> AD, On), )) Ив, C?i)

М{2С>> =

8<?*} )'Рс„ ("«)>М[)„ («'«))-> (х„)

П ))

Доказано, что задачу оценивания стратегии ПС можно представить как задачу классификации, решение которой сводится к выбору модели (4) одной из возможных стратегий ПС, которой в наибольшей степени соответствует текущая последовательность:

8 = (к,>:"1>»П}......■ик,.хк }.-.>um>wm>xm}\ (5)

к,т<п

Обосновано, что разрабатываемый язык представления знаний должен включать в себя средства описания моделей стратегий ПС вида (4) и текущей последовательности вида (5).

Разработан синтаксис языка представления знаний, подразумевающий наличие следующих частей: 1) общего описания процесса взаимодействия сторон, включающего определения метрики P^t>s<77C))> множеств возможных состояний Вк и действий сторон Ск, Dk и Ек, 2) описания всех возможных стратегий ПС и 3) описания текущей последовательности g.

Определен словарь языка, включающий в себя синтаксические единицы для описания перечисленных структурных элементов, а также ключевые слова и команды для выполнения различных операций с базами знаний. Введены ключевые слова: defmetric - начало блока описания метрики p{sk,s*nc^, def-state — начало блока описания состояния (терма лингвистической переменной Вк), defaction — начало блока описания действия одной из сторон (терма лингвистической переменной Ск, Dk или Ек), dcfstrategy - начало блока описания стратегии ПС, defsequence - начало блока описания текущей последовательности, и другие. Фрагмент программного кода, описывающий соответственно действие и подмножество состояний, выглядит следующим образом: (defaction сО 1 (паше "Действие 1С") (action "Ход 1" (CF 0.9)) (action "Ход 2" (CF 1)) )

(defstate Ь0

(паше "Благоприятные состояния") (distance 0.2)

(actions (person 1 с01,с02) (person2 е01,е02)) )

В первом блоке определено действие с идентификатором с01 и названием "Действие 1С", имеющее два варианта осуществления: "Ход 1" и "Ход 2", каждый из которых описывает данное действие соответственно со значениями функций принадлежности 0.9 и 1. Во втором блоке определено ограниченное подмножество состояний системы с идентификатором Ь0 и названием "Благоприятные состояния", элементами которого являются возможные состояния sk,

для которых значение расстояния p(s£,-'(яс)) равно 0.2. В состояниях из данного подмножества возможны действия первой стороны с идентификаторами с01 и с02 и действия второй стороны с идентификаторами е01 и е02.

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

Совокупность моделей (4), построенных для каждой цели еТ, каж-

I

дой ситуации, включающей исходное состояние е 50 с 5, имеющиеся ресурсы 9, е ©, составляют базу знаний С.

Рассмотрено формирование базы знаний <5 на основе априорной и апостериорной информации. Моделирование стратегии ПС только по априорной информации предполагает получение этой информации в виде знаний и использование ее в неизменном виде для построения модели. В этом случае стратегия ПС описывается по выражению (4) с помощью последовательностей отношений вида (2) и (3). Данное описание на разработанном языке представления знаний выполняется с помощью синтаксических единиц defstrategy, имеющих следующий вид:

((1еГ51га1е§у "Стратегия 1"

((Ь0,с01,с101 => е01 0.7), (Ь0,с01,с301,е01 => Ы 0.7))

((Ы,с1 l.dll =>е11 0.8), (Ы,с11,с111,е11 =>Ь2 0.8))

Г

где Ь0,с01,сЮ1 и е01 — это идентификаторы соответственно термов лингвистических переменных Вк, Ск, Ок и Ек, определенные с помощью описанных ранее синтаксических единиц defstate и defact¡on, а элементы (Ь0,с01,й01 => е01 0.7) и (Ь0,с01401,е01 => Ы 0.7) описывают соответственно отношения вида (2) и (3) и степени их достоверности.

В случае построения модели по апостериорной информации вы-

полняется формирование выборки наблюдений х2С,50,8(2С)), каждый элемент которой описывает возможный вариант осуществления моделируемой стратегии g^2C\ Значения каждого из элементов данной выборки переводятся в

форму лингвистических переменных Вк, Ск, Ок и Ек, после чего выполняется формирование базовых множеств отношений Я' вида (3) и Н' вида (4).

Затем из множества /?' исключаются элементы, дублирующие уже существующие отношения, и для оставшихся элементов этих множеств вычисляется информационная мера В результате последовательности отно-

шений вида (2) и соответствующих им последовательности Я;!2С> отношений вида (3), описывающие модель М((2С), формируются по условию:

где р — относительное пороговое значение, выбираемое в соответствии со спецификой решаемой задачи, Rfc) - последовательность отношений

g(2C\k = 0,1,...,и-1, описывающих действия, выполняемые в каждой ситуации

i.k

в зависимости от стратегии g(2C\ fff.2C) - последовательность отношений

lfic\ к = 0,1,...,и -1, описывающая динамику движения системы F в результате

1к

осуществления данной стратегии.

Далее по контрольной выборке данных (t2c,so,0(2C)) определяется значение тестового критерия. В случае, если полученное значение не удовлетворяет условию адекватности, в выборку Fv(t2c,.s0,G(2C)) добавляется новая информация, и описанная процедура повторяется. Иначе модель Мрс) включается в базу знаний.

Для описания элементов обучающей и контрольной выборок данных разработаны синтаксические единицы defselection и defcontrol, в которых задаются название моделируемой стратегии и образующая рассматриваемый эле-

мент последовательность кортежей «состояние системы - действия сторон». Построение моделей осуществляется следующим образом: 1) с помощью

синтаксических единиц defselection описываются элементы обучающей выборки данных, представляющие собой варианты осуществления моделируемой стратегии g^2C\ 2) с помощью синтаксических единиц defcontrol описываются

элементы контрольной выборки данных, представляющие собой варианты осуществления этой же стратегии, 3) с помощью разработанных команд create и check запускаются процедуры построения и проверки базы знаний. Эти команды имеют следующий синтаксис:

(create (strategy "Стратегия 1")) (check (strategy "Стратегия 1"))

где "Стратегия 1" - это название моделируемой стратегии

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

В структуру интерпретатора входят синтаксический и семантический анализаторы и модуль выполнения. Синтаксический и семантический анализаторы предназначены для проверки корректности синтаксиса анализируемого программного кода, разбиения синтаксически правильных совокупностей на составные части и проверки их семантики. Модуль выполнения предназначен

дая преобразования полученных синтаксических единиц к виду структурных

нийМ™ ЗЫ ЗНЗНИЙ' ^ П°СЛе^ЮЩей ^Работки и формирГаниТб^зГ ™ ™еДлявыполнения команД. предназначенных для модификации пополнения и обработки накопленных знаний. 4-"к<щии, по

залач™™™^ ИНТеРПреТЭТОра П0Л0Жен алгоритм, обеспечивающий решение задачи прогнозирования действий ПС в текущей ситуации и состоящий из двух

стаатегииПГ ,ЭТаП°М-Раб0ТЫ ДаНН°Г° алг0Ритма шляется этап оценивания стратегии ПС, который предложено выполнять следующим образом

Для каждого к-го элемента текущей последовательности £ определяются

термы лингвистических переменных (л), (и), („), ^1 (х), наи.

лу-шгим образом описывающие данный элемент. Затем для каждой модели < КЭЖД0Й из ^Ратегий из базы знаний С определяется степень достоверности отношения вида (2)> соот.

ветствующего данным термам. Эта величина обозначена как г*1?^(2С)). Предложена метрика

позволяющая оценивать близость стратегии ПС Я,(2С) текущей последовательности Доказано, что данная метрика должна быть определена следующим образом-

i 1 т

к=I

5 е {0,0.1,...,1.0} где \;к - линейно возрастающие весовые коэффициенты.

Показано, что решение задачи оценивания стратегии ПС может быть получено с помощью метрики из условия:

г'(2С)=аге ¿шр р(¿,£;(2С>) (8)

/

После выбора стратегии ПС по выражению (8) выполняется интерпретация модели М(1С) этой стратегии из базы знаний 6.

Вторым этапом данного алгоритма является получение прогноза следующего действия ПС на основе знаний, описывающих модель М(2С> предполагаемой стратегии ПС. Этот этап предложено выполнять следующим образом

Определяются термы Ът.п, ст+1у2, ¿т+1у3 лингвистических переменных (") и (и-), наилучшим образом описывающие текущее со-

стояние системы F s,n и действия um+i и 1гя+1, выполненные 1С и ЗС. Затем во множестве Л(2С), описывающем модель Mfc) предполагаемой стратегии ПС g"2C), отыскиваются все отношения вида (2), антецеденты которых соответствуют данным термам. Из них выбирается отношение, степень достоверности которого максимальна.

Множество альтернатив следующего действия ПС предложено определять по выражению:

(х) = max j^ (s,и, w) ® /л^с)(s,и, w,x)'j (9)

где \}.кт (s,u,n) = >2 - нечеткое множество, пред-

ставленное конъюнкцией нечетких подмножеств значений текущего состояния системы F и действий, выполненных 1С и ЗС, : ц j (х) - не-

четкое отношение из множества Rfc\ определенное описанным выше способом, ® - операция Т-нормы. В качестве операции Т-нормы выбрана операция минимума: a®6 = min{a,6}.

На основе полученной оценки стратегии g'(2C> и имеющейся конечной последовательности g по приведенному алгоритму делается прогноз. Попадание действительного значения хода ПС xm+i во множество Цг,п+1 (х) свидетельствует об адекватности выбранной стратегии g'(2c\ В противном случае текущая последовательность пополняется новым кортежем {■sn,M„+|,wm+I,j:m+1}, полученным в результате наблюдений, и процедура оценивания стратегии повторяется.

Для запуска процедур обработки знаний по приведенному алгоритму в разработанном языке реализованы команды (get strategy) и (get forecast). Каждая из них может быть выполнена только после построения базы знаний и определения текущей последовательности с помощью синтаксической единицы defse-quence. Первая команда запускает процедуру выполнения первого этапа алгоритма и возвращает оценку стратегии ПС g'(2C) и значение расстояния

p(g>g'(2C'>j- Вторая команда запускает процедуру выполнения второго этапа алгоритма и возвращает множество альтернатив следующего хода ПС

Четвертая глава посвящена методике построения программного обеспечения систем управления базами знаний, использующего разработанный язык представления знаний.

Предложена структура системы управления базами знаний в составе ИС прогнозирования, приведенная на рисунке 2.

Рис. 2. Структура СУБЗ в составе ИС прогнозирования

Модуль управления входной информацией предназначен для преобразования информации, вводимой через интерфейс ИС, в программный код и ее передачи в синтаксический анализатор. Модуль управления выходной информацией предназначен для отображения полученного прогноза ц,я+1(х) через интерфейс пользователя ИС. Модули, входящие в структуру интерпретатора языка представления знаний, предназначены для проверки и выполнения программного кода.

Рассмотрены обучающий и рабочий режимы интеллектуальной системы прогнозирования. В режиме обучения выполняется построение базы знаний Для этого разработчик ИС передает в модуль управления входной информацией следующие данные: метрику обучающую Vn(t2С,*0,е(2С)) и

контрольную Vf{x2C,s0>Q(2C)j выборки, после чего средствами разработанного языка запускает процедуру построения моделей (4). Разработчик может запускать процедуру неоднократно, всякий раз добавляя новую информацию до тех пор, пока полученное значение критерия качества не будет соответствовать условию адекватности. По окончании процедуры база знаний сформирована

В рабочем режиме пользователь ИС вводит данные, соответствующие

имеющемуся (начальному) участку текущей последовательности g и запускает

процедуру оценивания стратегии ПС с помощью команды (get strategy) После этого, введя информацию: свой ход ик+1, ход третьей стороны пользователь ИС запускает процедуру обработки знаний для получения прогноза с помощью команды (get forecast).

Для исследования ИС прогнозирования действий ПС был разработан программный комплекс на языке программирования С#, включающий в себя модуль К11Ьап«1^е, в котором реализован интерпретатор разработанного языка, модуль Кпо\у1е<1«еМапа£етеп18уБ1ет) в котором реализованы операции, необходимые для построения ИС прогнозирования, и графическую оболочку, предназначенную для обеспечения взаимодействия пользователя и ИС.

Практическое исследование разработанного программного комплекса было выполнено путем решения прикладной задачи построения и использования базы знаний средствами программного обеспечения СУБЗ для получения прогноза действий ПС. Результаты решения данной задачи подтвердили эффективность предложенных в настоящем исследовании алгоритмов и методов.

В заключении сформулированы основные результаты и выводы по работе.

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

Основные результаты работы

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

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

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

4. Разработан программный комплекс, позволяющий строить и исследовать интеллектуальные системы прогнозирования действий противодействующей стороны, в структуру которого входит СУБЗ, реализованная в соответствии с предложенной методикой.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Пинчер Д.В. Компьютерная поддержка оценивания ситуации. // Гага-ринские чтения. Том 4. Сб. научных трудов XXXV международной молодёжной конференции. - М.: МАТИ, 2009. - с. 38-39.

2. Пинчер Д.В., Токарев В.Л. Методы оценивания стратегии противодействующей стороны. // Актуальные вопросы развития современной науки, техники и технологий: Материалы II Всероссийской научно-технической конференции / НИИРРР. - М., 2010. - с. 120-122.

3. Пинчер Д.В. Разработка методов принятия решений в условиях противодействия сторон. // Гагаринские чтения. Том 4. Сб. научных трудов XXXVI международной молодёжной конференции. -М.: МАТИ, 2010. - с. 45-46.

4. Пинчер Д.В. Задача оценивания стратегии противодействующей стороны. // В мире научных открытий. №4, ч.Ю. - Красноярск: Научно-инновационный центр, 2010 - с. 79-81.

5. Пинчер Д.В., Токарев ВЛ. Оценивание стратегии противодействующей стороны. // Доклады ТУСУР №22. Томск: ТУСУР, 2010. - с. 263265.

6. Пинчер Д.В., Токарев ВЛ. Построение модели стратегии противодействующей стороны. // III международная научно-практическая конференция «Актуальные проблемы аппаратно-программного и информационного обеспечения науки, образования, культуры и бизнеса»: Сборник научных трудов / МГУПИ - М., 2010. - с. 55-59.

7. Пинчер Д.В. Особенности построения идентификатора стратегии противодействующей стороны. // III международная научная конференция «Актуальные вопросы современной техники и технологии»: Сборник научных трудов / Гравис - Липецк, 2011. - с.43-45.

8. Пинчер Д.В. Оценивание состояния системы в задаче принятия решений. // Вестник компьютерных и информационных технологий. №7. М.: Машиностроение, 2011. - с. 37-41.

9. Пинчер Д.В. Структура модели стратегии противодействующей стороны. // Математические методы в технике и технологиях - ММТТ-24. Том 8. Сб. трудов XXIV Междунар. науч. конф. - Пенза: Пенз. гос. технол. академия 2011.-с. 159-161

10. Пинчер Д.В. Лингвистическая модель стратегии противодействующей стороны. // В мире научных открытий. №8 (20). Красноярск: Научно-инновационный центр, 2011. - с. 146-153.

11. Пинчер Д.В., Токарев ВЛ. Компьютерная поддержка принятия решений по прогнозированию действий противодействующей стороны. // Известия ТулГУ. Технические науки. №5(3). Тула: Изд-во ТулГУ, 2011. -с. 270-276.

12. Пинчер Д.В. Задача прогнозирования действий противодействующей стороны. // Интеллектуальные и информационные системы: Материалы Всероссийской научно-технической конференции/ Тульский государственный университет. - Тула, 2011. - с.40-43.

Изд. лиц. ЛР № 020300 от 12.02.97. Подписано в печать 25.04.12 Формат бумаги 60x84 Vi6. Бумага офсетная. Усл. печ. л. 0,9. Уч.-изд. л. 0,8. Тираж 100 экз. Заказ 033 Тульский государственный университет 300012, г. Тула, просп. Ленина, 92 Отпечатано в Издательстве ТулГУ 300012, г. Тула, просп. Ленина, 95

61 12-5/2763

МИНОБРНАУКИ РОССИИ ФГБОУ ВПО «Тульский государственный университет»

На правах рукописи

Пинчер Денис Владимирович

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ СИСТЕМ УПРАВЛЕНИЯ БАЗАМИ ЗНАНИЙ

ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ ПРОГНОЗИРОВАНИЯ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель — д.т.н., проф. Токарев В.Л.

Тула 2012

Содержание

Список используемых сокращений.................................................................5

Введение..........................................................................................................

1. Задача разработки программного обеспечения систем управления

базами знаний.............................................................................................................

1.1. Особенности программной обработки знаний в задачах

прогнозирования действий противодействующей стороны.............................13

1.1.1. Особенности знаний, используемых в интеллектуальных

системах прогнозирования ...................................................................................14

1.1.2. Анализ задачи построения программного обеспечения СУБЗ.....19

1.1.3. Обзор существующих моделей представления знаний.................21

1.1.4. Обзор существующих методов получения знаний........................26

1.2. Анализ программных средств обработки знаний, используемых для

решения задач прогнозирования..........................................................................31

1.2.1. Обзор существующих интеллектуальных систем

31

прогнозирования..................................................................................................

1.2.2. Обзор инструментальных средств для построения ИС.................32

1.3. Этапы разработки программного обеспечения систем управления базами знаний.........................................................................................................36

1.3.1. Этап описания данных......................................................................36

1.3.2. Обзор языков представления знаний...............................................41

1.3.3. Этап построения баз знаний.............................................................46

1.3.4. Этап обработки знаний.....................................................................47

Выводы по главе 1.......................................................................................49

2. Алгоритмы построения баз знаний в программном обеспечении СУБЗ

50

2.1. Разработка синтаксиса языка представления знаний.......................50

2.1.1. Формализация задачи оценивания стратегии ПС..........................50

2.1.2. Построение модели стратегии ПС...................................................58

2.1.3. Синтаксические единицы ЯПЗ.........................................................66

2.2. Алгоритмическое обеспечение построения и проверки баз знаний

......................................................................68

2.2.1. Построение базы знаний...................................................................69

2.2.2. Проверка качества знаний................................................................71

2.2.3. Структура программного кода для построения и проверки базы

знаний средствами ЯПЗ............................................................................—..........72

2.3. Теоретическое исследование алгоритмов обработки данных.........74

Выводы по главе 2.......................................................................................^3

3. Алгоритмы обработки знаний в программном обеспечении СУБЗ ....84

3.1. Принцип работы интерпретатора ЯПЗ...............................................84

3.2. Алгоритм оценивания стратегии ПС..................................................85

3.2.1. Первый этап оценивания стратегии.................................................86

3.2.2. Второй этап оценивания стратегии.................................................92

3.3. Алгоритм обработки знаний для прогнозирования следующих

действий ПС ...........................................................................................................

3.3.1. Формирование прогноза...................................................................

3.3.2. Проверка адекватности полученного прогноза..............................97

3.3.3. Структура программного кода для получения прогноза действий

ПС............................................................................................................................99

3.4. Теоретическое исследование алгоритмов обработки знаний........100

Выводы по главе 3 .....................................................................................^^

4. Построение программного обеспечения СУБЗ...................................Ю7

4.1. Структура и принцип работы СУБЗ.................................................107

4.1.1. Структура СУБЗ...............................................................................109

4.1.2. Принцип работы СУБЗ в обучающем режиме ПС.......................110

4.1.3. Принцип работы СУБЗ в рабочем режиме ИС.............................Ш

4.2. Программная реализация языка представления знаний.................112

4.2.1. Ключевые слова и структура программного кода на ЯПЗ..........113

4.3. Разработка программного комплекса для построения ИС прогнозирования..................................................................................................И8

4.3.1. Структура программного комплекса.............................................119

4.3.2. Реализация режима обучения ИС..................................................123

4.3.3. Реализация рабочего режима ИС...................................................124

4.4. Практическое исследование ИС прогнозирования.........................127

4.4.1. Подготовительный этап..................................................................128

4.4.2. Этапы обучения и решения задачи................................................130

Выводы по главе 4.....................................................................................134

Заключение.....................................................................................................135

Список литературы........................................................................................138

Список используемых сокращений

БД База данных

БЗ База знаний

ис Интел л е кту ал ь н ая система

ПС Проти во действу ющая сторона

СУБЗ Система управления базами знаний

япз Язык представления знаний

Введение

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

Основными компонентами любой интеллектуальной системы (ИС) являются база знаний (БЗ) и система управления базами знаний (СУБЗ). База знаний представляет собой совокупность знаний о предметной области, а СУБЗ - программное средство, в котором реализована совокупность алгоритмов, обеспечивающих работу со знаниями - то есть, их получение, пополнение, обработку и интерпретацию. Эффективность работы любой интеллектуальной системы напрямую зависит от эффективности выполнения каждого из этих процессов. Потому вопросам разработки математического и программного обеспечения СУБЗ в составе интеллектуальных систем традиционно уделяется много внимания.

Значительный вклад в развитие математического аппарата СУБЗ в составе интеллектуальных систем и методов построения соответствующего программного обеспечения внесли отечественные учёные Д.А. Поспелов, Т.А. Гав-рилова, В.Ф. Хорошевский, Б.З. Мильнер, В.М. Вагин, А.Л. Гапоненко и другие, а также ряд зарубежных учёных: К. Вииг, С. Осуга, Ю. Саэки, М. Исидзука, У. Букович, Р. Уильяме, Л. Прусак, Т. Давенпорт и др.

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

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

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

Объектом исследования являются программные системы управления базами знаний в составе интеллектуальных систем прогнозирования.

Предметом исследования является математическое и программное обеспечение систем управления базами знаний.

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

В соответствии с указанной целью в диссертационной работе были поставлены следующие задачи:

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

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

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

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

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

Научная новизна работы заключается в разработке комплекса программных, языковых и интеллектуальных средств, с помощью которых реализуется создание и использование базы знаний, а именно:

1. Предложен язык представления знаний, отличающийся возможностью описания информации в виде последовательности пар «ситуация - действие противодействующей стороны» и позволяющий описывать стратегии ПС.

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

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

представления знаний и позволяющая создавать СУБЗ в составе интеллектуальных систем прогнозирования.

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

Практическая значимость работы заключатся в следующем:

1. Разработанный язык представления знаний позволяет в простой и понятной форме описывать процессы взаимодействия сторон и стратегии ПС, что упрощает написание, проверку и отладку программного кода.

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

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

На защиту выносятся:

1. Язык представления знаний о возможных стратегиях ПС.

2. Алгоритмическое обеспечение интерпретатора данного языка.

3. Методика построения программного обеспечения СУБЗ, использующего разработанный язык программирования.

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

туальных компьютерных систем» на кафедре «Электронные вычислительные машины» ФГБОУ ВПО «Тульский государственный университет». Разработанное программное обеспечение системы управления базами знаний используется в производственном процессе в РУНЦ РГРТУ «Информационная безопасность», г. Рязань, в составе интеллектуальной системы защиты информации.

Апробация работы. Основные положения и результаты диссертационного исследования докладывались и обсуждались на научных конференциях и семинарах: 1. «Гагаринские чтения». XXXV международная молодёжная конференция, МАТИ, Москва, 2009г. 2. «Интеллектуальные и информационные системы: Материалы Всероссийской научно-технической конференции». Тульский государственный университет. - Тула, 2009 г. 3. «Актуальные вопросы развития современной науки, техники и технологий». II всероссийская заочная научно-практическая конференция, НИИРРР, Москва, 2010 г. 4. «Научное творчество XXI века». II всероссийская заочная научная конференция с международным участием, Научно-инновационный центр, Красноярск, 2010 г. 5. «Электронные средства и системы управления». VI международная научно-практическая конференция, ТУ СУР, Томск, 2010 г. 6. «Актуальные проблемы аппаратно-программного и информационного обеспечения науки, образования, культуры и бизнеса». Международная научно-практическая конференция, МГУ ГШ, Москва, 2010 г. 7. «Актуальные вопросы современной техники и технологии». III международная заочная конференция, Липецк, 2011 г.

Публикации. По теме диссертационного исследования опубликовано 12 печатных работ, в том числе 6 статей и 6 докладов в сборниках трудов конференций, включая 5 публикаций в периодических изданиях, рекомендуемых ВАК РФ для публикаций материалов кандидатских диссертаций.

Структура и объем работы» Диссертация состоит из введения, четырех глав, заключения, библиографического списка (102 наименований) и приложений. Основная часть диссертации содержит 131 страницу машинописного текста, включая 6 рисунков, 17 таблиц.

и

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

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

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

В четвертой главе рассматривается методика построения программного обеспечения СУБЗ в составе ИС прогнозирования действий противодействующей стороны, испол