توابع اکتشافی:
توابع اکتشافی عبارتند از معیارها، روشها یا اصولی برای تصمیم‌گیری بین چندین خط‌مشی و انتخاب اثربخش‌ترین برای دستیابی به اهداف موردنظر. توابع اکتشافی نتیجه برقراری اعتدال بین دو نیاز هستند: نیاز به ساخت معیار‌های ساده و در همان زمان توانایی تمایز درست بین انتخاب‌های خوب و بد.
پایان نامه - مقاله - پروژه
خاصیت توابع اکتشافی خوب این است که ابزار ساده‌ای برای تشخیص خط مشی‌های بهتر ارائه دهند و در حالی که به صورت شرطی لازم، تشخیص خط‌مشی‌های اثربخش را تضمین نمی‌کنند اما اغلب به صورت شرط کافی این تضمین را فراهم ‌آورند. بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت‌های ممکن برای تعیین یک جواب دقیق می‌باشند. زمان لازم برای یافتن یک جواب دقیق اغلب بیشتر از یک طول عمر است. توابع اکتشافی با بهره گرفتن از روش‌هایی که نیازمند ارزیابی‌های کمتر هستند و جوابهایی در محدودیت‌های زمانی قابل قبول ارائه می‌نمایند، دارای نقشی اثربخش در حل چنین مسائلی خواهند بود.
الگوریتمهای جستجو اغلب برای افزایش کارایی به دانش مرتبط با جهان مسأله نیاز دارند، اما مسائل 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

 

    1. 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

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...