Об эффективных алгоритмах для задачи CSP и их программной реализации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Скворцов, Евгений Сергеевич

• Скворцов, Евгений Сергеевич
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Скворцов, Евгений Сергеевич

Введение

1 Общее описание проблематики.

2 Проблемы, решаемые в диссертации

2.1 Используемые подходы.

2.2 Амальгамы подклассов CSP.

2.3 Эффективность алгоритма Локальный Поиск

2.4 Алгоритм VEGAS.

1 Амальгамы подклассов CSP

1.1 Основные определения теории клонов и теории задачи CSP

1.1.1 Задача CSP.

1.1.2 Клоны.

1.1.3 Амальгамы клонов

1.2 Строение клона функций, сохраняющих амальгаму.

1.2.1 Случай дизъюнктных множеств.

1.2.2 Общий случай.

1.3 Склеивание двух клонов.

1.4 Критерий полиномиальности амальгамы.

1.4.1 О мощности множества С

1.4.2 Случай монолитности одного из клонов.

1.4.3 Канонический вид задачи.

2 Эффективность Локального Поиска

2.1 Основные определения.

2.1.1 Задача Выполнимость и Локальный Поиск

2.1.2 Теорема Вормальда.

2.2 Локальный Поиск за Один Просмотр.

2.2.1 Модель.

2.3 Локальный Поиск.

2.3.1 Модель.

2.3.2 Эксперименты.

3 Алгоритм VEGAS

3.1 Основные определения.

3.1.1 Взвешенная Максимальная Выполнимость.

3.1.2 Генетические алгоритмы.

3.2 Описание алгоритма VEGAS.

3.2.1 Эволюция среды обитания.

3.2.2 Моделирование социальной структуры популяции

3.2.3 Алгоритм TabuSearch.

3.3 Результаты экспериментов.

3.3.1 Сравнение эффективности VEGAS и GASAT

3.3.2 Исследование влияния социальной структуры популяции на эффективность вычисления.

Введение диссертации (часть автореферата) на тему «Об эффективных алгоритмах для задачи CSP и их программной реализации»

1 Общее описание проблематики

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

Мы будем использовать стандартные определения комбинаторной задачи, класса задач NP, сведения, полиномиальности и NP-полноты задачи, см. например [1, 56]. Данная работа относится к исследованию комбинаторной задачи CSP (От английского 'Constraint Satisfaction Problem', в немногочисленной русскоязычной литературе встречается также название 'Обобщенная выполнимость'). Цель данного направления — разработать эффективные универсальные алгоритмы для задач из класса NP. Задача CSP является лишь одной из многих известных NP-полных задач, однако в последнее десятилетие стало ясно, что она занимает особое место. Сведение задачи к NP-полной очень часто оказывается громоздким и искусственным. Преимущество задачи CSP состоит в том, что большинство комбинаторных задач может быть представлено в виде CSP просто и естественно. Многие комбинаторные задачи могут быть естественным образом охарактеризованы как подклассы задачи CSP. Теория задачи CSP находит свое применение в таких областях как теория реляционных баз данных [43, 65], временная и пространственная логика [62], распознавание зрительных образов [52], автоматическое доказательство теорем [16], техническое проектирование [55], анализ языков программирования [54] и естественных языков [4], биоинформатика [45] и многих других.

Формулируется задача CSP следующим образом. Пусть даны множество переменных V и множество их возможных значений D. Ограничением называется пара, состоящая из вектора переменных (vi,., v^) и отношения р С Dk. Говорят, что функция ф : V —► D, ставящая в соответствие переменным их значения, удовлетворяет ограничению ((г^,., г^), р), если вектор (c/>(vi),., ф(ьк)) содержится в отношении р. В конкретной задаче CSP даны множества V и D, а также некоторое множество ограничений С. Требуется указать значения переменных (т. е. выбрать функцию ф : V —> D) так, чтобы удовлетворялись все ограничения из С.

Впервые общая задача CSP была введена Монтанари в 1974 г. [52] при решении одной из задач машинного зрения — распознавания формы многогранников по их двумерному изображению. В последующие годы этот формализм был активно использован для моделирования прикладных задач, а затем и разработки универсальных алгоритмов для их решения. В настоящее время существуют специальные декларативные языки программирования: ECLiPSc[5], Oz[59], 2LP[50], СН1Р[30] и Newton[31], в которых для решения задачи достаточно записать ее в виде CSP, существуют библиотеки с подобной функциональностью для С++ (например ILOG[58]), расширениями, позволяющими решать задачу CSP, снабжено большинство современных версий Prolog[53].

