پایان نامه ارائه مدلی برای حل مسائل ارضاء محدودیت با استفاده از سیستم های چند عامله

فهرست:

فصل اول: مقدمه

مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem) ............................................ 3

تعریف مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem):...............................................  3

الگوریتمهای کلاسیک مسائل ارضاء محدودیت....................................................................................................................  5

CSP  به عنوان یک مسئله جستجو......................................................................................................................................  7

بهبود کارآیی الگوریتمهای جستجوتوسط توابع اکتشافی یا به عبارتی هیوریستیک ها..............................................  8

محدودیتهای ویژه.....................................................................................................................................................................  12

کاربرد جستجوهای محلی در حل مسائل ارضاء محدودیت............................................................................................  12

ساختار مسئله............................................................................................................................................................................  12

سیستمهای چند عامله............................................................................................................................................ 14

حل مسائل CSP توسط سیستمهای چند عامله؛(DCSP)......................................................................... 16

فصل دوم: مروری بر تحقیقات پیشین

مرور کلی...................................................................................................................................................................  19

الگوریتمهای هرس دامنه.......................................................................................................................................  22

الگوریتم تصفیه........................................................................................................................................................................   22

الگوریتم فرا استدلال..............................................................................................................................................................   25

الگوریتمهای اکتشافی.............................................................................................................................................  27

الگوریتم عقبگرد نامتقارن..........................................................................................................................................................   28

الگوریتم الزام ضعیف نامتقارن....................................................................................................................................................  32

الگوریتمهایی که از ترکیب روشهای متمرکز و توزیع شده استفاده می کنند............................................ 33

الگوریتم APO.............................................................................................................................................................................  33

الگوریتمهای ناقص..................................................................................................................................................  37

الگوریتم  DBA ........................................................................................................................................................................  37

الگوریتمهای مبتنی بر کلونی مورچه ها در حل مسائل ارضاء محدودیت توزیع شده.................................................  37

فصل سوم: طراحی و پیاده سازی روشهای پیشنهادی برای مسائل DCSP و بررسی نتایج حاصله

معیارهای ارزیابی کیفیت روشهای حل مسائل ارضاء محدودیت توزیع شده........................................ 44

-1-1- میانگین زمان اجرای الگوریتم با افزایش مقیاس مسأله....................................................................................................  45

3-1-2- میانگین تعداد چرخه های اجرا شده تا رسیدن به یک راه حل ......................................................................................  45

3-1-3- تعداد پیام های ارسال و دریافت شده.....................................................................................................................................  45

3-1-4- NCCC ......................................................................................................................................................  45

3-1-5- قانونی و کامل بودن..................................................................................................................................................................... 46

محکها و مجموعه داده ای مورد استفاده برای آزمایشات.........................................................................  45

3-2-1- مسأله n-وزیر .............................................................................................................................................................................  46

3-2-2- مسأله رنگ­آمیزی گراف ...........................................................................................................................................................  47

3-2-3- مسائل زمانبندی ........................................................................................................................................................................  48

3-2-4- مسائل ارضاء محدودیت باینری ..............................................................................................................................................  51

3-3- طراحی و پیاده سازی روشهای پیشنهادی و نتایج حاصله از آنها................................................................ 52

3-3-1- استفاده از ترکیب الگوریتمهای تکاملی و سیستمهای چندعامله برای حل مسائل ارضاء محدودیت ..................  52

3-3-2- قدرت مورچه ها در حل مسائل ارضاء محدودیت توزیع شده..........................................................................................  60

 فصل چهارم: روش جدید ارائه شده

4-1- مروری بر مفاهیم و موضوعات مورد بحث دراین روش پیشنهادی.............................................................. 69

توصیف مسائل ارضاء محدودیت توزیع شده؛(DCSP)   ............................................................................................  69

تعریف محدودیت Alldiff یا Alldifferent .............................................................................................................  70

توابع اکتشافی ........................................................................................................................................................................  70

تقسیم بندی الگوریتم های مطرح شده برای مسائل DCSP ...................................................................... 71

4-3- توصیف روش جدید ارائه شده و جزئیات پیاده سازی آن.............................................................................. 73

4-4- حل یک مثال با استفاده از این الگوریتم........................................................................................................... 80

4-5- ارزیابی و مقایسه الگوریتم ما با دیگر روشها....................................................................................................  82

4-6- نتیجه گیری و برشمردن مزایا و معایب این روش.........................................................................................  84

