دانلود پایان نامه

………………………………………….. 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
جدول4-1 مقايسه الگوريتم پيشنهادي ما با دو روش ديگر از لحاظ تعداد سيکلهاي مورد نياز براي حل ……… 82
جدول4-2 مقايسه روش پيشنهادي ما با روش ERA از لحاظ ميانگين زمان اجرا ……………………………………….. 82

فصل اول

مقدمه
از سال 1974، مسائل ارضاء محدويت (CSP1) در مسأله پردازش تصوير2 پيشنهاد شد. پس از آن CSP به طور گسترده در بسياري از حوزه هاي هوش مصنوعي و علوم کامپيوتر به عنوان يک روش حل مهم مورد استفاده قرار گرفته است. از مسأله چند وزير3 و رنگ آميزي گراف4 گرفته و ديگر مسائل کلاسيک گرفته تا زمانبندي5 و تخصيص منابع6 و ديگر مسائل کاربردي بزرگ ميتوانند براي حل شدن به عنوان يک مسأله CSP فرموله شوند. بعد از سال 1990 با جايگزين شدن زبان برنامه نويسي عمومي به جاي زبان برنامه نويسي منطقي مسأله ارضاء محدوديت کاربرد CSP براي حل مسائل بسيار بهبود يافت [1]. يک CSP، با يک مجموعه از متغيرها، دامنه اي براي هر يک از آنها و محدوديتهايي در مقاديري که متغيرها ممکن است به صورت همزمان به خودشان بگيرند، تعريف ميشوند. نقش الگوريتمهاي ارضاء محدوديت، نسبت دادن مقاديري به متغيرهاست به نحوي که با تمام محدوديتها سازگاري داشته باشد يا مشخص کند که هيچ انتسابي امکانپذير نيست. امروزه تکنيکهاي ارضاء محدوديت در حوزه هاي مختلفي از جمله بينايي ماشين، پردازش زبانهاي طبيعي، اثبات قضايا، زمانبندي و… به کار ميروند [4].
از طرف ديگر موقعيتهايي وجود دارد که در آن يک مسأله بايستي در يک مد توزيع شده حل شود به عنوان مثال در شرايطي که استفاده


دیدگاهتان را بنویسید