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