| دانلود پایان نامه : ارائه مدلی برای حل مسائل ارضاء محدودیت با بهره گرفتن از سیستمهای چند عامله | ... | |
|
مورد توجه زیادی قرار گرفته است. و این مسأله بدان علت است که بسیاری از مسائل اعم از مسائل کلاسیکی همانند مسأله n-وزیر و رنگ آمیزی گراف گرفته و تا مسائل کاربردی بزرگ دنیای واقعی همچون زمانبندی و برنامه ریزی و تخصیص منابع میتوانند برای حل شدن به عنوان یک مسأله مسأله ارضاء محدودیت توزیع شده فرموله شوند. بنابراین ارائه یک شیوه جدید و یا اصلاح شیوه های فعلی تاثیر زیادی بر دامنه تحقیقاتی این فیلد میگذارد. آنچه در این پایان نامه ارائه میشود ارائه تکنیکی جدید برای حل مسائل ارضاء محدودیت توزیع شده است. این تکنیک جدید محدودیتها را در یک سیستم که ترکیبی از سیستمهای توزیع شده و متمرکز است اداره و کنترل می کند که با بهره گیری از یک سری ویژگیهای خاص تعریف شده از سیستمهای ترکیبی دیگر موجود متمایز میشود. نتایج حاصله نشان می دهد که این الگوریتم در مسائل با مقیاس بزرگ کارایی خوبی خواهد داشت و تقریبا یک پیچیدگی زمانی خطی را با افزایش مقیاس مسأله به دست میآورد. همچنین مقایسه این روش با چند روش دیگر بهبود عملکرد این روش را در پارامترهای مختلف نسبت به دیگر روشها نشان میدهد.
فهرست مطالب
عنوان صفحه فصل اول: مقدمه مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem) …………………………………….. 3تعریف مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem):……………………………………….. 3 فصل دوم: مروری بر تحقیقات پیشین مرور کلی………………………………………………………………………………………………………………………………………………. 19 فصل سوم: طراحی و پیاده سازی روش های پیشنهادی برای مسائل DCSP و بررسی نتایج حاصله معیارهای ارزیابی کیفیت روش های حل مسائل ارضاء محدودیت توزیع شده…………………………………. 44 3-1-2- میانگین تعداد چرخه های اجرا شده تا رسیدن به یک راه حل ………………………………………………………………………….. 45 3-1-3- تعداد پیام های ارسال و دریافت شده……………………………………………………………………………………………………………………. 45 3-1-4- NCCC …………………………………………………………………………………………………………………………………… 45 3-1-5- قانونی و کامل بودن………………………………………………………………………………………………………………………………………………… 46 محکها و مجموعه داده ای مورد استفاده برای آزمایشات………………………………………………………………. 45 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 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، مسائل ارضاء محدویت (CSP[1]) در مسأله پردازش تصویر[2] پیشنهاد شد. پس از آن CSP به طور گسترده در بسیاری از حوزه های هوش مصنوعی و علوم کامپیوتر به عنوان یک روش حل مهم مورد استفاده قرار گرفته است. از مسأله چند وزیر[3] و رنگ آمیزی گراف[4] گرفته و دیگر مسائل کلاسیک گرفته تا زمانبندی[5] و تخصیص منابع[6] و دیگر مسائل کاربردی بزرگ میتوانند برای حل شدن به عنوان یک مسأله CSP فرموله شوند. بعد از سال 1990 با جایگزین شدن زبان برنامه نویسی عمومی به جای زبان برنامه نویسی منطقی مسأله ارضاء محدودیت کاربرد CSP برای حل مسائل بسیار بهبود یافت [1]. یک CSP، با یک مجموعه از متغیرها، دامنه ای برای هر یک از آنها و محدودیتهایی در مقادیری که متغیرها ممکن است به صورت همزمان به خودشان بگیرند، تعریف میشوند. نقش الگوریتمهای ارضاء محدودیت، نسبت دادن مقادیری به متغیرهاست به نحوی که با تمام محدودیتها سازگاری داشته باشد یا مشخص کند که هیچ انتسابی امکانپذیر نیست. امروزه تکنیکهای ارضاء محدودیت در حوزه های مختلفی از جمله بینایی ماشین، پردازش زبانهای طبیعی، اثبات قضایا، زمانبندی و… به کار میروند [4]. از طرف دیگر موقعیتهایی وجود دارد که در آن یک مسأله بایستی در یک مد توزیع شده حل شود به عنوان مثال در شرایطی که استفاده از یک کنترل کننده مرکزی ممکن نیست و یا اینکه میخواهیم استفاده مناسبی از منابع توزیع شده و یا امکانات محاسباتی داشته باشیم. در چنین مواقعی عاملها[7] برای رسیدن به یک هدف مشترک تلاش می کنند. هر سیستم چند عامله یک سیستم محاسباتی است که در آن چندین عامل جهت رسیدن به یک هدف خاص با هم در تعامل هستند و با هم کار می کنند [4]. مسأله ارضاء محدودیت توزیع شده (DCSP[8]) در واقع حالت توزیع شدهی مسأله ارضاء محدودیت کلاسیک است که در آن متغیرها بین عاملهای مستقل توزیع شدهاند. این محیط توزیع شده شامل تعدادی عامل هوشمند است که هر کدام، یک یا چند متغیر را مالک میشوند و مقدار آن را کنترل می کنند. همه این عامل ها در تلاشند تا با حفظ استقلالشان به هدف مشترک دست یابند. هدف هنوز یافتن یک انتساب برای متغیرهاست که محدودیتها را هم در نظر داشته باشد اما هر عامل، برای مقدار متغیر مالکش با خودمختاری نسبی تصمیم میگیرد. هر چند عاملها یک دید عمومی ندارند اما هر یک از آنها می تواند با همسایه اش در گراف محدودیت ارتباط برقرار کند. هر عامل سعی می کند نه تنها با ارضاء محدودیتهای محلی خود بلکه با برقرای ارتباط با سایر عاملها به منظور حل محدودیتهای خارجی به این هدف نزدیک و نزدیکتر شود. به طور کلی تمام
[جمعه 1398-07-12] [ 12:30:00 ق.ظ ]
لینک ثابت
|
||
|
کلیه مطالب این سایت فاقد اعتبار و از رده خارج است. تعطیل کامل
کلیه مطالب این سایت فاقد اعتبار و از رده خارج است. تعطیل کامل |
 |
|
