الگوریتم کلونی مورچه ها

دانلود  الگوریتم کلونی مورچه اسلاید

فهرست مطالب:

           - مقدمه

           -  بهینه سازی مسایل روش کلونی مورچه

           - مورچه چگونه میتوانند کوتاه ترین مسیر پیدا کنند؟

           - مزیتهای ACO

         - کاربرد ACO            

           - مسیر یابی شبکه کامپیوتری استفاده ACO

          - الگوریتم ACO

           - الگوریتم کلی حرکت

           - نتیجه گیری

مقدمه:

الگوریتم کلونی مورچه برای اولین بار سال 1992توسط دوریگو Dorigo) ) همکارانش یک راه حل چند عامله (Multi Agent) برای مسائل مشکل بهینه سازی فروشنده دوره گرد ارائه شد.

عامل هوشند  Intelligent Agent) )  موجودی است طریق حسگر قادر درک پیرامون خود بوده طریق تاثیر گذارنده می تواند روی محیط تاثیر بگذارد.

آنچه بنیان فکری الگوریتم مورچگان آن بنا شده است می توان بسادگی و در یک جمله بیان نمود: " مورچه بین موانع محدودیت های موجود طبیعت همیشه از بین جایگشت های متفاوت برای رسیدن به غذا، بهینه ترین راه را انتخاب می کنند".  

بهینه سازی مسایل بوسیله کلونی مورچه

همانطور می دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست گاه حل آن بسیار دشوار است گاه نیز بسیار زمانبر. بعنوان مثال مسئله فروشنده دوره گردTSP)) این مسئله فروشنده دوره گرد باید یک شهر شروع کرده، شهرهای دیگر برود سپس شهر مبدا بازگردد بطوریکه هر شهر فقط یکبار عبور کند کوتاهترین مسیر نیز طی کرده باشد. اگر تعداد این شهرها n باشد حالت کلی این مسئله مرتبه  (n-1)!است برای فقط شهر زمان واقعا زیادی می برد:

روز1013*7/1 =  S1016*433/2 = ms10*1018*433/2 = 20!

با انجام یک الگوریتم برنامه سازی پویا برای این مسئله ، زمان مرتبه نمایی بدست می آید آن مناسب نیست. البته الگوریتم های دیگری نیز ارائه شده ولی هیچ کدام کارایی مناسبی ندارند. ACO الگوریتم کامل مناسبی برای حل مسئله TSP است.

مورچه چگونه میتوانند کوتاه ترین مسیر پیدا کنند؟

مورچه هنگام راه رفتن خود ردی ماده شیمیایی فرومون (Pheromone  ) جای می گذارند البته این ماده بزودی تبخیر می شود ولی کوتاه مدت بعنوان رد مورچه سطح زمین باقی می ماند.

یک رفتار پایه ای ساده مورچه های وجود دارد :

آنها هنگام انتخاب بین دو مسیر بصورت احتمالاتیStatistical)   ) مسیری انتخاب می کنند فرومون بیشتری داشته باشد یا بعبارت دیگر مورچه های بیشتری قبلا آن عبور کرده باشند. حال میبینیم همین تمهید ساده چگونه منجر پیدا کردن کوتاهترین مسیر خواهد شد :...............