معرفی روش های اصلاح شده در بهينه سازی کولونی مورچه ها

صفحه 1:


صفحه 2:
بنام خدا 

صفحه 3:
معرفي روشهاي اصلاح شده در بهیته سازي كولوني مور چه ها و پیتننهاد یک ‎{ee‏ ۱ 

صفحه 4:
2 we vey oa * روش هاي متفاوت بهينه سازي هوشمند ر# بهينه سازي كولوني.مورجه ها ‎eras ry‏ ار ‏او ‏اه زور۱ ل 406 8 ‎8 ‎Te ee P alias ie ‎ 

صفحه 5:
ee OSE Dn ‏ا ا‎ New eee SROs nee Dy ‏كارايي چنداني ندارند ترد‎ ‏وقت‎ * ‏هزینه زیاد‎ * ‏بررسي تمامي فضاي جواب تقريبا غير ممكن است‎ * ‏ل ل را لد‎ ‏كستره فضاي جستجو را" كاهش دهند.‎ ‏اف‎ ‏انجام چنین فرایند هايي موفق تر عمل مي کنند.‎ ‏شبكه هاي عصبي و بهينه سازي‎ tthe CDE OCS ID) 20 ‏ا‎ Leer rene ‏و‎ 

صفحه 6:
Nye ‏او‎ حل این مسنله مخصوصا وقتي تعداد شهرها زياد باشدء با 7 0 را ات در زر ۵ ۹۹۹ ‏ره‎ serene ‎cap ate | Wim rascal‏ اعمانون .رده برمدمس// :مهدا ‎UMN p Ae eM NCA ICR icc‏ 

صفحه 7:
2060 0 2 ss 

صفحه 8:
و ا 4 ره ۱۱۱ برلیاولین‌بار مطرح شد. مشاهده شده است که مورچه ها معمولا بعد از گذشت مدت ‎ee SE Ie)‏ ۱ به صورت.دسته جمعي از اين مسير استفاده مي كنند. مكانيزم حاكم بر رفتار أآنها به اين صورت است كه هر مورچه به سمت هدف مورد نظر (غذا) حرکت مي كند وادر ‎BN (canara) Chee ere ere ree ae er‏ ‎oe eee Eye eer Cars Neer) WEES‏ ثابتي تبخير مي شود و مورجه هاي ديكر را به سمت خود جذب مي کند. 

صفحه 9:
,© به طور همزمان تعداد زيادي مورجه به اين كار يرداخته و مسير هاي مختلف را آزمایش مي کنند. بنابراين مورجه ها به مسيري همكراءخواهند شد كه فرمون در آن از غلظت بيشتري برخوردار است. 

صفحه 10:
۲ ‏ات‎ ‎50 ere epeneccy pe eee 

صفحه 11:
#7 با توجه به احتمالات» به طور متوسط يك از دو جهت به راه خود ادامه مي دهند» مساو 

صفحه 12:
زمان مسير هاي کوتاه تر» حاوي فرمون تر مورجه ها به سمت مسير هاي كوتاه تر 

