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

نکه الگوريتمهاي بر اساس اين رمزگشا ممکن است نتوانند راه حلي براي همه پيدا کنند. اما نويسندگان اين مقاله يک متد رمزگذاري طراحي کردهاند که نه تنها راه حل براي هر مسأله CSP را کاور ميکند بلکه همچنين يک فضاي جستجوي قابل مديريت و کنترل را نيز نگه ميدارد. آنها يک متد به نام MCE109 را بر اساس رمزگشاي ذکر شده پيشنهاد داده اند. در MCE هر عامل به عنوان يک عنصر از فضاي جستجوي S نشان داده شده است که برخي رفتارها براي دادن مقدار به متغيرها به طور مستقيم براي آن طراحي شده است. هر عامل بايد مقداري اطلاعات ثبت کند.
به وسيله MCE هر عامل شامل يک جايگشت و يک انتساب براي تمام متغيرهاست. در واقع انتساب همان چيزي است که مورد نيازاست. بنابراين MCD110 منطبق با MCE براي انتقال P به V طراحي شده است. ايده اصلي MCD نسبت دادن مقدار با کمترين تعداد نقض محدوديت به متغير است. متغيرها ميتوانند به ترتيبي که در جايگشت اتفاق ميافتند در نظر گرفته شوند و تنها محدوديت هاي بين متغيرها و مقدار انتسابي قبلياشان نگهداري ميشود. بعد از اينکه MCD انجام شد هيچ متغيري بدون مقدار باقي نميماند.
دو نوع از رفتارهايي که براي عاملها طراحي شده اند، يکي رفتارهايي که بر روي P انجام ميشوند (رفتار 111p) و ديگري رفتارهايي که بر روي V انجام ميشوند (رفتار v112) . وقتي رفتار V توسط يک عامل انجام ميشود انرژي ميتواند مستقيما به روز رساني شود. اما وقتي رفتار P بايد انرژي قبل از به روز رساني توسط MCD رمزگشايي شود. اگر MCD رمزگشايي کردن را براي هر عامل از اولين متغير درون جايگشت شروع کند اطلاعات توليد شده توسط رفتار V ها از دست خواهد رفت. بنابراين يک پارامتر pos براي MCD معرفي شده است که اولين موقعيت تغيير يافته به وسيله رفتار P را نشان ميدهد. بنابراين مقدار متغيرهاي قبل از pos، دست نخورده باقي ميماند بطوريکه که اغلب اطلاعات توليد شده توسط رفتار V ميتواند حفظ شود. براي يک عامل جديد pos به مقدار 1 تنطيم ميشود. MCD(CSAgent,Pos) نشان ميدهد که برروي عامل انجام شده است. در حقيقت الگوريتم 1 تنها يک پياده سازي عمومي از ايده MCD است و ميتواند براي تمام انواع CSP ها استفاده شود. براي CSP هاي خاص اين ايده ميتواند با دانشي از مسأله ترکيب شود. به عنوان مثال وقتي با مسأله رنگ آميزي گراف سروکار داريم درجه گره ميتواند استفاده شود.
پس از تعريف عامل به طور کامل، در اين مقاله، سه رفتار براي عاملها براي رسيدن به هدف طراحي شده است. اين رفتارها به ترتيب رفتار رقابتي113 ، رفتار خودآموز114 ، رفتار جهشي115 نامگذاري شده اند، که دوتاي اول مربوط به رفتار P و آخري متعلق به رفتار V است.
رفتار رقابتي: در اين رفتار انرژي يک عامل با همسايگانش مقايسه ميشود. يک عامل ميتواند زنده بماند اگر انرژياش نسبت به همسايگانش ماکسيمم باشد در غير اين صورت آن عامل بايد بميرد و يکي از فرزندان همسايه با بيشترين انرژي جايگزين او خواهد شد.
رفتار خودآموز: اجتماع جستجوي محلي با EA ميتواند عملکرد آن را بهبود بخشد. علاوه برا اين عاملها از مقداري دانش نسبت به مسأله برخوردار ميباشند. بنابراين با الهام گيري از تابع اکتشافي کمترين برخورد،[29] و [30] و بهره گيري از متد رمزگذاري براي عاملها، نويسندگان اين مقاله رفتار رفتار خودآموز را طراحي کرده اند. جزئيات اين روش در الگوريتم 3 در اين مقاله نشان داده شده است.
رفتار جهشي: اين رفتار مشابه همان جهشي است که در الگوريتم ژنتيک سنتي اتفاق ميافتد.اين متد در واقع براي کمک به عملکرد رفتار قبلي طراحي شده است.
پس از تعريف محيط، عاملها و همچنين طراحي رفتارها، الگوريتم MAEA-CSPs به صورت زير پياده سازي شده است. براي حل مسأله CSP، همه عاملها بايد اين سه رفتار را به ترتيب اتخاذ کنند. در اينجا اين رفتارها به وسيله ابزارهاي تکاملي کنترل شده است به طوريکه شبکه عاملها ميتواند نسل به نسل تکامل يابد. در هر نسل ابتدا رفتارهاي رقابتي در هر عامل انجام ميشود و در نتيجه عاملهايي با انرژي کم از شبکه حذف ميشوند و بنابراين فضا براي عاملهاي با انرژي بيشتر باز خواهد شد. سپس رفتارهاي خودآموز و جهش براساس نوع مسأله و حالت عاملها انجام ميشود. به منظور کاهش هزينه محاسباتي، دو رفتار اخير تنها در عاملهاي بهترين در شبکه عاملهاي جاري انجام ميشود. اين فرآيند به طور مکرر ادامه مييابد تا زماني که يک عامل با انرژي صفر يافته شود يا اينکه پيچيدگي محاسباتي ماکسيمم شود.
پس از پياده سازي اين روش نتايج ابتدا بر روي چند محک از کلاس مسائل ارضاء محدوديت غير جايگشتي همانند مسأله رنگ آميزي گراف و يا نمونه هاي مختلفي از مسائل ارضاء محدوديت باينري تست شده است و نتيجه با 4 الگوريتم ديگر مقايسه شده است. سپس تست براي بخش مسائل ارضاء محدوديت جايگشتي انجام شده که براي آن از محکهاي n-وزير و يا مسأله زمانبندي کار استفاده شده است. پيچيدگي فضايي و همگرايي به جواب به صورت تئوري آناليز شده است. همچنين آناليز پارامترها نشان ميدهد که الگوريتم MAEA-CSPs کاملا قوي116 است و همچنين استفاده از آن آسان است. در مرحله بعد اثبات شده که اين الگوريتم داراي پيچيدگي زماني O(n1.07) است و با مقايسه اين روش با 6 الگوريتم ديگر نشان داده اند که اين روش بسيار بهتر از روشهاي ديگر عمل ميکند. دلايل بهتر شدن اين روش نسبت به روشهاي قبل سه مورد عنوان شده است: اول طبقهبندي کردن مسائل CSP در دو دسته مسائل ارضاء محدوديت جايگشتي و مسائل ارضاء محدوديت غير جايگشتي بر اساس خصوصياتشان، بنابراين، رفتارها
ي عاملها ميتواند در دو نوع مختلف طراحي شود. دوم، رمزگذاري کمترين برخورد117 بر معايب متد رمزگذاري معمولي غلبه کرده است. البته اگرچه متد MCE خود يک روش حريصانه است اما رفتار جهش استفاده شده ميتواند از افتادن الگوريتم در نقطه بهينه محلي118 جلوگيري کند. و در پايان اينکه يک انتخاب طبيعي واقعي در طبيعت تنها در يک محيط محلي اتفاق ميافتد و يک فرد تنها ميتواند با محيط اطرافش در تعامل باشد. در شبکه عاملهاي طراحي شده براي اين کار هر عامل تنها ميتواند محيط محلي اش را درک کند و اين مدل به واقعيت نزديکتر است نسبت به انتخاب جمعيت در الگوريتمهاي تکاملي سنتي و همچنين در اين شبکه عاملهاي طراحي شده هيچ کنترل مرکزي نياز نيست.
شکل 3-6 نتيجه ارزيابي مقياسپذيري119 اين الگوريتم با افزايش ابعاد مسأله را نشان ميدهد. اين آزمايش بر روي مسأله n-وزير با رشد n از 5×104 تا 107 انجام شده است. نتيجه به دست آمده نشان ميدهد که الگوريتم MAEA-CSPs يک پيچيدگي زماني خطي O(n1.07) دارد.

