پاورپوینت الگوریتم کلونی مورچه و زنبور عسل،

دسته بندي : کتاب » فنی و مهندسی
این پاورپوینت در مورد الگوریتم کلونی مورچه و زنبور عسل در 160 اسلاید زیبا شامل الگوریتم کلونی مورچه و زنبور عسل،شرح الگوریتم کلونی مورچه و زنبور عسل،لگوریتم کلونی زنبور عسل،الگوریتم زنبور،الگوریتم کلونی مورچه ها،الگوریتم مورچه،الگوریتم بهینه سازی مورچه،Ant Colony Optimization Algorithm ،شبکه عصبی،بهینه‌سازی گروه مورچه‌ها یا ACO ،الگوریتم کلونی مورچه،ABC،،و....می باشد.



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

مسير يابي داخل شهري و بين شهري
مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا
مسير يابي شبکه هاي کامپيوتري
مسير يابي شبکه هاي کامپيوتري با استفاده از ACO :

در ابتدا مقدمه اي از نحوه مسير يابي در شبکه هاي کامپيوتري را توضيح خواهيم داد :

اطلاعات بر روي شبکه بصورت بسته هاي اطلاعاتي کوچکي (Packet) منتقل مي شوند. هر يک از اين بسته ها بر روي شبکه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي که مسيرياب (Router) نام دارند عبور مي کنند. در داخل هر مسيرياب جدولي قرار دارد تا بهترين و کوتاهترين مسير بعدي تا مقصد از طريق آن مشخص مي شود، بنابر اين بسته هاي اطلاعاتي حين گذر از مسيرياب ها با توجه به محتويات اين جداول عبور داده مي شوند.

روشي بنام ACR : Ant Colony Routering پيشنهاد شده که بر اساس ايده کلوني مورچه به بهينه سازي جداول مي پردازيد و در واقع به هر مسيري با توجه به بهينگي آن امتياز مي دهد. استفاده از ACR به اين منظور داراي برتري نسبت به ساير روش هاست که با طبيعت ديناميک شبکه سازگاري دارد، زيرا به عنوان مثال ممکن است مسيري پر ترافيک شود يا حتي مسير يابي (Router) از کار افتاده باشد و بدليل انعطاف پذيري که ACO در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترس قرار مي دهد.

در دنیای واقعی مورچه‌ها ابتدا به طور تصادفی به این سو و آن سو می روند تا غذا بیابند. سپس به لانه بر می گردند و ردّی از فرومون(Pheromone) به جا می گذارند. چنین ردهایی پس از باران به رنگ سفید در می آیند و قابل رویت اند. مورچه های دیگر وقتی این مسیر را می یابند، گاه پرسه زدن را رها کرده و آن را دنبال می کنند. سپس اگر به غذا برسند به خانه بر می گردند و رد دیگری از خود در کنار رد قبل می گذارند؛ و به عبارتی مسیر قبل را تقویت می کنند. فرومون به مرور تبخیر می‌شود که از سه جهت مفید است:

- باعث می‌شود مسیر جذابیت کمتری برای مورچه‌های بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راه های کوتاه‌تر را بیش تر می‌پیماید و تقویت می‌کند هر راهی بین خانه و غذا که کوتاه‌تر(بهتر) باشد بیشتر تقویت می‌شود و آنکه دورتر است کمتر

- اگر فرومون اصلاً تبخیر نمی شد، مسیرهایی که چند بار طی می‌شدند، چنان بیش از حد جذّاب می‌شدند که جستجوی تصادفی برای غذا را بسیار محدود می‌کردند.

- وقتی غذای انتهای یک مسیر جذاب تمام می‌شد رد باقی می‌ماند.

لذا وقتی یک مورچه مسیر کوتاهی (خوبی) را از خانه تا غذا بیابد بقیه ی مورچه‌ها به احتمال زیادی همان مسیر را دنبال می‌کنند و با تقویت مداوم آن مسیر و تبخیر رد های دیگر، به مرور همه ی مورچه ها هم مسیر می‌شوند. هدف الگوریتم مورچه‌ها تقلید این رفتار توسط مورچه‌هایی مصنوعی ست که روی نمودار در حال حرکت اند. مساله یافتن کوتاه‌ترین مسیر است و حلالش این مورچه‌های مصنوعی اند.

