حالت دوم: اینکه مقادیر دریافتی از همسایه های با اولویت بالاتر یک عامل، با مقدار فعلی آن عامل سازگار نیست اما آن عامل می تواند مقدار دیگری را از دامنه اش انتخاب کند که با دیدگاه[۵۱] فعلیاش سازگار باشد. در این صورت آن مقدار جدید را انتخاب می کند و این مقدار را به همراه کل دیدگاهش یا به عبارتی کل دانشی را که تا الان کسب کرده به همسایگان با اولویت پایینترش اطلاع میدهد.
حالت سوم: اینکه مقادیر دریافتی از همسایه های با اولویت بالاتر یک عامل، با مقدار فعلی آن عامل سازگار نیست و آن عامل هم نمیتواند مقدار دیگری را از دامنهاش انتخاب کند که با دیدگاه فعلیاش سازگار باشد. در این صورت عامل جاری مقدار فعلیاش را حفظ می کند و بازمیگردد به عامل قبلی با پیغامی مبنی بر اینکه امکان تغییر مقدار انتساب برایش وجود ندارد که این کار با ارسال یک پیام گزارهء نادرست انجام می شود. عامل قبلی در واقع عاملی با پایینترین اولویت در لیست دیدگاه عامل جاری است. حال عامل جاری فرض می کند که آن عامل همسایه که پیغام گزارهءهای نادرست را دریافت کرده مقدارش را تغییر خواهد داد پس مقدار آن عامل را از دیدگاهش حذف می کند و تلاش برای یافتن یک مقدار جدید توسط عامل همسایه از سر گرفته می شود و این روند تا رسیدن به یک راه حل ادامه پیدا می کند.
( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
در ادامه مثالی ساده از پیاده سازی این الگوریتم را بر روی مسأله کلاسیک ۴وزیر را داریم:
در سیکل ۱ هر عامل یک مقدار میگیرد و مقدارش را به عاملهای با اولویت پایینتر اعلام می کند.
شکل ۲-۳ سیکل ۱ الگوریتم ABT بر روی مسأله ۴ وزیر. تمامی عاملها فعالند[۴] .
شکل ۲-۴ سیکل ۲ از الگوریتم ABT بر روی مسأله ۴وزیر. عاملهای A2 ، A3 و A4 فعالند. گزارهء نادرست در این مرحله عبارت است از [۴]:
A2 =۱ → A3≠۱ A1=1 ʌ .
در سیکل ۲ هر عامل سعی می کند مقداری را بیابد که با مقدار دیدگاهش سازگار باشد. عاملهای A2 و A3 موفق میشوند مقدار سازگار با دیدگاهشان را بیابند اما A4 قادر به پیدا کردن یک مقدار مناسب نیست پس یک پیغام گزارهء نادرست به صورت: A2 =۱ → A3≠۱ ʌ A1=1 به عامل A3 ارسال می کند. البته این در حالی است که دیدگاه عامل A4 هنوز به صورت: {A1=1, A2=1, A3=1} است و هنوز به روز رسانی های انجام شده بر روی عاملهای با اولویت بالاتر به عاملهای با اولویت پایینتر ارسال نشده است. پس از ارسال این پیغام A4 مقدار عامل A3 را با فرض اینکه A3 مقدارش را تغییر خواهد داد از داخل دیدگاهش حذف خواهد کرد و سپس یک تغییر انتساب مناسب با دیدگاه فعلیاش انجام میدهد.
شکل ۲-۵ سیکل ۳ از الگوریتم ABT بر روی مسأله ۴ وزیر. تنها عامل A3 فعال است. گزارهء نادرست در این مرحله عبارت است از[۴]: A1=1→ A2≠ ۳
شکل ۲-۶ سیکل ۴ و ۵ از الگوریتم ABT بر روی مسأله ۴وزیر. A2 و A3 و A4 فعالند. گزارهء نادرست در این مرحله عبارت است از[۴]:
A2 =۴ → A3≠۴ A1=1 ʌ .
شکل ۲-۷ سیکل ۶ از الگوریتم ABT بر روی مسأله ۴وزیر. تنها A4 فعال است. گزارهء نادرست در این مرحله عبارت است از[۴]: A2 =۴ → A3≠۲ A1=1 ʌ .
شکل ۲-۸ سیکل ۷ و ۸ از الگوریتم ABT بر روی مسأله ۴وزیر. A3 در سیکل اول فعال است و A2 در سیکل ۲٫ گزارهء نادرست در این مرحله عبارت است از[۴]:
A2 =۴ → A1≠۴ A1=1 ʌ .
شکل ۲-۹ سیکل ۹ از الگوریتم ABT بر روی مسأله ۴وزیر. تنها عامل A1 فعال است [۴].
شکل ۲-۱۰ سیکل ۱۰ از الگوریتم ABT بر روی مسأله ۴وزیر . تنها عامل A3 فعال است [۴].
این الگوریتم در واقع چهارچوب اصلی روش های مدرن برای مسائل ارضاء محدودیت توزیع شده را تشکیل میدهد [۴].
اگر چه روش بازگشت به عقب برای مسائل کوچک خوب عمل می کند اما پیچیدگی محاسباتی برای مسائل کمی بزرگتر، نمایی باقی میماند. مطالعات بسیاری جهت بررسی بهبود این روش صورت گرفته که تکنیکهای سازگاری [۲۴] و وابستگی [۲۵] از آن جملهاند. با این حال هنوز قادر به حل CSPهای با مقیاس بزرگ در یک زمان اجرای منطقی نبودهاند.
الگوریتم الزام ضعیف نامتقارن
الگوریتم AWC یکی از اولین الگوریتمها برای حل مسائل DCSP است که توسط یوکو[۵۲] در سال ۱۹۹۵ پیشنهاد شد[۵۵]. این الگوریتم بسیاری از خصوصیات ABT را به ارث میبرد اما از یک روش ابتکاری جدید به نام کمترین تناقض[۵۳] سود میبرد. با بهره گرفتن از این روش احتمال اتخاذ تصمیمات بد و انتخاب راه حل های نامناسب کاهش مییابد. کارآیی این دو الگوریتم با بهره گرفتن از انواع روش های اکتشافی ارائه شده به سرعت بهبود یافته است.
الگوریتم AWC یکی از اولین الگوریتمهای استفاده شده برای حل مسائل DCSP است. این الگوریتم به هر عامل یک مقدار اولویت اختصاص میدهد که به صورت دینامیک تغییر می کند. همچنین، AWC از تابع اکتشافی الزام ضعیف[۵۴] برای نسبت دادن این مقادیر اولویت استفاده می کند. سپس هر عامل یک مقدار برای متغیرش انتخاب می کند و یک پیغام “درست؟[۵۵]” برای همسایگانش ارسال می کند. این پیغام شامل مقدار متغیر و اولویتش است. وقتی یک عامل یک پیغام “درست؟” دریافت می کند، دیدگاهش را بروزرسانی می کند و لیست گزارهءهای نادرستش را برای گزارهءهای نادرست نقض شده چک می کند. هر گزارهء نادرست از یک مجموعه از جفت گزارهءهای نادرستی تشکیل شده است که ترکیبی از عاملها و مقادیری که به یک شرایط ناسازگار منجر شده است را توصیف می کند. در آغاز، تنها گزارهءهای نادرست در لیست گزارهءهای نادرست یک عامل، محدودیت در آن متغیر است. زمان چک کردن لیست گزارهءهای نادرست، عاملها تنها نقضهای گزارهءهای نادرست اولویت بالاتر را چک می کنند.
الگوریتمهایی که از ترکیب روش های متمرکز و توزیع شده استفاده می کنند
همانطور که پیشتر گفته شد برخی از این الگوریتمها مانند الگوریتم عقب گرد نامتقارن، و الگوریتم الزام ضعیف نامتقارن، کاملا توزیع شده هستند در حالیکه برخی دیگر از ترکیب روش های توزیع شده و متمرکز استفاده می کنند. یکی از موفق ترین الگوریتمهای مطرح در دسته دوم الگوریتم APO است که روند کار این الگوریتم به شرح زیر است.
الگوریتم APO
ایده اصلی الگوریتم APO، انتخاب عامل های خاص به عنوان عامل واسط برای حل متمرکز زیر مسأله های محلی است. این عامل های واسط سعی می کنند با راه اندازی یک جلسه واسطه گری اطلاعات ضروری و مورد نیاز خود را نسبت به زیر مسأله جمع آوری کنند. همانطور که در شکل نشان داده شده است، الگوریتم با ارسال پیغام “آغاز[۵۶]” توسط هر عامل به عاملهای همسایه اش آغاز می شود. این پیغام شامل اطلاعات اولیه در مورد فرستنده است. اطلاعاتی نظیر اسم، اولویت، مقدار و … . با دریافت هر پیغام “آغاز” عامل گیرنده، اطلاعات دریافتی را داخل دیدگاه خود نگه میدارد. دیدگاه عامل همانطور که پیشتر نیز گفته شد، لیستی است که شامل اطلاعات اولیه راجع به عاملهای مرتبط با هر عامل است و در واقع نشان دهنده دید عامل از محیط پیرامون خود است. سپس هر عامل با جستجو در دیدگاه عامل خود سعی می کند در صورت وجود محدودیت نقض شده در میان عوامل موجود در آن را بیابد. اگر محدودیت یا محدودیتهای نقض شده ای یافت شود، این عامل بررسی می کند که آیا عامل با اولویت تری وجود دارد که آمادگی خود را برای جلسه واسطه گری اعلام کرده باشد، اگر چنین عاملی وجود داشته باشد، عامل مذکور خود، نقش عامل واسط را خواهد پذیرفت. اولویت عاملها در APO بر اساس تعداد همسایگان آنها تعیین می شود. اگر دو یا چند عامل تعداد همسایگان مشابهی داشته باشند، این اولویت بر اساس ترتیب الفبائی نام متغیرهای آنها تعیین خواهد شد. مسلما در نظرگرفتن اولویت برای عاملها مزایای زیادی دارد. تضمین انتخاب عاملی که حداکثر دانش را نسبت به زیرمسأله دارد به عنوان عامل واسط (عاملی که حداکثر تعداد همسایگان را دارد، حداکثر دانش نسبت به زیرمسأله را هم خواهد داشت) و عاملی که به آن اجازه اتخاذ تصمیمات اصلی داده می شود یکی از مهمترین مزایای در نظرگرفتن اولویت برای عاملهاست. بعد از انتخاب عامل واسط، این عامل در ابتدا سعی می کند به صورت محلی تناقضات موجود را با تغییر مقدار متغیر خود حل کند اما اگر انجام این کار مقدور نباشد، یعنی هیچ یک از مقادیر موجود در دامنه عامل واسط نتواند تناقضات موجود را حل کند، عامل واسط با ارسال پیغام “ارزیابی؟[۵۷]” برای عاملهایی که اسامی آنها را در لیست مطلوب[۵۸] خود ذخیره کرده است یک جلسه واسطه گری را آغاز می کند. لیست مطلوب لیستی است که توسط هر عامل نگهداری می شود و شامل تمامی اطلاعات عاملهایی است که به طریقی به صاحب این لیست متصل هستند. این اتصال ممکن است به صورت مستقیم توسط یک لینک برقرار شده باشد و یا به صورت غیرمستقیم توسط تعدادی لینک پی در پی انجام شده باشد. در واقع دیدگاه عامل و لیست مطلوب دو ساختار داده اصلی هستند که توسط هر عامل تعریف میشوند. تفاوت اصلی بین این دو لیست این است که دیدگاه عامل تنها اطلاعات مربوط به عاملهایی را نگه میدارد که مستقیما به صاحب لیست متصلند. اما لیست مطلوب حاوی اطلاعات مربوط به تمامی عاملهایی است که مستقیما و یا غیر مستقیم به صاحب آن متصل شده اند. اگر عامل گیرنده پیغام “ارزیابی؟” در حال شرکت در جلسه دیگری باشد و یا منتظر دریافت پیغامی مشابه از عامل با اولویت بالاتر باشد، با پیغام “انتظار[۵۹]” پاسخ خواهد داد؛ در غیر این صورت با ارسال پیغام “ارزیابی؟” اطلاعات کاملتری از خود را در اختیار عامل واسط قرار خواهد داد. هنگامیکه عامل واسط تمامی پاسخها را دریافت می کند، اقدام به انجام یک جستجوی شاخه و قید [۲۳] در میان عاملهایی که با پیغام “ارزیابی؟” پاسخ داده اند می کند. اگر عامل واسط با انجام این جستجو موفق به یافتن راه حل شود، با ارسال پیغام “موافقم[۶۰]” به سایر عاملهای شرکت کننده در جلسه آنها را از مقادیر جدید پیشنهادی برای متغیرهایشان آگاه می کند. همچنین با ارسال پیغام “درست؟” برای عاملهایی که در جلسه واسطه گری شرکت نکرده اند به آنها در به روز رسانی دیدگاه عاملشان کمک می کند. گاهی راه حلهای یافت شده توسط واسط برای عاملهای خارج از جلسه واسطه گری ایجاد محدودیتهای جدیدی می کند. در چنین شرایطی عامل واسط نام این عاملها را به لیست مطلوب خود اضافه می کند و یک اتصال مجازی بین خود و آنها به وجود میآورد. بنابراین عامل واسط این طور تصور خواهد کرد که به طریقی به عامل مربوطه متصل شده است. این کار باعث می شود که در ادامه فرایند حل مسأله، عامل واسط اشتباه انجام شده را تکرار نکند و از این به بعد هنگام بررسی راه حلهای موجود برای حل مسأله، عاملی را که قبلا با اتخاذ تصمیمی موجب بوجود آمدن تناقض برای آن شده است، درنظر بگیرد تا اشتباه گذشته را دوباره تکرار نکند. به این مرحله از الگوریتم مرحله برقراری اتصال گفته می شود.
شکل ۲-۱۱ الگوریتم APO [22]
گرچه الگوریتم APO نسبت به الگوریتمهای پیشین خود برتری های قابل توجهی دارد، روش های هوشمند متعددی نیز اخیرا ارائه شده اند که سعی در برطرف کردن نقاط ضعف این الگوریتمها دارند. برای مثال میلر فعالیتهایی در زمینه گسترش APO برای اجرا در محیط های پویا [۱۷]، برای حل مسائل بهینه سازی [۱۹] و برای تأمین امنیت داده ها و حفظ خصوصی بودن آنها [۱۹] انجام داده است. همچنین بنیش و سیده با تغییر استراتژی انتخاب عامل واسط، کارایی APO را بهبود دادند. آنها اثبات کردند که انتخاب عاملهای با کمترین تعداد همسایه منجر به حل سریعتر مسأله خواهد شد [۲۰]. به علاوه یک استراتژی دوگانه غیرمتمرکز متفاوت را نیز که بر مبنای ABT کار میکرد، ارائه کردند [۲۱]. در سال ۲۰۰۷ سمانه حسینی و کامران زمانیفر یک استراتژی مبتنی بر تعداد تناقضات به نام maxCAPO رامعرفی کردند که با بهره گرفتن از آن عاملهای مؤثرتر و نیرومندتری به عنوان عامل واسط انتخاب میشوند[۲۲]. ایده اصلی مطرح در این استراتژی این است که، عاملهایی که کاملترین اطلاعات را نسبت به تناقضات موجود در مسأله دارند میتوانند به راه حلهای بهتری برای حل زیر مسائل دست پیدا کنند و این خود منجر به افزایش سرعت الگوریتم و کاهش تعداد پیغامهای رد و بدل شده می شود. در ادامه به تشریح کاملتری از این استراتژی میپردازیم.
الگوریتم maxCAPO:
APO برای هر عامل یک عدد اولویت مشخص می کند. این عدد بر اساس سایز لیست مطلوب هر عامل تولید می شود. ایده اولیه این روش که برای انتخاب عامل واسط مورد استفاده قرار میگیرد این است که عاملهایی که بیشترین اطلاعات را نسبت به مسأله داشته باشند میتوانند با اتخاذ تصمیمات مناسبتر، راه حل های بهتری را اتخاذ کنند. بنابراین اولویت دهی به عاملها یک نکته کلیدی و بسیار مهم است زیرا تضمین می کند که تصمیمات توسط عاملهایی گرفته میشوند که بیشترین دانش را نسبت به مسأله دارند. اما بر اساس این روش انتخاب عامل واسط، بارها اتفاق میافتد که چندین عامل، سایز لیست مطلوب مشابهی داشته باشند. در چنین شرایطی، APO اولویت عاملها را بر اساس ترتیب الفبائی نام آنها مشخص می کند. برای مثال اولویت عاملی به نام ND5 بیشتر از اولویت عاملی به نام ND2 است، البته اگر سایز لیست مطلوب در هر دو یکسان باشد. به نظر میرسد که این روش اولویت دهی به عاملها یک روش تصادفی برای رهایی از گره به وجود آمده در چنین شرایطی باشد. در الگوریتم maxCAPO این روش تصادفی با روش اکتشافی بیشترین برخورد[۶۱] جایگزین شده است. ایده پردازان این روش معتقدند در شرایطی که تعداد همسایگان چند عامل مساوی با یکدیگرند، عاملی که حداکثر تناقضات را دارد می تواند با ارسال و دریافت تعداد کمتری پیغام نسبت به سایر عاملها تصمیمات بهتری را نیز اتخاذ کند. بنابراین در الگوریتم maxCAPO، اولویت عاملها ابتدا بر اساس سایز لیست مطلوب آنها مشخص می شود و در مرحله بعد بر اساس تناقضات هر عامل. دقیقا همان دلیلی که برای اهمیت در نظر گرفتن اولویت برای عاملها ذکر شد، در اینجا نیز در مورد اهمیت استفاده از این روش ابتکاری صادق است. در واقع با انتخاب عاملهایی که بیشترین تعداد تناقضات را دارند به عنوان واسط، maxCAPO تضمین می کند که عاملی که حداکثر دانش را نسبت به زیرمسأله دارد نقش عامل واسط را به عهده گرفته است و بنابراین قدرت اتخاذ تصمیمات اصلی به مناسبترین عامل داده شده است. و این مسأله مسلما کارآیی فرایند واسطه گری را بهبود خواهد بخشید. البته در الگوریتم maxCAPO نیز ممکن است با حالتی مواجه شویم که اولا سایز لیست مطلوب چند عامل یکسان باشد و ثانیا تعداد تناقضات موجود بین برخی از این عاملها با عاملهای همسایه شان یکسان باشد. اگر چه چنین حالتی بسیار نادر اتفاق میافتد، اما در صورت بروز چنین حالتی در maxCAPO نیز بر اساس ترتیب الفبایی نام عاملها تصمیم مناسب در جهت انتخاب عامل واسط اتخاذ خواهد شد. پس به این نتیجه میرسیم که در الگوریتم maxCAPO، عامل واسط ابتدا بر اساس سایز لیست عاملها، در مرحله بعد بر اساس تعداد تناقضات عاملها و در مرحله آخر بر اساس ترتیب الفبایی نام عاملها انتخاب می شود.
الگوریتمهای ناقص
۲-۵-۱- الگوریتم [۶۲]DBA
DBA نسخه توزیع شده الگوریتم انفجاری متمرکز است [۵۲]. DBA الگوریتمی ناقص است که اگر هیچ راه حلی برای یک مسأله وجود نداشته باشد خاتمه یافتن را ضمانت نمیکند. در این الگوریتم هر عامل با دو پیام “درست؟” و “بهبود؟[۶۳]” با همسایگانش ارتباط بر قرار می کند. در هر مرحله از الگوریتم، هر عامل مقدار متغیر فعلیش را با همسایگانش مبادله می کند (از طریق یک پیام"درست؟")، کاهش وزن ممکن را اگر که مقدار فعلی را تغییر میدهد محاسبه می کند و مقدار پیشرفت (بهبود) محاسبه شده را به همسایگانش میفرستد (از طریق پیام"بهبود؟") و تصمیم میگیرد که آیا بیشترین مقدار پیشرفت را دارد. اگر چنین است مقدار را تغییر میدهد و پیشرفت را اعمال می کند. این الگوریتم، برای جلوگیری از مینیمم های موضعی، وزن نقض محدودیت ها را که در ابتدا به ۱ تخصیص داده شده اند افزایش میدهد. برای جلوگیری از تغییرات متغیر همزمان میان عاملهای مجاور تنها عاملی که بیشترین کاهش وزن را داشته باشد حق این را دارد که مقدار فعلیش را تغییر دهد. اگر پیوند رخ دهد عاملها این پیوندها را بر اساس شناسههایشان از بین میبرد.
الگوریتمهای مبتنی بر کلونی مورچه ها در حل مسائل ارضاء محدودیت توزیع شده
بهینه سازی کلونی مورچگان (ACO[64]) شیوه تکاملی مهمی برای حل مسائل مختلف بهینه سازی است. الگوریتم ها یی که بر مبنای ACO هستند برای حل بسیاری از مسائلی از قبیل فروشنده دوره گرد[۶۵] [۳۷]، انتساب درجه دوم[۶۶] [۳۸]، زمان بندی شغلی و غیره بکار میروند. تفاوت اصلی در کاربرد ACO برای DCSP با دیگر برنامه های کاربردی به عمومیت DCSPها بر میگردد. همانطور که گفته شد بسیاری از مسائل میتوانند به صورت یک مسأله DCSP طرح ریزی شوند، بنابراین ارائه شیوه جدید و یا اصلاح شیوه های فعلی تاثیر زیادی بر دامنه تحقیقاتی این فیلد میگذارد.
این بخش بر الگوریتم های DCSP/CSP، ACO محور تاکید دارد. ACOروشی اکتشافی است که در جهت حل مسائل دشوار بهینه سازی از قبیل فروشنده دوره گرد، انتساب درجه دوم و مسائل رنگ آمیزی گراف [۳۹، ۴۰] پیشنهاد شده است. کاربرد بهینه سازی کلونی مورچگان در بافت CSP در آثار سلنن[۶۷] و سایرین دیده می شود [۴۳-۴۱]. آن ها تغییراتی در ACO اولیه به وجود آورده اند تا CSP ها را حل کند. آن ها هم چنین با افزودن تکنیکهای جستجوی محلی و مراحل پیش پردازشی برای حل کننده CSPهای ACO محور سعی در بهبود نتایج ACO داشتند. بعدها تارنت[۶۸] و بریدج [۶۹] تحقیق جامعتری از کاری که پیش از این توسط سلنن ارائه شد انجام دادند. آنها تعدادی متغیر از الگوریتم قبلی برداشتند و آزمایشاتی بر روی این متغیر ها انجام دادند. در الگوریتم مورچه ارائه شده توسط سلنن [۴۱] و تمام دیگر الگوریتمهایش[۴۴]، هر مورچه یک انتساب کامل متغیر به متغیر با پیمودن گراف ساختار میسازد. در همه این الگوریتم ها در ابتدا گراف محدودیت[۷۰] تبدیل به گراف دیگری با نام گراف ساختار[۷۱] می شود. این گراف، که مورچه های مصنوعی فرومون هایشان را بر آن قرار می دهند با یک رٲس به ازای هرجفت ” متغیر- مقدار” مربوط به آن مسأله CSP همراه است. بین هر دو گره یک یال <Xi ,v> منطبق با دو متغیر متفاوت برقرار است. شکل زیر از مقاله [۴۴] مثالی از این مورد است.
شکل ۲-۱۲ مثالی از گراف ساختار[۴۴]
مورچه ها با قرار دادن فرومون هایشان بر روی یالهای گراف ارتباط بر قرار می کنند. برای ایجاد انتساب کامل هر مورچه به طور مکرر متغیری را برای تخصیص و گرهی را در گراف که منطبق بر یک تخصیص مقدار برای این متغیر است تا زمانی که همه متغیرها تخصیص داده شده اند انتخاب می کند تا زمانی که تمامی متغیرها مقداردهی شوند. انتخاب متغیر بعدی برای مقداردهی بر اساس تابع اکتشافی کوچکترین دامنه است که یک متغیر مقداردهی نشدهای را به عنوان متغیر برای مقداردهی انتخاب می کند که در دامنهاش کمترین مقدار سازگار با مقادیر انتسابی تاکنون را دارد. انتخاب یک مقدار برای متغیر بسته به دنبالههای فرومون به طور احتمالی صورت میگیرد. بقیهی این الگوریتم خیلی به الگوریتم پایهای ACO شباهت دارد.
