• عامله………………………………………………………………………………………………………………………….. 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

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

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


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