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

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

Ant  Colony  Optimization
( ACO )

فهرست مطالب

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

           مقدمه

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

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

           – مزیتهای ACO

         – کاربرد ACO            

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

          – الگوریتم ACO

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

           – نتیجه گیری

مقدمه

الگوريتم کلوني مورچه براي اولين بار در سال 1992توسط دوريگو Dorigo) ) و همکارانش به عنوان يک راه حل

چند عامله (Multi Agent) براي مسائل مشکل بهينه سازي مثل فروشنده دوره گرد ارائه شد.

عامل هوشند  Intelligent Agent) )  موجودي است که از طريق حسگر ها قادر به

درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد.

آنچه بنيان فكري الگوريتم مورچگان بر آن بنا شده است را مي توان بسادگي و در يك جمله بيان نمود:

” مورچه ها در بين موانع و محدوديت هاي موجود در طبيعت هميشه

 از بين جايگشت هاي متفاوت براي رسيدن به غذا،

بهينه ترين راه را انتخاب مي كنند”.  

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

همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يک مسئله بهينه سازيست

که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گردTSP))

در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده،

به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند

و کوتاهترين مسير را نيز طي کرده باشد.

اگر تعداد اين شهرها n باشد در حالت کلي اين مسئله از مرتبه  (n-1)!است که براي فقط 21 شهر زمان واقعا زيادي مي برد:

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

با انجام يک الگوريتم برنامه سازي پويا براي اين مسئله ، زمان از مرتبه نمايي

بدست مي آيد که آن هم مناسب نيست.

البته الگوريتم هاي ديگري نيز ارائه شده ولي هيچ کدام کارايي مناسبي ندارند.

ACO الگوريتم کامل و مناسبي براي حل مسئله TSP است.

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

مورچه ها هنگام راه رفتن از خود ردي از ماده شيميايي فرومون (Pheromone  )

جاي مي گذارند البته اين ماده بزودي تبخير مي شود ولي در کوتاه مدت

بعنوان رد مورچه بر سطح زمين باقي مي ماند.

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

آنها هنگام انتخاب بين دو مسير بصورت احتمالاتيStatistical)   )

مسيري را انتخاب مي کنند که فرومون بيشتري داشته باشد يا بعبارت ديگر

مورچه هاي بيشتري قبلا از آن عبور کرده باشند.

حال می بینیم که همين تمهيد ساده چگونه منجر به پيدا کردن کوتاهترين مسير خواهد شد :

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

همانطور که در شکل مي بينيم مورچه ها روي مسير AB در حرکت اند (در دو جهت مخالف)

اگر در مسير مورچه ها مانعي قرار دهیم مورچه ها دو راه براي انتخاب کردن دارند.

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

اولين مورچه ازA  مي آيد و بهC  مي رسد، در مسير هيچ فروموني نمي بيند

بنابر اين براي مسير چپ و راست احتمال يکسان مي دهد

و بطورتصادفي و احتمالاتي مسير CED را انتخاب مي کند.

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

مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرومون را روي CED حس مي کنند

و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا)  انتخاب مي کنند. در نهايت مسير CED  بعنوان

مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED کوتاهتر است زمان رفت و برگشت

از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد

چون فرومون بيشتري در آن وجود دارد.

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

نکته بسيار با اهميت اين است که هر چند احتمال انتخاب مسير پر فرومون

تر توسط مورچه ها بيشتر است ولي اين کماکان احتمال است و قطعيت نيست.

يعني اگر مسير CED پرفرومون تر از CFD باشد به هيچ عنوان نمي شود نتيجه گرفت

که همه مورچه ها از مسيرCED  عبور خواهند کرد بلکه تنها مي توان گفت که

مثلا 90% مورچه ها از مسير کوتاهتر عبور خواهند کرد.

اگر تصادفا اولين مورچه مسير( CFDمسير دورتر) را انتخاب مي کرد و ردي از فرومون

بر جاي مي گذاشت آنگاه همه مورچه ها بدنبال او حرکت مي کردند و هيچ وقت کوتاهترين

مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در ACO بر عهده دارند.

متن بالا فقط تکه هایی از محتوی متن پروژه میباشد

که به صورت نمونه در این صفحه درج شده است.

شما بعد از پرداخت آنلاین فایل را فورا دانلود نمایید .

فرمت فایل :پاورپوینت

تعداد اسلاید:22