فصل پنجم: نتیجه گیری

5-1- نتیجه گیری.........................................................................................................................................................  87

5-2- پیشنهادات و کارهای آینده...............................................................................................................................  89

فهرست منابع.........................................................................................................................................  90

منبع:

[1] Caihong Zhao, Yanyan Cui, “An Improved Algorithm of CSP. 2012 International Workshop on Information and Electronics Engineering (IWIEE)”, pp. 2832 – 2837, 2012.

[2] Stuart Russell, peter Nerving. “Artificial Intelligence: A Modern Approach(second edition)”, 2009.

[3] W. Zhong, J. Liu, M. Xue, and L. Jiao, “A Multiagent Evolutionary Algorithm for Constraint Satisfaction Problems,” IEEE, pp.54-73, 2004.

[4] Y. Shoham, K. L. Brown, “ MULTIAGENT SYSTEMS, Algorithmic, Game-Theoretic and Logical Foundations”, 2009, 2010.

[5] J. Liu, “Autonomous Agents and Multi-Agent Systems: Explorations in Learning Self-Organization, and Adaptive Computation”, Singapore:World Scientific, 2001.

[6] J. Liu, H. Jing, and Y. Y. Tang, “Multi-agent oriented constraint satisfaction”, Artif. Intell., vol. 136, no. 1, pp.101–144, 2002.

[7] W. Zhong, J. Liu, M. Xue, and L. Jiao, “A multiagent genetic algorithm for global numerical optimization”, IEEE Trans. Syst., Man, and Cybern. B, vol. 34, no. 2, pp.1128-1141, 2004.

[8] Makoto yokoo ."Multiagent systems. A modern approach to Distributed Artificial Intelligence." edited by Gerhard Weiss, The MIT Press, ISBN: 0262731312, 1999.

 [9] Yokoo, M., Durfee, E. H., “Distributed constraint Satisfaction for formalizing distributed problem solving”, .12th IEEE International Conference on Distributed Computing Systems, 1, pp. 614–621, 1992.

[10] Sycara, K., Roth, S. F., Sadeh N., Fox, M. S., “Distributed constrained heuristic search”, International Journal of IEEE Transactions on Systems, Man and Cybernetics, 21(6), pp. 1446–1461, 1991.

[11] Modi, A P. J., Veloso, M., Smith, S., Cmradar, J. Oh., “A personal assistant agent for calendar management. Agent Oriented Information Systems (AOIS)”, 2004.

[12] Conry, S. E., Kuwabara, K., Lesser, V. R., Meyer R. A., “Multistage negotiation for distributed constraint satisfaction”, International Journal of IEEE Transactions on Systems, Man and Cybernetics 21(6), pp.1462–1477, 1991.

[13] Huhns, M. N., Bridgeland, D. M., “Multi-agent truth maintenance”, International Journal of IEEE Transactions on Systems, Man and Cybernetics 21(6), pp. 1437–1445, 1991.

[14] Yokoo, M., Durfee, E. H., “Distributed constraint Satisfaction for formalizing distributed problem solving”, 12th IEEE International Conference on Distributed Computing Systems, 1, pp. 614–621, 1992.

[15] Yokoo, M., “Asynchronous weak-commitment search for solving distributed constraint satisfaction problems”, The First International Conference on Principles and Practice of Constraint Programming, pp.88–102, 1995.

[16] Mailler, R., Lesser V., “Asynchronous partial overlay: a new algorithm for solving distributed constraint satisfaction problems”, Journal of Artificial Intelligence Research (JAIR) 25, pp. 529-576, 2006.  

 [17] Mailler, R., “Comparing two approaches to dynamic, distributed constraint satisfaction”, Fourth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2005),pp. 1049–1056, 2005.

[18] Mailler, R., Lesser, V., “Solving distributed constraint optimization problems using cooperative mediation”, Third International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2004), pp.438–445, 2004.

[19] Mailler, R., “Solving distributed CSPs using dynamic partial centralization without explicit constraint passing”, Second Workshop on the Challenges in the Coordination of Large Scale Multi-Agent Systems (LSMAS 2005), pp.27-41, 2005.

[20] Benish, M., Sadeh, N., “Effect of mediator selection strategy for distributed constraint satisfaction”, Workshop on Distributed Constraint Reasoning (DCR)., 2005.