صفحه 13:
ار 7 واقع مورچه ال اي هستند که با ار تباط سم( ۰ ( ۱ از فرمون و این حافظه» جواب مسئله را به صورت 

صفحه 14:
ما مسئله هاي 750505 متقارن در- مختصات دو بعدي را ا را رد ۱ مي كنيم» هرشهر با يك جفت مرتب ( ارم , 4< ) نشان داده مي شود. مرا فاصله اقليدسي بين ذو شهر ,و7 مي ‎a eg‏ ميخي ‎ea‏ ار تال دز شهر هاي موجود قرار مي دهیم و مورجه ها طبق قانون ‎Rye ie ree aes ee ee eee Ee‏ انتخاب مي کنند. در این انتخاب دو معیار به طور همزمان مد نظر قرار مي كيرند: ). فاصله تا شهر بعدي و 

صفحه 15:
(* در ابتداي الكوريتم فرمون موجود در تمامي مسيرها برابر فرض شده ومقداري در بازه [1(,0] به آن اختصاص ذداذه مي شود. سيس شهر مقصد يا شهرح با توجه به معيارهاي بالاء از فرمول زير محاسبه مي شود: 

صفحه 16:
oe rer ese) ‏رل را زر(‎ ce ‏الل‎ ‏شهر هايي است كه مورجه ءا ام از ان عبور تكرده‎ استء احتمال انتخاب شهر 2:به عنوان شهر بعدي از رابطه زير محاسبه مي شود: 

صفحه 17:
وجود 6 تا حدي به الکوریتم حالت تصلافي تزریق مي ‎OES IETS‏ خر رل مينيمم موضعي بالا خواهد بود جرا كه استفاده از 0683 ‎ee‏ ا ل ل ل ی كند كه تا حدي از دام مينيمم موضعي برهد. ۶ براي بدست آوردن جواب بهینه مقادير يارامتر ها بايد به ‎eC‏ و 1 مك رادي وابسته به مسئله خواهند بود اما طبق نتايج شبيه سازي هاي انجام شده مقادير ©.00 - 00 و © - 6 منجر به نتايج 

صفحه 18:
ا ال در در از را شده» در دى مرخله تغييز مي كند: | رت ار ۹۳ 2- مر 

صفحه 19:
2 Isiisne] هر باركه همه مورجه ها به شهري كه سفر خود را ازائجا اغاز ا ا ل ل 0 5000 را بدست مي آوريم و مسير هر كدام از مورجه ها را كه كوتاه تر لا له ابتدا فرمون تمامي مسير ها زا.به يك نسبت كم .مي كنيم (در بحث حاضر در اين مرحله مقدار فرمون تمامي مسير ها در ©.00 ضرب شده است.) و مقداري فرمون به تمام بل هايي که عضو ‎Wee eee aS re TO Ber]‏ ۱ ‎ae ere meme‏ ل تر زد بره نا ‎Jb Se‏ کوتاه ترین مسیر برابرخواهد بود. 

صفحه 20:
۲۰۰ ۰ ‏وی‎ Umea ِ تست تم میرف مرو ادا 0 ۳ Se} 1 ae 4 a ‏يارامتر .© تضعيف فرمون (تبخير)‎ ‏سات ما نفدو طول کوتاه ترین مسیر طی‎ ‏ا ل د”‎ 

صفحه 21:
۱ ٩۱ * براي اینکه علاوه بر بهترین مورچه به دیگر مورچه ها هم اهمیت قایل شويم و بتوانيم از اطلاعات با ارزش مسير آنها استفاده كنيم ىدا بلس ا اا 0 ديكر مي رود: بايد در مسير يَتُموده شنده مقداري فرمون طبق فرمول زير تزريق شود و در عين حال به طور همزمان بايد عمل تبخير نيز اعمال رد ‎eee ep ee eae DM)‏ ار رن ‎peeve Sie tO Oe eee Rc a ee Ber!‏ ‎ 

صفحه 22:
ا اا اك 0. روش 00 ل ‎Ober‏ ‏تزريقي را خودش ياد مي كيرد .اطلاعات بيشتر در مرجع[ ك] آمده است. در اين روش مقدار فرمون تزريقي برابر خواهد بود با: ضريب + در آن مقداري ثابت و در بازه [0(,0] است ‎ES oo‏ ل 2 2 ل ‎(REI‏ ‏قرار دهيم. ‎oe‏ ل لك ۱ 0 

صفحه 23:
(© طبق شبيه سازي"هاي انجام شده زوشهاي اول و دوم هر دو ا ل ل ا ا ا لا ال لل تسس |دست! باعت مي شود الكوريتم خيلي سریع به مینیمم موضعي همگر| شود. 

صفحه 24:
الكوريتم هاي اصلاح شده 

صفحه 25:
416 6 Cotvay Gystesr) در اين روش از ایده كولوني هاي موازي استفاده شده ‎lps Jha se eyo‏ يه تيس هاي موضعي دارد. روش ©0000 از فيدبك مثبت استفاده مي ‎EE ARH rao eCmer‏ منفي را هم وارد الكوريتم كرد. در اين روش () كولوني ‎eer‏ ور ام مر وم سم سل را (!,>ا) مورجه ! ام است كه به كولوني ءا ام تعلق دارريد. در ‎OLS)‏ ا ا ا حرکت مي باشند . هر مورچه در بازه زماني[0,] » از شهر ز به شهر ز مي رود. 

صفحه 26:
Pheromone trail An ant continuously moves to a next city according to preference for the intensitiy of pheromone and proximity to it. An ant generating a good tour can lay stronger intensity of pheormone through subtours. Colony 3 Colony 1 

صفحه 27:
( نحوه انتقلب د ودر زير توضيح داده مي شود: ‎iene 5310)‏ ل الا ل )( ۱ ام در زمان ؛ بكيريم و ضريب تبخير و طول ىم علي شده توسط مورجه ي (دا,ءا) باشدء بعد از © بازه ي زماني ميزان فرمون بين كد | 051 كك 06 ۲ 

صفحه 28:
بر كت ال الگوریتم ار موترتري را ایفا مي کند جرا که به دلیل تعدد كولوني ها تعداد وب ها بالا رفتة و فضاي جستجوهوسیع تر شذه است و در وم ا ا را ۱ اثر به دام افتادن در مینیمم هاي موضعي بسیار پایین مي آید. 

صفحه 29:
(* 77 میزانتمایلبه انتخابشیر و لسلکسه در لثر ارتباط بسین كولوتي‌ه شکلمي‌گیرد.) اه باشدء ‎ee DE ee‏ را ۱ فرمور) و لكر منفيباشدء فيدبكمنفيليجاد خواهد شد(كاهشس ‎Pere Pen aces cee Bore‏ نخولهد دلشتِ ()پارلمتر بایاس‌لستو هميشه میزا ن ثابتياز ‎Cee‏ اك 

صفحه 30:
ee eee eet ep rele ‏ا‎ ‎1 700 2 _ a) ue NotVisited™ (2) ان وله 0 if j€ NotVisited™ (t) of = 

