Введение к работе
Актуальность темы исследований. Важной задачей, с которой сталкиваются при проектировании систем поддержки принятия решений, является разработка таких моделей и методов, которые способны функционировать в открытых и динамичных проблемных областях, с возможностью корректировки и пополнении модели принятия решений в процессе поиска. Абдуктивный вывод успешно используется для достижения этой цели, и заключается в выводе причины для наблюдения. Вывод по абдукции не является строгим, это правдоподобный вывод, который может подвергаться пересмотру, что позволяет повысить гибкость разрабатываемых моделей и методов для интеллектуальных систем.
Вывод по абдукции успешно применяется для решения задач диагностики неисправностей, распознавания образов, понимания естественного языка, накопления и обработки знаний, пересмотра убеждений, в автоматизированном планировании и составлении расписаний.
Ключевыми характеристиками абдуктивных решателей являются скорость поиска решений, возможность пересмотра решений и обеспечение непротиворечивости выводимых решений.
Одним из вариантов организации абдуктивного вывода, определяющим высокую скорость поиска решений, мощные средства для пересмотра решений и обеспечения непротиворечивости выводимых решений, является сохранение выводимых данных в системе поддержки истинности, основанной на предположениях (Assumption-based Truth-Maintenance System, ATMS).
В настоящее время системы поддержки истинности, основанные на предположениях, стали широко используемой частью интеллектуальных систем. Они используются в диагностике, в экспертных системах.
В теорию и практику организации абдуктивного вывода большой вклад внесли отечественные учёные Финн В.К., Кузнецов С.О., Аншаков О.М., Виноградов Д.В., Рузавин Г.И., Васюков В.Л. и другие, а так же учёные Пирс Ч.С., Пол Г., Флэч П., Какас А., Габбай М., Бергадано Ф., Дюбуа Д., Прейд Х., МакИлрайт Ш., Аллемань Д., Джозефсон Дж., Конолиге К., Ковальски Р., Тони Ф., Иноу К., Сакама Ч., Левек Х., Кокс Ф., Пиетржиковски Т., Аппелт Д., Поллак М., Консоле Л., Дюпре Д., Пул Д. и другие.
При реализации алгоритмов абдуктивного вывода могут использоваться возможности, предоставляемые системами поддержки истинности. Значительный вклад в исследование и разработку систем поддержки истинности внесли такие учёные, как Дойл Дж., разработавший одну из самых первых систем поддержки истинности, ДеКлир Дж., который ввёл термин “основанный на предположениях” и представил соответствующую систему поддержки истинности, МакАллестер Д., Рейтер Р., Мартинс Дж., Форбус К. и другие. К достоинствам данных систем относится обеспечение объяснений и сохранение произведённых и промежуточных выводов, работа с противоречиями, умолчаниями, новыми фактами и обоснованиями.
В процессе абдуктивного вывода происходит постоянное уточнение решений, причём возникает проблема представления промежуточных решений в памяти компьютера. Реализация существующих алгоритмов абдуктивного вывода становится неэффективной из-за необходимости обработки избыточных данных, что непосредственно влияет на скорость абдуктивного вывода. Для решения этой задачи можно использовать возможности, предоставляемые системой поддержки истинности на основе предположений, с использованием которой реализован программный комплекс.
Для абдуктивного вывода необходимо связать гипотезы, из которых компонуются решения, с наблюдением через причинно-следственные отношения. Для корректности абдуктивного вывода необходимо своевременно выявить противоречивые гипотезы и их комбинации. Данные гипотезы не должны включаться в решение задачи абдуктивного вывода. Для работы с предположениями, множественными вариантами и появляющимися противоречиями в процессе абдуктивного вывода можно использовать возможности системы поддержки истинности на основе предположений, на основе которой может быть реализован абдуктивный вывод.
Показаны преимущества применения систем поддержки истинности при реализации абдуктивного вывода. Важнейшим этапом, влияющим на эффективность алгоритма абдуктивного вывода, является использование возможностей системы поддержки истинности на основе предположений для кэширования промежуточных результатов и исключения повторных вычислений. В рамках темы исследований решаются такие актуальные вопросы информатики, как разработка интегрированных средств представления знаний, моделирование рассуждений различного типа; разработка логических моделей и методов взаимодействия информационных процессов. Таким образом, разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений является актуальной задачей.
Объектом исследования являются системы поддержки истинности, основанные на предположениях. Предметом исследования являются методы и алгоритмы систем поддержки истинности на основе предположений для реализации абдуктивного вывода.
Целью работы является исследование, разработка методов, алгоритмов и соответствующих программных средств, реализующих абдуктивный вывод с использованием систем поддержки истинности на основе предположений.
Для достижения указанной цели требовалось решение следующих задач:
-
Исследование существующих методов и алгоритмов абдуктивного вывода.
-
Разработка алгоритма абдуктивного вывода с применением первичных импликат.
-
Разработка эвристического метода для алгоритма абдуктивного вывода с применением первичных импликат.
-
Исследование возможностей систем поддержки истинности на основе предположений для организации абдуктивного вывода.
-
Разработка на основе системы поддержки истинности, основанной на предположениях, алгоритма абдуктивного вывода.
-
Разработка модификации алгоритма абдуктивного вывода на основе системы поддержки истинности для решения задачи составления расписаний.
-
Разработка на основе системы поддержки истинности, основанной на предположениях, эвристического метода выбора начального порядка литер в исходных дизъюнктах.
-
Разработка и программная реализация на базе системы поддержки истинности алгоритма абдуктивного вывода.
-
Проверка работы алгоритма и его программной реализации на задаче составления расписания работ в сложных технических объектах.
Методы исследования. Поставленные задачи решаются с использованием методов дискретной математики, математической логики, теории информации, искусственного интеллекта, а также методов анализа вычислительной сложности алгоритмов.
Достоверность научных положений. Достоверность и обоснованность научных результатов подтверждена теоретическими выкладками, данными компьютерного моделирования, а также сравнением полученных результатов с результатами, приведёнными в научной литературе.
Научная новизна. Новыми являются:
-
Алгоритм абдуктивного вывода с использованием первичных импликат и его модификация.
-
Эвристический метод выбора начального порядка в исходных литерах для алгоритмов абдуктивного вывода с использованием первичных импликат.
-
Алгоритм абдуктивного вывода на базе системы поддержки истинности, основанной на предположениях, и его модификация.
-
Эвристический метод выбора начального порядка в исходных литерах для алгоритмов абдуктивного вывода на базе системы поддержки истинности, основанной на предположениях.
Практическая значимость работы заключается в создании программного комплекса, реализующего составление расписания работ в сложных технических объектах, с использованием алгоритма абдуктивного вывода на базе системы поддержки истинности, основанной на предположениях.
Практическая значимость работы подтверждена использованием полученных результатов в интеллектуальной системе поддержки принятия решений “СПРИНТ-РВ” и в учебном процессе в МЭИ (ТУ) при изучении дисциплины “Математическая логика”, о чём имеются акты о внедрении.
Реализация результатов. Результаты диссертационной работы Хотимчука К.Ю. вошли в отчёты по НИР, выполняемым кафедрой ПМ по грантам РФФИ № 09-01-00076а “Исследование и разработка методов анализа данных и обнаружения знаний в «зашумленных» базах данных”, № 08-07-00212 “Исследование и разработка методов и инструментальных средств индуктивного формирования понятий в интеллектуальных системах поддержки принятия решений”, в отчёты по НИР, выполняемым Хотимчуком К.Ю. по гранту “У.М.Н.И.К.”, а также были использованы в учебном процессе в курсе “Математическая логика”. На разработанный в диссертационной работе программный комплекс выдано свидетельство о государственной регистрации программы для ЭВМ №2010614887 (27 июня 2010 г.).
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 13-й, 16-й и 17-й научно-технических конференциях аспирантов и студентов “Радиоэлектроника, электротехника и энергетика” в МЭИ (ТУ) (г. Москва, 2007, 2010, 2011 г.), 11-й и 12-й национальных конференциях по искусственному интеллекту с международным участием КИИ-2008 (г. Дубна, 2008 г.) и КИИ-2010 (г. Тверь, 2010 г.), “Информационные технологии в науке, социологии, экономике и бизнесе” IT+S&E’11 (Украина, г. Гурзуф, 2011 г.), МНТК-2010 (г. Москва, 2010 г.), “Повышение эффективности электрического хозяйства потребителей в условиях ресурсных ограничений. Материалы Всероссийской научно-практической конференции с международным участием”.
Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 12 печатных работах, из них 3 – в журналах, относящихся к списку ВАКа.
Структура и объём работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы (72 наименования) и приложения. Диссертация содержит 114 страниц машинописного текста (без приложений).
