• الگوریتمهای کلاسیک مسائل ارضاء محدودیت…………………………………………………………………………………………………….. 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

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 تا 104 در گامهای 50 تایی ………………………………………………………………………………………………………………………………………………………………. 82

 

 

 

 

فهرست جداول

 

عنوان                                                                                                                                        صفحه

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

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...