پاورپوینت کامل و جامع با عنوان الگوریتم بهینه سازی کلونی مورچگان (ACO) در 75 اسلاید - دانلود فایل
دانلود فایل پاورپوینت کامل و جامع با عنوان الگوریتم بهینه سازی کلونی مورچگان (ACO) در 75 اسلاید
دانلود فایل پاورپوینت کامل و جامع با عنوان الگوریتم بهینه سازی کلونی مورچگان (ACO) در 75 اسلاید
بهینه سازی گروه مورچه ها یا ACO همانطور که می دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. برای مثال مسئله فروشنده دوره گرد را نیز می توان مطرح کرد. در این روش(ACo)، مورچه های مصنوعی به وسیلهٔ حرکت بر روی نمودار مسئله و با باقی گذاشتن نشانه هایی بر روی نمودار، همچون مورچه های واقعی که در مسیر حرکت خود نشانه های باقی می گذارند، باعث می شوند که مورچه های مصنوعی بعدی بتوانند راه حل های بهتری را برای مسئله فراهم نمایند. همچنین در این روش می توان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت.
روش که از رفتار مورچه ها در یافتن مسیر بین محل لانه و غذا الهام گرفته شده؛ اولین بار در ۱۹۹۲ توسط مارکو دوریگو (Marco Dorigo) در پایان نامهٔ دکترایش مطرح شد.
مقدمه الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه ها حشراتی اجتماعی هستند که در کلونی ها زندگی می کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچه ها دارای نوعی هوشمندی توده ای است که اخیراً مورد توجه دانشمندان قرار گرفته است در دنیای واقعی مورچه ها ابتدا به طور تصادفی به این سو و آن سو می روند تا غذا بیابند. سپس به لانه بر می گردند و ردّی از فرومون (Pheromone) به جا می گذارند. چنین ردهایی پس از باران به رنگ سفید در می آیند و قابل رویت اند. مورچه های دیگر وقتی این مسیر را می یابند، گاه پرسه زدن را رها کرده و آن را دنبال می کنند. سپس اگر به غذا برسند به خانه بر می گردند و رد دیگری از خود در کنار رد قبل می گذارند؛ و به عبارتی مسیر قبل را تقویت می کنند. فرومون به مرور تبخیر می شود که از سه جهت مفید است:
- باعث می شود مسیر جذابیت کمتری برای مورچه های بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راه های کوتاه تر را بیش تر می پیماید و تقویت می کند هر راهی بین خانه و غذا که کوتاه تر (بهتر) باشد بیشتر تقویت می شود و آنکه دورتر است کمتر.
- اگر فرومون اصلاً تبخیر نمی شد، مسیرهایی که چند بار طی می شدند، چنان بیش از حد جذّاب می شدند که جستجوی تصادفی برای غذا را بسیار محدود می کردند.
- وقتی غذای انتهای یک مسیر جذاب تمام می شد رد باقی می ماند.
از کابردهای این الگوریتم، رسیدن به راه حل تقریباً بهینه در مسئله فروشنده دوره گرد است. به طوری که انواع الگوریتم مورچه ها برای حل این مسئله تهیه شده. زیرا این روش عددی نسبت به روشهای تحلیلی و genetic در مواردی که نمودار مدام با زمان تغییر کند یک مزیت دارد؛ و آن این که الگوریتمی ست با قابلیت تکرار. و لذا با گذر زمان می تواند جواب را به طور زنده تغییر دهد. که این خاصیت در روتینگ شبکه های کامپیوتری و سامانه حمل و نقل شهری مهم است.
در مسئله فروشنده دوره گرد باید از یک شهر شروع کرده، به شهرهای دیگر برود و سپس به شهر مبدا بازگردد بطوریکه از هر شهر فقط یکبار عبور کند و کوتاهترین مسیر را نیز طی کرده باشد. اگر تعداد این شهرها n باشد در حالت کلی این مسئله از مرتبه (n-1)! است که برای فقط ۲۱ شهر زمان واقعاً زیادی می برد:
روز۱۰۱۳*۷/۱ = S۱۰۱۶*۴۳۳/۲ = ms۱۰*۱۰۱۸*۴۳۳/۲ =!۲۰
با انجام یک الگوریتم برنامه سازی پویا برای این مسئله، زمان از مرتبه نمایی بدست می آید که آن هم مناسب نیست. البته الگوریتم های دیگری نیز ارائه شده ولی هیچ کدام کارایی مناسبی ندارند. ACO الگوریتم کامل و مناسبی برای حل مسئله TSP است.
مزیتهای ACO<تبخیر شدن فرومون> و <احتمال-تصادف>به مورچه ها امکان پیدا کردن کوتاهترین مسیر را می دهد. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینه سازی می شوند. مثلاً در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گره ها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال (یا گره ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچه ها می توانند پس از مدت کوتاهی مسیر بهینه (کوتاهترین) را بیابند.
کاربردهای ACOاز کاربردهای ACO می توان به بهینه کردن هر مسئله ای که نیاز به یافتن کوتاهترین مسیر دارد، اشاره نمود:
۱. مسیر یابی داخل شهری و بین شهری.
۲. مسیر یابی بین پست های شبکه های توزیع برق ولتاژ بالا.
۳. مسیر یابی شبکه های کامپیوتری. 4-استفاده ازوب. 5-استفاده ازACOدربهینه سازی شبکه های توزیع آب و...
فهرست مطالب:
مقدمه
الهام از طبیعت
رفتار کاوشگرایانه مورچه ها و بهینه سازی
تاریخچه
آزمایشات پل دو راهه
پل های مساوی
نتایج آزمایشات پل های مساوی
پل های نامساوی
نتایج آزمایشات پل های نامساوی
یک مدل احتمالی
به سمت مورچه های مصنوعی
ابزارهای مورچه های مصنوعی
ردپای فرومونی مصنوعی
اطلاعات ابتکاری
مورچه های مصنوعی و حرکت روی گراف
الگوریتم ACO
تنظیمات پارامتر برای الگوریتم ACO فاقد جستجوی محلی
جستجوی محلی چیست؟
به روز رسانی فرومون بر اساس کیفیت جواب ها
رفتار جستجوی مسیر مورچه ها
رفتار مورچه ها با در نظر گرفتن هر دو ابزار
مسیریابی مجدد و به روز رسانی فرومون
و...