استفاده ازالگوریتم مورچگان برای بهینه سازی Ant Colony Optimization
الگوریتم مورچگان:
استفاده از الگوریتم های ابتکاری در حل مسئله بهینه سازی امری ضروری و اجتناب ناپذیر است. این روش از توانایی مورچه ها در پیدا کردن کوتاه ترین مسیر بین لانه و یک منبع غذایی الهام گرفته است. وقتی مورچه ها در محیط اطراف حرکت می نمایند، اثری شیمیایی به نام فرومون از خود بجای می گذارند. وقتی جمعیتی از مورچه ها از چند مسیر بین لانه و یک منبع غذایی حرکت می کنند، پس از مدت زمان معینی مشاهده می شود که در مسیرهای متفاوت، فرومونهای برجای گذاشته شده متفاوت می باشد. این امر ناشی از این واقعیت است که مورچه هایی که در مسیر کوتاه حرکت می کنند، به علت کوتاه تر بودن مسیر در یک مدت زمان معین تردد بیشتری داشته اند چون مورچه ها، مسیر کوتاه تر را انتخاب کرده اند. با استفاده از روش مورچه ها، روش جستجوئی پیاده سازی می شود که در هر مرحله ای از اطلاعات مراحل قبلی برای رسیدن به هدف استفاده میگردد.
تاریخچه الگوریتم مورچگان:
به کارگیری سیستم مورچگان اولین بار (الگوریتم مورچگان) توسط Dorgio و همکاران و خود او به عنوان یک نگرش با چندین عامل برای حل مسائل بهینه سازی ترکیبی یا راه حل چندعامله (multi Agent) مشکل، مانند مسئله فروشنده دوره گرد یا (TSP) (Traveling Sales Person) و مسئله تخصیص منابع یا QAP پیشنهاد و ارائه شد.
خصوصیات مورچه ها:
1- اجتماعی بودن: مطالعات نشان داده است که مورچه ها حشراتی اجتماعی هستند که در کلونی ها زندگی می کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا در جهت بقاء یک جزء از آن.
2. هوشمندی توده ای: مورچه ها با وجود کور و کم هوش بودن کوتاهترین مسیر رفت و برگشت از خانه تا غذا را پیدا می کنند. این یکی از مهمترین و جالبترین رفتار مورچه ها می باشد که این نوع رفتار مورچه ها دارای نوعی هوشمندی توده ای است که عناصر رفتاری تصادفی(احتمال) دارند و بین آنها (همدیگر) هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیرمستقیم و با استفاده از نشانه ها با یکدیگر در تماس هستند.
مورچه ها چگونه کوتاهترین مسیر را انتخاب می کنند؟
مورچه ها هنگام راه رفتن از خود ردی از ماده شیمیایی فرومون (pheromone) بجای می گذارند که البته این ماده بزودی تبخیر می شود ولی در کوتاه مدت بعنوان رد مورچه بر سطح زمین باقی می ماند.
یک رفتار پایه ای ساده در مورچه ها وجود دارد:
آنها هنگام انتخاب بین دو مسیر بصورت احتمالاتی (statistical) مسیری را انتخاب می کنند که فرومون بیشتری داشته باشد یا بعبارت دیگر مورچه های بیشتری قبلاً از آن جا عبور کرده باشند.
ویژگیهای الگوریتم مورچگان:
این الگوریتم مورچگان:
1. چندمنظوره میباشد، به عبارت دیگر می تواند برای انواع مشابه یک مساله به کار رود.
2. قوی میباشد، یعین با کمترین تغییرات برای دیگر مسائل بهینه سازی ترکیبی به کار برده می شود.
3. یک روش مبتنی بر جمعیت می باشد.
مزیتهای ACO:
ایجاد انعطاف در حل هرگونه مسئله بهینه سازی
پسخورد مثبت (پسخورد مثبت، منجر به کشف سریع جوابهاب خوب می شود)
محاسبات توزیع شده (محاسبات توزیع شده از همگرایی زودرس و بی موقع جلوگیری می کند)
– هیوریستیک آزمند سازنده (به کشف جوابهای قابل قبول در مراحل اولیه جستجو کمک می کند).
کاربردهای الگوریتم مورچگان:
از کاربردهای الگوریتم (ACO) می توان به بهینه کردن هر مسئله ای که نیاز به یافتن کوتاهترین مسیر دارد استفاده می شود:
1- مسیریابی داخل شهری و بین شهری
2- مسیریابی بین پست های شبکه های توزیع برق ولتاژ بالا
3- مسیریابی شبکه های کامپیوتری
4-مسیر یابی تامین مواد اولیه جهت تولید به هنگام
الگوریتم مورچگان و بهره گیری از مساله فروشنده دوره گرد جهت مساله سازی
در مسئله فروشنده دوره گرد، یک فروشنده سفر خود را از یک شهر آغاز کرده و پس از یک سفر کامل دوباره به شهر خودش بازمی گردد و از هر شهر فقط یکبار عبور می کند ودرضمن باید از همه شهرها عبور نموده و کمترین مسافت را طی نماید.
قانون 1: تصمیم گیری
قانون2: بروز رسانی
قانون3-تبخیر
نرم افزارهای کاربردی در این الگوریتم:
مدلهای ریاضی که در این الگوریتم استفاده می شود جوابهای آن بااستفاده از نرم افزار LINGO بدست می آید.
– در برنامه های کامپیوتری الگوریتم از زبان برنامه نویسی C (Borland C ++5.02) نیز استفاده می شود.
جمع بندی و نتیجه گیری:
– روشهای بهینه یابی موجود برای حل مسائل سخت که بطور عمده شامل تعداد بسیار زیادی متغیر و محدودیت می باشند که از کارآیی عملی آنها در حل مسائل با ابعاد واقعی می کاهد. بدین علت از الگوریتمهای ابتکاری و فوق ابتکاری هیوریستیک بر مبنای بهینه یابی کلنی مورچگان استفاده نمود.
استفاده از الگوریتم لانه مورچه و اقتباس از آن در صنعت برای یافتن کوتاهترین مسیر جهت تامین بهنگام مواد و قطعات باعث کاهش هزینه های تولید و انبارداری و بهبود بهره وری می شود.
می توان از روی این الگوریتم برای مسائل چندین عامله نمونه سازی کرد ولااقل به جوابی در حد بهینه و در کمترین زمان یافت.
منابع:
1. ح. توحیدی و ح. نظام آبادی پور وس. سریزدی «انتخاب ویژگی با استفاده از الگوریتم جمعیت مورچگان باینری» هشتمین کنفرانس سیستمهای هوشمند، 1386.
2. م. صفاری و 1. جمال نیا «الگوریتم های لانه مورچه و کاربرد آن در نگهداری پیشگیرانه» اولین همایش ملی مدیریت صنعتی.
3. م.م. سپهری و ع. جعفری «حل مساله تامین بهنگام قطعات موردنیاز سیستم های تولیدی با استفاده از مدل ریاضی و الگوریتم مورچگان» نشریه دانشکده فنی، اردیبهشت ماه 1383.
پایان