Частным случаем задачи CSP, в котором множество значений переменных двухэлементно, а разрешенные ограничения — дизъюнкции ли-тералов(клозы), является задача ВЫПОЛНИМОСТЬ, одна из первых задач, NP-полнота которых была доказана. Задача ВЫПОЛНИМОСТЬ представляет самостоятельный интерес, так как формулируется она проще, чем CSP, и в то же время сведение задачи CSP к задаче ВЫПОЛНИМОСТЬ не составляет труда.

Сама задача Выполнимость является в настоящее время объектом активного исследования. Ей посвящена ежегодная конференция SAT (это название является сокращением от SATISFIABILITY — английского названия задачи ВЫПОЛНИМОСТЬ), проводящаяся с 1996-го года. С 2005-го года выпускается журнал JSAT. Важное место в исследовании задачи Выполнимость занимает разработка реально работающих программ-решателей. При конференции SAT регулярно проходит соревнование таких программ, в котором принимают участие десятки программных продуктов, созданных учеными со всего мира. Прогресс, достигнуты!! в разработке алгоритмов для практических задач, огромен: многие задачи, еще 10 лет назад считавшиеся практически неразрешимыми, современными программами могут быть решены за доли секунды.

Возможный путь решения задачи CSP — это сведение ее к задаче ВЫПОЛНИМОСТЬ и использование эффективных эвристических алгоритмов. Однако, богатый язык общей задачи CSP позволяет сохранить при моделировании структуру исходной задачи, что дает ряд преимуществ. Во-первых, как было отмечено выше, многие задачи могут быть естественным образом охарактеризованы как ограниченные задачи CSP. Например, fc-раскраска графа — это в точности задача CSP на fc-элементном множестве, в которой в качестве отношения ограничения используется только неравенство. Во-вторых, большая структурированность задачи позволяет перенести в теорию CSP и обобщить алгоритмы, разработанные для других комбинаторных задач. Кроме того, язык задачи CSP оказывается проще для понимания, поэтому запись задачи в виде CSP на практике оказывается предпочтительнее кодирования в виде задачи ВЫПОЛНИМОСТЬ с точки зрения взаимодействия с заказчиком при моделировании предметной области.

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

Список литературы диссертационного исследования кандидат физико-математических наук Скворцов, Евгений Сергеевич, 2008 год

1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи// М.: Мир, 1982.

2. Левин Л. А. Универсальные задачи перебора// Проблемы передачи информации. 1973. Т.9, №3. С. 115-116.

3. Achlioptas D. Lower bounds for random 3-SAT via differential equations/ / Theor. Comput. Sci. 2001. Vol.265. №1-2. P.159-185.

4. Allen J. Natural Language Understanding// Benjamin Cummings, 1994.

5. Apt K., Wallace M. Constraint Logic Programming using Eclipse// Cambridge University Press, 2007.

6. Asahiro Y., Iwama K., Miyano E. Random generation of test instances with controlled attributes// DIMACS Series on Discrete Mathematics and Theoretical Computer Science. 1996. Vol.26. P.377-393.

7. Asano Т., Williamson. D. Improved approximation algorithms for MAX SAT// J. Algorithms. 2002. Vol.42.№l. P.173-202.

8. Bertoni A., Carpentieri M., Campadelli P., Grossi G. A genetic model: Analysis and application to MAX-SAT// Evolutionary Computation. 2000. Vol.8. P.291-310.

9. Bramelette M., Bouchard E. Handbook of Genetic Algorithms // Van Nostrand Reinhold, New York, 1991.

10. Bulatov A., Jeavons P., Krokhin A. Classifying the complexity of constraints using finite algebras// SIAM J. Comput. 2005. Vol.34. №3 P.720-742.

11. Bulatov A., Krokhin A., Jeavons P. Constraint satisfaction problems and finite algebras// Proceedings of 27th International Colloquium on Automata, Languages and Programming (ICALP'00). LNCS Vol. 1853. Springer-Verlag, 2000. P.272-282.

12. Cohen D., Jeavons P., Gault R. New tractable classes from old// Principles and Practice of Constraint Programming CP2000. LNCS Vol. 1894. P. 160-171.

13. Cohen D., Jeavons P., Koubarakis M. Building tractable disjunctive constraints// Journal of the ACM. 2000. Vol.47. P. 826-853.

14. Cohen D.A. Jeavons P., Gyssens M. A structural decomposition for hy-■ pergraphs// Contemporary Mathematics. 1994. Vol.178. P.161-177.

15. Cook S. The complexity of theorem-proving procedures// The 3rd IEEE Symp. on the Foundations of Computer Science. 1971. P.151-158.

16. Dechter R., Dechter A. Structure-driven algorithms for truth maintenance// Artificial Intelligence. 1996. Vol. 82. №1-2. P. 1-20.

17. Dechter R., Pearl J. Tree clustering for constraint networks// Artificial Intelligence. 1989. Vol.38. P.353-366.