شکل 3-6 ميانگين زمان اجراي الگوريتم MAEA-CSPs در حل مسأله n-وزير[3]
ارزيابي ديگر، مقايسه الگوريتم MAEA-CSPs با چهار الگوريتم ديگردر اجراي محکهاي مسائل ارضاء محدوديت باينري است. اين چهار الگوريتم در واقع چهار روش برتر از ميان 11 روش مورد مقايسه در[57] بود که عبارتند از : [59] و [58]H-GA.1, ، [59] و [58] H-GA.3 ، [60] و [61] SAW، [62] Glass-Box . اين کار بر روي test suite :
http://www.xs4all.nl/~bcraenen/resources/csps_modelE_v20_d20.tar.gz
که براي مقايسه کارايي 11 الگوريتم موجود در [57] استفاده شده، انجام گرفته است. که اين test suite حاوي 250 نمونه مختلف مسأله قابل حل است. هر نمونه 20 متغير دارد و دامنه اين متغيرها
D={Di | Di={1, 2, . . . , 20 } and 1?i?20 }
است. اين 250 نمونه بر اساس ميزان دشواري اشان در 10 گروه تقسيم بندي شده اند؛ p={0.24, 0.25, 0.26, 0.27, 0.28, 0.29, 0.30, 0.31, 0.32, 0.33} ، و هر گروه شامل 25 نمونه است. واضح است هر چه p بزرگتر باشد نسبت دشواري آن مسأله بيشتر است. در اينجا 10 اجراي مستقل در هر 25 نمونه از يک مقدار p داده شده انجام شده است که در کل 250 عدد نقطه داده اي120 براي محاسبه اندازه گيري استفاده شده است. ميزان سودمندي121 و کارايي122 اين الگوريتم توسط دو متد SR و ME اندازه گيري شده است. همانطور که گفتيم SR در واقع احتمال برد هر اجرا براي يافتن يک راه حل را نشان ميدهد، از آنجايي که تمام نمونه هاي موجود در test suit قابل حل هستند بيشترين مقدار SR، 100% است. خطا براي يک تک اجرا به صورت تعداد محدوديتهاي نقض شده توسط بهترين CSAgent در شبکه عاملها زماني که اجرا خاتمه مييابد تعريف ميشود. براي هر مجموعه اجراي داده شده ME ميانگين اين مقدار خطاها ست. کارايي123 به وسيله ميانگين تعداد ارزيابيها براي يک راه حل124 اندازه گيري ميشود، که به طور گسترده در اندازه گيري هزينه محاسباتي در EA ها مورد استفاده قرار ميگيرد.

