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

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

/

Ахаев Александр Валерьевич

МЕТОДИКА, МОДЕЛ1Ц1 АЛГОРИТМЫ ВЫБОРА ПРОГРАММНЫХ ПРОДУКТОВ НА ОСНОВЕ ОНТОЛОГИИ И НЕЧЕТКОЙ МЕРЫ

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Томск-2014

005557679

005557679

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Томский государственный университет систем управления и радиоэлектроники» (ТУСУР)

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

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

доктор технических наук, профессор Ходашинский Илья Александрович

Тузовский Анатолий Федорович, доктор технических наук, профессор, профессор кафедры оптимизации систем управления Национального исследовательского Томского политехнического университета

Аршинский Леонид Вадимович, доктор технических наук, доцент, заведующий кафедрой информационных систем и защиты информации Иркутского государственного университета путей сообщения

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

Институт систем информатики Ершова СО РАН (г. Новосибирск)

им. А.П.

Защита состоится 19 декабря 2014 г. в 15 час. 15 мин. на заседании диссертационного совета Д 212.268.02 в ТУСУРа по адресу: 634050, г. Томск, пр. Ленина, 40.

С диссертацией можно ознакомиться в научной библиотеке ТУСУРа по адресу: г. Томск, ул. Красноармейская, 146 и на сайте ТУСУРа: http://tusiir.nl/rti/science/news/diss.html

Автореферат разослан 1» 1 ^ 2014 г.

Ученый секретарь диссертационного совета

Мещеряков Роман Валерьевич

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

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

Отправным этапом решения проблемы является анализ предметной области. Широко распространенным подходом к анализу предметной области является онтологическое моделирование. В данном научном направлении работают многие ученые: И.Л. Артемьева, Т.А. Гаврилова, В.В. Грибова, Н.Г. Загоруйко, Ю.А. Загорулько, A.C. Клещев, C.B. Мальцева, Л.В. Массель, Д.Е. Пальчунов, В.Ш. Рубашкин, Г.В. Рыбина, А.Ф. Тузовский, В.Ф. Хорошевский, В.З. Ямпольский, Н.Г. Ярушкина, Т. Gruber, N. Guarino, J. Lugger, D. McGuinness, N. Noy, R. Studer.

Задачи выбора наилучшей альтернативы отличаются большим разнообразием и решаются различными методами в зависимости от типа входной информации. Однако в реальных задачах принятия решений критерии выбора взаимозависимы, следовательно, традиционные операторы агрегации на основе аддитивных мер для объединения таких критериев не применимы. Для моделирования субъективного принятия решений используются нечеткие меры (G. Choquet, M. Grabish, M. Rubens, M. Sugeno, W. Wang, R. Yager, L. Zadeh), a в качестве оператора агрегации применяются нечеткие интегралы (А.Н. Алфимцев, С.Л. Блюмин, В.В. Девятков, С.А. Сакулин, M. Detyniecki, С. Labreuche, J. Marichal, V. Pasrija, M. Roubens, С. Tan, X. Wang). Несмотря на обширные исследования в рассматриваемой области, которые показали высокую адекватность нечетких моделей при решении отдельных задач, до сих пор не найдено оптимальное решение проблемы выбора наилучшего программного продукта с учетом предпочтений покупателя.

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

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

Для достижения поставленной цели решены следующие основные задачи:

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

2) разработка методики построения модели для выбора программного продукта на основе онтологии;

3) разработка языка представления знаний, ориентированного на решение задач выбора программного продукта, и разработка алгоритмов пополнения базы знаний из программной документации;

4) разработка модели выбора наилучшего программного продукта по предпочтениям пользователя на основе нечеткой меры и интеграла Шоке;

5) разработка численного метода оптимизации нечеткой меры на основе империалистического алгоритма;

6) реализация веб-ориентированного программного комплекса для выбора программных продуктов.

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

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

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

Научная новизна

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

2. Разработана многокритериальная модель выбора наилучшего программного продукта по предпочтениям пользователя. Отличительной особенностью модели является использование нечеткой меры и применение интеграла Шоке в качестве оператора агрегации.

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

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

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

Результаты диссертационной работы внедрены в ООО «Информационно-технологическая сервисная компания» (ИТСК), о чем имеется акт внедрения, а также используются в учебном процессе на кафедре комплексной информационной безопасности электронно-вычислительных систем Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Томский государственный университет систем управления и радиоэлектроники» (ТУСУР).

