استفاده از روش مبتنی بر تعداد تناقضات برای حل مسائل ارضاء محدودیت توزیعشده

مسائل ارضاء محدودیت توزیع شده (DCSPs) گروه وسیعی از مسائل مطرح در دنیای واقعی را پوشش می دهند . این مسئله،DCSPرا به زمینة مهمی از تحقیقات تبدیل میکند. با در نظر گرفتن کلیة تلاشهائی که اخیراً برای حل این دسته از مسائل انجام شده است میتوان الگوریتمرا Asynchronous Partial Overlay (APO) به عنوان یکی از موفقترین این تلاشها برشمرد. این الگوریتم برای حل یک مسئلة ارضاء محدودیت ابتدا آن را به بخشهای کوچکتری تقسیم میکند و سپس با انتخاب عاملهائی به عنوان عامل واسط سعی در حل متمرکز زیر مسئلههای تولید شده دارد. این مقاله روش جدید و مؤثری را برای انتخاب این عاملهای واسط معرفی میکند. به علاوه دو نسخة گسترش یافته از الگوریتم،APO به نام های MaxCAPO و MaxCIAPOکه از این استراتژی استفاده میکنند ارائه خواهند شد . ایدة اصلی مطر ح در این استراتژی این است که تعداد تناقضات (محدودیتهای نقض شده) مرتبط با عاملهای واسط تأثیر مستقیم بر کارآئی آن دارد. نتایج تجربی نشان میدهد که انتخاب عاملهای واسط از میان عاملهائی که بیشترین تعداد تناقضات را دارند نه تنها منجر به کاهش قابل توجهی در پیچیدگی الگوریتمAPO میشود، بلکه میتواند منجر به کاهش پیچیدگی الگوریتم های مشتق شده از،APO نظیر IAPOنیز بشود.

Keywords:

مسائل ارضاء محدودیت توزیعشده , خودمختاری , سیستمهای چندعاملی , عملیات واسطهگری , هوش مصنوعی