18. Eiben A.E., Ven Der Hauw J.K., Van Hemert J.I. Graph coloring with adaptive evolutionary algorithms// Journal of Heuristics. 1998. Vol.4.№l. P.25-46.

19. Feder T., Vardi M. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory// SIAM Journal of Computing. 1998. Vol.28. P.57-104.

20. Fleurent. J., Ferland J. Genetic algorithms and hybrids for graph coloring// Annals of Operations Research. 1996. Vol. 63. P.437-461.

21. Freuder E. Complexity of k-tree structured constraint satisfaction problems/ / The 8th National Conference on Artificial Intelligence AAAI-90. 1990. P. 4-9.

22. Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning// Addison-Wesley, 1989.

23. Gottlob G., Leone L., Scarcello F. A comparison of structural CSP decomposition methods// Artificial Intelligence. 2000. Vol. 124. №. 2. P.243-282.

24. Grohe M., Schwentick T., Segoufin L. When is the evaluation of conjunctive queries tractable?// The 33rd Annual ACM Simposium on Theory of Computing. ACM Press, 2001. P.657-666.

25. Gu. J. Efficient local search for very large-scale satisfiability problem// ACM SIGART Bulletin. 1992. Vol. 3. № 1. P. 8-12.

26. Han H., Xiaowei Y., Zhifeng H. Chunguo W., Yanchun L., Xi Z. Hybrid chromosome genetic algorithm for generalized traveling salesman problems// Advances in Natural Computation. 2005. LNCS Vol. 3612. P. 137-140.

27. Hansen P., Jaumard. B. Algorithms for the maximum satisfiability problem// Computing. 1990. Vol.44. P.279-303.

28. Hao J., Dorne R. A new population-based method for satisfiability problems// The 11th European Conf. on Artificial Intelligence. John Wiley & Sons, 1994. P. 135-139.

29. Hao J., Lardeux F., Saubion F. Evolutionary computing for the satisfiability problem// Applications of Evolutionary Computing. 2003. LNCS Vol.2611. P.258-267.

30. Hentenryck V. The CLP Language CHIP: Constraint Solving and Applications/ / Proceedings of the IEEE Computer Society InternationalConference. 1991. P. 382-387.'

31. Hentenryck V., Michel L. Newton: Constraint Programming over Nonlinear Real Constraints// Science of Computer Programming. 1997. Vol. 30. P. 83-118.

32. Hirsch E., Kojevnikov A. UnitWalk: A new SAT solver that uses local search guided by unit clause elimination// Annals of Mathematics and Artificial Intelligence. 2001. Vol. 43, №1-4. P. 91-111.

33. Hirsch E. A. Worst-case study of local search for Max-k-Sat// Discrete Appl. Math. 2003. Vol. 130. №2. P.173-184.

34. Holland J. Adaptation in Natural and Artificial Systems// The University of Michigan Press, 1975.

35. Hoos H. Satisfiability Library, http://www.satlib.org.

36. Hoos H., Stutzle T. Stochastic Local Search, foundations and applications. Elsevier, 2005.

37. Jeavons P. On the algebraic structure of combinatorial problems// Theoretical Computer Science. 1998. Vol.200. P. 185-204.

38. Jeavons P., Cohen D., Cooper M. Constraints, consistency and closure// Artificial Intelligence. 1998. Vol.101. №1-2. P.251-265.

39. Jeavons P., Cohen D., Gyssens M. A unifying framework for tractable constraints// Proceedings 1st International Conference on Constraint Programming—CP'95. Springer-Verlag, 1995. LNCS Vol.976. P. 276291.

40. Jeavons P., Cohen D., Gyssens M. Closure properties of constraints// Journal of the ACM. 1997. Vol.44. P.527-548.

41. Jong K. D., Spears W. Using genetic algorithms to solve np-complete problems/ / Proceedings of the International Conference on Genetic Algorithms. 1989. P. 124-132.

42. Kolaitis P., Vardi M. Conjunctive-query containment and, constraint satisfaction// J. Comput. Syst. Sci. 2000. Vol. 61. №.2. P.302-332.

43. Koutsoupias E., Papadimitriou C. H. On the greedy algorithm for satisfiability// Information Processing Letters. 1992. Vol.43, №1. P.53-55.

44. Krippahl L., Barahona P. Applying constraint programming to protein structure determination// Proceedings 5th International Conference on Constraint Programming. Springer-Verlag, 1999. LNCS Vol. 1713. P. 289-302.

45. Lardeux F., Saubion F., Hao J.-K. A hybrid genetic algorithm for the satisfiability problem// The 1st Int. Workshop on Heuristics. 2002. P. 6977.

46. Lardeux F., Saubion F., Hao J.K. A chessboard coloring problem for SAT solver// Technical report. LERIA, Université d'Angers, 2003.