Основные положения, выносимые на защиту

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

Соответствует пункту 1 паспорта специальности: Разработка новых математических методов моделирования объектов и явлений.

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

Соответствует пункту 1 паспорта специальности: Разработка новых математических методов моделирования объектов и явлений.

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

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

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

Соответствует пункту 4 паспорта специальности: Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента.

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

выставках: Томский IEEE семинар «Интеллектуальные системы моделирования, проектирования и управления» (Томск, 2011-2014); Всероссийская научно-техническая конференция «Научная сессия ТУСУР» (Томск, 2011-2014); Всероссийская научно-практическая конференция «Молодежь и современные информационные технологии» (Томск, 2011); XIX Международная научно-практическая конференция студентов и молодых ученых «Современные техника и технологии» (Томск, 2012); Региональная выставка научных достижений молодых ученых «СибНова-2012» (Томск, 2012); VIII Международная научно-практическая конференция «Электронные средства и системы управления», посвященная 50-летию ТУСУРа (Томск, 2012); XVIII Байкальская Всероссийская конференция и Школа-семинар научной молодежи «Информационные и математические технологии в науке и управлении» (Иркутск, 2013), Научный семинар Сибирского государственного университета телекоммуникаций и информатики (Новосибирск, 2013).

Публикации по теме работы. По теме диссертации опубликовано 20 работ, из них 4 - в периодических изданиях, рекомендованных ВАК Министерства образования и науки Российской Федерации для публикации научных работ. В том числе получены два свидетельства о государственной регистрации программы для ЭВМ (№2013611467, №2013660254).

Личный вклад автора. Постановка задачи была проведена совместно с научным руководителем. Все результаты работы получены автором лично. Программная реализация веб-ориентированного программного комплекса выполнена автором лично.

Объем и структура работы. Диссертационная работа состоит из введения, пяти глав и заключения. Объем работы составляет 142 страницы. Список литературы содержит 138 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Для систем, основанных на знаниях, в частности, предназначенных для функционирования в сети Интернет часто применяется онтологический подход. Онтология (О) определятся по формуле (1):

О = <Т, A, R, D>, (1)

где Т - множество терминов, обозначающих объекты и понятия предметной области, А - множество атрибутов понятий, R - множество отношений (связей) между терминами, D - множество определений понятий и отношений.

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

Нечеткий интеграл Шоке от функции h: Z —► [0, 1] на множестве Z = :2,...,-л} по нечеткой мере 2Z —» [0,1] определяется по формуле (2):

С,(h)=¿[//(.-(0)-л(-(,-1,)МЛ«„) > (2)

где (/) - обозначение перестановки вида Mz(oj)= Ф

fy/) ={Z(r)>— >Z(n)}-

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

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

Пусть имеется множество программных продуктов (альтернатив) S = {îi, s2, ..., s,}, на выбор которых влияют два фактора:

• бизнес предпочтения BP = {bp\, bp2, ..., bpi) — общие требования к s„ которые определяют область применения ПП;

• пользовательские предпочтения FP = {fpu /рг, •••, fpj), — специализированные требования к s» которые определяют наличие функциональных возможностей в ПП.

В соответствии с данными факторами выбор подразделяется на:

1) выбор множества SS программных продуктов по бизнес предпочтениям BP из множества S, где SS = {si(BP),..., sv(BP)}, (SS Q. S);

2) выбор наилучшего программного продукта по функциональным возможностям FP из множества SS (глава 3).

Определение множества SS осуществляется при помощи онтологии Ош по правилам из Rs. При этом множество правил актуализируются при помощи онтологии Ojoc. Учитывая вышесказанное, предлагается модель выбора программных продуктов следующего вида:

< BP, SS, 0sa,Rs,0j0c>, где BP - множество бизнес предпочтений, которое включает в себя входные данные выбора; SS - множество программных продуктов, которое представляет собой выходные данные выбора; О- онтология предметной области; О ¿ж -онтология программной документации; Rs = {rsb rs2, ..., rsp} - множество правил на оригинальном языке представления знаний.

Данная модель строится по методике, представленной в виде пошагового (поэтапного) описания.

Вход: Знания экспертов о предметной области и ее структуре.

Выход: Модель выбора программных продуктов < BP, SS, Osa, Rs, Ojoc >.

Шаг 1. Формирование онтологии предметной области (О*,);

Шаг 2. Формирование онтологии программной документации {0Л1С).

Шаг 3. Генерация базы правил (Я5).