صفحه 31:
1۹۹۱/۹/6 (Ceseicaly OodPied PCC) © بررسي ها"در جهت كشف روابط ميان بارامترها با هم و تاثير آنها بر سرعت. همكراييء منجر به استفاده از 8 شد. استفاده از الكوريتم زنتيكي باعث مي ا ات توسط مورچه ها ایجاد شود. 

صفحه 32:
5 0 ee} ال ‎ESP OSes eer‏ در تکرار قبلي طي کرده و بهترین طول بدست آمده توسط مورچه هاي ديكر. دددوى ا د20 براي هر مورجه برابر است با ارزش هر ا ‎ES‏ ‎uae‏ مرا ‏امسر مد 

صفحه 33:
x3 7 7 1 ‏تفت‎ Grd ‏ناك‎ 

صفحه 34:
و ۱ لا ‎EAN GS WARE‏ برخوردي میان بلج ها وجود نخواهد داشت تطر ‎Me‏ 

صفحه 35:
وی را ۱۵0 مسئله 2150502 و بررسي را رد مراحل بين بعضي دبل هاء تقاطع وجود دارد كه باعث مي شود سرعت“"همكرايي كاهش يابد.و يا در اغلب موارد در مينيمم مَوضعي به دام بيفتد. © مشكل اصلي در ايّن ارتباط كه با احتمال بالا رخ مي دهد اين است كه مسير زر وجود داردء باعث ايجاد تقاطع مي شود. 

صفحه 36:
ا ‎fe Rene TEES See br‏ ‎SPOR Dre Lee Core erat ae Er Romer‏ مي گیرد. در هر مفایسه دو سمل مورد مقایسه حذف مي شوند در نتیجه مسیر كلي جواب,به دو مسیرک جدا.از هم تفسیم مي شود. به رک رل یو رل کرد فا سیر بسته شود. هر بار با امتحان هر دو شيوه اتصالء آرايشي انتخاب مي شود که طول كمتري را بدست دهد. 

صفحه 37:
‎ID)‏ را با اجراي يك ‎ey ben ie Pree er‏ 02 22 دهیم که با هم تقاطع داشته باشند. ‎(Ee) (Cp dete pial SEO‏ ار ويررسي تقاطع در هر یک از. مجموعه هاء سرعت عملياتي را افزایش مي دهیم . 

صفحه 38:


صفحه 39:


صفحه 40:
۱ ‏ل‎ re rae) می بینیم: ite ll 0 kro OD نتایج با رم بعد از بح ‎deo‏ 4 none) Vac ce ee) eee - 9 (Wem ‏یک‎ as De hace ee ee trur OO اه ما ۱/۳۰۰9 2 مه ار دم 

صفحه 41:
© بنابراين اين روش را ‎eee ere ere eerie reser Ca)‏ کیرد.در بحتهای راهم سرعت بالاتري سبت به آن ‎ys‏ 

صفحه 42:
با تشكر از. حوضله شما بزركواران ا ‎(EATER‏ ‏0 ‎OPES‏ ل ا ا لت 0