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

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

فرمت فایل دانلودی: .zip
فرمت فایل اصلی: pptx
تعداد صفحات: 160
حجم فایل: 3255
قیمت: 7500 تومان

بخشی از متن:
این پاورپوینت در مورد الگوریتم کلونی مورچه و زنبور عسل در 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 یک الگوریتم مناس

پرداخت با کلیه کارتهای عضو شتاب امکان پذیر است.