автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование возможности применения Constraint - Пролога с вероятностью для решения прикладных задач

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ (ЛЭТИ)

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

Саввин Константин Олегович

ИССЛЕДОВАНИЕ ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ СОШТКАШТ-ПРОЛОГА С ВЕРОЯТНОСТЬЮ ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ

Специальность: 05.13.11 - Математическое и программное

обеспечение вычислительных машин, комплексов, систем и сетей

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

Научный руководитель -кандидат технических наук, доцент В.Б. Вальковский

Санкт-Петербург - 1999

СОДЕРЖАНИЕ

ВВЕДЕНИЕ,, .................................................... 5

1. ОБЗОР ПРОБЛЕМАТИКИ. ..................................... 10

1.1. Constraint Logic Programming (CLP) . ................. 10

1.1.1. Преимущества CLP. ................................ 13

1.1.2. Механизм логического вывода в CLP - языках. ..... 17

1.1.3. CLP-системы. ..................................... 19

1.1.4. Области применения. .............................. 19

1.2. Обработка недостоверной информации. ................. 22

1.2.1. Неопределенность в искусственном интеллекте. .... 22

1.2.2. Вероятностная логика. ............................ 26

1.2.3. Вероятностное логическое программирование. ...... 31

1.2.4. Задача абдукции. ................................. 39

1.3. Логистика. ........................................... 42

1.4. Общие выводы. Задачи диссертационной работы. ........ 47

2. ВЕРОЯТНОСТНЫЙ ВЫВОД В СРЕДЕ CLP. ........................ 51

2.1. Использование метода статистических испытаний. ...... 51

2.1.1. Базовые возможности. ............................. 51

2.1.2. Арифметизация логических формул.................. 56

2.1.3. Логические зависимости ........................... 57

2.1.4. Условные вероятности............................. 58

2.1.5. Случайные параметры, вероятностные распределения 60

2.2. Вопросы эффективности. Формула успеха. .............. 61

2.2.1. Аппроксимационная логическая формула успеха. .... 61

2.2.2. Constraint формула успеха ........................ 6 6

2.2.3. Использование формулы успеха..................... 70

2.3. Выв оды. .............................................. 75

3. АБДУКТИВНЫЙ ВЫВОД В СРЕДЕ CLP. .......................... 77

3.1. Задача абдукции для значений. ....................... 7 8

3.1.1. Оценка значения вероятности недостоверного

предложения при известной вероятности цели. ..... 7 8

3.1.2. Оценка значения стохастического параметра. ...... 81

3.2. Задача абдукции для зависимостей .................... 86

3.2.1. Эмпирическая зависимость ......................... 87

3.2.2. Аналитическая зависимость в вероятностных программах....................................... 8 8

3.3 о Использование результатов решения задачи абдукции. .. 94 3.4. Выв оды. .............................................. 97

4. РАСШИРЕНИЕ CLP(R) ДЛЯ РАБОТЫ С ВЕРОЯТНОСТЬЮ. ........... 98

4.1. Общее описание и технология применения. ............. 98

4.2. Список предикатов...................................102

4.2.1. Описательные предикаты. ......................... 102

4.2.2. Генерирующие предикаты. ......................... 107

4.2.3. Стартовые предикаты ............................. 10 9

4.2.4. Сервисные предикаты.............................110

4.3. Выв оды. ............................................. 113

5. РЕШЕНИЕ ПРИКЛАДНЫХ ЗАДАЧ. ..............................114

5.1. Архитектура прикладных систем ...................... 114

5.2. Прототипное приложение..............................118

5.2.1. Классическая постановка задачи сетевого планирования.................................... 118

5.2.2. Вероятностное сетевое планирование. ............ 121

5.3. Применение предложенного подхода в задачах логистики. .......................................... 145

5.4. Выводы. .............................................150

ЗАКЛЮЧЕНИЕ ................................................. 152

СПИСОК ЛИТЕРАТУРЫ. ......................................... 15 б

ПРИЛОЖЕНИЕ 1. CLP-СИСТЕМЫ. ................................164

ПРИЛОЖЕНИЕ 2. ОПРЕДЕЛЕНИЕ МОДЕЛИ. ЗАДАЧА ВЫЧИСЛЕНИЯ

ВЕРОЯТНОСТИ СЛЕДСТВИЯ....................................168

ПРИЛОЖЕНИЕ 3. КАНОНИЧЕСКАЯ МОДЕЛЬ В ВЕРОЯТНОСТНОЙ ЛОГИКЕ. 170 ПРИЛОЖЕНИЕ 4. ТЕХНОЛОГИЯ РЕОРГАНИЗАЦИИ ПРОИЗВОДСТВА

ТЕХНОЛОГИЧЕСКОГО УНИВЕРСИТЕТА ЭЙДХОВЕНА. ................ 172

ПРИЛОЖЕНИЕ 5. РЕВЕРСИВНАЯ ЛОГИСТИКА. ..................... 175

ПРИЛОЖЕНИЕ 6. ЗАВИСИМОСТЬ ВЕРОЯТНОСТИ ЦЕЛИ ОТ

ВЕРОЯТНОСТЕЙ НЕДОСТОВЕРНЫХ ПРЕДЛОЖЕНИЙ. ................. 178

ВВЕДЕНИЕ.

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

