WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 | 2 ||

Оно представляется вполне правдоподобным, но мы пока не смогли дать чисто математического обоснования его справедливости. Тем не менее мы считаем возможным принять это допущение, поскольку получаемые на его основе результаты весьма хорошо соответствуют экспериментальным данным. Принимая допущение 1, мы можем применить теорему Вормальда к набору параметров и получить описывающую их эволюцию систему e дифференциальных уравнений (система (2.16) в диссертации). Изучая решения этой системы дифференциальных уравнений, мы получаем второй основной результат главы 2.

Теорема 2.3 Для любого положительного существует константа cтакая, что для случайной 3-КНФ, распределенной по закону (n, n), количество клозов, выполненных набором значений, получаемым по окончании работы алгоритма ЛП, почти наверняка равно c2n + o(n).

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

При численном решении системы дифференциальных уравнений для ЛП мы ограничиваем число переменных eab условиями a 20, b 20. Сравнение полученных значений с экспериментальными данными представлено в таблицах 1 и 2.

c (эксперимент) c (система (2.8)) 3 2.95 2.4 3.91 3.10 9.53 9.Таблица 1: Зависимость качества решения, найденного алгоритмом ЛПОП, от плотности задачи. Экспериментальные данные и предсказание системы (2.8).

c (эксперимент) c (система (2.16)) 3 2.936 2.4 3.884 3.10 9.430 9.Таблица 2: Зависимость качества решения, найденного алгоритмом ЛП, от плотности задачи. Экспериментальные данные и предсказание системы (2.16).

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

В главе 3 описывается модификация генетического алгоритма решения задачи Выполнимость, учитывающая влияние индивидов на окружаюРис. 2: Графики зависимости количества неудовлетворенных клозов от времени работы алгоритма ЛП. Тонкие линии отражают значения, полученные из запусков алгоритма на конкретных задачах, а жирная линия отвечает результатам численного решения системы дифференциальных уравнений. На оси ординат откладывается отношение числа невыполненных клозов к числу переменных, а на оси абсцисс – отношение числа проделанных шагов к числу переменных. Наклонная часть графиков отражает работу алгоритма до попадания в локальный минимум, далее каждый график продолжается горизонтальной линией, соответствующей количеству клозов, неудовлетворенных в конце работы.

щую среду. Разработанный нами алгоритм мы назвали VEGAS (сокращенно от Valuation Enhanced Genetic Algorithm for Satisfability1). В то время как в классическом варианте популяция обитает и развивается в неизменном окружении, в предлагаемом нами алгоритме популяция и окружающая среда активно влияют друг на друга, эволюционируя вместе. В предлагаемой модели каждый клоз C мы считаем формой хищника и интерпретируем удовлетворение вектором клоза C как способность существа x x защититься от хищника C. Эволюция среды в алгоритме VEGAS реализована следующим образом. Когда в результате размножения появляется существо с генотипом хищники, от которых это существо не защищеx, но, размножаются, что в терминах задачи выражается в увеличении веса клозов, которые нарушаются вектором Увеличения весов невыполненx.

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

Алгоритм был реализован на языке C++ в среде Microsoft Visual Studio.

Тестирование эффективности проводились на персональном компьютере Pentium IV тактовой частотой 3GHz. Для того, чтобы оценить насколько включение воздействия индивидов на окружающую среду влияет на эффективность вычислений, мы сравниваем VEGAS с одним из лучших генетических алгоритмов – алгоритмом GASAT на ряде известных тестовых задач [32]. Результаты тестирования представлены в таблице 3. В колонке время указано среднее время вычисления закончившегося решением задачи (в секундах), если задача была решена хотя бы один раз. Если решение не было найдено, то в скобках указывается число невыполненых ограничений для наилучшего найденного индивида. В таблице приведены результаты тестирования версии GASAT, выложенной на сайте авторов (колонка GASAT), а также результаты, полученные самими авторами алгоритма GASAT (колонка GASAT(авт)).

Проведенные тесты показывают, что VEGAS может решить больший класс задач, чем GASAT, а задачи, посильные GASAT, алгоритм VEGAS решает за меньшее время, оказываясь таким образом сильнее своего предшественника. Представляется, что предложенная нами модификация генеУсиленный взвешиванием генетический алгоритм для задачи Выполнимость Задачи GASAT(авт) VEGAS GASAT Кол-во Кол-во Время Время Время Файл Успех Успех Успех перем.

