شکل ۱-۵ کاهش گراف محدودیت به درخت توسط حذف گرهها [۲] ………………………………………………………….. ۱۳
شکل ۱-۶ کاهش گراف محدودیت به درخت توسط تجزیه گراف [۲] ……………………………………………………………. ۱۴
شکل ۱-۷ یک شبکه حسگر واقعی برای مانیتور کردن محیط داخلی یک ساختمان[۴] ………………………………. ۱۵

شکل ۲-۱ یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 20
شکل ۲-۲ چهار حالت مختلف از مسئله کلاسیک رنگ آمیزی گراف و نتیجه پیاده سازی الگوریتم تصفیه برای هر یک از این مسائل[۴] ……………………………………………………………………………………………………………………………………. ۲۴
شکل ۲-۳ سیکل ۱ الگوریتم ABT بر روی مسئله ۴ وزیر[۴] ………………………………………………………………………… ۲۹
شکل ۲-۴ سیکل ۲ از الگوریتم ABT بر روی مسئله ۴وزیر[۴] ……………………………………………………………………… ۲۹
شکل ۲-۵ سیکل ۳ از الگوریتم ABT بر روی مسئله ۴ وزیر[۴] …………………………………………………………………….. ۳۰
شکل ۲-۶ سیکل ۴ و ۵ از الگوریتم ABT بر روی مسئله ۴وزیر[۴] ……………………………………………………………… ۳۰
شکل ۲-۷ سیکل ۶ از الگوریتم ABT بر روی مسئله ۴وزیر[۴] ……………………………………………………………………… ۳۱
شکل ۲-۸ سیکل ۷ و ۸ از الگوریتم ABT بر روی مسئله ۴وزیر[۴] ………………………………………………………….. ۳۱
شکل ۲-۹ سیکل ۹ از الگوریتم ABT بر روی مسئله ۴وزیر[۴] ……………………………………………………………………… ۳۱
شکل ۲-۱۰ سیکل ۱۰ از الگوریتم ABT بر روی مسئله ۴وزیر [۴] ……………………………………………………………… ۳۲
شکل ۲-۱۱ الگوریتم APO [22] ……………………………………………………………………………………………………………………. 35
شکل ۲-۱۲ مثالی از گراف ساختار [۴۴] …………………………………………………………………………………………………………. ۳۹
شکل ۲-۱۳ ساختن یک گراف برای یک مسأله با سه متغیر …………………………………………………………………………… ۴۰
شکل ۳-۱ جهت حرکات ممکن یک مهره وزیر در یک صفحه شطرنج ……………………………………………………………. ۴۶
شکل ۳-۲ یک جواب برای مسأله ۸-وزیر …………………………………………………………………………………………………………. ۴۷
شکل ۳-۳ مثالی از رنگ آمیزی گراف(یک رنگ آمیزی از گراف معروف پترسن) …………………………………………… ۴۸
شکل ۳-۴ مثالی از مساله CSP [4] …………………………………………………………………………………………………………………. 52
شکل ۳-۵ مدل فرض شده از محیط شبکه مانند عاملها[۳] ……………………………………………………………………………. ۵۳
شکل ۳-۶ میانگین زمان اجرای الگوریتم MAEA-CSPs در حل مسأله n-وزیر [۳] ……………………………………. ۵۸
شکل ۳-۷ مقایسه الگوریتم MAEA-CSPs با ۴ الگوریتم دیگر با معیارهای SR، ME و AES [4] ……………. 59
شکل ۳-۸ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم ۲ ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها ………………………………………………………………………… ۶۳
شکل ۳-۹ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم ۲ ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………………………… 63
شکل ۳-۱۰ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .۳۲ ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. ۶۳
شکل ۳-۱۱ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم ۲٫۳ ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 64
شکل ۳-۱۲ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .۷۲ ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. ۶۴
شکل ۳-۱۳ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم ۲٫۷ ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 65
شکل ۴-۱ یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 72
شکل ۴-۲ مرحله ۱ تا ۴ از الگوریتم DACA ………………………………………………………………………………………………….. 80
شکل ۴-۳ مرحله ۵ از الگوریتم DACA ………………………………………………………………………………………………………….. 81
شکل ۴-۴ مرحله پایانی الگوریتم DACA ……………………………………………………………………………………………………….. 82
شکل ۴-۵ میانگین زمان اجرای الگوریتم DACA در اجرای مسأله n-وزیر با افزایش n از ۴ تا ۱۰^۴ در گامهای ۵۰ تایی ………………………………………………………………………………………………………………………………………………………………. ۸۲
فهرست جداول
عنوان صفحه
جدول ۳-۱ نتایج بدست آمده از آزمایش MAEA-CSPs بر روی مسائل ارضاء محدودیت باینری …………… ۵۹
جدول ۳-۲ مقادیر متفاوت از تعداد مورچه ها برای سایزها و تراکم­های متفاوت …………………………………………….۶۰
جدول۴-۱ مقایسه الگوریتم پیشنهادی ما با دو روش دیگر از لحاظ تعداد سیکلهای مورد نیاز برای حل ……… ۸۲
جدول۴-۲ مقایسه روش پیشنهادی ما با روش ERA از لحاظ میانگین زمان اجرا ……………………………………….. ۸۲
فصل اول
مقدمه
از سال ۱۹۷۴، مسائل ارضاء محدویت (CSP^[1]) در مسأله پردازش تصویر^[۲] پیشنهاد شد. پس از آن CSP به طور گسترده در بسیاری از حوزه های هوش مصنوعی و علوم کامپیوتر به عنوان یک روش حل مهم مورد استفاده قرار گرفته است. از مسأله چند وزیر^[۳] و رنگ آمیزی گراف^[۴] گرفته و دیگر مسائل کلاسیک گرفته تا زمانبندی^[۵] و تخصیص منابع^[۶] و دیگر مسائل کاربردی بزرگ می­توانند برای حل شدن به عنوان یک مسأله CSP فرموله شوند. بعد از سال ۱۹۹۰ با جایگزین شدن زبان برنامه نویسی عمومی به جای زبان برنامه نویسی منطقی مسأله ارضاء محدودیت کاربرد CSP برای حل مسائل بسیار بهبود یافت [۱]. یک CSP، با یک مجموعه از متغیرها، دامنه ای برای هر یک از آنها و محدودیتهایی در مقادیری که متغیرها ممکن است به صورت همزمان به خودشان بگیرند، تعریف می­شوند. نقش الگوریتمهای ارضاء محدودیت، نسبت دادن مقادیری به متغیرهاست به نحوی که با تمام محدودیتها سازگاری داشته باشد یا مشخص کند که هیچ انتسابی امکان پذیر نیست. امروزه تکنیکهای ارضاء محدودیت در حوزه های مختلفی از جمله بینایی ماشین، پردازش زبانهای طبیعی، اثبات قضایا، زمانبندی و… به کار می­روند [۴].
از طرف دیگر موقعیتهایی وجود دارد که در آن یک مسأله بایستی در یک مد توزیع شده حل شود به عنوان مثال در شرایطی که استفاده از یک کنترل کننده مرکزی ممکن نیست و یا اینکه می­خواهیم استفاده مناسبی از منابع توزیع شده و یا امکانات محاسباتی داشته باشیم. در چنین مواقعی عاملها^[۷] برای رسیدن به یک هدف مشترک تلاش می­ کنند. هر سیستم چند عامله یک سیستم محاسباتی است که در آن چندین عامل جهت رسیدن به یک هدف خاص با هم در تعامل هستند و با هم کار می­ کنند [۴].
مسأله ارضاء محدودیت توزیع شده (DCSP^[8]) در واقع حالت توزیع شده مسأله­ ارضاء محدودیت کلاسیک است که در آن متغیرها بین عاملهای مستقل توزیع شده ­اند. این محیط توزیع شده شامل تعدادی عامل هوشمند است که هر کدام، یک یا چند متغیر را مالک می­شوند و مقدار آن را کنترل می­ کنند. همه این عامل ها در تلاشند تا با حفظ استقلالشان به هدف مشترک دست یابند. هدف هنوز یافتن یک انتساب برای متغیرهاست که محدودیتها را هم در نظر داشته باشد اما هر عامل، برای مقدار متغیر مالکش با خودمختاری نسبی تصمیم می­گیرد. هر چند عاملها یک دید عمومی ندارند اما هر یک از آنها می ­تواند با همسایه اش در گراف محدودیت ارتباط برقرار کند. هر عامل سعی می­ کند نه تنها با ارضاء محدودیتهای محلی خود بلکه با برقرای ارتباط با سایر عاملها به منظور حل محدودیتهای خارجی به این هدف نزدیک و نزدیکتر شود. به طور کلی تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده است را می­توان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. در یک سیستم چند عاملی به هر عامل یک یا چند متغیر از میان متغیرهای توزیع شده منتسب می­ شود. وظیفه این عامل خودمختار کنترل و مدیریت مقدار این متغیر می­باشد [۴] و [۲۲]. این مسأله عمومی کاربردهای زیادی در زندگی واقعی دارد. مثلا در بسیاری از مسائل تخصیص منابع: در شبکه های حس گر بی سیم، کنترل علائم راهنمایی شهری، شبکه های حس گر توزیع شده، مسائل نجات یافتن از فاجعه و بسیاری از مسائل مربوط به زمان بندی مثلا برای قطارها و دانشگاه ها. هدف معمول در حل همه این مسائل یافتن مقادیر مناسب برای تخصیص دادن به متغیر های توزیع شده است. به عبارت دیگر هر مسأله ای که هدف آن یافتن مقدار مناسبی برای تخصیص به متغیرهای توزیع شده است می ­تواند به عنوان DCSP طرح ریزی شود.