شکل 3-7 مقايسه الگوريتم MAEA-CSPs با 4 الگوريتم ديگر با معيارهاي SR ، ME و AES [3]
همانطور که ميبينيم، SR الگوريتم MAEA-CSPs بالاترين مقدار را در ميان اين 5 الگوريتم دارد با مقداري برابر با 100% براي p=0.24-0.26 . همچنين شکل (.b) نشان دهنده اين است که MAEA-CSPs کمترين و در واقع بهترين مقدار ME را دارد. از آنجا که AES از نظر آماري زماني که SR بسيار پايين است قابل اعتماد نيست، EAS تنها زماني که SR بالاتر از 10% است رسم شده است. تماميSR هاي هر 5 الگوريتم براي p=0.30-0.33 پايين هستند اما ميزان ME براي MAEA-CSPs در اين بازه نسبت به بقيه بسيار کمتر است و حداکثر 1 تا 3 محدوديت ارضاء نشدهاند. خلاصه اينکه الگوريتم MAEA-CSPs بسيار بهتر از 4 روش ديگر عمل ميکند. جدول (3-1) مقادير به دست آمده براي الگوريتم MAEA-CSPs را بر روي محکهاي مسائل ارضاء محدوديت باينري را نشان ميدهد.

جدول(3-1): نتايج به دست آمده از آزمايش MAEA-CSPs بر روي محکهاي مسائل ارضاء محدوديت باينري
0.28
0.27
0.26
0.25
0.24
p
0.425
0.82
1
1
1
SR
0.548
0.18
0
0
0
ME
33666
26574
10384
3055
1400
AES
0.33
0.32
0.31
0.30
0.29
p
0.028
0.012
0.024
0.072
0.264
SR
2.725
2.204
1.736
1.164
0.774
ME
26281
57428
29324
39564
39486
AES

