پاورپوینت درمورد الگوریتم کلونی مورچه ها
الگوریتم کلونی مورچه ها
Ant Colony Optimization
( ACO )
فهرست مطالب
پاورپوینت درمورد الگوریتم کلونی مورچه ها
مقدمه
بهینه سازی مسایل به روش کلونی مورچه
مورچه ها چگونه می توانند کوتاه ترین مسیر را پیدا کنند؟
– مزیتهای ACO
– کاربرد ACO
– مسیر یابی شبکه های کامپیوتری با استفاده از ACO
– الگوریتم ACO
– الگوریتم کلی حرکت
– نتیجه گیری
مقدمه
الگوریتم کلونی مورچه برای اولین بار در سال ۱۹۹۲توسط دوریگو Dorigo) ) و همکارانش به عنوان یک راه حل
چند عامله (Multi Agent) برای مسائل مشکل بهینه سازی مثل فروشنده دوره گرد ارائه شد.
عامل هوشند Intelligent Agent) ) موجودی است که از طریق حسگر ها قادر به
درک پیرامون خود بوده و از طریق تاثیر گذارنده ها می تواند روی محیط تاثیر بگذارد.
آنچه بنیان فکری الگوریتم مورچگان بر آن بنا شده است را می توان بسادگی و در یک جمله بیان نمود:
” مورچه ها در بین موانع و محدودیت های موجود در طبیعت همیشه
از بین جایگشت های متفاوت برای رسیدن به غذا،
بهینه ترین راه را انتخاب می کنند”.
بهینه سازی مسایل بوسیله کلونی مورچه
همانطور که می دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست
که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. بعنوان مثال مسئله فروشنده دوره گردTSP))
در این مسئله فروشنده دوره گرد باید از یک شهر شروع کرده،
به شهرهای دیگر برود و سپس به شهر مبدا بازگردد بطوریکه از هر شهر فقط یکبار عبور کند
و کوتاهترین مسیر را نیز طی کرده باشد.
اگر تعداد این شهرها n باشد در حالت کلی این مسئله از مرتبه (n-1)!است که برای فقط ۲۱ شهر زمان واقعا زیادی می برد:
روز۱۰۱۳*۷/۱ = S1016*433/2 = ms10*1018*433/2 = 20!
با انجام یک الگوریتم برنامه سازی پویا برای این مسئله ، زمان از مرتبه نمایی
بدست می آید که آن هم مناسب نیست.
البته الگوریتم های دیگری نیز ارائه شده ولی هیچ کدام کارایی مناسبی ندارند.
ACO الگوریتم کامل و مناسبی برای حل مسئله TSP است.
پاورپوینت درمورد الگوریتم کلونی مورچه ها
مورچه ها هنگام راه رفتن از خود ردی از ماده شیمیایی فرومون (Pheromone )
جای می گذارند البته این ماده بزودی تبخیر می شود ولی در کوتاه مدت
بعنوان رد مورچه بر سطح زمین باقی می ماند.
یک رفتار پایه ای ساده در مورچه های وجود دارد :
آنها هنگام انتخاب بین دو مسیر بصورت احتمالاتیStatistical) )
مسیری را انتخاب می کنند که فرومون بیشتری داشته باشد یا بعبارت دیگر
مورچه های بیشتری قبلا از آن عبور کرده باشند.
حال می بینیم که همین تمهید ساده چگونه منجر به پیدا کردن کوتاهترین مسیر خواهد شد :
مورچه ها چگونه می توانند کوتاه ترین مسیر را پیدا کنند؟
همانطور که در شکل می بینیم مورچه ها روی مسیر AB در حرکت اند (در دو جهت مخالف)
اگر در مسیر مورچه ها مانعی قرار دهیم مورچه ها دو راه برای انتخاب کردن دارند.
مورچه ها چگونه می توانند کوتاه ترین مسیر را پیدا کنند؟
اولین مورچه ازA می آید و بهC می رسد، در مسیر هیچ فرومونی نمی بیند
بنابر این برای مسیر چپ و راست احتمال یکسان می دهد
و بطورتصادفی و احتمالاتی مسیر CED را انتخاب می کند.
مورچه ها چگونه می توانند کوتاه ترین مسیر را پیدا کنند؟
مورچه ها در حال برگشت و به مرور زمان یک اثر بیشتر فرومون را روی CED حس می کنند
و آنرا بطور احتمالی و تصادفی ( نه حتما و قطعا) انتخاب می کنند. در نهایت مسیر CED بعنوان
مسیر کوتاهتر برگزیده می شود. در حقیقت چون طول مسیر CED کوتاهتر است زمان رفت و برگشت
از آن هم کمتر می شود و در نتیجه مورچه های بیشتری نسبت به مسیر دیگر آنرا طی خواهند کرد
چون فرومون بیشتری در آن وجود دارد.
پاورپوینت درمورد الگوریتم کلونی مورچه ها
نکته بسیار با اهمیت این است که هر چند احتمال انتخاب مسیر پر فرومون
تر توسط مورچه ها بیشتر است ولی این کماکان احتمال است و قطعیت نیست.
یعنی اگر مسیر CED پرفرومون تر از CFD باشد به هیچ عنوان نمی شود نتیجه گرفت
که همه مورچه ها از مسیرCED عبور خواهند کرد بلکه تنها می توان گفت که
مثلا ۹۰% مورچه ها از مسیر کوتاهتر عبور خواهند کرد.
اگر تصادفا اولین مورچه مسیر( CFDمسیر دورتر) را انتخاب می کرد و ردی از فرومون
بر جای می گذاشت آنگاه همه مورچه ها بدنبال او حرکت می کردند و هیچ وقت کوتاهترین
مسیر یافته نمی شد. بنابراین تصادف و احتمال نقش عمده ای در ACO بر عهده دارند.
- ۹۷/۰۵/۳۰