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

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

فهرست:

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

مسئله ارضاء محدودیت(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