اگرچه الگوریتمهای قوی و مهم مبتنی بر ACO برای حل CSPها وجود دارد اما تنها تحقیقات مهمی که در زمینه حل DCSPها وجود دارد، تحقیقات منتشر شده مرتن ^[۷۲] و هولوت^[۷۳] است[۴۷-۴۵]. آن ها مدلهای متنوعی از الگوریتم های مبتنی بر مورچه ها ارائه دادند (به نام CSAA) تا شکل توزیع شده CSP همچنین مدل های پویا و نیمه کامل این مسأله را حل کنند. CSAA در گام اول برای حل یک DCSP گراف محدودیت اصلی را به گراف ساختار که رئوس و یالهای بیشتری نسبت به گراف اولی دارد تغییر می­دهد. شکل ۳ نمونه ­ای از این تغییر را که در آن گراف اولیه سه متغیر داردAϵ{۴, ۵,۶} ،Bϵ{۲, ۳}، C ϵ{۲, ۳}را نشان می­دهد و مسأله دو محدودیت دارد:B+C = B˃C , A. گراف ساختارشامل گره های اصلی، گره های انتخابی، یالهای انتخابی و یالهای مقدار است. هر کدام از گره های اصلی متغیری را نشان می­ دهند. شکل ۳(a) گره های اصلی گراف را نشان می­دهد. همانطور که در شکل ۳(a) نشان داده شده در این مثال سه متغیر وجود دارد:A ، B و C. در شکل ۳(b) هر گره اصلی از طریق تعدادی یالهای انتخابی (که با خط چین نشان داده شده است) به گره های انتخابی متصل شده است. از یک گره انتخابی تنها یک گره اصلی می ­تواند به دست آید. یالهای انتخابی ترتیب متغیر ها را مشخص می­ کنند. در مسأله­ای با N متغیر هر گره اصلی N-1 گره انتخابی دارد. در مثالی که در شکل ۳ ارائه شده است B و C در حرکت بعدی می­توانند از گره A انتخاب شوند. بنابراین ما دو انتخاب داریم AB و AC که می­توان از یال A به آن رسید. گره های انتخابی از طریق یالهای مقدار به گره اصلی بعدی متصل است، که هر کدام با یک مقدار ممکن برای متغیر مرتبط با گره اصلی قبلی همراه است.

