توابع اکتشافی:
توابع اکتشافی عبارتند از معیارها، روشها یا اصولی برای تصمیمگیری بین چندین خطمشی و انتخاب اثربخشترین برای دستیابی به اهداف موردنظر. توابع اکتشافی نتیجه برقراری اعتدال بین دو نیاز هستند: نیاز به ساخت معیارهای ساده و در همان زمان توانایی تمایز درست بین انتخابهای خوب و بد.
خاصیت توابع اکتشافی خوب این است که ابزار سادهای برای تشخیص خط مشیهای بهتر ارائه دهند و در حالی که به صورت شرطی لازم، تشخیص خطمشیهای اثربخش را تضمین نمیکنند اما اغلب به صورت شرط کافی این تضمین را فراهم آورند. بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالتهای ممکن برای تعیین یک جواب دقیق میباشند. زمان لازم برای یافتن یک جواب دقیق اغلب بیشتر از یک طول عمر است. توابع اکتشافی با بهره گرفتن از روشهایی که نیازمند ارزیابیهای کمتر هستند و جوابهایی در محدودیتهای زمانی قابل قبول ارائه مینمایند، دارای نقشی اثربخش در حل چنین مسائلی خواهند بود.
الگوریتمهای جستجو اغلب برای افزایش کارایی به دانش مرتبط با جهان مسأله نیاز دارند، اما مسائل CSP میتوانند بدون دانش وابسته به جهان مسأله به صورت کارایی حل شوند. روش های عمومی قادرند با پاسخ به سوالات زیر توابع اکتشافی عمومی مناسبی را جهت افزایش کارایی الگوریتمهای حل مسائل CSP پیشنهاد دهند:
متغیر بعدی که قرار است مقدار بگیرد کدام است؟
مقدار گیری بر اساس چه ترتیبی انجام شود؟
مقداردهی متغیر جاری چه پیامدهایی برای سایر متغیرهای انتساب نیافته دارد؟
چگونه میتوان از تکرار مسیرهای منجر به شکست جلوگیری کرد؟
بر این اساس توابع اکتشافی مختلفی تعریف و طراحی شده اند که ما در روشمان از تابع اکتشافی کمترین برخورد استفاده کردهایم. این تابع اکتشافی که با نام تابع اکتشافی “مقدار با کمترین محدودیت”[۱۳۰] نیز شناخته می شود تعریف آن به صورت زیر است:
پس از انتخاب متغیر، مقدار خاصی برای انتساب باید انتخاب شود. تابع اکتشافی مقدار با حداقل محدودیت، مقداری را برای یک متغیر انتخاب می کند که در گراف محدودیت باعث ایجاد کمترین محدودیت در متغیرهای مجاور گردد.
تقسیم بندی الگوریتم های مطرح شده برای مسائل DCSP
همانطور که پیشتر گفته شد، تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده است را میتوان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. مثلا در بسیاری از مسائل تخصیص منابع: در شبکه های حس گر بی سیم، کنترل علائم راهنمایی شهری، شبکه های حس گر توزیع شده، مسائل نجات یافتن از فاجعه و بسیاری از مسائل مربوط به زمان بندی مثلا برای قطارها و دانشگاه ها. هدف معمول در حل همه این مسائل یافتن مقادیر مناسب برای تخصیص دادن به متغیر های توزیع شده است. به عبارت دیگر هر مسأله ای که هدف آن یافتن مقدار مناسبی برای تخصیص به متغیرهای توزیع شده است می تواند به عنوان DCSP طرح ریزی شود. با توجه به وسعت این دسته از مسائل، الگوریتمهای متنوعی برای حل آنها از سال ۱۹۹۱ تاکنون ارائه شده است. برخی از این الگوریتمها مانند الگوریتم عقب گرد نامتقارن ABT [14] ، و الگوریتم AWC [15] ، کاملا توزیع شده هستند در حالیکه برخی دیگر از ترکیب روش های توزیع شده و متمرکز استفاده می کنند. یکی از موفق ترین الگوریتمهای مطرح در دسته دوم الگوریتم APO است [۱۶]که توسط میلر و لزر ارائه شده است. با یک دید گسترده تر ما دسته بندی زیر را برای الگوریتمهای مسائل ارضاء محدودیت توزیع شده ارائه دادیم:
شکل ۴-۱ یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP
به طور کلی الگوریتم هایی که برای حل DCSP وجود دارند می تواند به دو گروه تقسیم شوند: کامل [۱۳۱]و ناقص[۱۳۲]. الگوریتم های کامل، الگوریتم هایی هستند که یافتن راه حل را، البته اگر وجود داشته باشد، تضمین می کنند و یا وقتی که مسأله راه حلی ندارد از کار متوقف میشوند. الگوریتم های کامل خود به دو گروه تقسیم میشوند: روش های کاملا توزیع شده و دوم ترکیب روش های توزیع شده و متمرکز. الگوریتم های کاملا توزیع شده، الگوریتم هایی هستند که یک گره مرکزی ندارند. و هر گره نیز اطلاعات محدودی درباره محدودیتهایش دارد. در این گروه، عامل ها با هم هماهنگ میشوند تا مسأله را با بهره گرفتن از دانش محدودی که دربارهاش دارند حل کنند. یوکو[۱۳۳] و سایرین همکاری های مهمی در الگوریتم های کاملا توزیع شده داشته اند. آنها الگوریتم عقبگرد نامتقارن را ایجاد کردند که کامل بودن[۱۳۴] را تضمین می کند[۳۶-۳۲]. بعدها این الگوریتم را به الگوریتم کارامدتری با نام الزام ضعیف نامتقارن، با معرفی ترتیب پویا در میان عاملها، گسترش دادند.
گروه دیگر الگوریتم های کامل، الگوریتم هایی هستند که در واقع از ترکیب روش های توزیع شده و متمرکز استفاده می کنند. در این دسته الگوریتمها برخی عامل ها در تلاشند تا اطلاعاتی را از عامل های دیگر جمع آوری کنند تا مسأله را از بنیاد حل کنند و سپس اجازه دهند عامل های شرکت کننده مقادیری را که برای متغیرهایشان انتخاب شده است را بدانند. APO مثال خوبی برای این گروه از الگوریتم ها است. استفاده از درجه ای از متمرکز سازی به الگوریتم ها اجازه میدهد با پیامهای کمتری نسبت به الگوریتم های کاملا نامتمرکز مسأله را حل کنند. از سوی دیگر این متمرکز سازی آسنکرونی حل مسأله را کاهش میدهد. به عبارت دیگر همانطور که برخی از عامل ها اطلاعاتشان را به یال مرکزی میفرستند تا پردازش شود، بار محاسباتی به طور نامتقارنی بین عامل ها تقسیم می شود که منجر به کاهش دادن همزمانی پروسه حل مسأله می شود[۳۱].
در چارت بالا یک طبقه بندی کلی از الگوریتم های اصلی در این زمینه را نشان دادهایم که در واقع میتوان گفت این چارت تقسیم بندی خوبی از الگوریتم هایDCSP بر اساس دو ویژگی مهم این الگوریتم ها یعنی کامل بودن[۱۳۵] و متمرکزسازی[۱۳۶] انجام میدهد.
توصیف روش جدید ارائه شده و جزئیات پیاده سازی آن
در این بخش ما یک روش جدید به نام DACA[137] ارائه خواهیم داد برای حل آن دسته از مسائلی که محدودیتهای Alldiff دارند. در این فیلد مسأله اصلی در واقع روش استفاده شده برای ارضاء محدودیتهاست. محدودیتها می تواند به صورت مستقیم، غیر مستقیم و یا با بهره گرفتن از روش های ترکیبی دستکاری و اداره شوند. روش پیشنهادی ما این محدودیتها را در یک سیستم که ترکیبی از سیستمهای توزیع شده و متمرکز است اداره و کنترل می کند. برای تشکیل این ساختار ترکیبی ابتدا سیستم چند-عامله[۱۳۸] ای تعریف میکنیم که در آن هر عامل یکی از متغیر های مسأله را مالک می شود. کار با انتخاب یک مقدار تصادفی توسط هر عامل برای متغیر مالکش شروع می شود. از آنجایی که این الگوریتم برای آن دسته از مسائلی طراحی شده که قطعا یکی از محدودیتهای تعریف شده اش محدودیت Alldiff است، پس از همان ابتدا عاملها با انتخاب مقادیر غیر تکراری برای متغیر مالکشان ارضاء[۱۳۹] این محدودیت را تضمین می کنند. در ادامه کار نیز اگر نیاز به تغییر مقدار باشد عاملها با تعویض مقادیرشان با یکدیگر، به جای انتخاب یک مقدار جدید از دامنه، از نقض شدن این محدودیت جلوگیری می کنند. در مرحله بعد اجتماعات[۱۴۰] مختلفی از عاملهایی که مقدار متغیرشان با یکدیگر در تناقض هستند تشکیل می شود. رهبر[۱۴۱] هر اجتماع عاملی است که مقدارش با همه اعضای آن اجتماع در تناقض است. علاوه بر تشکیل این اجتماعات، تمامی عاملها در این مرحله در دو دسته عاملهای آزاد[۱۴۲] و عاملهای درگیر[۱۴۳] طبقه بندی میشوند. عاملهای آزاد آن دسته از عاملهایی هستند که مقدار فعلی متغیرشان با هیچ یک از مقادیرانتخابی عاملهای دیگر در تناقض نیست. مابقی عاملها با عنوان عاملهای درگیر شناخته میشوند. تقسیم بندی عاملها در دو گروه عاملهای آزاد و عاملهای درگیر و همچنین تشکیل ساختارهای اجتماع با دخیل کردن درجه ای از متمرکز سازی موجب کاهش تعداد پیامهای ارسال و دریافتی می شود. در ابتدا کار به عهده عاملهای درگیر گذاشته می شود. امتیاز هر عامل برابر است با منفی تعداد محدودیتهای نقض شده توسط مقدار متغیر آن عامل. هر عامل رهبر با بهبود امتیاز خود و اعضای اجتماعش به یافتن یک راه حل برای مسأله کمک می کند. به دلیل تشکیل همین ساختارهای اجتماع، یک تعویض مناسب توسط یک عامل رهبر نه تنها موجب افزایش امتیاز خودش می شود بلکه تأثیر بسزایی در امتیازات دیگر عاملها خواهدداشت و این خود منجر به یک جهش بزرگ به سمت راه حل مسأله و نهایتا حل سریعتر مسأله خواهد شد. تمامی این ویژگیهای بیان شده تا کنون موجب شده تا الگوریتم پیشنهادی ما یک زمان اجرای منطقی برای حل مسائل با مقیاس بزرگ را ارائه دهد. زمانی که امتیاز تمامی عاملها به صفر برسد یک راه حل یافته شده است.
به منظور ارزیابی کارآیی DACA از محک n-وزیر استفاده کردیم. نتایج آزمایشات نشان میدهد که الگوریتم ما همیشه با یک راه حل قانونی و در یک مدت زمان اجرای منطقی برای مسائل با مقیاس بزرگ خاتمه مییابد. همچنین نتایج به دست آمده حاکی از آن است که الگوریتم ما تقریبا یک پیچیدگی زمانی خطی را با افزایش مقایس مسأله ارائه میدهد. در پایان مقایسه روش ما با سه الگوریتم ABT ، Asynchronous Backtracking with Min-Conflict Heuristic Algorithm و همچنین یک روش پیشنهادی دیگر به نام ERA[144] نشان میدهد که روش ما بسیار بهتر از این سه روش عمل می کند. در ادامه مراحل مختلف الگوریتم را با جزئیات بیشتری شرح میدهیم.
مرحله ۱: یک سیستم چند عامله تعریف می شود که در آن هر عامل یکی از متغیرهای مسأله را مالک می شود. عاملها کارشان را با انتساب یک مقدار تصادفی از دامنه به متغیرشان شروع می کنند. مقدار انتخابی توسط هر عامل در بین همسایگانش منحصر به فرد است، یعنی با مقادیر انتخابی توسط دیگر عاملهای همسایه اش متفاوت است.
مرحله ۲: همه عاملها به طور همزمان امتیازشان را بر اساس فرمول (۱) محاسبه می کنند، اگر C مجموعه ای از محدودیتها به صورت {C1, . . . , Cm} باشد، عامل α یک عنصر در فضای جستجو است که امتیازش به صورت تابع امتیاز زیر محاسبه می شود:
∀ α ∈ S, Score (α) = -∑ β (α, Ci)
۱ α violates Ci (۱)
Where β (α, Ci) =
۰ otherwise
که در واقع β در این فرمول یک شمارنده است که به ازای هر محدودیت نقض شده توسط مقدار اتخاذی آن عامل یکی به آن اضافه می شود. و در نهایت امتیاز هر عامل برابر می شود با منفی تعداد محدودیتهای نقض شده.
مرحله ۳: در این مرحله عاملها بر اساس امتیاز فعلیاشان در دو گروه عاملهای آزاد و عاملهای درگیرکلاسیفای میشوند. عاملهایی با امتیاز فعلی صفر، در گروه عاملهای آزاد و مابقی عاملها به عنوان عاملهای درگیر شناخته میشوند.
مرحله ۴: همزمان با محاسبه امتیاز هر عامل درگیر لیستی از عاملهایی را که مقدار متغیرشان با مقدار متغیر خودش ناسازگار است را ذخیره می کند. سپس هر عامل اجتماعی از این عاملها به نام CSCommunity[145] با رهبری خودش تشکیل میدهد.
Algorithm 1: CSCommunity Organizing
Input: Assign Values to agents and Number of Variables;
Output: All of communities, leaders, free agents and score of all agents
-
- for i=1 to Number Of Variables do
۱٫۱٫ for j= i to Number Of Variables do
۱٫۱٫۱ if assigned value to variable
i violated assigned value of variable j
۱٫۱٫۱٫۱٫ Decrease scores of agents i and j
۱٫۱٫۱٫۲٫ Append i and j to Constraint graph
۱٫۱٫۱٫۳٫ Append j to CSComunity of leader i
۱٫۲٫ if assigned value to variable i not violate any
[شنبه 1400-08-01] [ 11:40:00 ب.ظ ]
|