۹۰۰۰

۱۰۰۰۰

DACA

۴۶٫۷

۶۱٫۴

۷۹٫۵

۹۱٫۴

۱۱۵٫۹

ERA

۲۸۴٫۵

۴۰۰٫۷

–

–

–

نتیجه گیری و برشمردن مزایا و معایب این روش
در این فصل ما ابتدا با توجه به گستردگی الگوریتمهای پیشنهادی برای مسائل DCSP، یک طبقه بندی کلی از الگوریتم های اصلی در این زمینه بر اساس دو ویژگی مهم این الگوریتم ها یعنی کامل بودن^[۱۴۸] و متمرکزسازی^[۱۴۹] انجام دادیم و گفتیم که دسته ای از این الگوریتمها روشهایی هستند که از ترکیبی از روش های توزیع شده و متمرکز استفاده می­ کنند. بر این اساس ما تکنیکی جدید به نام DACA که تلفیقی از روش های توزیع شده و متمرکز است برای حل دسته­ای خاص و پر کاربرد از مسائل DCSP ها یعنی مسائل ارضاء محدودیت توزیع شده ای که شامل محدودیت Alldiff هستند را پیشنهاد دادیم. ارائه الگوریتمی خاص منظوره که قطعا کارآیی بیشتری نسبت به الگوریتمهای همه منظوره دارد، تقسیم عاملها به دو گروه مختلف کاری و همچنین تشکیل اجتماعاتی بین عاملها بر مبنای یک ویژگی خاص، خصوصیاتی است که روش پیشنهادی ما را از دیگر روش های موجود متمایز کرده است. این دو ویژگی اخیر یعنی طبقه بندی کردن عاملها و تشکیل ساختارهای اجتماع، با دخیل کردن درجه ای از متمرکز سازی در روند حل مسأله موجب کاهش تعداد پیامهای ارسال و دریافتی که یکی از پارامترهای مهم در این فیلد است، شده است. به دلیل تشکیل همین ساختارهای اجتماع، یک تعویض مناسب توسط یک عامل رهبر نه تنها موجب افزایش امتیاز خودش می­ شود بلکه تأثیر بسزایی در امتیازات دیگر عاملها خواهد داشت و این خود منجر به یک جهش بزرگ به سمت راه حل مسأله و نهایتا حل سریعتر مسأله خواهد شد. تمامی این ویژگیهای بیان شده تا کنون موجب شده تا الگوریتم پیشنهادی ما یک زمان اجرای منطقی برای حل مسائل با مقیاس بزرگ را ارائه دهد. علاوه بر این، استفاده از توابع اکتشافی در روند حل مسأله ویژگی دیگری است که به افزایش کارآیی این الگوریتم کمک می­ کند.

