مکانیزمی که در این روش برای استفاده از EA در نظرگرفته شده است تا حدودی با EA های سنتی متفاوت است. در EA های سنتی، آن دسته از افرادی^[۹۹] که تولید فرزند خواهند کرد معمولا از بین تمام افراد بر اساس تابع برازش ^[۱۰۰] اشان انتخاب می­شوند. بنابراین یک تابع توزیع عمومی^[۱۰۱] از یک جمعیت باید تعیین شود. اما در حالت طبیعی، یک انتخاب سراسری^[۱۰۲] وجود ندارد و یک تابع توزیع عمومی هرگز نمی­تواند تعیین شود. در حقیقت یک انتخاب طبیعی واقعی تنها در یک محیط محلی اتفاق می­افتد و هر فرد تنها می ­تواند با محیط اطرافش در تعامل باشد. به این معنی که، در هر مرحله، یک تکامل طبیعی تنها یک نوع از پدیده های محلی است. این اطلاعات می ­تواند تنها پس از یک فرایند انتشار به صورت جهانی به اشتراک گذاشته شود. در شبکه فوق، عاملها برای رسیدن به اهدافشان با یکدیگر رقابت خواهند کرد به طوریکه هر عامل بتواند منابع بیشتری به دست آورد. از آنجا که هر عامل تنها محیط محلی خود را درک می­ کند رفتارهای رقابتی اش تنها می ­تواند بین او و همسایگانش اتفاق بیفتد. هیچ انتخاب سراسری بین همه وجود ندارد، بنابراین یک تابع توزیع عمومی نیاز نیست. یک عامل با همسایگانش در تعامل است، به طوریکه اطلاعات به آنها منتقل می­ شود و به اینصورت اطلاعات به تدریج در کل شبکه منتشر می­ شود. این مدل از شبکه عاملها به مکانیزم تکامل واقعی در طبیعت نسبت به مدل یک جمعیت در EA های سنتی بسیار نزدیکتر است.

