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

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

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

Специальность 05.13.17 – Теоретические основы информатики

А В Т О Р Е Ф Е Р А Т

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

кандидата технических наук

Москва – 2011

Работа выполнена на кафедре Прикладной математики Московского энергетического института (Технического университета)

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

Вадим Николаевич Вагин

Официальные оппоненты: доктор физико-математических наук, профессор

Геннадий Семёнович Осипов;

кандидат физико-математических наук, ведущий научный сотрудник

Алексей Николаевич Аверкин

Ведущая организация: ГУ "Российский НИИ информационных технологий и систем автоматизированного проектирования", г. Москва

Защита состоится «23» июня 2011 г. в 18 час. 00 мин. на заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (Техническом университете) Москва, Красноказарменная ул., 17 (ауд. Г-306).

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (Технического университета).

Отзывы в двух экземплярах, заверенные печатью, просьба направлять г. Москва, Красноказарменная улица, Ученый Совет МЭИ (ТУ).

Автореферат разослан «____» ___________ 2011 г.

Ученый секретарь

диссертационного совета Д 212.157.01

кандидат технических наук,

доцент

Общая характеристика работы

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

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

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

Одним из вариантов организации абдуктивного вывода, определяющим высокую скорость поиска решений, мощные средства для пересмотра решений и обеспечения непротиворечивости выводимых решений, является сохранение выводимых данных в системе поддержки истинности, основанной на предположениях (Assumption-based Truth-Maintenance System, ATMS).

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

В теорию и практику организации абдуктивного вывода большой вклад внесли отечественные учёные , , и другие, а так же учёные , Мак Джозефсон Дж., и другие.

При реализации алгоритмов абдуктивного вывода могут использоваться возможности, предоставляемые системами поддержки истинности. Значительный вклад в исследование и разработку систем поддержки истинности внесли такие учёные, как Дойл Дж., разработавший одну из самых первых систем поддержки истинности, ДеКлир Дж., который ввёл термин “основанный на предположениях” и представил соответствующую систему поддержки истинности, Мак Мартинс Дж., и другие. К достоинствам данных систем относится обеспечение объяснений и сохранение произведённых и промежуточных выводов, работа с противоречиями, умолчаниями, новыми фактами и обоснованиями.

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

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

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

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

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

Для достижения указанной цели требовалось решение следующих задач:

1)  Исследование существующих методов и алгоритмов абдуктивного вывода.

2)  Разработка алгоритма абдуктивного вывода с применением первичных импликат.

3)  Разработка эвристического метода для алгоритма абдуктивного вывода с применением первичных импликат.

4)  Исследование возможностей систем поддержки истинности на основе предположений для организации абдуктивного вывода.

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

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

7)  Разработка на основе системы поддержки истинности, основанной на предположениях, эвристического метода выбора начального порядка литер в исходных дизъюнктах.

8)  Разработка и программная реализация на базе системы поддержки истинности алгоритма абдуктивного вывода.

9)  Проверка работы алгоритма и его программной реализации на задаче составления расписания работ в сложных технических объектах.

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

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

Научная новизна. Новыми являются:

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

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

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

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

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

Практическая значимость работы подтверждена использованием полученных результатов в интеллектуальной системе поддержки принятия решений “СПРИНТ-РВ” и в учебном процессе в МЭИ (ТУ) при изучении дисциплины “Математическая логика”, о чём имеются акты о внедрении.

Реализация результатов. Результаты диссертационной работы вошли в отчёты по НИР, выполняемым кафедрой ПМ по грантам РФФИ № 09-01-00076а “Исследование и разработка методов анализа данных и обнаружения знаний в «зашумленных» базах данных”, № 08-07-00212 “Исследование и разработка методов и инструментальных средств индуктивного формирования понятий в интеллектуальных системах поддержки принятия решений”, в отчёты по НИР, выполняемым по гранту “У. М.Н. И.К.”, а также были использованы в учебном процессе в курсе “Математическая логика”. На разработанный в диссертационной работе программный комплекс выдано свидетельство о государственной регистрации программы для ЭВМ № 000 (27 июня 2010 г.).