- کاربرد جستجوهای محلی در حل مسائل ارضاء محدودیت……………………………………………………………………………….. 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
جدول 3-2 مقادیر متفاوت از تعداد مورچه ها برای سایزها و تراکمهای متفاوت …………………………………………….60
[چهارشنبه 1399-10-10] [ 04:31:00 ق.ظ ]
|