با بهره گرفتن از رفتارهای طراحی شده، عاملها در طول روند تعامل با محیط و دیگر عاملها، هر عامل تا حد ممکن انرژی­اش را افزایش می­دهد به طوریکه MAEA-CSP می ­تواند راه حلها را بیابد. در این روش عاملها به این صورت تعریف می­شوند: یک عامل a یک عنصر در فضای جستجوی S است با انرژی برابر با منفی تعداد محدودیتهای نقض شده در مسأله.
هدف هر عامل ماکسیمایز کردن انرژی به وسیله رفتارهایی است که می ­تواند از خود بروز دهد. واضح است که هرچه انرژی یک عامل بالاتر باشد آن عامل، عامل بهتری است. وقتی انرژی یک عامل به صفر افزایش می­یابد آن عامل یک راه حل^[۱۰۳] شده است. دامنه برای هر متغیر متناهی و گسسته است، بنابراین اعضا می­توانند با اعداد طبیعی شماره گذاری شوند. وقتی تمام دامنه ها به مجموعه ای از اعداد طبیعی منتقل شدند، راه حل های اغلب CSP ها ویژگیهای خاصی به خود می­گیرند. بر اساس آنها، CSP ها می­توانند به دو گروه تقسیم بندی شوند: فرض کنید S مجموعه راه حل ها برای یک CSP باشد و تمام مجموعه دامنه ها به وسیله مجموعه ای از اعداد طبیعی ارائه شده باشند. حال اگر هر s ϵ S یک جایگشت^[۱۰۴] از ۱, ۲, …, n باشد، CSP به عنوان یک مسائل ارضاء محدودیت جایگشتی تعریف می­ شود در غیر اینصورت به صورت یک مسائل ارضاء محدودیت غیر جایگشتی. برای یک مسائل ارضاء محدودیت غیر جایگشتی فضای جستجو هنوز S است. از آنجایی که مسائل ارضاء محدودیت جایگشتی یک مورد خاص از مسائل ارضاء محدودیت غیر جایگشتی است فضای جستجو می ­تواند برای این حالت به مجموعه ای از تمام جایگشتهای ۱, ۲, …, n کاهش پیدا کند.
وقتی از EA ها برای حل مسائل استفاده می­ شود، فضای جستجو باید رمزگذاری^[۱۰۵] شود به طوریکه افراد می­توانند در یک شکل رمزگذاری یکنواخت^[۱۰۶] ارائه شوند. به عنوان مثال GA ها معمولا فضای جستجو را با بهره گرفتن از کد باینری رمزگذاری می­ کنند، بنابراین هر فرد یک دنباله­ای از بیتهاست. برای مسائل ارضاء محدودیت جایگشتی طبیعی است که هر فرد را به صورت یک جایگشت از ۱, ۲, …, n ارائه دهیم. برای مسائل ارضاء محدودیت غیر جایگشتی، روشی که بیشترین فابلیت فهم را دارد یعنی واضح ترین روش ارائه هرفرد به صورت یک عنصری از S است که این توسط اکثریت الگوریتمهای موجود استفاده می­ شود. به عنوان مثال در [۲۶] و [۲۷]، هر فرد توسط یک جایگشت از متغیرها ارائه می­ شود و جایگشت به وسیله یک رمزگشای^[۱۰۷] ساده به یک نمونه جزئی^[۱۰۸] انتقال می­یابد. این رمزگشا متغیرها را به ترتیبی که در جایگشت آمده­اند در نظر می­گیرد و اولین مقدارممکن از دامنه را به آن متغیر نسبت می­دهد. اگر هیچ مقداری بدون شناسایی یک تناقض ممکن نبود آن متغیر بدون مقدار رها می­گردد. این رمزگشا در واقع از یک الگوریتم حریصانه استفاده می­ کند بنابراین با یک مسأله جدی روبرو هستیم و آن این است که برای اغلب CSP ها این رمزگشا نمی­تواند هر جایگشتی را به یک راه حل رمزگشایی کند. نتیجه اینکه الگوریتمهای بر اساس این رمزگشا ممکن است نتوانند راه حلی برای همه پیدا کنند. اما نویسندگان این مقاله یک متد رمزگذاری طراحی کرده ­اند که نه تنها راه حل برای هر مسأله CSP را کاور می­ کند بلکه همچنین یک فضای جستجوی قابل مدیریت و کنترل را نیز نگه می­دارد. آنها یک متد به نام MCE^[109] را بر اساس رمزگشای ذکر شده پیشنهاد داده اند. در MCE هر عامل به عنوان یک عنصر از فضای جستجوی S نشان داده شده است که برخی رفتارها برای دادن مقدار به متغیرها به طور مستقیم برای آن طراحی شده است. هر عامل باید مقداری اطلاعات ثبت کند.
به وسیله MCE هر عامل شامل یک جایگشت و یک انتساب برای تمام متغیرهاست. در واقع انتساب همان چیزی است که مورد نیازاست. بنابراین MCD^[110] منطبق با MCE برای انتقال P به V طراحی شده است. ایده اصلی MCD نسبت دادن مقدار با کمترین تعداد نقض محدودیت به متغیر است. متغیرها می­توانند به ترتیبی که در جایگشت اتفاق می­افتند در نظر گرفته شوند و تنها محدودیت های بین متغیرها و مقدار انتسابی قبلی­اشان نگهداری می­ شود. بعد از اینکه MCD انجام شد هیچ متغیری بدون مقدار باقی نمی­ماند.
دو نوع از رفتارهایی که برای عاملها طراحی شده اند، یکی رفتارهایی که بر روی P انجام می­شوند (رفتار ^[۱۱۱]p) و دیگری رفتارهایی که بر روی V انجام می­شوند (رفتار v^[112]) . وقتی رفتار V توسط یک عامل انجام می­ شود انرژی می ­تواند مستقیما به روز رسانی شود. اما وقتی رفتار P باید انرژی قبل از به روز رسانی توسط MCD رمزگشایی شود. اگر MCD رمزگشایی کردن را برای هر عامل از اولین متغیر درون جایگشت شروع کند اطلاعات تولید شده توسط رفتار V ها از دست خواهد رفت. بنابراین یک پارامتر pos برای MCD معرفی شده است که اولین موقعیت تغییر یافته به وسیله رفتار P را نشان می­دهد. بنابراین مقدار متغیرهای قبل از pos، دست نخورده باقی می­ماند بطوریکه که اغلب اطلاعات تولید شده توسط رفتار V می ­تواند حفظ شود. برای یک عامل جدید pos به مقدار ۱ تنطیم می­ شود. MCD(CSAgent,Pos) نشان می­دهد که برروی عامل انجام شده است. در حقیقت الگوریتم ۱ تنها یک پیاده سازی عمومی از ایده MCD است و می ­تواند برای تمام انواع CSP ها استفاده شود. برای CSP های خاص این ایده می ­تواند با دانشی از مسأله ترکیب شود. به عنوان مثال وقتی با مسأله رنگ آمیزی گراف سروکار داریم درجه گره می ­تواند استفاده شود.
پس از تعریف عامل به طور کامل، در این مقاله، سه رفتار برای عاملها برای رسیدن به هدف طراحی شده است. این رفتارها به ترتیب رفتار رقابتی^[۱۱۳] ، رفتار خودآموز^[۱۱۴] ، رفتار جهشی^[۱۱۵] نامگذاری شده اند، که دوتای اول مربوط به رفتار P و آخری متعلق به رفتار V است.
رفتار رقابتی: در این رفتار انرژی یک عامل با همسایگانش مقایسه می­ شود. یک عامل می ­تواند زنده بماند اگر انرژی­اش نسبت به همسایگانش ماکسیمم باشد در غیر این صورت آن عامل باید بمیرد و یکی از فرزندان همسایه با بیشترین انرژی جایگزین او خواهد شد.
رفتار خودآموز: اجتماع جستجوی محلی با EA می ­تواند عملکرد آن را بهبود بخشد. علاوه برا این عاملها از مقداری دانش نسبت به مسأله برخوردار می­باشند. بنابراین با الهام گیری از تابع اکتشافی کمترین برخورد،[۲۹] و [۳۰] و بهره گیری از متد رمزگذاری برای عاملها، نویسندگان این مقاله رفتار رفتار خودآموز را طراحی کرده اند. جزئیات این روش در الگوریتم ۳ در این مقاله نشان داده شده است.
رفتار جهشی: این رفتار مشابه همان جهشی است که در الگوریتم ژنتیک سنتی اتفاق می­افتد.این متد در واقع برای کمک به عملکرد رفتار قبلی طراحی شده است.
پس از تعریف محیط، عاملها و همچنین طراحی رفتارها، الگوریتم MAEA-CSPs به صورت زیر پیاده سازی شده است. برای حل مسأله CSP، همه عاملها باید این سه رفتار را به ترتیب اتخاذ کنند. در اینجا این رفتارها به وسیله ابزارهای تکاملی کنترل شده است به طوریکه شبکه عاملها می ­تواند نسل به نسل تکامل یابد. در هر نسل ابتدا رفتارهای رقابتی در هر عامل انجام می­ شود و در نتیجه عاملهایی با انرژی کم از شبکه حذف می­شوند و بنابراین فضا برای عاملهای با انرژی بیشتر باز خواهد شد. سپس رفتارهای خودآموز و جهش براساس نوع مسأله و حالت عاملها انجام می­ شود. به منظور کاهش هزینه محاسباتی، دو رفتار اخیر تنها در عاملهای بهترین در شبکه عاملهای جاری انجام می­ شود. این فرایند به طور مکرر ادامه می­یابد تا زمانی که یک عامل با انرژی صفر یافته شود یا اینکه پیچیدگی محاسباتی ماکسیمم شود.
پس از پیاده سازی این روش نتایج ابتدا بر روی چند محک از کلاس مسائل ارضاء محدودیت غیر جایگشتی همانند مسأله رنگ آمیزی گراف و یا نمونه های مختلفی از مسائل ارضاء محدودیت باینری تست شده است و نتیجه با ۴ الگوریتم دیگر مقایسه شده است. سپس تست برای بخش مسائل ارضاء محدودیت جایگشتی انجام شده که برای آن از محکهای n-وزیر و یا مسأله زمانبندی کار استفاده شده است. پیچیدگی فضایی و همگرایی به جواب به صورت تئوری آنالیز شده است. همچنین آنالیز پارامترها نشان می­دهد که الگوریتم MAEA-CSPs کاملا قوی^[۱۱۶] است و همچنین استفاده از آن آسان است. در مرحله بعد اثبات شده که این الگوریتم دارای پیچیدگی زمانی O(n^1.07) است و با مقایسه این روش با ۶ الگوریتم دیگر نشان داده اند که این روش بسیار بهتر از روش های دیگر عمل می­ کند. دلایل بهتر شدن این روش نسبت به روش های قبل سه مورد عنوان شده است: اول طبقه ­بندی کردن مسائل CSP در دو دسته مسائل ارضاء محدودیت جایگشتی و مسائل ارضاء محدودیت غیر جایگشتی بر اساس خصوصیاتشان، بنابراین، رفتارهای عاملها می ­تواند در دو نوع مختلف طراحی شود. دوم، رمزگذاری کمترین برخورد^[۱۱۷] بر معایب متد رمزگذاری معمولی غلبه کرده است. البته اگرچه متد MCE خود یک روش حریصانه است اما رفتار جهش استفاده شده می ­تواند از افتادن الگوریتم در نقطه بهینه محلی^[۱۱۸] جلوگیری کند. و در پایان اینکه یک انتخاب طبیعی واقعی در طبیعت تنها در یک محیط محلی اتفاق می­افتد و یک فرد تنها می ­تواند با محیط اطرافش در تعامل باشد. در شبکه عاملهای طراحی شده برای این کار هر عامل تنها می ­تواند محیط محلی اش را درک کند و این مدل به واقعیت نزدیکتر است نسبت به انتخاب جمعیت در الگوریتمهای تکاملی سنتی و همچنین در این شبکه عاملهای طراحی شده هیچ کنترل مرکزی نیاز نیست.
شکل ۳-۶ نتیجه ارزیابی مقیاس­پذیری^[۱۱۹] این الگوریتم با افزایش ابعاد مسأله را نشان می­دهد. این آزمایش بر روی مسأله n-وزیر با رشد n از ۵×۱۰^۴ تا ۱۰^۷ انجام شده است. نتیجه به دست آمده نشان می­دهد که الگوریتم MAEA-CSPs یک پیچیدگی زمانی خطی O(n^1.07) دارد.
شکل ۳-۶ میانگین زمان اجرای الگوریتم MAEA-CSPs در حل مسأله n-وزیر[۳]
ارزیابی دیگر، مقایسه الگوریتم MAEA-CSPs با چهار الگوریتم دیگردر اجرای محکهای مسائل ارضاء محدودیت باینری است. این چهار الگوریتم در واقع چهار روش برتر از میان ۱۱ روش مورد مقایسه در[۵۷] بود که عبارتند از : [۵۹] و [۵۸]H-GA.1, ، [۵۹] و [۵۸] H-GA.3 ، [۶۰] و [۶۱] SAW، [۶۲] Glass-Box . این کار بر روی test suite :
http://www.xs4all.nl/~bcraenen/resources/csps_modelE_v20_d20.tar.gz
که برای مقایسه کارایی ۱۱ الگوریتم موجود در [۵۷] استفاده شده، انجام گرفته است. که این test suite حاوی ۲۵۰ نمونه مختلف مسأله قابل حل است. هر نمونه ۲۰ متغیر دارد و دامنه این متغیرها
D={D_i | D_i={1, 2, . . . , 20 } and 1≤i≤۲۰ }
است. این ۲۵۰ نمونه بر اساس میزان دشواری اشان در ۱۰ گروه تقسیم بندی شده اند؛ p={0.24, 0.25, 0.26, 0.27, 0.28, 0.29, 0.30, 0.31, 0.32, 0.33} ، و هر گروه شامل ۲۵ نمونه است. واضح است هر چه p بزرگتر باشد نسبت دشواری آن مسأله بیشتر است. در اینجا ۱۰ اجرای مستقل در هر ۲۵ نمونه از یک مقدار p داده شده انجام شده است که در کل ۲۵۰ عدد نقطه داده ای^[۱۲۰] برای محاسبه اندازه گیری استفاده شده است. میزان سودمندی^[۱۲۱] و کارایی^[۱۲۲] این الگوریتم توسط دو متد SR و ME اندازه گیری شده است. همانطور که گفتیم SR در واقع احتمال برد هر اجرا برای یافتن یک راه حل را نشان می­دهد، از آنجایی که تمام نمونه های موجود در test suit قابل حل هستند بیشترین مقدار SR، ۱۰۰% است. خطا برای یک تک اجرا به صورت تعداد محدودیتهای نقض شده توسط بهترین CSAgent در شبکه عاملها زمانی که اجرا خاتمه می­یابد تعریف می­ شود. برای هر مجموعه اجرای داده شده ME میانگین این مقدار خطاها ست. کارایی^[۱۲۳] به وسیله میانگین تعداد ارزیابیها برای یک راه حل^[۱۲۴] اندازه گیری می­ شود، که به طور گسترده در اندازه گیری هزینه محاسباتی در EA ها مورد استفاده قرار می­گیرد.
شکل ۳-۷ مقایسه الگوریتم MAEA-CSPs با ۴ الگوریتم دیگر با معیارهای SR ، ME و AES [3]
همانطور که می­بینیم، SR الگوریتم MAEA-CSPs بالاترین مقدار را در میان این ۵ الگوریتم دارد با مقداری برابر با ۱۰۰% برای p=0.24-0.26 . همچنین شکل (.b) نشان دهنده این است که MAEA-CSPs کمترین و در واقع بهترین مقدار ME را دارد. از آنجا که AES از نظر آماری زمانی که SR بسیار پایین است قابل اعتماد نیست، EAS تنها زمانی که SR بالاتر از ۱۰% است رسم شده است. تمامیSR های هر ۵ الگوریتم برای p=0.30-0.33 پایین هستند اما میزان ME برای MAEA-CSPs در این بازه نسبت به بقیه بسیار کمتر است و حداکثر ۱ تا ۳ محدودیت ارضاء نشده­اند. خلاصه اینکه الگوریتم MAEA-CSPs بسیار بهتر از ۴ روش دیگر عمل می­ کند. جدول (۳-۱) مقادیر به دست آمده برای الگوریتم MAEA-CSPs را بر روی محکهای مسائل ارضاء محدودیت باینری را نشان می­دهد.
جدول(۳-۱): نتایج به دست آمده از آزمایش MAEA-CSPs بر روی محکهای مسائل ارضاء محدودیت باینری