از کابردهای این الگوریتم، رسیدن به راه حل تقریباً بهینه در مسئله فروشنده دوره‌ گرد است. به طوری که انواع الگوریتم مورچه‌ها برای حل این مساله تهیه شده. زیرا این روش عددی نسبت به روشهای تحلیلی و genetic در مواردی که نمودار مدام با زمان تغییر کند یک مزیت دارد؛ و آن این که الگوریتمی ست با قابلیت تکرار. و لذا با گذر زمان می‌تواند جواب را به طور زنده تغییر دهد. که این خاصیت در روتینگ شبکه های کامپیوتری و سامانه حمل و نقل شهری مهم است.

استفاده پژوهشگران از الگوي کلوني مورچه‌ها جهت اداره ترافيک

پژوهشگران سوييسي به تازگي براي تهيه نرم افزاري جهت اداره ترافيک و شبکه هاي جاده اي از الگوي کلوني مورچه ها استفاده مي کنند.به گزارش باشگاه خبرنگاران به نقل از شبکه يورونيوز، کلني مورچه ها قادر است هم زمان تعداد زيادي از فعاليتهاي روزمره را اداره کند که عبارتند از رسيدگي به تخمها ، ساخت تونل و رفت و امد براي يافتن اذوقه.همه اين فعاليتها به دقت سازماندهي شده است.

به گفته پژوهشگران مورچه ها نوعي هوش جمعي دارند. مشاهده ساختارهاي اجتماعي انان نتيجه مبادلات چند جانبه اي است که به ظاهر ساده اند. اين مبادلات به کمک ارتباطهاي شيميايي صورت مي گيرد که مورچه ها با شاخکهاي خود اين علائم را دريافت مي کنند. فرومون ماده اي شيميايي است که مورچه پس از عبور از خود برجا مي گذارد.ازمايشي ساده اين پديده را ثابت مي کند. پژوهشگران با قراردادن دو مسير کوتاه و بلند در برابر مورچه ها براي رسيدن به غذا پي بردند پس از مدتي همه مورچه ها از مسير کوتاه تر عبور مي کنند که علت ان تمرکز فرومون در مسير انان است.هر چه ميزان تمرکز فرومون در مسير کوتاه تر بيشتر باشد ميزان تردد در ان بيشتر مي شود.مورچه ها در طبيعت با اين ماده مي توانند کوتاه ترين مسير را بين لانه خود و چندين منبع غذايي پيدا کنند.اين توان مورچه ها به الگوريتمي تبديل شده است که با ان نرم افزاري براي اداره ترافيک جاده اي تهيه شده است.به اين ترتيب مي توان کوتاهترين مسير را بين چند شهر تشخيص داد.در اين نرم افراز فرايند ترددهاي يک کاميون براي تحويل بار به مشتريانش به مسير يک مورچه تشبيه مي شود و اين فرايند با توجه به تحولات غيرمنتظره ممکن است تغيير کند. با اين روش بهينه سازي بر پايه رفتار مورچه ها شرکتي مي تواند مسير تحويل بارهايش را در مدت زمان پانزده دقيقه انجام دهد.دهها هزار خودرو مي توانند با اين نرم افزار مسير خود را بهينه سازي کنند .

بهينه‌سازي مسائل بروش کلوني مورچه (ACO):

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

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

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

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

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

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

همانطور که در شکل 1-1 مي بينيم مورچه هاي روي مسير AB در حرکت اند (در دو جهت مخالف) اگر در مسير مورچه ها مانعي قرار ديهم(شکل 2-1) مورچه ها دو راه براي انتخاب کردن دارند. اولين مورچه ازA مي آيد و بهC مي رسد، در مسير هيچ فروموني نمي بيند بنابر اين براي مسير چپ و راست احتمال يکسان مي دهد و بطور تصادفي و احتمالاتي مسير CED را انتخاب مي کند. اولين مورچه اي که مورچه اول را دنبال مي کند زودتر از مورچه اولي که از مسير CFD رفته به مقصد مي رسد. مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرومون را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا) انتخاب مي کنند. در نهايت مسير CED بعنوان مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED کوتاهتر است زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد چون فرومون بيشتري در آن وجود دارد.

