محدودیتها و الگوریتم

دانلود پایان نامه

مرحله 9: الگوریتم خاتمه مییابد اگر امتیاز تمامی عاملها به صفر برسد.
Algorithm 4: DACA(Distributed Alldiff Constraint Algorithm) for solving DCSPs with Alldiff constraints
Input: agent assignments, leaders list, free agents list,
constraint graph, scores list.
Output: solution
CSCommunity Organizing;
while (Not Find Solution) do
while find successfully exchange & not find solution
Assignment Exchange Operation Leaders with Leaders).
. if do not successfully exchange in step 3.1. then Assignment Exchang Operation (Leaders with FreeAgents)
. if do not successfully exchange in step
Help by FreeAgents.
if do not successfully exchange in prior steps then do Random Exchange and go to step 1.
حل یک مثال با استفاده از این الگوریتم
به منظور توصیف بهتر الگوریتم DACA، روند کار این الگوریتم را بر روی مثال کوچکی از مسأله کلاسیک چند-وزیر دنبال میکنیم. برای سادگی و افزایش تفهیم یک مسأله 4-وزیر را با استفاده از این الگوریتم حل میکنیم. طبق تعریف در ابتدا هر عامل یکی از متغیرهای مسأله را مالک میشود. انتخاب مقدار اولیه برای متغیرها به صورت مقادیر تصادفی غیر تکراری توسط عاملها به صورت شکل زیر انجام میشود و تلاش برای رسیدن به یک راه حل آغاز میشود.
عاملها امتیازشان را بر اساس تابع امتیاز تعریف شده محاسبه میکنند، مثلا امتیاز عامل A برابر است با 2- چون مقدار انتخابی این عامل باعث ایجاد یک تهدید برای عامل B و یک تهدید برای عامل C شده است و همانطور که گفتیم امتیاز هر عامل برابر است با منفی تعداد محدودیتهای نقض شده. عامل A در حین محاسبه امتیازش لیستی از عاملهایی را که مقدارشان با مقدار انتخابیش در تناقض است را نیز به صورت شکل 4-2 تهیه میکند و اجتماعی از این عاملها به رهبری خودش میسازد. مابقی این عاملها نیز همین کار را به صورت شکل4-2 انجام میدهند و همه عاملها این اطلاعات جمع آوری کرده اشان را در CSCBOARD به اشتراک میگذارند تا همه عاملها بتوانند برای مراحل بعدی از آن استفاده کنند.
شکل 4-2 مرحله 1 تا 4 از الگوریتم DACA، هر عامل یکی از 4 متغیر A، B، C، D را مالک میشوند، سپس هر عامل امتیاز خود را محاسبه میکند و در این حین ساختار CSCommunity و همچنین رهبر ها مشخص میشوند.
حال هر یک از عاملها سعی میکنند امتیازشان را به صفر کاهش دهند، برای عملیات تعویض انتساب هر رهبر، مقدار انتخابی توسط رهبرهای دیگر راچک میکند. رهبر A تشخیص میدهد که D یک مورد مناسب برای تعویض مقدار انتسابی اش با آن است. پس A یک پیام “درخواست تعویض مقدار” به عامل D میفرستد. عامل D قبل از پاسخ دادن به این درخواست، این تعویض را ارزیابی میکند که ببیند این تعویض چه تأثیری بر روی امتیاز خود و اعضای اجتماعش خواهد گذاشت. عامل D این تعویض را مناسب میبیند و موافقتش را برای این تعویض با یک پیام به A اطلاع میدهد و تعویض به صورت شکل 4-3 انجام میپذیرد. این تعویض موجب میشود که امتیاز عاملهای A و D به صفر برسد و همچنین بهبودی در امتیاز اعضای اجتماعشان به وجود آید. این دو عامل پس از به روز رسانی امتیاز خود و اعضای اجتماعشان به لیست عاملهای آزاد اضافه میشوند و اجتماعشان نیز از بین میرود. با ثبت این اتفاق در CSCBOARD، رهبرهای دیگر نیز از مقادیر جدید انتسابی A و D مطلع شده و اگر لازم دیدند تغییراتی را در ساختار اجتماعشان ایجاد میکنند. مثلا B، عاملهای A و D را از لیست اعضای اجتماعش حذف میکند و همچنین امتیازش را نیز به روز رسانی میکند. بعد از انجام این مرحله CSCBOARD به صورت شکل 4-3 خواهد بود.
شکل 4-3 مرحله 5 از الگوریتم DACA، عملیات تعویض انتساب بین عاملهای A وD اتفاق افتاده است، امتیاز A و D به صفر میرسد عاملهای دیگر نیز به محض اطلاع از این تعویض امتیازشان را بروزرسانی میکنند، A و D به لیست عاملهای آزاد اضافه میشوند و اجتماعشان نیز از بین میرود.
در مرحله بعد عامل B سعی میکند امتیازش را به صفر برساند، ابتدا با بررسی تنها رهبر باقیمانده یعنی C متوجه میشود که تعویض مقدار انتسابی با C هیچ سودی برایش ندارد پس به سراغ عاملهای آزاد میرود. با یک تعویض موفقیت آمیز بین B و A در نهایت این الگوریتم خاتمه مییابد در حالیکه یک راه حل به صورت شکل4-4 یافته شده است.
شکل 4-4 مرحله پایانی الگوریتم DACA، بایک تعویض انتساب موفقیت آمیز بین B و A امتیاز همه عاملها صفر میشود و الگوریتم با یک راه حل قانونی خاتمه مییابد.
ارزیابی و مقایسه الگوریتم ما با دیگر روشها
ما به منظور ارزیابی و تست کارآیی این الگوریتم از محک کلاسیک n-وزیر استفاده کرده ایم. این الگوریتم با مسائل 4-وزیر تا 104-وزیر تست شد و مشاهده کردیم که DACA قادر به یافتن یک راه حل برای تمامی حالتهای این طیف گسترده در یک مدت زمان منطقی است. شکل 4-5 میانگین زمان اجرای این الگوریتم را با افزایش مقیاس مسأله با گامهای 50 تایی نشان میدهد. این نمودار گویای این واقعیت است که الگوریتم ما یک پیچیدگی تقریبا خطی را با افزایش مقیاس مسأله دارد، این درحالیست که پیچیدگی زمانی یک الگوریتم همانند ABT یک رشد نمایی را با افزایش مقیاس مسأله طی خواهد کرد تا بدانجایی که قادر به حل مسائل با مقیاس اندکی بزرگ در یک مدت زمان منطقی نخواهد بود. این آزمایش بر روی یک سیستم با مشخصات: 2.16GHz Core(TM) 2 Due PC with 2GB RAM. انجام شده است.
شکل 4-5 میانگین زمان اجرای الگوریتم DACA در اجرای مسأله با افزایش n-وزیر از 4 تا 104 در گامهای 50 تایی.