ما به منظور ارزیابی و تست کارآیی این الگوریتم از محک کلاسیک n-وزیر استفاده کرده ایم. این الگوریتم با مسائل ۴-وزیرتا ۱۰^۴-وزیر تست شد و مشاهده کردیم که DACA قادر به یافتن یک راه حل برای تمامی حالتهای این طیف گسترده در یک مدت زمان منطقی است. نتایج آزمایشات نشان می­دهد که الگوریتم ما همیشه با یک راه حل قانونی و در یک مدت زمان اجرای منطقی برای مسائل با مقیاس بزرگ خاتمه می­یابد. همچنین نتایج به دست آمده حاکی از آن است که الگوریتم ما تقریبا یک پیچیدگی زمانی خطی را با افزایش مقیاس مسأله ارائه می­دهد. از آنجایی که عمده کار این الگوریتم به عهده رهبرهاست و تعداد رهبرها بسیار کمتر از تعداد کل عاملهاست این موجب کاهش میزان فضای حافظه مورد نیاز در حین اجرای الگوریتم می­ شود و این خود تأثیر بسزایی در حل مسائل با مقیاس بزرگ که میزان حافظه زیادی نیاز دارند خواهد داشت. در پایان مقایسه روش ما با سه الگوریتم ABT،Asynchronous Backtracking with Min-Conflict Heuristic Algorithm و همچنین یک روش پیشنهادی دیگر به نام ERA^[150] نشان می­دهد که روش ما بسیار بهتر از این سه روش عمل می­ کند.
اشکال اصلی الگوریتم پیشنهادی ما زمانی که برای حل یک مسأله واقعی و کاملا توزیع شده بکار می­رود فقدان امنیت است. همان طور که شرح داده شد در الگوریتم ما از یک CSCBOARD به منظور اطلاع عاملها از مقادیر انتخابی دیگران استفاده می­ شود. بنابراین روش ما نمی­تواند روش مناسبی برای محیطهایی که مسأله امنیت در آنها حائز اهمیت است، باشد. این امر می ­تواند موضوع بالقوه ای برای تحقیقات آینده باشد.
فصل پنجم
نتیجه گیری
مسأله ارضاء محدودیت توزیع شده سالهاست که در حوزه تحقیق سیستمهای چند عامله مورد توجه زیادی قرار گرفته است. و این مسأله به این دلیل است که بسیاری از مسائل اعم از مسائل کلاسیکی همانند مسأله n-وزیر و رنگ آمیزی گراف گرفته و تا مسائل کاربردی بزرگ دنیای واقعی همچون زمانبندی و برنامه ریزی و تخصیص منابع می­توانند برای حل شدن به عنوان یک مسأله DCSP فرموله شوند. به طور کلی تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده است را می­توان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. بنابراین ارائه یک شیوه جدید و یا اصلاح شیوه های فعلی تاثیر زیادی بر دامنه تحقیقاتی این فیلد می­ گذارد.
هم اکنون با یک دید روشن نسبت به مسائل ارضاء محدودیت می­توان گفت در این فیلد مسأله اصلی در واقع روش استفاده شده برای ارضاء محدودیتهاست. محدودیتها می ­تواند به صورت مستقیم، غیر مستقیم و یا با بهره گرفتن از روش های ترکیبی دستکاری و اداره شوند. بر این اساس و با توجه به گستردگی الگوریتمهای پیشنهادی برای مسائل DCSP، ما یک طبقه بندی کلی از الگوریتم های اصلی در این زمینه بر اساس دو ویژگی مهم این الگوریتم ها یعنی کامل بودن و متمرکزسازی انجام دادیم و گفتیم که دسته ای از این الگوریتمها روشهایی هستند که از ترکیبی از روش های توزیع شده و متمرکز استفاده می­ کنند. سپس ما تکنیکی جدید به نام DACA که تلفیقی از روش های توزیع شده و متمرکز است برای حل دسته ای خاص و پر کاربرد از مسائل DCSP ها یعنی مسائل ارضاء محدودیت توزیع شده ای که شامل محدودیت Alldiff هستند را پیشنهاد دادیم. روش پیشنهادی ما این محدودیتها را در یک سیستم که ترکیبی از سیستمهای توزیع شده و متمرکز است اداره و کنترل می­ کند. شناسایی محدودیتهای خاص و پرکاربرد و ارائه تکنیکهای خاص منظوره که قطعا کارآیی بیشتری نسبت به الگوریتمهای همه منظوره دارند موضوعی است که شاید بهتر باشد از این پس در این فیلد بیشتر مورد توجه قرار گیرد.
موارد زیر سه مسأله مهمی هستند که باید علاوه بر حل کننده های DCSP با هر حل کننده مسأله توزیع شده دیگری هم تامین شوند.
میزان بالای آسنکرونی
میزان بالای امنیت
تعداد کم پیام ها(هزینه ارتباطی پایین)
تامین میزان بالای آسنکرونی نکته کلیدی برای هر الگوریتم توزیع شده به منظور سود بردن از ظرفیت محاسباتی از یک سیستم توزیع شده­است. موثرترین و مطلوب ترین الگوریتم برای حل یک مسأله توزیع شده الگوریتمی است که در آن همه گره های سیستم توزیع شده به طور همزمان در تلاشند تا راه حلی را پیدا کنند. الگوریتمهایی که بیشتر مواقع در آن یک و یا تعداد کمی از عامل ها مشغول کارند و بقیه در انتظار دریافت نتایج عامل کارگر هستند برای حل مسأله توزیع شده مناسب نیستند چرا که مقدار قابل توجهی از منابع محاسباتی را از دست می­ دهند. به عبارت دیگر زمانی که باید برای یافتن راه حل صرف شود برای منتظر ماندن برای دیگر عاملها به هدر می­رود. برای کاهش زمان و انرژی برای حل کردن باید بر الگوریتم های متقارن و آسنکرون تمرکز کنیم.
معیار مهم دیگر یک محیط توزیع شده، امنیت است. این موضوع در DCSP ها هم مهم است. امنیت جنبه های متعددی در مسائل ارضاء محدودیت توزیع شده دارد. یکی از مهم ترین چیزهایی که باید از دیگر عاملها مصون نگه داشته شود مقادیر انتخابی توسط هر عامل در هر گام از الگوریتم است. در حقیقت الگوریتمی که برای DCSP پیشهاد شد در صورتی امن است که عاملی نتواند هیچ اطلاعات اضافی درباره مقدار تخصیص داده شده به متغیر هایی که به دیگر عاملها متعلق هستند، بدست آورد. یک راه برای دستیابی به امنیت استفاده از رمزنویسی در مسیر پیام است. برای مثال یوکو و سایرین الگوریتم ایمنی فراهم کردند که از حفاظت کلید عمومی^[۱۵۱] استفاده می­ کند تا مقادیر انتخابی توسط هر عامل را از دیگر عامل ها ایمن نگه دارد [۴۸]. استفاده از رمز نویسی چالش های بخصوصی دارد. به عنوان مثال یک سربار اضافی برای اجرای الگوریتمهای رمزنگاری در هر گره تحمیل می­ کند و بیشتر مواقع این الگوریتمها کلیدهای طولانی نیاز دارند. از سوی دیگر تقریبا در همه الگوریتم CDSP موجود که از مسائل رمز نویسی استفاده نمی­کنند عامل ها نمی ­توانند مقادیر انتخابی را از همسایگانشان در امان نگاه دارند چرا که تشخیص یک تناقض نیازمند دانستن هر دو طرف مقادیر محدودیت است. در طول پروسه ی این تحقیق یک عامل می ­تواند اطلاعاتی در مورد دامنه مقادیر ی که می­توانند به متغیر های سایر عامل ها تخصیص داده شوند بدست آورند و یا مقدار نهایی را که به متغیرهایشان تخصیص داده شده را بیابند. اگرچه حتی بدون استفاده از رمز نگاری امنیت کامل امری دشوار در این موضوع نیست، الگوریتمها سعی در جلوگیری از افشای اطلاعات بیشتر دارند.
دیگر معیار مهم حل مسأله توزیع شده که ما در این بخش به آن می­پردازیم تعداد پیام هایی است که مبادله شده ­اند. این پارامتر در هر سیستم توزیع شده­ای مهم است چرا که یکی از هزینه برترین بخشهای سیستم های توزیع شده ارتباط است. این پارامتر خیلی مهم است (به ویژه در زمینه DCSP) که تعداد پیام ها همیشه برای ارزیابی حل کننده های DCSP بکار می­رود. ایجاد یک مسأله CSP کاملا توزیع شده نیازمند اختصاص هر گره از گراف مسأله به یک میزبان در محیط توزیع شده دارد.