کوتاهترین مسیر در گراف با کمک الگوریتم کلونی مورچگان

ما در مطلب قبلی مسئله ایجاد حلقه در پیدا کردن کوتاهترین مسیر در گراف با کمک الگوریتم کونی مورچه ها بررسی کردیم و راه حلی که پیشنهاد دادیم اضافه کردن یک قابلیت به مورچه ها بود. این قابلیت داشتن حافظه محدود در مورچه ها است. (ما این مورچه ها را مورچه های مصنوعی نام گذاری کردیم،  این مورچه ها مهمترین ویژگی های مورچه های واقعی رو دارن بعلاوه یک سری قابلیت اضافه که باعث بهبود الگوریتم كلوني مورچه ها میشه)
پیش از ادامه مطلب در صورتن نیاز مطلب که در مورد مسئله حلقه در گراف را قبلا مطرح کردیم یک بار مرورو کنید تا ابهامی به وجود نیاید.

خوب بریم سراغ سوال اصلی: چطوری اضافه کردن حافظه محدود، مسئله حلقه در کوتاهترین مسیر در گراف رو حل میکنه؟

مورچه های مصنوعی از این حافظه برای نگهداری دو نوع اطلاعات استفاده میکنند

• نگهداری مسیری که تا حالا آمده اند: از آنجایی که این حافظه محدود است ممکن است مورچه ها نتواند همه مسیر را در حافظه خود نگهداری در نتیجه مورچه های مصنوعی در هر لحظه بخشی از مسیری (نه لزوما همه مسیر) که تا کنون آمده اند را در حافظه خود ذخیره دارند.
• نگهداری هزینه مسیر که تا حالا آمده اند: یک اطلاع دیگری که مورچه ها در حافظه نگهداری می کنند، هزینه ای مسیرهای است که تا کنون از آنها عبور کرده اند. مانند مسیر، این اطلاعات نیز ممکن است شامل هزینه تمام مسیر طی شده نباشد و ممکن است تنها هزینه های بخشی از مسیر را نگهداری کند.

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

1. حذف کردن مسیرهای که در آنها حلقه وجود دارد.
2. ارزیابی کیفیت مسیرهای که که توسط مورچه ها برای رسیدن به غذا (مقصد) ایجاد شده است – دقت داشته باشید این ارزیابی کاملا تخمینی است، و ممکن است دقیق نباشد. نکته مهم این است که این تخمین کمک می کند تا راه حل بهتری پیدا شود.

اضافه کردن قابلیت حافظه محدود به مورچه ها و تبخیر فرمون (که قبلا معرفی کردیم) به الگوریتم ACO ، نسخه جدیدی از الگوریتم ACO می شود که با عنوان Simple ACO یا به اختصار S-ACO شناخته می شود. در مطلب بعدی این الگوریتم را با جزییات بیشتری توضیح می دهیم.