Шаг 4. Приобретение знаний из программной документации. Шаг 5. Тестирование на машине логического вывода (МЛВ). На рисунке 1 показана ШЛ-диаграмма взаимодействия данных этапов построения модели._

Методика построения модели выбора программного продукта

Эксперты и специалисты по знаниям

Алгоритм конвертации онтологии

Алгоритм приобретения знаний

Г Сформировать онтологию | I Сформировать онтологию I предметной области I I программной документации J

V

V

гологию | >(екгации I

Ц;

Сгенерировать базу правил |

Извлечь правило из программной докумекшти

I Тестировать на МЛВ

Рисунок 1. Ш/£-диаграмма взаимодействия этапов построения модели

Онтология предметной области. При построении онтологии Ом проблема большого количества альтернатив и их параметров решается, прежде всего, за счет выделения понятий в соответствии с бизнес предпочтениями BP и пользовательскими предпочтениями FP программных продуктов Таким образом, взяв за основу выражение (1) онтология предметной области определяется как:

Osa = <T(S, BP), A(FP), {is_a, define}, D>, где T(S, BP) — множество терминов, зависящих от понятий и элементов множеств S и BP; A(FP) - множество атрибутов терминов, зависящих от понятий и элементов множества FP; {is_a, define} - множество отношений между терминами; D - множество, содержащее определения терминов, атрибутов и отношений.

Онтология может быть представлена на одном из языков описания (OWL/RDF/XML) для дальнейшего использования.

Язык представления знаний. На основе разработанной онтологии Ом, формируется набор правил вида: ЕСЛИ <антецедент> ТО <консеквент>, где антецедент является описанием данных, а консеквент — одно или более действий, которые должны быть выполнены. Рассматриваемый язык правил представлен ниже.

<правило> ::= ЕСЛИ <антецедент>

ТОГДА <консеквент> КОНЕЦЕСЛИ; <антецедент> ::= (И {<условие>}+) | (ИЛИ {<условие>}+) <консеквент> ::= И {<действие>}+ <условие> ::= (<переменная> <знак> <значение>) <действие> ::= <переменная > = <значение>; |

<переменная > = ф<имя_функции>(<значение>); Под условием понимается предложение, по которому осуществляется поиск в базе правил, а под действием - действия, выполняемые при успешном исходе поиска (промежуточные, выступающих далее как условия, или целевые). Значениями в консеквенте являются числа, символы (выделяются кавычками) или переменные. Знак - это один из знаков сравнения: «больше» (<), «меньше» (>), «равно» (=) или «неравно» (о).

Отличительными элементами языка являются встроенные функции (название начинается на букву «ф»). Примеры правил приведены в таблице 1.

Таблица 1. Примеры правил

Правило на оригинальном ЯПЗ Интерпретация правила

ЕСЛИ (ТипПредприятия = «Хозрасчетный») II (ПодвидУчета = «Бухгалтерский и оперативный учет») II (Версия = «ПРОФ») II (ПодвидДеятельности = «Квартплата») ТОГДА ПрограммныйПродукт = «1С:Председатель ТСЖ»; КОНЕЦЕСЛИ; Если тип предприятия хозрасчетный, подвид учета бухгалтерский и оперативный, версия ПРОФ, а подвидом деятельности является квартплата, то рекомендовать программный продукт «1С: Председатель ТСЖ».

ЕСЛИ (ВидДеятельности = «ЖКХ») ТОГДА ПодвидДеятельности = ф Уточкыть/7ВД(«квартплата», «субсидии»); КОНЕЦЕСЛИ; Если видом деятельности является ЖКХ, то уточнить у пользователя подвид деятельности, предложив в качестве вариантов выбора: <квартплата> и <субсидии>.

Результатом конвертации онтологии Ом являются знания о ПП в виде множества правил Rs. Алгоритм создания правила приведен ниже.

Вход: Онтология Oia на языке OWL.

Выход: Правило rsp на оригинальном языке представления знаний.

Шаг 1. Формирование конструкции правила rs 'р по онтологии Ош\

Шаг 2. Формирование правила rsp.

Конструкция правила формируется исходя из следующих положений:

1) Если два понятия связаны отношением «класс-подкласс», то понятие «класс» является консеквентом, понятие «подкласс» является антецедентом. Если «класс» состоит из нескольких «подклассов», то понятия «подкласс» в консеквенте являются параметрами встроенной функции фУточнить.