[21] Benish, M., Sadeh, N., “Examining distributed constraint satisfaction problem (DCSP) coordination tradeoffs”. International Conference on Automated Agents and Multi-Agent Systems (AAMAS), pp. 1405-1412, 2006.

[22] S.Hoseyni, K.Zamanifar, the impact of the conflict on solving distributed constraint satisfaction Problems, Computing and Informatics, Vol. 28, 2009, pp.673–693, 2007.

[23] Freuder, E. C., Wallace, R. J., Partial constraint satisfaction. Journal of Artificial Intelligence, 58(13), pp.21–70, 1992.

[24] Y. Deville and P. Van Hentenryck, “Efficient arc consistency algorithm for a class of CSP problems,” in Proceedings of the International Joint Conference on Artificial Intelligence, v1, pp.325, 1991.

[25] M. Bruynooghe, “Solving combinational search problems by intelligent backtracking,” Inform. Process. Lett. 12(1), pp.36-39, 1981.

[27] A. Eiben and J. I. Van Hemert, “SAW-ing EAs: Adapting the fitness function for solving constrained problems,” in New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glover, Eds. New York: McGraw-Hill, pp.389-402, 1999.

[28] B. Craenen and A. Eiben, “Stepwise adaption of weights with refinement and decay on constraint satisfaction problems,” in Proc. Genetic and Evolutionary Computation Conf., GECCO-2001, L. Spector, E. Goodman, A. Wu, W. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon, and E. Burke, Eds., pp.291-298, , 2001.

[29] S. Minton, M. D. Johnston, and A. B. Philips, “Solving large-scale constraint-satisfaction and scheduling problems using a heuristic repair method,” in Proceedings of the National Conference on Artificial Intelligence, 1990.

[30] S. Minton, M. D. Johnston, A. B. Philips, and P. Laird, “Minimizing conflicts: a heuristic repair method for constraint-satisfaction and scheduling problems,” Artificial Intelligence, Volume 58, pp.161-205, 1992.

[31] Hoseini Semnani, Samaneh, and Kamran Zamanifar. "The power of ants in solving Distributed Constraint Satisfaction Problems." Applied Soft Computing 12.2 (2012): 640-651,2012.

[32] M. Yokoo, E.H. Durfee, T. Ishida, K. Kuwabara, Distributed constraint satisfaction for formalizing distributed problem solving, in: International Conference on Distributed Computing Systems, pp. 614–621. , 1992.

[33] M. Yokoo, Y. Kitamura, Multi-agent real-time-a* with selection: introducing competition in cooperative search, in: Proceedings of the Second International Conference on Multi-Agent Systems, Kyoto, Japan, 1996.

[34] M. Yokoo, K. Hirayama, Algorithms for distributed constraint satisfaction: a review, Autonomous Agents and Multi-Agent Systems (2000) 198–212,2000.

[35] M. Yokoo, K. Hirayama, Distributed breakout algorithm for solving distributed constraint satisfaction problems, in: International Conference on Multi-Agent Systems (ICMAS), 1996.

[36] M. Yokoo, K. Hirayama, Distributed constraint satisfaction algorithm for complex local problems, in: Third International Conference on Multi-Agent Systems, Paris, pp: 372–379, 1998.

[37] M. Dorigo, L. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation 1 (1) (1997) 53, 1997.

[38] L.M. Gambardella, E.D. Taillard, M. Dorigo, Ant colonies for the quadratic assignment problem, The Journal of the Operational Research Society 50 (2) (1999) ,pp:167–176, 1999.

[39] D. Costa, A. Hertz, Ants can color graphs, Journal of the Operational Research Society (1997) . pp: 295–305,1997.

[40] E. Salari, K. Eshghi, An ACO algorithm for the graph coloring problem, International Journal of Contemporary Mathematical Sciences 3 (6) (2008), pp: 293–304, 2008.

[41] C. Solnon, Ants can solve constraint satisfaction problems, IEEE Transactions on Evolutionary Computation 6 (4) (2002) .pp.347–357, 2002.

[42] C. Solnon, Solving permutation constraint satisfaction problems with artificial ants, in:  ECAI’2000, IOS Press, Amsterdam, The Netherlands, 2000, pp:118–122, 2000.

[43] J.I. Hemert, C. Solnon, A study into ant colony optimisation, evolutionary computation and constraint programming on binary constraint satisfaction problems, Evolutionary Computation in Combinatorial Optimization, LectureNotes in Computer Science 3004 ,pp.114–123,2004.