клозов aim-100-1_6-yes1-1.cnf 0,43 (1) 100 160 100% 0% 2% aim-200-1_6-yes1-1.cnf 2,48 (1) 200 320 85% 0% par8-1-c.cnf 0,06 0,17 0,64 254 100% 10% 100% par8-1.cnf 1,04 41,87 8,350 1149 100% 10% 17% par8-2.cnf 1,45 (1) 11,350 1157 85% 0% 25% par32-5-c.cnf (4) (13) (5) 1339 5350 0% 0% 0% par32-5.cnf (8) (129) (16) 3176 10325 0% 0% 0% 14,91 15,22 479,color-15-4.cnf 900 45675 100% 100% 100% 255,45 (3) (5) color-22-5.cnf 2420 272129 40% 0% 0% dp11u10.shuffled.cnf (2) (81) (36) 9197 25271 0% 0% 0% (3) (8) (39) mat25.shuffled.cnf 588 1968 0% 0% 0% (2) (8) (56) mat26.shuffled.cnf 744 2464 0% 0% 0% g125.18.cnf 5,92 30,19 92,2250 70163 100% 100% 98% g250.29.cnf 313,08 (2) (2) 7250 454622 5% 0% 0% Таблица 3: Таблица сравнения эффективности алгоритмов VEGAS и GASAT.

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

Автор благодарит своего научного руководителя профессора М. В. Волкова за внимание к работе и помощь в подготовке текста диссертации, а также доцента А. А. Булатова за постановку задач и постоянное внимание к работе. Автор с чувством глубокой благодарности вспоминает своего первого научного руководителя профессора Е. В. Суханова.

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

[2] Левин Л. А. Универсальные задачи перебора// Проблемы передачи информации. 1973.

T. 9, № 3. С. 115–116.

[3] Allen J. Natural Language Understanding. Benjamin Cummings, 1994.

[4] Apt K., Wallace M. Constraint Logic Programming using Eclipse. Cambridge University Press, 2007.

[5] Backofen R., Will S. A constraint-based approach to fast and exact structure prediction in three-dimensional protein models// Constraints. 2006. Vol.11. № 1. P.5–30.

[6] 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.

[7] Bramelette M., Bouchard E. Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1991.

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

[9] Bulatov A., Krokhin A., Jeavons P. Constraint satisfaction problems and finite algebras// Proc. 27th Int. Colloq. Automata, Languages and Programming (ICALP’00). LNCS Vol. 1853.

Springer, 2000. P.272–282.

[10] Cohen D., Jeavons P., Gault R. New tractable classes from old// Principles and Practice of Constraint Programming CP’00. LNCS Vol. 1894. Springer, 2000. P.160–171.

[11] Cohen D., Jeavons P., Koubarakis M. Building tractable disjunctive constraints// J. ACM. 2000.

Vol.47. P. 826–853.

[12] Cohen D.A. Jeavons P., Gyssens M. A structural decomposition for hypergraphs// Contemporary Mathematics. 1994. Vol.178. P.161–177.

[13] Cook S. The complexity of theorem-proving procedures// 3rd IEEE Symp. the Foundations Comput. Sci. 1971. P.151–158.

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

[15] Dechter R., Pearl J. Tree clustering for constraint networks// Artificial Intelligence. 1989.

Vol.38. P.353–366.

[16] Eiben A.E., Ven Der Hauw J.K., Van Hemert J.I. Graph coloring with adaptive evolutionary algorithms// J. Heuristics. 1998. Vol.4, № 1. P.25–46.

[17] Feder T., Vardi M. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory// SIAM J. Comput. 1998. Vol. 28. P.57– 104.

[18] Fleurent. J., Ferland J. Genetic algorithms and hybrids for graph coloring// Ann. Operations Research. 1996. Vol. 63. P.437–461.

[19] Freuder E. Complexity of k-tree structured constraint satisfaction problems// 8th Nat. Conf.

Artificial Intelligence AAAI’90. 1990. P. 4–9.

[20] Goldberg D. Genetic Algorithms in Search, Oprimization, and Machine Learning. AddisonWesley, 1989.

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

[22] Grohe M., Schwentick T., Segoufin L. When is the evaluation of conjunctive queries tractable// 33rd Annual ACM Symp. Theory of Computing. ACM Press, 2001. P.657–666.

[23] Gu. J. Efficient local search for very large-scale satisfiability problem// ACM SIGART Bull.

1992. Vol. 3, № 1. P. 8–12.

[24] Han H., Xiaowei Y., Zhifeng H. Chunguo W., Yanchun L., Xi Z. Hybrid chromosome genetic algorithm for generalized traveling salesman problems// Adv. Natural Comput. LNCS Vol. 3612.

Springer, 2005. P.137–140.

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