2) Если два понятия («источник-приемник») связаны отношением «определяет», то понятие «источник» является антецедентом, понятие «приемник» является консеквентом. Если «источников» несколько, то понятия в антецеденте соединяются оператором И.

В таблице 2 представлены примеры формирования правил.

Таблица 2. Примеры формирования правил

Онтологическое представление Представление на оригинальном ЯПЗ

В define А (В определяет А), С define А, D define А ЕСЛИ ВII С И О ТОГДА А КОНЕЦЕСЛИ;

Bis aF (В является подклассом класса F) ЕСЛИ ^ ТОГДА В КОНЕЦЕСЛИ;

D is a G, Е is a G ЕСЛИ в ТОГДА фУточнитъф, Е); КОНЕЦЕСЛИ;

Алгоритм приобретения знаний из программной документации.

При решении проблемы выбора ПП важным является вопрос извлечения знаний из программной документации. Для подобного типа документов существует стандарты: ГОСТ Р ИСО/МЭК 12119-2000 и ГОСТ 19.402-78. Однако на практике программная документация содержит значительное количество отклонений от стандартов. Отсюда возникает проблема недостаточной структурированности информации. Поэтому для пополнения базы знаний решается задача извлечения знаний из слабоструктурированного документа. В диссертационной работе предлагается решить данную задачу с использованием онтологического подхода. Алгоритм приобретения знаний представлен ниже.

Вход: Программная документация Tdoc в виде текстового документа.

Выход: Правило rsp на оригинальном ЯПЗ.

Шаг 0. Формирование онтологии программной документации Odoc\

Шаг 1. Аннотирование документа - выявление множества структурных блоков Bdoc ~ {bd\, bd2, ..., bdp).

Шаг 2. Извлечение фактов Vdoc = {vd¡, vd2, ..., vd7} в структурных блоках;

Шаг 3. Формирование правила rsp для базы знаний.

В соответствии с выражением (1) онтология программной документации определяется как:

Odoc= <T(Tdoc, S, BP), KW, {is_a,part_of}, D>, где T(Tdoc, S, BP) - множество терминов, которые зависят от понятий и элементов текстового документа Tdoc и множеств S, BP; KW = {foci, kw2, ..., k\vr} — множество ключевых слов, которые представляют собой лингвистические атрибуты; {is a, part of) - множество отношений между терминами; D - множество, содержащее определения терминов, атрибутов и отношений.

Процесс аннотирования документа определяется тройкой вида:

^ Tdoc, Odoci Bdoc

где Tjoc - программная документация по конкретному ПП; Odoc - онтология программной документации; Bdoc - множество структурных блоков.

После определения структуры документа происходит обработка структурных блоков В. Ниже представлена обработка (алгоритм) блока

функциональных возможностей программного продукта. Алгоритм выполняется в цикле (обход по шаблону РТ, РТ с К\¥).

Вход: Фрагмент (структурный блок) Ьс1р документа полученный при аннотировании и шаблон РТ, представляющий собой множество наименований наиболее важных функциональных возможностей.

Выход: Множество извлеченных из Т&ж характеристик РР' {РР' Е РР) программного продукта.

Шаг 1. Поиск слова (словосочетания) IV во фрагменте Ьс1р документа по наименованию к\\'г функциональной возможности ПП из шаблона РТ;

Шаг 2. Выявление участка в Ьс1р с описанием функциональной возможности fpj программного продукта по граничным символам;

Шаг 3. Определение отсутствия слов отрицания в выявленном участке;

Шаг 4. Запись найденной функциональной возможности/р].

Результатом проведенного анализа программной документации является правило на оригинальном языке представления знаний. Полученные правила позволяют значительно сузить область поиска до 2-10 альтернатив. Если покупатель затрудняется сделать окончательный выбор самостоятельно, он может сделать это с использованием модели выбора наилучшего программного продукта на основе нечеткой меры.

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

Пусть имеется множество программных продуктов (альтернатив) (55 £ 5), задаваемых на множестве функциональных возможностей (атрибутов, признаков) РР и оцениваемых к экспертами, тогда трехмерная матрица вида продукт-атрибут-эксперт

Р = 11Л<11 (/ = Ь2, ..., тп;)= 1,2,..., п;к= 1,2, ...,д) определяет степень выраженности атрибута fpj в программном продукте 5/, определенную экспертом к, 0 < < 1. Тогда для каждого программного продукта si существует срез по эксперту к вида Мл = {/,\ь---,/,пк}-