[44] F. Tarrant, D. Bridge, When ants attack: ant algorithms for constraint satisfaction problems, Artificial Intelligence Review, pp. 455–476, Springer 2005.

[45] K. Mertens, T. Holvoet, Y. Berbers, The DynCOAA algorithm for dynamic constraint optimization problems, in: Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, ACM, pp. 1421–1423, 2006.

[46] K. Mertens, T. Holvoet, CSAA; a constraint satisfaction ant algorithm framework, in: Sixth International Conference on Adaptive Computing in Design and Manufacture (ACDM’04), Springer-Verlag, pp. 285–294, , 2004.

[47] K. Mertens, T. Holvoet, CSAA: a distributed ant algorithm framework for constraint satisfaction, in: 17th International Florida Artificial Intelligence Research Society Conference, USA, pp. 764–769, 2004.

[48] Makoto Yokoo, Koutarou Suzuki, Katsutoshi Hirayama, Secure distributed constraint satisfaction: reaching agreement without revealing private information,in: CP ‘02. Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, 2003.

[49] A. Meisels, E. Kaplansky, I. Razgon, R. Zivan, Comparing performance of distributed constraints processing algorithms, in: CDR Workshop at AAMAS’02, 2002.

[50] T. Stützle, H.H. Hoos, MAX–MIN ant system, Journal of Future Generation Computer Systems 16 (2000), pp:889–914, 2000.

[51] J. Culberson, I. Gent, Frozen development in graph coloring, Theoretical Computer Science 265 (1–2) (2001) 227–264,2001.

[52] K. Hirayama, M. Yokoo, The distributed breakout algorithms, Artificial Intelligence – Special Issue: Distributed Constraint Satisfaction 161 (January (1–2)) (2005), pp:89–115,2005.

[53] A. Meisels, E. Kaplansky, I. Razgon, R. Zivan, Comparing performance of distributed constraints processing algorithms, in: CDR Workshop at AAMAS’02, 2002.

[54] Tsang, Edward. "A glimpse of constraint satisfaction." Artificial Intelligence Review 13.3 (1999), pp.215-227.1999.

[55] Yokoo, M. Asynchronous weak-commitment search for solving distributed constraint satisfaction problems.. In Proceedings of the First International Conference on Principles and Practice of Constraint Programming (CP-95), Lecture Notes in Computer Science 976, (1995). Pp. 88–102, 1995.

[56] Pesant, Gilles, Claude-Guy Quimper, and Alessandro Zanarini. "Counting-based search: Branching heuristics for constraint satisfaction problems." Journal of Artificial Intelligence Research 43.1 (2012). pp:173-210, 2012.

[57] B. G. W. Craenen, A. E. Eiben, and J. I. Van Hemert, “Comparing evolutionary algorithms on binary constraint satisfaction problems,” IEEE Trans. Evol. Comput., vol. 7, Oct., pp.424-444, 2003.

[58] A. Eiben, P.-E. Raué, and Z. Ruttkay, “Solving constraint satisfaction problems using genetic algorithms,” in Proc. 1st IEEE Conf. Evolutionary Computation, pp.542-547, 1994.

[59] B. Craenen, A. Eiben, and E. Marchiori, “Solving constraint satisfaction problems with heuristic-based evolutionary algorithms,” in Proc. Congress Evolutionary Computation , pp.1571-1577, 2000.

[60] A. Eiben and J. I. Van Hemert, “SAW-ing EAs: Adapting the fitness function for solving constrained problems,” in New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glover, Eds. New York: McGraw-Hill, pp.389-402, 1999.

[61] B. Craenen and A. Eiben, “Stepwise adaption of weights with refinement and decay on constraint satisfaction problems,” in Proc. Genetic and Evolutionary Computation Conf., GECCO-2001, L. Spector, E. Goodman, A. Wu, W. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon, and E. Burke, Eds., pp.291-298, 2001.

[62] E. Marchiori, “Combining constraint processing and genetic algorithms for constraint satisfaction problems,” in Proc. 7th Int. Conf. Genetic Algorithms, T. Bäck, Ed., pp.330-337, 1997.

[63] J. Liu, H. Jing, and Y. Y. Tang, “Multi-agent oriented constraint satisfaction,” Artif. Intell., vol. 136, no. 1, 2002, pp.101-144.

[64] at.gsia.cmu.edu/COLOR/instances.html