47. Li C., Jurkowiak B., Purdom P. Integrating symmetry breaking into a dll procedure// Fifth International Symposium on the Theory and Applications of Satisfiability Testing (SAT2002). P.149-155.

48. Mackworth A. Consistency in networks of relations// Artificial Intelligence. 1977. Vol. 8. P.99-118.

49. McAloon K., TYetkoff C. 2LP: Linear Programming and Logic Programming/ / Principles and Practice of Constraint Programming. MIT Press. P. 101-116.

50. Mitchell D. G., Selman B., Levesque H. J. Hard and easy distributions for SAT problems// Proceedings of the Tenth National Conference on Artificial Intelligence. Menlo Park, California: AAAI Press, 1992. P. 459465.

51. Montanari U. Networks of constraints: Fundamental properties and applications to picture processing// Information Sciences. 1974. Vol. 7. P. 95-132.

52. Narboni G. A. From Prolog III to Prolog IV: The Logic of Constraint Programming Revisited// Constraints. Springer-Netherlands. Vol.4. №4. 2004.

53. Nadel B. Constraint satisfaction in Prolog: Complexity and theory-based heuristics// Information Sciences. 1995. Vol.83. №3-4. P.113-131.

54. Nadel B., Lin J. Automobile transmission design as a constraint satisfaction problem: Modeling the kinematik level// Artificial Intelligence for Engineering Design, Anaysis and Manufacturing (AI EDAM). 1991. Vol.5. №3. P. 137-171.

55. Papadimitriou C. Computational Complexity// Addison-Wesley, 1994.

56. Poschel R., Kaluznin L. Punktionen- und Relationenalgebren. DVW, Berlin, 1979.

57. Puget J. F. A C++ implementation of CLP// Proceedings of the Second Singapore International Conference on Intelligent Systems. 1994. P. 256261.

58. Roy P.V. Logic programming in Oz with Mozart// Proceesings of the 1999 international conference on Logic programming. 1999. P. 38-51.

59. Sclman B., Levesque H., Mitchell D. GSAT A new method for solving hard satisfiability problems// The 10th National Conference on Artificial Intelligence (AAAI-92). 1992. P.440-446.

60. Schaefer T. The complexity of satisfiability problems// Proceedings 10th ACM Symposium on Theory of Computing (STOC'78). 1978. P. 216226.

61. Schwalb E., Vila L. Temporal constraints: a survey// Constraints. 1998. Vol. 3, №. 2-3. P. 129-149.

62. Simpson A., Dandy G., Murphy L. Genetic algorithms compared to other techniques for pipe optimization// Journal of Water Resources Planning and Management. 1994. Vol. 120. №4. P. 423-443.

63. Thornton C. Parity: the problem that won't go away// Advances in Artificial Intelligence. Springer-Verlag, 1996. LNCS Vol. 1081. P. 362-374.

64. Vardi M. Constraint satisfaction and database theory: a tutorial// Proceedings of 19th ACM Symposium on Priciples of Database Systems (PODS'00). 2000. P. 76-85.

65. Voorn R., Dastani M., Marchiori E. Finding simplest pattern structures using genetic programming// Proceedings of the Genetic and Evolutionary Computation Conference. 2001. P.3-10.

66. Wormald N. Differential equations for random processes and random graphs// The Annals of Applied Probability. 1995. Vol.5. №4. P.1217-1235.Работы автора по теме диссертации

67. Булатов А., Скворцов Е. Амальгамы комбинаторных задач// Российская конференция "Дискретный анализ и исследование операций", материалы конференции, Новосибирск. 2002. С. 136.

68. Скворцов Е. О клонах на множестве и его частях// Алгебра и логика. 2005. №1. С.97-113.

69. Скворцов Е. С. VEGAS — новый генетический алгоритм для задачи Выполнимость// Известия Уральского государственного университета. Серия Компьютерные науки и информационные технологии. 2008. №62. Р. 192-207.

70. Скворцов Е. Решение задачи Выполнимость генетическим алгоритмом/ / Труды 36й молодежной школы-конференции "Проблемы теоретической и прикладной математики". 2005. Р.373-375.

71. Amiri Е., Skvortsov Е. S. Pushing random walk beyond golden ratio // Computer Science Theory and Applications. CSR 2007. LNCS Vol. 4649. P.44-55.

72. Bulatov A., Skvortsov E. Amalgams of constraint satisfaction problems/ / The 18th International Joint Conference on Artificial Intelligence (IJCAI'03), Acapulco, Mexico. 2003. P. 197-202.

73. Bulatov A., Skvortsov E. Efficiency of local search// Theory and Applications of Satisfiability Testing SAT 2006. LNCS Vol. 4121. P.297-310.