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

Далее, разработан эвристический метод для алгоритма ABAA\M, заключающийся в перестановке литер в исходных дизъюнктах согласно алгоритму ReArrangeLiteras, что позволяет заметно ускорить решение ряда абдуктивных задач. Будем называть модификацию алгоритма ABAA\M, которая перед работой самого алгоритма выполняет ReArrangeLiteras, как ABAA\M\H.

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

Далее представлены шаги разработанного эвристического алгоритма ReArrangeLiteras.

Алгоритм 3. Алгоритм ReArrangeLiteras.

Алгоритм ReArrangeLiteras

Исходные данные:

ruleBase – база правил.

Требуется:

переставить литеры в дизъюнктах ruleBase для того, чтобы сократить процесс опровержения (т. е., построить как можно меньше вершин).

Начало.

Шаг 1.	Найти в ruleBase все дизъюнкты, содержащие хотя бы одну *-литеру. Обозначим их множество как StarClauses. Пусть N – число таких дизъюнктов. Рассмотрим i – номер текущего дизъюнкта. Присвоим i = 1.
Шаг 2.	Если , то Конец. Иначе рассмотрим clause – i-й дизъюнкт в StarClauses. Пусть литера lit – *-литера в этом дизъюнкте. Найти все дизъюнкты в ruleBase, в которых lit встречается без отрицания. Обозначим найденное множество как S. Пусть NS – число таких дизъюнктов. Рассмотрим j – номер текущего дизъюнкта. Присвоим j = 1.
Шаг 3.	Если , то присваиваем i = i + 1 и переход к шагу 2. Иначе рассмотрим clause – j-й дизъюнкт в S. Выполнить процедуру AnalyzeMath с параметрами clause, ruleBase. Выполнить процедуру AnalyzeArgumentCover с параметром clause. Присваиваем j = j + 1 и переход к шагу 3

Конец.

Алгоритм AnalyzeMath

Исходные данные:

clause – дизъюнкт.

Требуется:

Переставить математические литеры в дизъюнкте clause в конец вплоть до положительной литеры.

Начало.

Шаг 1.	Пусть N – число отрицательных литер в дизъюнкте clause. Рассмотрим i – номер текущей литеры. Присвоим i = 1.
Шаг 2.	Если , то Конец. Иначе рассмотрим lit – i-ю литеру в clause. Если это математическая литера, то поменять её местами с N-й литерой в дизъюнкте clause, присвоить N = N – 1 и к шагу 2. Иначе присвоить i = i + 1 и к шагу 2.

Конец.

Алгоритм AnalyzeArgumentCover

Исходные данные:

clause – дизъюнкт вида , где – литеры, не являющиеся математическими, – литеры, являющиеся математическими.

Требуется:

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

Начало.

Шаг 1.	Пусть Arguments – множество рассматриваемых аргументов. Присвоим . Рассмотрим i – текущая позиция литеры. Присвоим i = 1.
Шаг 2.	Если , то Конец. Иначе найти такую литеру litera среди , что . Присвоить . Поменять местами в дизъюнкте clause литеры litera и . Присвоить i = i + 1 и к шагу 2.

Конец.

На рис. 4 представлен график зависимости времени выполнения программы от числа технических работ для четырёх предложенных в этой работе алгоритмов – ImpAA\M, ImpAA\M\H, ABAA\M, ABAA\M\H. Эксперимент проводился на машине Core 2 Duo 2,20 GHz. Для 50 технических работ алгоритм ABAA\M по сравнению с алгоритмом ImpAA\M\H даёт выигрыш в 3 раза по времени, по сравнению с алгоритмом ImpAA\M даёт выигрыш в 4 раза по времени. Алгоритм ImpAA\M\H по сравнению с алгоритмом ImpAA\M даёт выигрыш 1,3 раза по времени. Алгоритм ABAA\M\H по сравнению с алгоритмом ABAA\M даёт выигрыш в 1,3 раза по времени.

Рис. 4

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

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

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

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

Транслятор базы знаний компилирует вводимый пользователем текст, удовлетворяющий определённым правилам, в объектную модель множества дизъюнктов. Библиотека ЛП1П предоставляет объектную модель наиболее используемых объектов ЛП1П – дизъюнкт, множество дизъюнктов, конъюнкт, множество конъюнктов, литера, аргумент, подстановка, резолюция, и др.

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

Решатель выполняет алгоритм абдуктивного вывода. Помимо реализации абдуктивного вывода с использованием систем поддержки истинности на основе предположений (алгоритм ABAA\M\H), разработана реализация абдуктивного вывода с использованием первичных импликат (алгоритма ImpAA\M\H). В зависимости от предпочтения пользователей, решатель использует тот или иной алгоритм.

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

