Исследование возможности применения Constraint - Пролога с вероятностью для решения прикладных задач тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Саввин, Константин Олегович

• Саввин, Константин Олегович
• кандидат технических наук
• 1999

Оглавление диссертации кандидат технических наук Саввин, Константин Олегович

ВВЕДЕНИЕ,,

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

1.1. Constraint Logic Programming (CLP)

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

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

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Исследование возможности применения Constraint - Пролога с вероятностью для решения прикладных задач»

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

Одной из характерных особенностей таких задач является то, что они так или иначе связаны с перебором различных вариантов, выбором допустимых или поиском оптимальных в некотором смысле решений. Языки и инструментальные системы, разработанные в рамках нового направления в логическом программировании 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-системы и области применения. Второй раздел посвящен теме обработки неопределенности. Дается общая характеристика проблемы и моделей представления неопределенности, приводятся аргументы в пользу выбора в данной работе вероятностной интерпретации неопределенности. Излагаются основные теоретические положения вероятностной логики и вероятностного логического программирования. Приведены основные трактовки задачи абдукции. В заключении представлены общие выводы и сформулированы основные задачи, поставленные в диссертационной работе.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Саввин, Константин Олегович

5.4. Выводы.

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

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

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

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

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

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

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

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

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

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

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

Научные результаты:

1. Предложен подход для обработки недостоверной информации (в вероятностной интерпретации) в среде CLP, ориентированный на решение практических задач.

2. Разработаны методы повышения эффективности логического вывода с вероятностью: предложен метод оптимизации вероятностного вывода в CLPпрограммах на основе аппроксимационной формулы успеха ® предложен способ построения аппроксимационной формулы успеха для реальных программ путем синтаксического анализа программы ® преложен способ построения constraint формулы успеха на основе setof-технологии ® предложены методы оптимизации вероятностного вывода в CLP-программах на основе constraint формулы успеха

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

Практические результаты:

1 о Предложена методика создания прикладных систем для решения практических задач в среде CLP с вероятностью.

2. Разработан инструментарий, обеспечивающий обработку недостоверной информации (в вероятностной интерпретации) в среде CLP(R).

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

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

Список литературы диссертационного исследования кандидат технических наук Саввин, Константин Олегович, 1999 год

1. P„Van Hentenryck. Constraint Satisfaction in Logic Programming, MIT Press, Cambridge, MA„ 1989.

2. J.Jaffar, J.M.Maher. Constraint Logic Programming: A survey. J. Logic Programming, 1994, No. 5.

3. T.Fruhwirth, A.Herold, V.Kuchenhoff, et al. Constraint Logic Programming: An Informal Introduction. Tech. Report ECRC-93-5, 1993. Munich, Germany.

4. M.Dincbas, H.Simonis, P.Van Hentenryck. Solving large scale combinatorial problem in logic programming. The Journal on Logic Programming, 1990, 8, pp. 75-93.

5. A.Aggoun, N.Beldiceanu. Extending CHIP in order to solve Complex Scheduling and Placement Problems. Math. Comput. Modelling 17(7), 1993, pp. 57-73.

6. J.Jaffar, S.Michaylov, P.J.Stuckey, R.H.C.Yap. The CLP(R) Language and System. ACM Transactions on Programming Languages and Systems, 1992, Vol. 14, No. 3, pp. 339-395.

7. N.J.Nilsson. Probabilistic Logic. Artificial Intelligence 18 (1), 1986. pp. 71-87 .

8. E.Dantsin. Probabilistic Logic Programming and their Semantic. In: Voronkov A (eds.) Lecture Notes in Computer Science. 1992, Vol. 592, Springer-Verlag, London, pp. 152164 .

9. Е.Я. Данцин. Вероятностная логика, Технический отчет, ЛОМИ, 19 92.10 . В.Б.Вальковский, К.О.Саввин. Логический вывод свероятностью в Constraint-Прологе, Известия СПбГЭТУ, Вып. 489. 1995. СПбГЭТУ, С.-Петербург. С. 37-49.

10. V.B.Valkovsky, M.В.Gerasimov, K.O.Savvin. CLP with

11. Probability in Scheduling Problems. In: 1996 Proceedings of the Second International Conference on the Practical- 157

12. Application of Constraint Technology. 1996. London, UK, pp. 299-315.12 . К.0.Саввин. Расширение CLP для работы с вероятностнойинформацией. Известия СПбГЭТУ, Вып. 515. 1997. СПбГЭТУ, С.-Петербург.13 . V.В.Valkovsky, K.O.Savvin, М.В.Gerasimov. Handling

13. Probabilistic Uncertainty in Constraint Logic Programming. In: Chawdhry P K, Roy R, Pant R К (eds), Soft Computing in Engineering Design and Manufacturing, Springer-Verlag London Ltd., UK. 1997.14 . V.В.Valkovsky, K.O.Savvin, M.В.Gerasimov. Abduction

14. Problem in Probabilistic Constraint Logic Programming. In: R.Roy, T.Furuhashi, P.K.Chawdhry (eds), Advances in Soft Computing Engineering Design and Manufacturing, Springer-Verlag London Ltd., UK. 1998.15 . С.H.Papadimitriou, K.Steiglitz. Combinatorial

15. Optimization: Algorithms and Complexity, Prentice Hall, 1982

