این پاورپوینت با موضوع کلیاتی از کلونی مورچه ها حشرات اجتماعی با 68 اسلاید با عناوین زیر
مقدمه
مدل حوزه الگوریتم مورچها
الگوریتمACO
تاریخچه الگوریتم مورچها
آزمایشات پل دو راهه
مدل احتمالی دنوبورگ
مورچهای مصنوعی
جستجوی محلی چیست؟
تفاوت الگوریتم ها
مسیریابی شبکه های کامپیوتری با روش الگوی ACO
منابع
مقدمه
کلونی مورچه ها،سیستم های گسترده ای هستند که علی رغم سادگی ، ساختار اجتماعی کاملاٌ سازمان یافته ای را عرضه می کنند .
از طریق این سازماندهی کلونی مورچگان می تواند وظایف پیچیده ای را انجام دهد که در برخی موارد فراتر از توانایی های یک مورچه است
مدل حوزه الگوریتم مورچها
حوزه الگوریتم های مورچه مدل هایی را مطالعه می کند که از مطالعات رفتارهای واقعی مورچه ها ناشی می شود و از این مدل ها به عنوان منبع انگیزشی برای طراحی الگوریتم های جدید به منظور حل مسائل بهینه سازی و مسائل کنترل توزیع شده استفاده می کند
آذوقه جویی، تقسیم کار و مشارکت در حمل و نقل ، مثال هایی از این موارد هستند
الگوریتمACO
یکی از موفق ترین مثال های الگوریتم های مورچه به بهینه سازی از طریق کلونی مورچه یا ACO شهرت دارد
ACO که برای حل مسائل بهینه سازی گسسته کاربرد دارد، از رفتار جمع آوری آذوقه مورچه ها الهام گرفته شده است
رفتار کاوشگرانه مورچها
•قوه بینایی بسیاری از گونه های مورچه بسیار ابتدایی و محدود است و حتی برخی از انواع آن ها کاملاً نابینا هستند اما کوتاه ترین مسیر رفت و برگشت از خانه تا غذا را پیدا می کنند
•نتیجه تحقیقات اخیر در مورد رفتار مورچه ها این بود که بیشترین ارتباط بین مورچه ها و یا میان هریک از آن ها و محیط اطرافشان ، با استفاده از مواد شیمیایی تولید شده توسط مورچه ها به نام فرمون صورت می گیرد.
مدل احتمالی دنوبورگ
دنوبورگ و همکارانش ، یک مدل ساده احتمالی برای نحوه عملکرد کلونی مورچه ها مطابق آنچه در آزمایش پل دو راهه مشاهده شد را ارائه کردند که با استفاده از شبیه سازی مورد ارزیابی قرار گرفت
احتمال این که مورچه ای در لحظه t به نقطه تصمیم iϵ{1,2}
برسد و شاخه aϵ{s,l}را انتخاب کند به طوری که s وl به ترتیب بیانگر شاخه های کوتاه و بلند باشند، تابعی از مقدار کل فرمون یعنی روی هر شاخه است که این مقدار با تعداد مورچه هایی که تا زمان t از آن شاخه عبور کرده اند، متناسب است
مقادیر بزرگ پارامتر α باعث تأکید زیاد روی مسیرهای تصادفی اولیه و نوسانات تصادفی می شود و به بروز رفتارهای بد از سوی الگوریتم می انجامد . اما معادله بالا با در نظر گرفتن مقدار 2 از طریق آزمایش بدست آمده است
مورچهای مصنوعی
•در ACO مورچه های مصنوعی فرایندها (زیر برنامه های) کامپیوتری هستند که بصورت احتمالی راه حل های مختلف مسئله را می سازند.
•آزمایشات پل دوراهه نشان می دهند که کلونی مورچه ها توانایی بالقوه ای برای بهینه سازی دارند
•به طرز جالب توجهی با الهام گرفتن از آزمایشات پل دو راهه ، امکان طراحی مورچه های مصنوعی که با حرکت روی یک گراف مشابه پل دوراهه، کوتاه ترین مسیر بین دو گره متناظر با لانه و منبع آذوقه را می یابند وجود دارد.
روش و ابزارهای مورچهای مصنوعی
•ردپای فرومونی مصنوعی
این مقادیر در طی مراحل یافتن راه حل، بصورت پویا تغییر می کنند تا منعکس کننده نتایج بدست آمده توسط مورچه های مصنوعی باشند
•اطلاعات ابتکاری
این اطلاعات مرتبط با ساختار مسئله مورد نظر، برای حل مسئله بکار می روند.
الگوریتم های متفاوت به روشهای گوناگون از این ابزارها استفاده می کنند...
جستجوی محلی چیست؟
•جستجوی محلی رویکردی کلی برای یافتن جواب هاب یا کیفیت بالا برای مسائل بهینه سازی ترکیبی دشوار در یک زمان منطقی است
•این روش بر پایه کاوش و جستجوی مکرر همسایه های جواب ها است و سعی دارد که از طریق تغییرات محلی ، جواب فعلی را بهبود بخشد
•وقتی الگوریتم های ACO برای حل TSP به کار می روند بهترین عملکرد زمانی است که الگوریتمACO از یک بهینه ساز محلی برای بهبود دادن جواب های ساخته شده مورچه استفاده کند
نکته
این مشکل بوجود خواهد آمد که مورچه ها در حین ایجاد جواب ، ممکن است حلقه ایجاد کنند
به دلیل مکانیزم به روز آوری رد فرمون هنگام رفت ، حلقه ها بیشتر و بیشتر برای مورچه ها جذاب می شوند و مورچه ها در دام آن ها گیر می افتند و مکانیزم ساده تری که در شرایط پل دوراهه مورچه ها را مجبور می ساخت ، کوتاه ترین مسیررا با احتمال بالایی انتخاب کنند دیگر کار نمی کند
و...