نکته بسيار با اهميت اين است که هر چند احتمال انتخاب مسير پر فرومون ت توسط مورچه ها بيشتر است ولي اين کماکان احتمال است و قطعيت نيست. يعني اگر مسير CED پرفرومون تر از CFD باشد به هيچ عنوان نمي شود نتيجه گرفت که همه مورچه ها از مسيرCED عبور خواهند کرد بلکه تنها مي توان گفت که مثلا 90% مورچه ها از مسير کوتاهتر عبور خواهند کرد. اگر فرض کنيم که بجاي اين احتمال قطعيت وجود مي داشت، يعني هر مورچه فقط و فقط مسير پرفرومون تر را انتخاب ميکرد آنگاه اساسا اين روش ممکن نبود به جواب برسد. اگر تصادفا اولين مورچه مسيرCFD(مسير دورتر) را انتخاب مي کرد و ردي از فرومون بر جاي مي گذاشت آنگاه همه مورچه ها بدنبال او حرکت مي کردند و هيچ وقت کوتاهترين مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در ACO بر عهده دارند.

نکته ديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير AB برداشته شود و فرومون تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرومون و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند.

مزيت‌هاي ACO:

همانطور که گقته شد «تبخير شدن فرومون» و «احتمال-تصادف» به مورچه ها امکان پيدا کردن کوتاهترين مسير را مي‌دهند. اين دو ويژگي باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازي مي شوند. مثلا در گراف شهرهاي مسئله فروشنده دوره گرد، اگر يکي از يالها (يا گره ها) حذف شود الگوريتم اين توانايي را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا کند. به اين ترتيب که اگر يال (يا گره اي) حذف شود ديگر لازم نيست که الگوريتم از ابتدا مسئله را حل کند بلکه از جايي که مسئله حل شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها مي توانند پس از مدت کوتاهي مسير بهينه(کوتاهترين) را بيابند.

کاربردهاي ACO:

از کاربردهاي ACO مي‌توان به بهينه کردن هر مسئله‌اي که نياز به يافتن کوتاهترين مسير دارد، اشاره نمود:

مسير يابي داخل شهري و بين شهري
مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا
مسير يابي شبکه هاي کامپيوتري
مسيريابي شبکه‌هاي کامپيوتري با استفاده از ACO:

در ابتدا مقدمه اي از نحوه مسير يابي در شبکه هاي کامپيوتري را توضيح خواهيم داد:

اطلاعات بر روي شبکه بصورت بسته هاي اطلاعاتي کوچکي (Packet) منتقل مي شوند. هر يک از اين بسته ها بر روي شبکه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي که مسيرياب (Router) نام دارند عبور مي کنند. در داخل هر مسيرياب جدولي قرار دارد تا بهترين و کوتاهترين مسير بعدي تا مقصد از طريق آن مشخص مي شود، بنابر اين بسته هاي اطلاعاتي حين گذر از مسيرياب ها با توجه به محتويات اين جداول عبور داده مي شوند.

روشي بنام ACR : Ant Colony Routering پيشنهاد شده که بر اساس ايده کلوني مورچه به بهينه سازي جداول مي‌پردازيد و در واقع به هر مسيري با توجه به بهينگي آن امتياز مي دهد. استفاده از ACR به اين منظور داراي برتري نسبت به ساير روش هاست که با طبيعت ديناميک شبکه سازگاري دارد، زيرا به عنوان مثال ممکن است مسيري پر ترافيک شود يا حتي مسير يابي (Router) از کار افتاده باشد و بدليل انعطاف پذيري که ACO در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترس قرار مي دهد.

روش بهینه‌‌سازی گروه مورچه‌ها بهینه‌سازی گروه مورچه‌ها یا ACO یک الگوریتم مناس