آموزش الگوریتم کلونی مورچه گان S-ACO – قسمت اول
در
مطلب قبلی الگوریتم S-ACO رو به عنوان یکی از پایه ای ترین الگوریتم های ACO معرفی کردیم. الگوریتم S-ACO به عنوان یکی از الگوریتم های آموزشی برای کسانی که می خواهند با الگوریتم کلونی مورچه گان آشنا شوند، ارائه می شوند. به همین منظور در این مطلب و چند مطلب آینده اجزاء این الگوریتم را به جزییات دقیق و کامل بررسی میکنیم.
الگوریتم S-ACO دارای 4 گام است که عبارتند از:
- حرکت مورچه از سمت لانه به سمت غذا برای پیدا کردن مسیر
- حرکت مورچه از سمت غذا به سمت لانه و به روز رسانی فرمون مسیر
- به روز رسانی فرمون ها بر اساس میزان کیفیت مسیر
- تبخیر فرمون
در این مطلب، بخش اول الگوریتم که “حرکت مورچه از سمت لانه به سمت غذا برای پیدا کردن مسیر” را بررسی می کنیم.
در الگوریتم S-ACO مورچه ها دو نوع رفتار حرکتی دارند 1- حرکت رو به جلو و 2-حرکت رو به عقب. در
حرکت رو به جلو مورچه ها سعی می کنند از لانه خود تا غذا یک مسیر را پیدا کنند، در
حرکت رو به عقب مورچه های سعی می کنند از غذا تا لانه خود را برگردند. هر کدوم از این رفتارهای حرکتی را
“مد حرکتی” نامگذاری میکنیم. یعنی وقتی مورچه در حال حرکت از لانه به سمت غذا است می گوییم مورچه در
مد حرکتی رو به جلو است و وقتی مورچه در حال بازگشت از محل غذا به لانه است می گوییم مورچه در
مد حرکتی برگشت هستند.
به عبارت دیگر وقتی یک مورچه از لانه شروع به حرکت می کند در مد حرکتی رو به جلو، است تا زمانی که به غذا برسد و بخواهد برگردد در این لحظه، مد حرکتی مورچه عوض می شود و به مد حرکتی برگشت تغییر میکند و سعی می کند تا مسیر رفته را برگردد.
الگوریتم کلونی مورچه گان : مسیر لانه تا غذا
گراف بالا را در نظر گیرید: وقتی مورچه در مد حرکتی رو به جلو است، به صورت احتمالی یکی از گره های گراف که از مکان فعالی (گره فعلی) قابل دسترس است را انتخاب میکند. گره قابل دسترسی، گرهی است که مسیر مستقیم به آن وجود داشته باشد (به عبارت دیگر در گراف یک یال بین آنها موجود باشد).
همانطورکه بیان شد انتخاب یکی از گره های قابل دسترسی، به صورت احتمالی می باشد که بر اساس میزان فرمون موجود در مسیرها می باشد که توسط مورچه ها بر روی آنها پاشیده شده است (اطلاعات کامل در مورد این بحت را می توانید در
این مطلب مطالعه کنید).
تا اینجا تمام اطلاعاتی که در مورد گام اول الگوریتم S-ACo به عنوان پایه ای ترین الگوریتم کلونی مورچه گان رو بیان کردیم در مطالب بعدی سایر گام ها را بررسی میکنیم.
یک نکته که بد نیست بدونید اینه که : در الگوریتم S-ACO وقتی مورچه ها در مد حرکتی رو به جلو هستند بر روی مسیر فرمون
نمی پاشند. عدم پاشیدن فرمون در مسیر لانه تا غذا (وقتی مورچه ها در مد حرکتی روبه جلو هستند) و مکانیزم تبخیر فرمون (که در مطالب بعدی توضیح میدهیم) کمک میکند تا از ایجاد حلقه در گراف جلوگیری شود. برای کسب اطلاعات کامل در مورد
مسئله حلقه این مطلب رو مطالعه کنید.
منبع (اطلاعات بیشتر)
http://mrmining.ir/2017/01/04/الگوریتم-کلونی-مورچه-گان-s-aco-قسمت-اول/