Нечеткая мера выражает значимость каждого подмножества атрибутов и определяется как 2 —► [0, 1], где 2Ш - множество всех подмножеств множества функциональных возможностей Л/^.

Тогда применительно к решаемой задаче значение интеграла Шоке (2) по нечеткой мере есть интегральная оценка программного продукта 5/:

У, = ¿(/('.(у),*) - и -1). к)ММт), (3)

где О) - обозначение перестановки вида 0</(/,(1 ),£)<•••</(/,(и),Л), /(/,(0),*)= 0; Л/да ={/(/,0)Д),...,/(/,(и),к)}.

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

выражены в виде матрицы обобщенных интегральных оценок У = Данная оценка в интервале от 0 до 1 представляет собой степень функционального наполнения ПП. Определение У выполняется с использованием нечеткого вывода, так как для экспертов данная задача является трудоемкой.

Зная вектор оценок || ук || для программного продукта 5/, значения при минимизации выражения суммы разности квадратов определяются как:

е = £-у,)2 —>шт е = -¿(/(/,(у)Д)-/(/,а-1)Д))МЧ4.) ->тт.(4)

4=1 ' 4-1V '

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

Пусть предпочтения пользователя представляют собой вектор РР, тогда - вектор интегральных оценок предпочтений пользователя, вычисленный с использованием значений мШт) п0 интегралу Шоке. Для определения наилучшего .$, необходимо найти минимальную разницу между оценками через выражение:

¿(Л--И„)2-> тт. (5)

4=1

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

Алгоритм расчета интегральной оценки программного продукта по функциональным возможностям.

Вход: Экспертные оценки (качественные и количественные) функциональных возможностей М'ц.

Выход: Интегральная оценка .у* программных продуктов.

Шаг 1. Нормирование:

Шаг 1.1. Нормирование количественных оценок с использованием обобщенной функции желательности Харрингтона;

Шаг 1.2. Приведение к единой универсальной шкале [0,1];

Шаг 2. Расчет интегральной оценки на основе нечеткого вывода:

Шаг 2.1. Формирование базы правил ЛГ5 = {г/,, г/2, ..., г/,} для определения взаимосвязи между входными (нормированные оценки М*) и выходной переменной у£

Шаг 2.2. Фаззификация входных переменных; Шаг 2.3. Агрегирование субусловий в нечетких правилах; Шаг 2.4. Активизация субзаключений в нечетких правилах; Шаг 2.5. Аккумуляция заключений нечетких правил; Шаг 2.6. Дефаззификация выходных переменных.

Нормирование оценок М осуществляется сначала по формуле:

4 = ехр[-ехр(-А/ ',*)], (6)

где ^ — оценка на шкале желательности.

Следующим этапом нормирования является пересчет полученных значений ¡^ в отметки на интервале от 0 до 1.

После нормирования всех характеристик Мц, осуществляется расчет интегральной оценки ук, реализованный в рамках основных этапов нечеткого вывода. Интегральные оценки Mik используются в (4) при оптимизации нечеткой меры р, на основе империалистического алгоритма.

Численный метод оптимизации нечеткой меры на основе империалистического алгоритма.

Решается задача нахождения оптимума (страны империалиста) при минимизации ошибки {стоимости) в (4), где //(Л/(,ч) - результат {позиция) решения {страны); е = с, - ошибка {стоимость) решения {страны). Все решения делятся на оптимумы и остальные решения {колонии), затем объединяются в кластеры {империи). На результат оптимизации влияют коэффициенты {сила)pt оптимума и Рр, кластера на интервале [0,1].

Вход: Экспертные оценки Mik функциональных возможностей и вектор ы\ обобщенных предпочтений программного продукта из (4).

Выход: Нечеткая мера p{M(ii)).

Шаг 1. Инициализация империй. Процесс инициализации империй начинается со случайной генерации N^ количества стран. Из них выбирается Nimp наиболее сильных стран (империалистов), которые будут формировать

империи. Сила определяется через нормализованную стоимость ^ = maxcj~ct,

i^f.mp

С,

где Cj - стоимость /-го империалиста (с = е). Тогда сила ^

Ее/

7=1

Оставшиеся Ncoi стран между империалистами пропорционально их силе. То есть количество колоний в z'-й империи определяется как А'С, = round {piNcol). Далее колонии случайным образом распределяются среди империалистов.

Шаг 2. Ассимиляция колоний. Процесс ассимиляции колоний моделируется их перемещением к империалисту. Направление перемещения совпадает с вектором, устремленным от колонии к империалисту. Расстояние перемещения х является случайной величиной, распределенной по нормальному закону х ~ U{0, fi d), где d - текущее расстояние между колонией и империалистом, а /? - число большее единицы, которое позволяет колониям сближаться с империалистом равновероятно со всех сторон. В большинстве реализаций алгоритма используется значение /? ~ 2.

Шаг 3. Обмен позициями между империалистом и колонией. Если после ассимиляции новая позиция одной или нескольких колоний империи является более выгодной, чем позиция самого империалиста, тогда империалист и колония меняются местами. Иначе переход на Шаг 4.

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

нее: ТС, =с, , где ГС, - сила i-й империи, с, — стоимость империалиста /-й империи, с, - средняя стоимость колоний империи, 0 < <f < 1. Значение <f = 0,1 обеспечивает минимальное влияние колоний на стоимость империи. <f

Шаг 5. Империалистическое соперничество. Процесс соперничества моделируется выбором самой слабой колонии слабой империи и инициированием борьбы за нее между другими империями. Сила /-й империи определяется через нормализованную стоимость ЛТС, каждой империи

(аналогично Шагу 1): =тахТС)-Щ Тогда сши (верояхНость победы)

тс,

Р —

определяется как: ■ Затем формируется вектор Р = [Рри Рр2, ... ,

I ХЩ 1-1

Ррютр-Л, вектор К = [гь Г2, ... , ГЮЩ-,], П, г2, ... , г№щ-х ~ и (0, 1), элементы которого случайно распределены по равномерному закону и вычисляется вектор Б = Р - К. Колония переходит к империи, для которой соответствующее значение вектора Б максимально.

Шаг 6. Уничтожение слабых империй. Если империя не содержит ни одной колонии, то уничтожить империю. Иначе переход на Шаг 7.

Шаг 7. Условие останова. Если осталась только одна империя, то закончить выполнение алгоритма. Позиция //(А/^,) империалиста оставшейся империи является выходным значением алгоритма. Иначе переход на Шаг 2.

Таким образом, на выходе получаем нечеткую меру я(М<*)) функционального наполнения в интервале от 0 до 1. После извлечения нечетких мер ПП выбирается наилучший по предпочтениям пользователя.

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

Вход: Пользовательские оценки (предпочтения) ЕР функциональных возможностей желаемого ПП; множество программных продуктов 55 с соответствующими интегральными оценками || ук || и нечеткими мерами //(А/(,ц).

Выход: Наилучший программный продукт 5 / (рекомендация).

Шаг 1. Нормирование пользовательских оценок по функции (6).

Шаг 2. Расчет интегральной оценки ур желаемого программного продукта (3) исходя из предпочтений РР с использованием /и(М{1к>).

Шаг 3. Определение вектора оценок || ук || наиболее близкого к || ур || по формуле 5. Соответствующий интегральной оценке программный продукт 5'/ является выходным значением алгоритма.

Шаг 4. Определение оценки «близости» V = [0, 1] найденного ПП к

Ур-Ук

предпочитаемому по формуле ^

1-

У к 1 -Ук

0,ук=0чук=1чу =\.

Шаг 5. Определение вербальной оценки «близости» найденного ПП к предпочитаемому.

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

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

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

Инженер по знаниям, Эксперт

££ Клие

I С >

| Интеллектуальный

| редактор

! Интерфейс

! пользователя <--

1..........И".....

Покупатель

Рисунок 2. Архитектура веб-ориентированного программного комплекса

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

Для разработки веб-ориентированного программного комплекса в соответствии с предложенной архитектурой и алгоритмическим обеспечением, выбрана платформа «Ю.Предприятия 8». В качестве системы управления базами данных выбран Microsoft SQL Server 2005, в качестве веб-сервера — Apache 2.2. При построении онтологии использовался редактор Protégé 4.3.

Программный комплекс включает в себя как обычное клиентское приложение, исполняемое в операционной системе компьютера ( Windows или Linux), так и веб-приложение, исполняемое в среде интернет-браузера (Windows Internet Explorer, Mozilla Firefox, Google Chrome или Safari).

Программный комплекс разделен на подсистемы в соответствии с выполняемыми задачами. На рисунке 3 представлена общая i/AÄ-диаграмма пакетов системы.

Сервер

im

Ю;

Модуль истории выбора

Механизм логического вывода

База правил

База фактов

Модуль приобретения

Модуль анализа функциональных

знании возможностей _/ V_

Подсистема построения ЭС

Подсистема истории выбора

Механизм выбора ПП

Подсистема анализа функциональных

возможностей

Подсистема приобретения знаний

Рисунок 3. ¿УЛЛ,-диаграмма пакетов системы

В пятой главе показано применение веб-ориентированного программного комплекса для выбора ПП экономического назначения -программных продуктов системы «1С:Предприятие 8» (ППС1С). Представлены результаты тестирования программного комплекса.

Программный комплекс апробирован на пятидесяти шести клиентах ИТСК, уже работающих с пятнадцатью ПП «1С:Предприятие 8» в восьми видах деятельности. Все клиенты проходившие тестирование были разделены на три подгруппы по длительности использования ППС1С: до года (17 клиентов), от одного года до двух лет (14 клиентов), более двух лет (25 клиентов). Во время тестирования выяснялись показатели соответствия предпочтений пользователя используемому ПП. Результаты тестирования представлены в таблице 3.

Показатель Длительность использования клиентом ППС1С Всего

до 1 года от 1 до 2 лет более 2 лет

кол-во % кол-во % кол-во % кол-во %

Общее количество клиентов 17 100 14 100 25 100 56 100

Текущая ППС1С соответствует бизнес предпочтениям 14 82 12 86 21 84 47 84

Текущая ППС1С не соответствует бизнес предпочтениям 3 18 2 14 4 16 9 16

Текущая ППС1С соответствует пользовательским предпочтениям 10 59 11 79 19 76 40 71

Текущая ППС1С не соответствует пользовательским предпочтениям 7 41 3 21 6 24 16 29

Текущая ППС1С удовлетворяет И 65 12 68 23 92 46 81

Текущая ППС1С не удовлетворяет 6 35 2 14 2 8 10 19

На основе полученных данных выявлено, что:

• в 84% случаев на основе методики и модели выбора программных продуктов программный комплекс рекомендует то решение, которое совпадает с решением, принятым ранее на основе рекомендаций экспертов;

• в 71% случаев на основе многокритериальной модели выбора наилучшего ПП программный комплекс рекомендует используемый ППС1С.

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

В заключении приводятся выводы по диссертационной работе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

5. Разработан веб-ориентированный программный комплекс и внедрен в ИТСК, где используется для оперативного предоставления квалифицированной рекомендации при выборе наилучшего программного продукта системы «1С:Предприятие 8». Результаты диссертационной работы используются в учебном процессе на кафедре комплексной информационной безопасности электронно-вычислительных систем ТУСУР.

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

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

В журналах, рекомендованных ВАК Министерства образования и науки Российской Федерации:

1. Адуева Т.В. Продукционная система выбора программных продуктов системы «1 С:Предприятие 8» / Т.В. Адуева, A.B. Ахаев, И.А. Ходашинский // Бизнес-информатика. - 2012. - №1(19). - С. 55-61.

2. Ахаев A.B. Алгоритм оценивания функционального наполнения программных продуктов на основе нечеткого логического вывода / A.B. Ахаев // Доклады Томского государственного университета систем управления и радиоэлектроники. - 2013. -№2(28). - С. 169-174.

3. Ахаев A.B., Алгоритмы и программные средства построения экспертных систем выбора программных продуктов на примере «1С:Предприятие 8» / A.B. Ахаев, И.А. Ходашинский // Информатика и системы управления. - 2013. -№4(38). - С. 70-79.

4. Ахаев A.B. Метод выбора программного продукта на основе интеграла Шоке и империалистического алгоритма / A.B. Ахаев, И.А. Ходашинский, А.Е. Анфилофьев // Доклады Томского государственного университета систем управления и радиоэлектроники. - 2014. - №2(32) - С. 224-229.

В других изданиях:

5. Ахаев A.B. Классификация программных продуктов «1С:Предприятие 8» / A.B. Ахаев // Научная сессия ТУ СУР 2011: Материалы докладов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых. - Томск: B-Спектр, 2011.-ч.2.-С. 165-168.

6. Ахаев A.B. Язык описания базы знаний продукционной системы выбора конфигураций программных продуктов «1С:Предприятие 8» / A.B. Ахаев // Молодежь и современные информационные технологии: Сборник трудов IX Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. - Томск: СПБ Графике, 2011. -ч.1.-С. 260-261.

7. Ахаев A.B. Модуль приобретения знаний из «1С»-инфописем с использованием онтологического подхода / A.B. Ахаев // Современные техника и технологии: сборник трудов XVIII Международной научно-практической конференции студентов, аспирантов и молодых ученых. - Томск: Изд-во ТПУ, 2012. — т.2. — С. 267-268.

8. Ахаев A.B. Использование онтологического подхода для приобретения знаний из «1С»-инфописьма / A.B. Ахаев // Материалы 50-й Международной научной студенческой конференции «Студент и научно-технический прогресс»: Информационные технологии. - Новосибирск, 2012. - С. 187.

9. Ахаев A.B. Структура продукционной системы выбора программных продуктов системы «1С:Предприятие 8» / A.B. Ахаев // Научная сессия ТУСУР 2012: Материалы Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых. - Томск: В-Спектр, 2012. - ч.З. - С. 9-11.

10. Ахаев A.B. Оценивание функционального наполнения программных продуктов системы «1С:Предприятие 8» на основе нечеткого вывода с использованием шкалы Харрингтона / A.B. Ахаев // Электронные средства и системы управления: Материалы докладов Международной научно-

практической конференции. - Томск: B-Спектр, 2012.-Ч.1.-С. 136-140.

11. Ахаев A.B. Web-ориентированная экспертная система выбора программных продуктов / A.B. Ахаев // Наука. Технологии. Инновации: материалы Всерос. науч. конф. студентов, аспирантов и молодых ученых. - Новосибирск: Изд-во НГТУ, 2012. - ч.З. - С. 263-266.

12.Ахаев A.B. Разработка web-ориентированной экспертной системы для выбора программных продуктов на примере «1С:Предприятие 8» / A.B. Ахаев // Современные техника и технологии: сборник трудов XIX Международной научно-практической конференции студентов, аспирантов и молодых ученых. -Томск: Изд-во ТПУ, 2013. - т.2. - С. 206-207.

13.Ахаев A.B. Методы и системы выбора наилучшего объекта / A.B. Ахаев // Научная сессия ТУ СУР 2013: Материалы Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых. - Томск: В-Спектр, 2013,-4.4.-С. 9-11.

14. Ахаев A.B. Web-ориентированная экспертная система для выбора программных продуктов системы «1С:Предприятие 8» / A.B. Ахаев, И.А. Ходашинский // Вычислительный интеллект (результаты, проблемы, перспективы): Материалы 2-й международной научно-технической конференции. - Черкассы, Украина: Маклаут, 2013. - С. 144-145.

15. Ахаев A.B. Алгоритмы и программные средства построения web-ориентированных экспертных систем выбора программных продуктов на примере «1С:Предприятие 8» / A.B. Ахаев // XVIII Байкальская Всероссийская конференция с международным участием «Информационные и математические технологии в науке и управлении». Иркутск, 2013. - С. 78-84.

16. Ахаев A.B. Онтологический подход к извлечению знаний из информационных писем о программных продуктах системы «1С:Предприятие 8» / A.B. Ахаев, И.А. Ходашинский // Материалы Всероссийской конференции с международным участием «Знания - Онтологии - Теории» (30HT-2013). -Новосибирск: ИМ СО РАН, 2013.-Т. 1.-С. 26-31.

17. Ахаев A.B. Формирование базы знаний экспертной системы на основе онтологии с использованием оригинального языка представления знаний / A.B. Ахаев, И.А. Ходашинский // Электронные средства и системы управления: Материалы докладов Международной научно-практической конференции. — Томск: В-Спектр, 2013. - ч.2. - С. 3-7.

18. Ахаев A.B. Алгоритм выбора программного продукта на основе интеграла Шоке // Научная сессия ТУСУР 2014: Материалы Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых. - Томск: В-Спектр, 2014.-ч.З.-С.15-17.

19. Свид. о государственной регистрации программы для ЭВМ №2013611467. Ахаев A.B., Ходашинский И.А., Подсистема оценивания функционального наполнения программных продуктов. Зарег. в Реестре программ для ЭВМ 21 января 2013 г.

20. Свид. о государственной регистрации программы для ЭВМ №2013660254. Ахаев A.B., Ходашинский И.А., Подсистема приобретения знаний о программных продуктах. Зарег. в Реестре программ для ЭВМ 29 октября 2013 г.

Тираж 100 экз. Заказ 839. Томский государственный университет систем управления и радиоэлектроники. 634050, г. Томск, пр. Ленина, 40.