Одной из характерных особенностей таких задач является то, что они так или иначе связаны с перебором различных вариантов, выбором допустимых или поиском оптимальных в некотором смысле решений. Языки и инструментальные системы, разработанные в рамках нового направления в логическом программировании Constraint Logic Programming [1] [2] [3] (далее по тексту CLP) , появившегося в конце 80-х, начале 90-х гг., отлично зарекомендовали себя при решении задач такого типа. Основная идея CLP - заменить механизм унификации логических переменных механизмом проверки совместности и разрешения ограничений (constraint solving and consistency checking) на некоторой области определения переменных логической программы. При этом CLP-системы сохранили все положительные свойства традиционного логического

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

специализированные оптимизационные алгоритмы [4][5].

- б -

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

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

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

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

Целью данной работы является разработка и реализация эффективных и удобных в использовании методов представления и обработки недостоверной информации, интегрированных в среду CLP, ориентированных на использование в задачах логистики. В частности, в работе предлагаются методы для реализации логического вывода с вероятностью. Рассматриваются вопросы повышения эффективности механизма вывода. Серьезное внимание уделено вопросам абдуктивного вывода (обратная задача в обработке недостоверной информации). Описывается программный инструментарий, реализующий разработанные методы в системе CLP(R) [б]. Кроме того, в работе предлагается технология создания прикладных систем с использованием разработанного подхода к представлению и обработке недостоверной информации, иллюстрируемая на примере прототипного приложения, а также обсуждаются возможные применения этого подхода в сфере логистики.

Для представления неопределенности выбрана вероятностная модель как наиболее близко соответствующая типу неопределенности, характерному для рассматриваемых задач. Кроме того, немаловажно, что модель имеет хорошее теоретическое обоснование. Базой для предложенного в работе подхода являются теория вероятностной логики, предложенная N.Nilson'oM в 1984 году [7] и теория вероятностного логического программирования [8] [9] .

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

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

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

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

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

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

Основные положения и результаты диссертационной работы опубликованы в 8 научных работах, в том числе в статьях [10] [11] [12] [13] [14] „ Результаты докладывались и обсуждались на научно-технических конференциях СПбГЭТУ в 1995-1998 гг.; на международной конференции: "Practical Application of Constraint Technology" (PACT'96) UK, London, 1996/ на международной конференции "The 2nd Online World Conference on Soft Computing in Engineering Design and Manufacturing" (WSC2), 1997; на международной конференции "The 3rd Online World Conference on Soft Computing in Engineering Design and Manufacturing" (WSC3), 1998; на ежегодных семинарах международного проекта INTAS-93-1702 (INTAS-93-1702EXT) "Efficient Symbolic Computing" в 1995-1998.

Работа выполнялась в рамках международного

исследовательского проекта INTAS-93-1702 "Efficient Symbolic Computing" 1995-1996, INTAS-93-1702EXT 1997-1998. Результаты работы были использованы в рамках НИР "Разработка интеллектуальных систем управления и систем транспортной логистики", выполняемой по заказу комитета по транспорту администрации СПб. Разработанный инструментарий был использован в учебном процессе при проведении лабораторных работ по курсу "Логическое программирование" и "Пролог в системах искусственного интеллекта".

1 ОБЗОР ПРОБЛЕМАТИКИ.

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

диссертационной работе.

1.1. Constraint Logic Programming (CLP).

Как уже отмечалось во введении, задачи логистики в значительной степени связаны с комбинаторикой, оптимизацией, планированием и т.п. Для решения подобных задач может использоваться целый спектр различных подходов. Это всевозможные методы и алгоритмы теории оптимизации [15] [16] и исследования операций [17] [18], рандомизированные алгоритмы [19], генетические алгоритмы [20] [21] и др. Большинство этих методов позволяют успешно решать поставленные задачи, но не лишены и определенных недостатков. Как правило, использование таких методов и алгоритмов требует значительных дополнительных усилий при формализации и постановке задачи в процессе перехода от специфической предметной области к сухому языку математической теории. Кроме того, программная

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

Несколько особняком в ряду способов решения подобных задач стоят средства логического программирования (ЛП) и, в частности, язык Пролог. Большинство комбинаторных

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

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

Универсальным методом, используемым при разработке переборных алгоритмов на Прологе, был метод "генерация-проверка" [22] . Суть метода состоит в выделении в программе двух частей, одна из которых предназначена для генерации вариантов решений - кандидатов, а другая для их проверки и отбора тех вариантов, которые действительно являются решениями задачи. Прямое следование данной схеме, очевидно, приводит к полному перебору вариантов, что неприемлемо для большинства задач реальной размерности. Оптимизация такого рода алгоритмов заключалась в попытках "погрузить" проверяющую часть как можно более глубоко в генерирующую. В пределе эти две части должны переплетаться так, чтобы программа сразу генерировала только правильные решения. Однако такого рода "оптимизация" часто требовала значительных дополнительных усилий, приводила к громоздким программам и потере гибкости. Таким образом, достижение приемлемого для

больших размерностей уровня производительности требовало неадекватных затрат и сводило на нет основные преимущества ЛП перед процедурными языками. В сочетании с неудобствами обработки численной информации это существенно ограничило применение Пролога в задачах рассматриваемого типа: он мог эффективно использоваться только в простых задачах с ограниченной размерностью (см. например [23]) и как средство быстрого прототипирования.

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

Основная идея CLP - заменить механизм унификации логических переменных механизмом проверки совместности и разрешения ограничений (constraint solving and consistency checking) на некоторой области определения переменных логической программы. Под этим подразумевается