قدرت مورچه ها در حل مسائل ارضاء محدوديت توزيع شده
در سال 2012، سمانه حسيني سمناني و کامران زماني فر از دانشگاه اصفهان الگوريتمي برمبناي الگوريتم کلوني مورچگان براي حل مسائل ارضاء محدوديت توزيع شده ارائه دادند. اين مقاله قدرت مورچه ها را در حل DCSP ها نشان ميدهد و رويکرد جديدي را براي چنين راه حلي توصيف ميکند که نشان ميدهد که به چه طريقي با حل کننده هاي DCSP پيشين که بر مبناي ACO هستند متفاوت است. الگوريتم پيشنهادي براي تامين مقتضيات ويژهاي که در شکل توزيع شده مسأله ارضاء محدوديت مهم هستند، طراحي شده است. اين مقاله معيارهاي مهم براي CSP توزيع شده را توصيف ميکند و سپس نشان ميدهد که چگونه الگوريتم پيشنهادي با به شمار آوردن اين محدوديتها در مکاني بالاتر از حل کنندههاي DCSP مشابه قرار ميگيرد. نهايتا، رويکرد پيشنهادي در مورد مسائل باينري تصادفي ارزيابي ميشود. نتايج نشان ميدهند که اين روش، در بسياري از موارد، از الگوريتم عقبگرد آسنکرون 125و الگوريتم انفجاري توزيع شده126 که در اين حوزهي تحقيق دو الگوريتم مهم به شمار ميروند، بهتر عمل ميکند. اين مقاله در واقع، رويکردي ناقص را براي حل DCSP ها بر پايه بهينه سازي فرا اکتشافي 127 کلوني مورچگان توصيف ميکند که در آن نويسندگان مقاله سعي داشتهاند حوزههاي نويد بخش فضاي جست و جو را با قرار دادن رديابي فرومون128 دنبال کن
ند. اين رديابي ها به صورت يک تابع اکتشافي براي عاملها عمل ميکنند و آنها را به سوي انتخاب مقادير اميد بخشتر براي تخصيص دادن به متغيرهايشان هدايت ميکنند.
تنظيمات پارامتر
عملکرد اغلب الگوريتم هاي مورچه ها بسته به مقاديري است که براي پارامترهايشان انتخاب شده است. الگوريتم هاي مبتني بر مورچه ها که در اين مقاله ارائه شده اند با ?، ?، ? و تعداد مورچه ها ها پارامتربندي ميشوند. اين پارامترها معمولا به طور تجربي انتخاب شده اند و مقادير آن بستگي به مسألهاي دارد که قرار است حل شود. مقادير انتخاب شده براي اين سه پارامتر بنا بر آنچه در مقالات پيشين انتخاب شده به اين شرح است: 2=? ، 8=? ، 0.02=?. البته ديگر مقادير هم بررسي شدهاند اما از اين مقادير بهترين نتايج به دست آمده است. به نظر ميرسد مقدار آخرين پارامتر (تعداد مورچه ها) مستقيما متناسب با اندازه و پيچيدگي مسأله است. جدول (3-2) مقادير انتخاب شده براي اين پارامتر را در هر مسأله نشان ميدهد.
جدول (3-2): مقادير متفاوت از تعداد مورچه ها براي سايزها و تراکمهاي متفاوت
Density
size
2.7
2.3
2

3
4
2
15
7
8
6
30
10
12
9
45
15
16
12
60
17
18
16
75

همانطور که در جدول (3-2) مشاهده ميشود ستون هاي سمت چپ اندازه متفاوت مسائلي را نشان ميدهند که در آزمايشات استفاده شده است. اندازه مسأله تعداد گرهها در گراف محدوديت را نشان ميدهد. اولين رديف اين جدول نسبت تعداد يال ها به تعداد گره در هر مسأله را نشان ميدهد. مقادير متفاوت (2، 2.3 و 2.7) که براي اين نسبت انتخاب شدهاند مسائل متفاوتي را با درجات متفاوتي از دشواري نشان ميدهند. اين مقادير مخصوص به صورتي انتخاب شده اند که سه ناحيه مهم در مرحله انتقالي را ارائه ميدادند [51]. سختترين مسأله آنهايي بودند که دقيقا در فاز انتقال هستند و تراکم آنها برابر 2.3 است. به عنوان مثال، مسأله اي با اندازه 30 و تراکم 2.3 گرافي را با 30 گره و 69 =20*2.3 يال ارائه ميدهد. همه يالها به طور تصادفي بين يالهاي گراف ايجاد شدهاند. در آزمايشاتي که در اين تحقيق انجام شدند تعداد مورچه ها با بزرگتر شدن و سخت تر شدن حل مسأله افزايش مييابد. در ساده ترين مسأله با 15 گره و 30 يال، که الگوريتم از دو مورچه استفاده ميکند، الگوريتم ميتواند خيلي سريع راه حلي پيدا کند، همانطور که دشواري افزايش مييابد: نهايتا سختترين مسأله با 75 گره و 172 يال به 18 عدد مورچه براي جست و جوي فضاي مسأله براي يافتن راه حلي در طول زماني مناسب نياز دارد.
نتايج تجربي
در اين بخش الگوريتم مبتني بر کلوني مورچه ها را که در اين مقاله ارائه شده است با دو الگوريتم تحقيقي ديگر DCSP يعني الگوريتم عقبگرد آسنکرون و الگوريتم انفجاري توزيع شده مقايسه شده است. هر دو الگوريتم هاي به روز هستند و در بسياري از مقالات به عنوان الگوريتم هاي مرجع در مقايسه با ساير الگوريتم ها بکار ميروند. ABT يک الگوريتم کامل است. اما DBA الگوريتمي ناقص است که اگر هيچ راه حلي براي يک مسأله وجود


پاسخی بگذارید