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

 

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

 

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

 

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

 

 

 

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

 

 

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

 

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

   

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

   

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

 

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

   

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

   

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

 

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

   

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

 

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

   

  • الگوریتم DBA ……………………………………………………………………………………………………………………………………………………  37

   

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

 

 

 

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

 

 

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

 

3-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-1  مثالی از مساله CSP [4] …………………………………………………………………………………………………………………. 4

 

شکل 1-2  یک طرح جامع از به کار بردن تکنیکهای ارضاء محدودیت برای حل مسائل [54] ……………………….. 5

 

شکل 1-3 (الف) نواحی استرالیا (ب) عملکرد توابع اکتشافی مختلف بر روی این نقشه [2] …………………………………………… 11 شکل 1-4 زیرمسأله های مستقل در گراف محدودیت [2] ……………………………………………………………………………… 13

 

شکل 1-5  کاهش گراف محدودیت به درخت توسط حذف گرهها [2] ………………………………………………………….. 13

 

شکل 1-6 کاهش گراف محدودیت به درخت توسط تجزیه گراف [2] ……………………………………………………………. 14

 

شکل 1-7 یک شبکه حسگر واقعی برای مانیتور کردن محیط داخلی یک ساختمان[4] ………………………………. 15

 

شکل 2-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 20

 

شکل 2-2 چهار حالت مختلف از مسئله کلاسیک رنگ آمیزی گراف و نتیجه پیاده سازی الگوریتم تصفیه برای هر یک از این مسائل[4] ……………………………………………………………………………………………………………………………………. 24

 

شکل 2-3 سیکل 1 الگوریتم ABT بر روی مسئله 4 وزیر[4] ………………………………………………………………………… 29

 

شکل 2-4 سیکل 2 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 29

 

شکل 2-5 سیکل 3 از الگوریتم ABT بر روی مسئله 4 وزیر[4] …………………………………………………………………….. 30

 

شکل 2-6 سیکل 4 و 5  از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………… 30

 

شکل 2-7 سیکل 6 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31

 

شکل 2-8  سیکل 7  و 8  از الگوریتم ABT بر روی مسئله 4وزیر[4] ………………………………………………………….. 31

 

شکل 2-9 سیکل 9 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31

 

شکل 2-10 سیکل 10  از الگوریتم ABT بر روی مسئله 4وزیر [4] ……………………………………………………………… 32

 

شکل 2-11 الگوریتم APO  [22] ……………………………………………………………………………………………………………………. 35

 

شکل 2-12 مثالی از گراف ساختار [44] …………………………………………………………………………………………………………. 39

 

شکل 2-13 ساختن یک گراف برای یک مسأله با سه متغیر …………………………………………………………………………… 40

 

شکل 3-1 جهت حرکات ممکن یک مهره وزیر در یک صفحه شطرنج ……………………………………………………………. 46

 

شکل 3-2 یک جواب برای مسأله 8-وزیر …………………………………………………………………………………………………………. 47

 

شکل 3-3 مثالی از رنگ آمیزی گراف(یک رنگ آمیزی از گراف معروف پترسن) …………………………………………… 48

 

شکل 3-4 مثالی از مساله CSP [4] …………………………………………………………………………………………………………………. 52

 

شکل 3-5 مدل فرض شده از محیط شبکه مانند عاملها[3] ……………………………………………………………………………. 53

 

شکل 3-6 میانگین زمان اجرای الگوریتم MAEA-CSPs در حل مسأله n-وزیر [3] ……………………………………. 58

 

شکل 3-7 مقایسه الگوریتم MAEA-CSPs با 4 الگوریتم دیگر با معیارهای SR، ME و AES [4] ……………. 59

 

شکل 3-8 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها ………………………………………………………………………… 63

 

شکل 3-9 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………………………… 63

 

شکل 3-10 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .32 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 63

 

شکل 3-11 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.3 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 64

 

شکل 3-12 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .72 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 64

 

شکل 3-13 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.7 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 65

 

شکل 4-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 72

 

شکل 4-2 مرحله 1 تا 4 از الگوریتم DACA ………………………………………………………………………………………………….. 80

 

شکل 4-3 مرحله 5 از الگوریتم DACA ………………………………………………………………………………………………………….. 81

 

شکل 4-4 مرحله پایانی الگوریتم DACA ……………………………………………………………………………………………………….. 82

 

شکل 4-5 میانگین زمان اجرای الگوریتم DACA در اجرای مسأله n-وزیر با افزایش n از 4 تا 10⁴ در گامهای 50 تایی ………………………………………………………………………………………………………………………………………………………………. 82

 

 

 

 

 

 

 

 

 

فهرست جداول

 

 

 

عنوان                                                                                                                                        صفحه

 

جدول 3-1 نتایج بدست آمده از آزمایش MAEA-CSPs بر روی مسائل ارضاء محدودیت باینری …………… 59

 

جدول 3-2 مقادیر متفاوت از تعداد مورچه ها برای سایزها و تراکم­های متفاوت …………………………………………….60