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

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

عاملها امتیازشان را بر اساس تابع امتیاز تعریف شده محاسبه می­ کنند، مثلا امتیاز عامل A برابر است با ۲- چون مقدار انتخابی این عامل باعث ایجاد یک تهدید برای عامل B و یک تهدید برای عامل C شده است و همانطور که گفتیم امتیاز هر عامل برابر است با منفی تعداد محدودیتهای نقض شده. عامل A در حین محاسبه امتیازش لیستی از عاملهایی را که مقدارشان با مقدار انتخابیش در تناقض است را نیز به صورت شکل ۴-۲ تهیه می­ کند و اجتماعی از این عاملها به رهبری خودش میسازد. مابقی این عاملها نیز همین کار را به صورت شکل۴-۲ انجام می­ دهند و همه عاملها این اطلاعات جمع آوری کرده اشان را در CSCBOARD به اشتراک می­گذارند تا همه عاملها بتوانند برای مراحل بعدی از آن استفاده کنند.
شکل ۴-۲ مرحله ۱ تا ۴ از الگوریتم DACA، هر عامل یکی از ۴ متغیر A، B، C، D را مالک می­شوند، سپس هر عامل امتیاز خود را محاسبه می­ کند و در این حین ساختار CSCommunity و همچنین رهبر ها مشخص می­شوند.
حال هر یک از عاملها سعی می­ کنند امتیازشان را به صفر کاهش دهند، برای عملیات تعویض انتساب هر رهبر، مقدار انتخابی توسط رهبرهای دیگر راچک می­ کند. رهبر A تشخیص می­دهد که D یک مورد مناسب برای تعویض مقدار انتسابی اش با آن است. پس A یک پیام “درخواست تعویض مقدار”^[۱۴۶] به عامل D می­فرستد. عامل D قبل از پاسخ دادن به این درخواست، این تعویض را ارزیابی می­ کند که ببیند این تعویض چه تأثیری بر روی امتیاز خود و اعضای اجتماعش خواهد گذاشت. عامل D این تعویض را مناسب می­بیند و موافقتش را برای این تعویض با یک پیام به A اطلاع می­دهد و تعویض به صورت شکل ۴-۳ انجام می­پذیرد. این تعویض موجب می­ شود که امتیاز عاملهای A و D به صفر برسد و همچنین بهبودی در امتیاز اعضای اجتماعشان به وجود آید. این دو عامل پس از به روز رسانی امتیاز خود و اعضای اجتماعشان به لیست عاملهای آزاد اضافه می­شوند و اجتماعشان نیز از بین می­رود. با ثبت این اتفاق در CSCBOARD، رهبرهای دیگر نیز از مقادیر جدید انتسابی A و D مطلع شده و اگر لازم دیدند تغییراتی را در ساختار اجتماعشان ایجاد می­ کنند. مثلا B، عاملهای A و D را از لیست اعضای اجتماعش حذف می­ کند و همچنین امتیازش را نیز به روز رسانی می­ کند. بعد از انجام این مرحله CSCBOARD به صورت شکل ۴-۳ خواهد بود.
شکل ۴-۳ مرحله ۵ از الگوریتم DACA، عملیات تعویض انتساب بین عاملهای A وD اتفاق افتاده است، امتیاز A و D به صفر می­رسد عاملهای دیگر نیز به محض اطلاع از این تعویض امتیازشان را بروزرسانی می­ کنند، A و D به لیست عاملهای آزاد اضافه می­شوند و اجتماعشان نیز از بین می­رود.
در مرحله بعد عامل B سعی می­ کند امتیازش را به صفر برساند، ابتدا با بررسی تنها رهبر باقیمانده یعنی C متوجه می­ شود که تعویض مقدار انتسابی با C هیچ سودی برایش ندارد پس به سراغ عاملهای آزاد می­رود. با یک تعویض موفقیت آمیز بین B و A در نهایت این الگوریتم خاتمه می­یابد در حالیکه یک راه حل به صورت شکل۴-۴ یافته شده است.
شکل ۴-۴ مرحله پایانی الگوریتم DACA، بایک تعویض انتساب موفقیت آمیز بین B و A امتیاز همه عاملها صفر می­ شود و الگوریتم با یک راه حل قانونی خاتمه می­یابد.

ارزیابی و مقایسه الگوریتم ما با دیگر روشها
ما به منظور ارزیابی و تست کارآیی این الگوریتم از محک کلاسیک n-وزیر استفاده کرده ایم. این الگوریتم با مسائل ۴-وزیر تا ۱۰^۴-وزیر تست شد و مشاهده کردیم که DACA قادر به یافتن یک راه حل برای تمامی حالتهای این طیف گسترده در یک مدت زمان منطقی است. شکل ۴-۵ میانگین زمان اجرای این الگوریتم را با افزایش مقیاس مسأله با گامهای ۵۰ تایی نشان می­دهد. این نمودار گویای این واقعیت است که الگوریتم ما یک پیچیدگی تقریبا خطی را با افزایش مقیاس مسأله دارد، این درحالیست که پیچیدگی زمانی یک الگوریتم همانند ABT یک رشد نمایی را با افزایش مقیاس مسأله طی خواهد کرد تا بدانجایی که قادر به حل مسائل با مقیاس اندکی بزرگ در یک مدت زمان منطقی نخواهد بود. این آزمایش بر روی یک سیستم با مشخصات: ۲٫۱۶GHz Core™ 2 Due PC with 2GB RAM. انجام شده است.
شکل ۴-۵ میانگین زمان اجرای الگوریتم DACA در اجرای مسأله با افزایش n-وزیر از ۴ تا ۱۰^۴ در گامهای ۵۰ تایی.
در مرحله بعدی آزمایشات، ما مقایسه ای از لحاظ تعداد سیکلهای مورد نیاز تا رسیدن به جواب برای حل مسأله n-وزیر بین الگوریتم DACA و دو الگوریتم دیگر یعنی ABT و asynchronous backtracking with min-conflict heuristic خواهیم داشت. نتیجه این آزمایش که در جدول۴-۱ آمده است حاکی از آن است که روش پیشنهادی ما در این مورد بسیار بهتر از دو روش دیگر عمل می­ کند.
جدول۴-۱: مقایسه الگوریتم پیشنهادی ما با دو روش دیگر از لحاظ تعداد سیکلهای مورد نیاز برای حل

n
Asynchronous bachtracking
Asynchronous bachtracking with min-conflict huristic
DACA algorithm

۱۰

۱۰۵٫۴

۱۰۲٫۶

۱۴٫۸

۵۰

۳۲۴٫۴

۳۲۶٫۸

۲۲٫۴

۱۰۰