الگوریتم بهینه سازی کلونی مورچگان (Ant Colony Optimization - ACO)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
الگوریتم بهینه سازی کلونی مورچگان (Ant Colony Optimization - ACO) :
📌 معرفی
الگوریتم بهینه سازی کلونی مورچگان (Ant Colony Optimization - ACO) توسط مارکو دوریگو در سال ۱۹۹۲ معرفی شد. این الگوریتم از رفتار مورچگان در یافتن کوتاه ترین مسیر بین لانه و منبع غذا الهام گرفته است. مورچگان با به جا گذاشتن فرمونی (Pheromone) روی مسیرها با یکدیگر ارتباط برقرار می کنند.
🐜 ایده اصلی
در ACO، تعدادی عامل مصنوعی (مورچه) به طور همزمان در گراف مسئله حرکت می کنند. هر مورچه با استفاده از یک قانون احتمالی که بر اساس مقدار فرمون و اطلاعات هیوریستیک (مثلا فاصله) است، گره بعدی را انتخاب می کند. پس از ساخت مسیر، مورچه ها بر اساس کیفیت مسیر، فرمون روی یال ها را به روزرسانی می کنند. با گذشت زمان، مسیرهای بهتر فرمون بیشتری جذب می کنند.
📐 فرمول بندی (قانون انتقال)
احتمال انتخاب یال (i,j) توسط مورچه k در گره i:
\[ p_{ij}^k = \frac{[\tau_{ij}]^\alpha [\eta_{ij}]^\beta}{\sum_{l \in N_i^k} [\tau_{il}]^\alpha [\eta_{il}]^\beta} \]که
\[ \tau_{ij} \]مقدار فرمون،
\[ \eta_{ij} \]اطلاعات هیوریستیک (معمولا
\[ 1/d_{ij} \])، و
\[ \alpha \],
\[ \beta \]پارامترهای کنترلی هستند.
🔄 به روزرسانی فرمون
پس از هر تکرار، فرمون ها تبخیر شده و مورچه ها بر اساس کیفیت مسیر خود فرمون اضافه می کنند:
\[ \tau_{ij} = (1-\rho) \tau_{ij} + \sum_{k} \Delta \tau_{ij}^k \]که
\[ \rho \]نرخ تبخیر فرمون است.
