الگوریتم مورچه

الگوریتم مورچه

اسلاید 1: کلونی مورچه ها و به طور کلی جوامع حشرات اجتماعی ،سیستم های گسترده ای هستند که علی رغم سادگی ، ساختار اجتماعی کاملاٌ سازمان یافته ای را عرضه می کنند . از طریق این سازماندهی کلونی مورچگان می تواند وظایف پیچیده ای را انجام دهد که در برخی موارد فراتر از توانایی های یک مورچه استمقدمه

اسلاید 2: حوزه الگوریتم های مورچه مدل هایی را مطالعه می کند که از مطالعات رفتارهای واقعی مورچه ها ناشی می شود و از این مدل ها به عنوان منبع انگیزشی برای طراحی الگوریتم های جدید به منظور حل مسائل بهینه سازی و مسائل کنترل توزیع شده (Distributed control) استفاده می کندآذوقه جویی، تقسیم کار و مشارکت در حمل و نقل ، مثال هایی از این موارد هستندالهام از طبیعت

اسلاید 3: یکی از موفق ترین مثال های الگوریتم های مورچه به بهینه سازی از طریق کلونی مورچه یا ACO شهرت داردACO که برای حل مسائل بهینه سازی گسسته کاربرد دارد، از رفتار جمع آوری آذوقه مورچه ها الهام گرفته شده است

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

اسلاید 5: الگوریتم مورچگان اولین بار در سال 1991 توسط مارکو دوریگو (Dorigo) برای حل مسائل بهینه سازی مشکلی مانند مسأله فروشنده دوره گرد Traveling) (Sales Person ارائه شدرفتار باقی گذاردن و تعقیب رد پا (Trail Pheromone) که مورچه از مواد شیمیایی به جا مانده از سایر مورچه ها تأثیر می گیرد، منشأ پیدایش ACO شدتاریخچه

اسلاید 6: یکی از آزمایشات درخشانی که توسط دنوبورگ و همکارانش طراحی و اجرا شد ، اتصال لانه گونه ای از مورچه های آرژانتینی به نام آی .هیومیلی توسط یک پل دوراهه به منبع آذوقه بودان ها آزمایشات خود را با طول پل های مساوی و نامساوی انجام دادندآزمایشات پل دو راهه

اسلاید 7: پل های مساوی

اسلاید 8: نتیجه این بود که تمام مورچه ها به سمت یک شاخه همگرا می شونداین مسئله بدین علت رخ می دهد که در ابتدای آزمایش در هیچ یک از پل ها فرومونی وجود ندارد بنابراین مورچه ها با احتمال تقریباً برابر هر دو پل را انتخاب می کننداما به دلیل نوسانات تصادفی ، تعداد بیشتری مورچه ها یکی از شاخه ها را بیشتر از دیگری برمی گزینندنتایج آزمایش پل های مساوی(آزمایش اول)

اسلاید 9:

اسلاید 10: پل های نامساوی

اسلاید 11: در بیشتر آزمایشات مورچه ها پس از گذشت مدتی شاخه کوتاه تر را انتخاب کردندبا توجه به مقدار فرمون بیشتری که در شاخه کوتاه تر وجود دارد شاخه کوتاه تر را برمی گزینندبنابراین فرمون به دلیل فرایند اتوکاتالیزور( بازخورد مثبت) روی شاخه کوتاه تر که توسط همه مورچه ها انتخاب می شود سریع تر انباشته می گرددنتایج ازمایش پل های نامساوی(آزمایش دوم)

اسلاید 12: الف. آزمايش پل با مسيرهاي با طول متفاوت ب. عبور مورچه‌هاي بيشتر از مسيرهاي كوتاه‌تربالف

اسلاید 13: نکتهبه طور جالب توجهی مشاهده می شود که حتی زمانی که طول شاخه بلند تر دو برابر شاخه کوتاه تر است ، تمام مورچه ها از مسیر کوتاه تر استفاده نمی کنند. بلکه درصد کمی ( مثلاً 10%) از مورچه ها ممکن است از شاخه بلند تر بگذرند. این عمل مورچه ها کشف مسیر نامیده می شود

اسلاید 14: نکته جالب است بدانیم که وقتی مسیر جدید و کوتاه تری بین لانه و آذوقه پس از مدتی در اختیار کلونی مورچه قرر داده شود با گذشت زمان باز هم مورچه ها شاخه کوتاه تر را انتخاب می کنند چون تبخیر کند فرمون به کلونی مورچه ها اجازه می دهد تا مسیر نیمه بهینه ای که به سمت ان همگرا شده اند را فراموش و مسیر جدید و کوتاه تر را کشف کنند

اسلاید 15:

اسلاید 16: دنوبورگ و همکارانش ، یک مدل ساده احتمالی برای نحوه عملکرد کلونی مورچه ها مطابق آنچه در آزمایش پل دو راهه مشاهده شد را ارائه کردند که با استفاده از شبیه سازی مورد ارزیابی قرار گرفت یک مدل احتمالی