شکل ۲-۱۳ ساختن یک گراف برای یک مسأله با سه متغیر. Aϵ{۴, ۵ ,۶} ، Bϵ{۲ ,۳} ، Cϵ{۲ ,۳} و دو محدودیت A=B+C و B>C. قسمت (a) هر گره اصلی یک متغیر را نشان میدهد. قسمت (b) رفتن به گره اصلی بعدی یک فرایند دو مرحله ای است: ابتدا انتخاب یال، سپس انتخاب مقدار برای متغیر جاری، A سه مقدار ممکن دارد، بنابراین سه یال مقدار از AB وجود دارد. قسمت © گراف تکمیل شده برای این مسأله[۴۴].
در این مثال سه مقدار ممکن برای متغیر/گره) , A {AЄ{۴, ۵, ۶) وجود دارد بنابراین ما سه یال از ABتا B داریم که هر کدام یکی از مقادیر ممکن که می­توان به یال A نسبت داد را ارائه می­ دهند. بخش C از این شکل رویه­ی مشابهی را برای همه یال های این گراف نشان می­دهد. برای مثال گره C به دو گره انتخابی متصل استCA , و CB. سپس همانطور که دو مقدار به گره C، (C Є{۲, ۳}) می­توان تخصیص داد دو یال مقدار از هر دو CA و CB به طور متوالی به گره های Aو B وجود دارد. محدودیتها درگره­های اصلی ذخیره شده ­اند: یک منبع از محدودیت B+C= A در گره های A، B و C ذخیره شده ­اند. یک منبع از B˃C در گره­های B و C ذخیره شده است.
بعد از تبدیل گراف محدودیت، CSAA گره­های یک گراف ساختار را بین میزبان^[۷۴] های مختلف محیط توزیع شده توزیع می­ کند. همانطور که مرتن و همکارانش می­گوید [۴۶،۴۷] تخصیص دادن هر گره گراف ساختار به یک میزبان در محیط توزیع شده ممکن است، اما برای کارایی، به خصوص در هزینه های ارتباطی CSAA چندین گره را از گراف توصیف شده به یک میزبان در محیط توزیع شده اختصاص می­دهد. تعداد میزبانها در نتایج تجربی که توسط مرتن ارائه شد تنها به دو عدد محدود شده است. محدودیتهای کاربرد این روش در بخش بعدی مورد بحث قرار خواهد گرفت.
CSAAاز چندین گروه از عامل ها در هر میزبان برای حل مسأله CSP مربوط به آن میزبان استفاده می­ کند. ارتباطهایی میان این گروه های مختلف وجود دارد. هر عامل از هر گروه، دریک گره اصلی از گراف که به طور تصادفی انتخاب شده قرار داده می­ شود. عامل در گراف حرکت می­ کند و در نتیجه مسیر عبورش را به یاد می­آورد. عامل ها هم چنین مسئول رسیدگی کردن به محدودیتها هستند. بهترین عاملها و عاملهایی که شکست خورده اند، فرومون ها را در ته هر چرخه^[۷۵] می­ریزند. وقتی که یک عامل به یک گره اصلی می­رسد ابتدا انتخاب می­ کند که چه یال انتخابی را اتخاذ کند. در گره انتخابی تعدادی یالهای مقدار وجود دارد که هر کدام مقداری را از دامنه گره اصلی قبلی نشان می­ دهند. بنابراین، انتخاب یک یال مقدار^[۷۶] به معنی انتخاب مقداری برای متغیری که به گره اصلی قبلی مرتبط می­باشد است. تنها یالهای مقداری که مقدارشان با مقادیری که اخیرا انتساب داده شده در تناقض نمی­باشند می­توانند انتخاب شوند. اگر چنین مقداری وجود نداشته باشد، مورچه شکست می­خورد و سپس به همه یالهایی که بر روی آن ها حرکت کرده­است، به منظور ریختن فرومونهای منفی، بر می­گردد. انتخاب مقدار تا زمانی که یک مورچه نهایتا راه حلی را پیدا کند ادامه می­یابد.
زمانی که یک عامل به یک گره اصلی می­رسد (برای مثال یال A اصلی در شکل ۳)، در ابتدا انتخاب می­ کند که بعد از این به کدام یال انتخابی برود (به عنوان مثال، یالی که به سمت گره انتخاب AB می­رود). از گره انتخابی، تعدادی یالهای مقدار وجود دارد که هر کدام به سمت گره اصلی B مشابه هدایت می­ شود. تعداد یالها برابر تعداد مقادیر در دامنه گره اصلی پیشین A است. هر یال مقدار با یکی از آن مقادیر همراه است بنابراین سه یال مقدار بین AB و B وجود دارد زیرا دامنه A از سه مقدار تشکیل شده است:{۴,۵,۶}ϵ A. بنابراین انتخاب یک یال مقدار یعنی انتخاب مقداری برای متغیر که با گره اصلی پیشین همراه است. تنها یال های مقداری که مقادیرشان تناقضی با مقادیری که قبلا تخصیص داده شده اند ایجاد نمی­کنند مجازند. بنابراین عامل باید محدودیتهای خاصی را در این نقطه چک کند (آن هایی که شامل متغیر فعلی A است). اگر هیچ مقداری وجود نداشته باشد که هیچ محدودیتی را نقض نکند، با مقادیری که در حال حاضر انتخاب شده اند هیچ راه حلی نمی­ توان پیدا کرد؛ بنابراین متغیر مرتبط با گره اصلی قبلی شکست می­خورد. وقتی که به همه متغیرها بتوان مقداری تخصیص داد، عامل راه حلی را با ترکیب همه مقادیر گردآوری شده از یال های مقدار که بر رویشان حرکت کرده است می­سازد. هیچ فرومونی در این مورد ریخته نمی­ شود؛ بنابراین الگوریتم پایان یافته است. وقتی متغیری شکست می­خورد، عامل به همه یال­هایی که بر روی آن ها حرکت کرده است بر می­گردد تا بر روی آنها فرومون منفی بریزد.
فصل سوم
طراحی و پیاده سازی روش های پیشنهادی برای مسائل DCSP
در این فصل ابتدا معیارها و متریک های مقایسه کارآیی روش های پیشنهادی را معرفی خواهیم کرد سپس محکها^[۷۷] و مجموعه های داده­ای مورد استفاده در این فیلد را مورد بررسی قرار خواهیم داد. و در پایان مروری خواهیم داشت بر جزئیات پیاده سازی روش های پیشنهادی.
۳-۱- معیارهای ارزیابی کیفیت روش های حل مسائل ارضاء محدودیت توزیع شده(DCSP)
به طور کلی معیارهای مقایسه کیفیت روش های حل مسائل DCSP شامل:
میانگین زمان اجرای الگوریتم با افزایش مقیاس مسأله
میانگین تعداد چرخه های اجرا شده تا رسیدن به یک راه حل
تعداد پیامهای ارسال و دریافت شده
تعداد وارسی های محدودیت ناموفق (NCCC^[78])
قانونی^[۷۹] و کامل^[۸۰] بودن
برخی معیارهای دیگر نیز بسته به نوع روش پیشنهادی در روش های مختلف استفاده شده که مختص همان روش خواهد بود و عمومیت ندارند. به عنوان مثال، ” تعداد اتصالات تولید شده” در روش APO که در واقع بیانگر پیچیدگی ارتباطی هستند و منظور از این پارامتر تعداد اتصالاتی است که در مرحله برقرای اتصال، توسط عاملهای واسط تولید می­شوند. و یا پارامترهایی نظیر: SR^[81] که در روشهایی که از الگوریتمهای EA استفاده کرده ­اند، احتمال برد هر اجرا برای یافتن یک راه حل را نشان می­دهد، و یا معیار دیگری در این نوع روشها به نام ME^[82] : خطا برای یک تک اجرا به صورت تعداد محدودیتهای نقض شده توسط بهترین عامل در شبکه عاملها زمانی که اجرا خاتمه می­یابد تعریف می­ شود. برای هر مجموعه اجرای داده شده ME میانگین این مقدار خطاهاست.
در ادامه هر کدام از این پارامترها را مختصرا شرح می­دهیم.

میانگین زمان اجرای الگوریتم با افزایش ابعاد^[۸۳] مسأله: در واقع نشان می­دهد با افزایش سایز مسأله زمان اجرای هر روش چه روندی را طی خواهد کرد. به عبارتی این متریک پیچیدگی زمانی الگوریتم پیشنهادی را مورد بررسی قرار می­دهد.
میانگین تعداد چرخه های اجرا شده تا رسیدن به یک راه حل: این پارامتر همانطور که از نامش پیداست تعداد چرخه های مورد نیاز برای حل مسأله را مورد ارزیابی قرار می­دهد که در واقع نشان دهنده پیچیدگی محاسباتی الگوریتم است.
تعداد پیام های ارسال و دریافت شده: این مقیاس تعداد پیام های مبادله شده در طول اجرای الگوریتم در بین عامل ها را نشان می­ دهند. این مقیاس، مقیاس خوبی برای ارزیابی مقدار هزینه ارتباطی مورد نیاز برای حل مسائل است.
NCCC: برای معرفی NCCC به عنوان مقیاس پیچیدگی محاسباتی ما روشی را که توسط میسلز^[۸۴] و سایرین ارائه شد را توضیح می­دهیم [۵۳] . در این روش هر عامل یک هزینه عامل^[۸۵] دارد که در ابتدا صفر تعیین شده است. این متغیر تعداد وارسی های محدودیت را که توسط هر عامل انجام گرفته است را نشان می­دهد. بنابراین بعد از هر وارسی محدودیت که توسط یک عامل انجام می­گیرد به این شمارنده یکی اضافه می­ شود. هم چنین یک فیلد اضافی به نام هزینه فرستنده^[۸۶] در هر پیام وجود دارد. هر عاملی قبل از فرستادن یک پیام، فیلد هزینه فرستنده پیام را با مقدار هزینه عاملش مقداردهی می­ کند. همچنین یک هزینه انتقال^[۸۷] نیز در این متریک در نظر گرفته می­ شود که در واقع همان تعداد پیامهای مبادله شده است که اگر بخواهیم پیچیدگی محاسباتی به طور جداگانه با بهره گرفتن از تعداد پیام ها محاسبه شود هزینه انتقال در محاسبه NCCC، صفر در نظر گرفته می­ شود. بنابراین وقتی که هر عامل پیامی را دریافت می­ کند، مقدار هزینه عاملش را با ماکسیمم مقدار بین {هزینه عامل و هزینه فرستنده} مقداردهی می­ کند. NCCC به طور منصفانه­ای پیچیدگی محاسباتی یک سیستم توزیع شده را با توجه به درجه آسنکرونی یک الگوریتم نشان می­دهد.
قانونی و کامل بودن: به بیانی ساده می­توان گفت که یک الگوریتم قانونی است، اگر آن الگوریتم در حل یک مسأله، راه حلی را اعلام کند، یا اعلام کند که راه حلی وجود ندارد، این درست است؛ به عبارتی اگر الگوریتم جوابی بدهد حتما درست است. کامل بودن برای یک الگوریتم یعنی اگر مسأله ای که قرار است توسط آن الگوریتم حل شود راه حلی داشته باشد آن الگوریتم حتما آن را پیدا خواهد کرد.
محکها و مجموعه داده ای متداول مورد استفاده برای آزمایشات
در این بخش سه نمونه از محکها و مجموعه داده­ای که بیشترین استفاده را در ارزیابی رزشهای این فیلد دارند معرفی و تشریح می­کنیم. اکثر این محکها و همچنین مجموعه داده­ای دیگر در مجموعه داده ای DIMACS Challenge قابل دسترسی است.
۳-۲-۱- مسأله n-وزیر
یکی از محکهای مورد استفاده در این فیلد مسأله n-وزیر است. معمای هشت وزیر از جمله مسائل کلاسیک مباحث طراحی الگوریتم است که در حالت کلی‌تر با عنوان معمای n-وزیر یا معمای چند وزیر مطرح می‌شود. وزیر مهره‌ای از مهره‌های بازی شطرنج است که می‌تواند در تمامی هشت جهت به هر تعداد خانه، تا زمانی که مهره‌ای مانع نباشد، حرکت کند. اگر در این مسیرها مهره‌ای از حریف قرار گرفته باشد، آن مهره در معرض خطر حمله توسط وزیر قرار دارد؛ یا به اصطلاح وزیر آن مهره را تهدید می‌کند.
 
شکل ۳-۱ جهت حرکات ممکن یک مهره وزیر در یک صفحه شطرنج
هدف از مساله هشت وزیر، چیدن ۸ مهره وزیر روی یک صفحه شطرنج خالی است، به قسمی­که هیچ مهره‌ای مهره‌های دیگر را تهدید نکند. به عبارت دیگر، ۸ وزیر باید به نحوی چیده شوند که هیچ‌کدام در یک سطر، یک ستون یا یک قطر قرار نداشته باشند. یک جواب مساله می‌تواند به صورت زیر باشد:
شکل ۳-۲ یک جواب برای مسأله ۸-وزیر
در حالت کلی به جای عدد ۸ از عدد طبیعی n استفاده شده و مساله به ازای هر n بزرگتر یا مساوی ۴ مورد بررسی قرار می‌گیرد. به این ترتیب، هدف مساله چیدن n مهره وزیر در یک صفحه شطرنج با ابعاد n × n است. در یک صفحه n در n تعداد n² خانه وجود دارد که از بین آنها n خانه برای قرار گرفتن n وزیر انتخاب می‌شود. در این انتخاب‌ها ترتیب اهمیتی ندارد. پس تعداد حالت‌های انتخاب n خانه برای چیدن n وزیر ترکیب n ازn² یا C(n,n²) است که حتی برای n‌های نه چندان بزرگ (نظیر ۸) عدد بزرگی به دست می‌آید. این خود گویای این واقعیت است که مسأله n-وزیر در حین سادگی در توصیف، حل آن به اندازه کافی سخت هست که تبدیل به یک مسأله کلاسیک و متعاقبا یک محک در فیلدهای مختلف علوم کامپیوتر شود.
۳-۲-۲- مسأله رنگ­آمیزی گراف^[۸۸]
مسأله رنگ آمیزی رئوس گراف، یک مسأله جاافتاده کلاسیک در تئوری گراف است که در آن به هر یک از رئوس گراف یک رنگ انتساب داده می­ شود ؛ ﺑﮕﻮﻧـﻪ­ای ﮐـﻪ ﺑـﻪ ﻫـﺮ دو گره ﻣﺠـﺎور دﻟﺨﻮاه از ﮔﺮاف، رﻧﮓ ﻫﺎی ﻣﺘﻔﺎوﺗﯽ اﺧﺘﺼـﺎص داده ﺷـﻮد. شکل زیر مثالی از این مسأله را نشان می­دهد.
سبز
سبز
سبز
قرمز
قرمز
قرمز
آبی
قرمز
آبی