[26] Hentenryck V. The CLP language CHIP: constraint solving and applications// Proc. IEEE Comput. Soc. Int. Conf. 1991. P. 382–387.

[27] Hentenryck V., Michel L. Newton: Constraint programming over nonlinear real constraints// Sci. Comput. Programming. 1997. Vol. 30. P. 83–118.

[28] Hiroaki U., Ouchi D., Takahashi K., Miyahara T. A co-evolving timeslot/room assignment genetic algorithm technique for university timetabling// 3rd Int. Conf. Practice and Theory of Automated Timetabling. LNCS Vol. 2079. Springer, 2000. P.48–63.

[29] Hirsch E., Kojevnikov A. UnitWalk: A new SAT solver that uses local search guided by unit clause elimination// Ann. Math. Artificial Intelligence. 2001. Vol. 43, № 1–4. P. 91–111.

[30] Hirsch E. A. Worst-case study of local search for Max-k-Sat// Discrete Appl. Math. 2003. Vol.

130. № 2. P.173–184.

[31] Holland J. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975.

[32] Hoos H. Satisfiability Library// http://www.satlib.org (Электронный ресурс).

[33] Hoos H., Stutzle T. Stochastic Local Search, foundations and applications. Elsevier, 2005.

[34] Jeavons P. On the algebraic structure of combinatorial problems// Theor. Comput. Sci.. 1998.

Vol. 200. P.185–204.

[35] Jeavons P., Cohen D., Gyssens M. Closure properties of constraints// J. ACM. 1997. Vol. 44.

P.527–548.

[36] Jong K. D., Spears W. Using genetic algorithms to solve np-complete problems// Proc. Int.

Conf. Genetic Algorithms. 1989. P.124–132.

[37] Kolaitis P., Vardi M. Conjunctive-query containment and constraint satisfaction// J. Comput.

Syst. Sci. 2000. Vol. 61, №2. P.302–332.

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

[39] Krippahl L., Barahona P. Applying constraint programming to protein structure determination// Proc. 5th Int. Conf. Constraint Programming. LNCS Vol. 1713. Springer, 1999. P. 289–302.

[40] Lardeux F., Saubion F., Hao J.-K. A hybrid genetic algorithm for the satisfiability problem// 1st Int. Workshop on Heuristics. 2002. P. 69–77.

[41] McAloon K., Tretkoff C. 2LP: Linear programming and logic programming// Principles and Practice of Constraint Programming. MIT Press. P. 101–116.

[42] Mitchell D. G., Selman B., Levesque H. J. Hard and easy distributions for SAT problems// Proc. 10th Nat. Conf. Artificial Intelligence. AAAI Press, 1992. P. 459–465.

[43] Montanari U. Networks of constraints: Fundamental properties and applications to picture processing// Information Sciences. 1974. Vol. 7. P. 95–132.

[44] Narboni G. A. From Prolog III to Prolog IV: The logic of constraint programming revisited// Constraints. 1999. Vol. 4, № 4. P.313–335.

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

[46] 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.

[47] Pschel R., Kalunin L. Funktionen- und Relationenalgebren. DVW, Berlin, 1979.

[48] Puget J. F. A C++ implementation of CLP// Proc. 2nd Singapore Int. Conf. Intelligent Systems. 1994. P. 256-261.

[49] Roy P.V. Logic programming in Oz with Mozart// Proc. Int. Conf. on Logic programming. 1999.

P. 38–51.

[50] Selman B., Levesque H., Mitchell D. GSAT – A new method for solving hard satisfiability problems// 10th Nat. Conf. Artificial Intelligence (AAAI-92). 1992. P.440–446.

[51] Schaefer T. The complexity of satisfiability problems// Proc. 10th ACM Symp. Theory Comp.

STOC’78. 1978. P. 216–226.

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

[53] Simpson A., Dandy G., Murphy L. Genetic algorithms compared to other techniques for pipe optimization// J. Water Resources Planning and Management. 1994. Vol. 120. № 4. P. 423–443.

[54] Vardi M. Constraint satisfaction and database theory: a tutorial// Proc. 19th ACM Symp.Priciples of Database Systems (PODS’00). 2000. P. 76–85.

[55] Voorn R., Dastani M., Marchiori E. Finding simplest pattern structures using genetic programming// Proc. Genetic and Evolutionary Comput. Conf. 2001. P.3–10.

[56] Wormald N. Differential equations for random processes and random graphs// Ann. Appl.

Probability. 1995. Vol.5, № 4. P.1217–1235.

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

[58] Скворцов E. О клонах на множестве и его частях// Алгебра и логика. 2005. Т. 44, № 1.

С. 97–113.

Pages:     | 1 | 2 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»