16. R.M.Karp. An Introduction to Randomized Algorithms. TR-90-024. University of California. International Computer Science University. Berkeley. California. 1990.

17. J.Grefenstette. Genetics Algorithms. IEEE Expert. October, 1993, pp. 5-8.

18. R.H.C.Yap. The CLP(R) programmer's manual. 1992, IBM Research Center. 26. J.Cohen. Constraint Logic Programming Languages.

19. WWW страница http://www.cosytec.com, COSYTEC. Complex Systems Technologies.

20. System written in CHIP. 2-nd Conference on Practical Application of Prolog, London, 1994.34 . H.Simonis, T.Cornelissens. Modeling Producer/Consumer

21. G.Shafer. A mathematical theory of evidence. Princeton University Press, Princeton, NJ. 1976.

22. C.Elkan. The paradoxical success of Fuzzy Logic. In: A Fuzzy logic symposium, IEEE Expert Intelligent systems & their applications. Aug. 1994.

23. R.Fagin, J.Y.Halpern, Uncertainty, belif and probability. Comput. Intell, 7 (191), pp 160-173.

24. R.Fagin, J.Y.Halpern, N.Megiddo, A logic reasoning about probabilistic. In: Proceedings of the 3-rd IEEE Symp. on Logic in Computer Science, 1988. pp 277-291.

25. M.H.van Emden, R.A.Kowalski. The semantics of predicate logic as a programming language. Journal ACM, 23(4), 1976, pp.733-742.45 . А.С.Kakas, R.A.Kowalski, F.Toni. Abductive Logic

26. Programming. Journal of Logic and Computations, Vol. 2, No.6, pp. 719-770.46 . P.A.Flatch. Abduction and Induction: Syllogistic and1.ferential Perspectives. Internet. INFOLAB. Tilburg University.47„H.Ade, M.Denecker. AILP: Abductive Inductive Logic

27. Programming. Internet. 48 . M.Pagnucco, N.Foo. The Relationship between Abduction and Changes in Belief States, Proceedings of ICLP'93 PostConference Workshop on Abductive Reasoning. Budapest, Hungary, June 1993.

28. M.Pagnucco, A.Nayak, N.Foo. Abductive Reasoning, Bbelief Expansion and Nonmonotomic Consequence, Proceedings of ICLP'95 Workshop on Abduction in Deductive Databases and Knowledge Based Systems. Shonan Village Center, Japan, June 1995.

29. WWW страница "http://www.clml.org". Council of Logistics Management.

30. WWW страница "http://www.dartgc.com". D.A.R.T. Logistics. 52 . K.Schwichtenberg Logistics Outsourcing: A Quick Quiz.

31. Competitive Advantage. Logistics Quarterly, No.2, 1997.- 161

32. Canadian Association of Logistics Management, http ://www.calm.org)

33. WWW страница: "http:/www.tue.nl/ivo/lbs". Eindhoven University of Technology.

34. M.Jenkins. Outsourcing The Invisible Natural Resource. International Warehouse Logistics Associations. WWW страница "http ://www.iwla.com".

35. Warehouse Logistics Associations. WWW страница "http ://www.iwla.com".

36. D.J.Bowersox, J.T.Mentzer, T.W.Speh. Logistics Leverage. Journal of Business Strategies, Vol.12, No.l, 1995.

37. R.Lennox. Decision Support Systems for Supply Chain Management. Logistics Quarterly, No.3, 1997. (Canadian Association of Logistics Management, http://www.calm.org)62 . E.Dantsin, V.Valkovsky. Abductive Reasoning in

38. Probabilistic Prolog. Report. Workshop of INTAS-93-1702 project (Efficient Symbolic Computing), International Euler Mathematical Institute, 1996. St.Petersburg, Russia. 63. Коршунов Ю.М. Математические основы кибернетики. M.,

39. Р.Гантер. Методы управления проектированием программного обеспечения, М., Мир, 1981.

40. D.Buede. Decision Analysis Software Survey: Aiding Insight IV. OR/MS Today. 1998. (http://lionhrtpub.com/software-surveys.shtml)68 . M.Jenkins. Technology's Logistics. Report. International

41. Warehouse Logistics Associations. WWW страница "http://www.iwla.com".69 . R.Bisdorff, R.Gabriel. Industrial Linear Optimization

42. M.Dincbas, P.Van Hentenryck, H.Simonis, et al. The Constraint Logic Programming Language CHIP. Proceedings of 2nd Int. Conf. On Fifth Generation Computer Systems, 1988, pp. 249-264.

43. P.Voda. The Constraint Language Trilogy: Semantics and Computations. Technical Report. Complete Logic Systems. 1988 .

44. A.Aiba, K.Sakai, Y.Sato, et al. Constraint Logic Programming Language CAL. Proceedings of Int. Conf. on Fifth generation Computer Systems, 1988, pp. 263-276.

45. W.Older, F.Benhamou. Programming in CLP(BNR) . 1st Workshop on Principles and Practice of Constraint Programming. 1993 .

46. R.Guintini. Redesign it + Produce it + Rent it + Support it + Renew it + Reuse it = Reverse Logistics Reinventing the Manufacturer's Business Model. Report. American Production and Inventory Control Society. 1997. (http://www.apics.org)