Рис. 5

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

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

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

2)  Выполнено исследование и анализ систем поддержки истинности. Особое внимание уделено системам поддержки истинности, основанным на предположениях, ключевым достоинством которых является сохранение выводов, что приводит к кэшированию промежуточных результатов, в результате чего нет необходимости в повторных вычислениях. Благодаря своим характеристикам, система поддержки истинности, основанная на предположениях (ATMS), выбрана в качестве основы для построения абдуктивного алгоритма.

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

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

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

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

Список работ, опубликованных по теме диссертации

1.  Н., Хотимчук К.Ю. Методы абдуктивного вывода в задачах планирования работы в сложных объектах // Известия РАН. Теория и системы управления, 2010, №5, с. 95-113.

2.  Н., Хотимчук К.Ю. Абдуктивный вывод versus дедукция // Программные продукты и системы, 2010, №4, с. 106-110.

3.  Вагин В.Н., Хотимчук К.Ю. Абдукция в задачах планирования работ в сложных объектах // Искусственный интеллект и принятие решений. – М.: Ленанд, 2011. – Т.1 с.3-13.

4.  Ю. Исследование методов нахождения минимальных абдуктивных объяснений // Радиоэлектроника, Электротехника и Энергетика. Тринадцатая Междунар. Науч.-техн. Конф. Студентов и аспирантов: Тез. Докл. В 3 т. Т. I. М.: Издательский дом МЭИ, 2007. – 508с. с. 378 – 379.

5.  Ю. Исследование и разработка методов нахождения минимальных абдуктивных объяснений // Технологии Microsoft в теории и практике программирования: труды IV Всероссийской конференции студентов, аспирантов и молодых учёных. Центральный регион. Москва, 2-3 апреля 2007 г. – М.: Вузовская книга, 2007. – 211 с. с. 127 – 128.

6.  Хотимчук К.Ю. Применение первичных импликат для нахождения минимальных абдуктивных объяснений // Труды международной научно-технической конференции “Информационные средства и технологии”. 16-18 октября 2007 г., в 3-х т. Т 3. – М.: МЭИ, 2007. – 220 с. с. 65 – 68.

7.  , Нахождение минимальных абдуктивных объяснений с помощью первичных импликат // Тр. 11й национальной конференции по искусственному интеллекту с международным участием (КИИ-2008. г. Дубна, Россия). 2008. Т. 2. P. 345-355.

8.  Хотимчук К.Ю. Решение задачи планирования работы сложных технических объектов с помощью алгоритмов абдуктивного вывода // Повышение эффективности электрического хозяйства потребителей в условиях ресурсных ограничений. Материалы Всероссийской научно-практической конференции с международным участием (Москва, 16 – 20 ноября 2009 г.) / Под общ. Ред. и . В 2-ч т. М.: Технетика, 2009. Том II – 258 с. с. 174 – 176.

9.  Хотимчук К.Ю. Применение алгоритмов абдуктивного вывода в решении задачи планирования работы сложных технических объектов // Радиоэлектроника, Электротехника и Энергетика. Шестнадцатая Междунар. Науч.-техн. Конф. Студентов и аспирантов: Тез. Докл. В 3 т. Т. I. М.: Издательский дом МЭИ, 2010. – 492с. с. 386 – 387.

10.  Вагин В.Н., Хотимчук К.Ю. Алгоритм абдуктивного вывода с использованием систем поддержки истинности на основе предположений // Двенадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2010 (20-24 сентября 2010 г., г. Тверь, Россия): Труды конференции. Т. 1. - М.: Физматлит, 2010. - 392 с. с. 73 – 82.

11.  Хотимчук К.Ю. Абдуктивный вывод с использованием систем поддержки истинности на основе предположений // Труды XVI Международной научно-технической конференции "Информационные средства и технологии". 19 – 21 октября 2010г., Москва. В 3 томах. Т.2. М.:Издательский дом МЭИ. 359 с. с. 242 – 249.

12.  Хотимчук К.Ю. Алгоритм абдуктивного вывода для решения задачи планирования работы сложных технических объектов // Радиоэлектроника, Электротехника и Энергетика. Семнадцатая Междунар. Науч.-техн. Конф. Студентов и аспирантов: Тез. Докл. В 3 т. Т. I. М.: Издательский дом МЭИ, 2011. – 488с. с. 385 – 386.

Свидетельство о государственной регистрации программы для ЭВМ “Fast Abductive Solver” № 000 (27 июня 2010 г.).