الگوریتم کلونی مورچگان یا الگوریتم بهینه سازی کلونی مورچه Ant Colony Optimization الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه‌ها حشراتی اجتماعی هستند که در کلونی‌ها زندگی می‌کنند و رفتار آن‌ها بیشتر در جهت بقاء کلونی است تا در جهت بقاء یک جزء از آن. یکی از مهم‌ترین و جالب‌ترین رفتار مورچه‌ها، رفتار آن‌ها برای یافتن غذا است و به ویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه است.
از همین رفتار مورچه ها در یافتن غذا و چگونگی پیدا کردن کوتاهترین مسیر بین منابع غذایی و کلونی، برای حل مسائل و بهینه سازی استفاده می‌شود و ایده اصلی در الگوریتم ACO پدیدار شده است. در این مقاله از سری مقالات آموزشی مجله پی استور به تشریح کامل این الگوریتم در حل مسائل خواهیم پرداخت و نحوه فرموله کردن الگوریتم مورچه را به صورت ریاضی توضیح خواهیم داد.
معرفی الگوریتم کلونی مورچگان ACO
الگوریتم بهینه سازی کلونی مورچگان تحت عنوان الگوریتم‌های هوش ازدحامی «Swarm Intelligence» شناخته شده و به مدل سازی رفتار مورچه‌های واقعی می‌پردازد. مورچه‌ها حشراتی هستند که می‌توانند گروه‌ها (کلونی‌ها) را شکل دهند. چنین رویکرد جمعیت محوری این امکان را برای الگوریتم ACO ایجاد می‌کند تا به حل مسائل بهینه سازی پویا به طور کاملا کارآمد بپردازد. مورچه‌ها به عنوان مخلوقات خودسازمانده می‌باشند. چنین ویژگی به عنوان هسته مسئله است چون این ویژگی دقیقاً همان چیزی است که باعث می‌شود حشرات به سرعت با شرایط متغیر محیطی شان به منظور دستیابی به اهداف از طریق تعامل، وفق بیابند.
از آن‌جایی که مورچه‌ها اصلاً چشم ندارند، تعاملات آن‌ها از طریق ماده شیمیایی فرومون Pheromone که از آن برای نشان گذاری مسیر استفاده می‌شود، انجام می‌گیرد. هرچه فرومون‌های بیشتری در مسیر قرار گیرد؛ مابقی مورچه‌ها از این مسیر بیشتر استفاده می‌کنند؛ بنابراین، چنین کمیتی نشان می‌دهد که این مسیر به عنوان یکی از بهینه‌ترین و کوتاهترین راه می‌باشد. اکنون نگاهی به یک نمونه عینی در شکل زیر می‌اندازیم. هدف پیدا کردن بهترین راه از نقطه آغازی N (آشیانه) به نقطه مقصد F (منبع غذا) می‌باشد.
ممکن است این حدس زده شود که احتمال برای مورچه‌ای که مسیر درست را می‌پیماید برابر با همان احتمالی می‌باشد که مسیر اشتباه را انتخاب کند. نکته در اینجا اینست که مورچه‌ای که کوتاهترین مسیر را می‌پیماید، اولین مورچه‌ای است که به نقطه مقصد رسیده و سپس به آشیانه ( نقطه مبدا حرکت) بر می‌گردد، بنابراین در این کوتاهترین مسیر فرومون های بیشتری وجود دارد. از این رو فرومون دقیقاً همان چیزی است که نشان می‌دهد که مورچه باید از چه مسیری برود و در پایان کوتاهترین راه، بهترین مسیر می‌باشد. تبخیر شدن فرومون و احتمال تصادف به مورچه‌ها امکان پیدا کردن کوتاهترین مسیر را می‌دهد. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینهسازی می‌شوند.
ساختار الگوریتم کلونی مورچگان
الگوریتم کلونی مورچگان از سه بخش تشکیل شده است. در بخش نخست، مقادیر پارامترهای مسئله تنظیم و متغیرهای جمعیت اولیه مقداردهی می‌شوند. بخش دوم شامل یک حلقه تکرار است که سه مرحله الگوریتم کلونی مورچگان را اجرا می‌کند. در هر حلقه از الگوریتم کلونی مورچگان، جواب‌های کاندید توسط تمامی مورچه‌های ساخته می‌شوند. جواب‌های تولید شده، از طریق یک الگوریتم جستجوی محلی بهبود می‌یابند. در مرحله سوم، فرومون‌ها به روز رسانی می‌شوند. شبه کد الگوریتم کلونی مورچگان در ادامه آمده است.
شبه کد الگوریتم کلونی مورچگان
- تنظیم پارامترهای الگوریتم کلونی مورچگان و مقداردهی اولیه فرمون
- تا زمان شرط توقف:
- شروع مرحله اول یا مرحله تولید جواب‌های کاندید (Construct Ant Solution)
- شروع مرحله دوم یا مرحله جستجوی محلی جواب‌ها (Local Search): در این مرحله، از جواب‌های بهینه محلی استفاده می‌شود تا مشخص شود کدام یک از فرومون‌ها باید به روز رسانی شوند.
- انجام مرحله سوم یا مرحله به روز رسانی فرومون (Pheromone Update)
- در صورت اتمام یا ارضای شرط توقف، اتمام الگوریتم در غیر این صورت برگرد به ۲.
فلوچارت الگوریتم کلونی مورچگان
مراحل الگوریتم کلونی مورچگان
در الگوریتم کلونی مورچگان، مورچه‌های مصنوعی، یک جواب کاندید برای مسأله بهینهسازی ترکیبیاتی داده شده را از طریق پیمایش گراف تولید می‌کنند. مورچه‌ها، برای تولید جواب کاندید، در راستای یال‌های گراف، از یک رأس به رأس دیگر حرکت می‌کنند و از این طریق، به طور تدریجی یک «جواب کاندید جزئی» (Partial Candidate Solution) را تولید می‌کنند. مورچه‌های بعدی، از اطلاعات فرومون منتشر شده به عنوان راهنما برای پیدا کردن مناطق بهتر در فضای جستجو و حرکت به سمت آن‌ها استفاده می‌کنند.
از یک سو، این مناطق، به احتمال زیاد حاوی جواب بهینه سراسری هستند و از سوی دیگر، در صورت حرکت مورچه‌های مصنوعی به سمت این مناطق، با سرعت بیشتری می‌توانند به جواب بهینه سراسری همگرا شوند. در ادامه، سه مرحله اصلی الگوریتم کلونی مورچگان با جزئیات بیشتری توضیح داده می‌شود.
۱- مرحله اول: تولید جواب‌های کاندید
در این مورد، می‌توانیم از دو رویکرد متفاوت استفاده کنیم: قرار دادن تمام مورچه‌ها در یک نقطه یا در نقطه‌های مختلف. اینکه از چه روشی می‌بایست استفاده شود بستگی به موقعیت خاص آن دارد. در این مرحله، این مقدار دهی اولیه به فرمون‌ها نیز انجام می‌شود. ارزش فرمون باید یک عدد صحیح کوچک باشد. این کار را باید به این منظور انجام داد تا از ماندن و حرکت نکردن مورچه‌ها در نقطه آغازی جلوگیری کرد.
چون الگوریتم ACO تلاش می‌کند تا به تقلید رفتار مورچه‌های واقعی با استفاده از فرآیند شبیه سازی بپردازد، از یک تابع احتمال برای توصیف مسیر استفاده می‌گردد. احتمال دسترسی به نقطه j از نقطه i (احتمال انتقال) بر طبق به فرمول زیر محاسبه می‌شود:
که در این فرمول τ_ij مقدار ماده شیمیایی فرومن در نقاط (i,j) می‌باشد. که حس مورچه نیز نامیده می‌شود. η_ij نسبت دید نقاط (i, j) است که چشم مورچه نامیده می‌شود و هیورستیک مسئله می‌باشد و بصورت η_ij=1⁄d_ij تعریف می‌شود که d_ij فاصله بین دو گره i و j است. α و β نیز پارامترهای سازگار، به معرفی اهمیت مسیر در برابر نسبت دید در زمان انتخاب نقطه بعدی برای حرکت می‌پردازد. tabuK فهرست گره‌های بازدید شده در مسیر کنونی که اصطلاحاً حافظه مورچه نامیده می‌شوند.
اگر α=۰ باشد، الگوریتم حریصانه شده، به صورتی که انتخاب گره بعدی، کمیت فرومون‌ها را مد نظر قرار نداده به این ترتیب انتخاب نزدیک‌ترین مسیر اولویت پیدا می‌کند. اگر β=۰ باشد الگوریتم تنها مقدار فرمون‌ها را بدون در نظر گرفتن طول مسیر، مد نظر قرار می‌دهد.
۲- مرحله دوم: جستجوی محلی جواب‌ها
بسته به پیاده‌سازی انجام شده از الگوریتم کلونی مورچگان، پس از تولید جواب‌های کاندید و پیش از اینکه فرومون‌ها به روز رسانی شوند، ممکن است فرآیندهای اضافی برای تضمین عملکرد بهینه الگوریتم ضروری باشند. بنابراین، این مرحله، اختیاری است. طبیعت این فرآیندها، ازدحامی است. یعنی توسط فقط یک مورچه مصنوعی قابل انجام نیست. به این دسته از فرآیندها، «عملیات کمکی یا پس‌زمینه» (Daemon Actions) گفته می‌شود.
شایع‌ترین عملیات پس‌زمینه در الگوریتم‌های مبتنی بر الگوریتم کلونی مورچگان، به‌کارگیری جستجوی محلی در جواب‌های کاندید تولید شده است. به‌عنوان نمونه، از جواب بهینه شده محلی برای تصمیم‌گیری در مورد به روز رسانی مقادیر فرومون‌ها استفاده می‌شود.
۳- مرحله سوم: بروز رسانی فررمون‌ها
در الگوریتم مورچگان بعد از اینکه مورچه‌ها دنبال کردن مسیر را به پایان رساندند، کمیت و مقدار فرمون‌ها می‌بایست تغییر یابد. این فرآیند دو مرحله دارد. ابتدا، نیاز داریم تا مقدار تمام فرمون‌ها را کاهش داده. دوم، نیاز به بروزرسانی فرمون‌های متصل به نقاط بازدید شده از طریق افزایش مقدار و کمیت آن داریم. تبخیر مسیر به صورت فرمول زیر تعریف می‌گردد:
که در این فرمول ρ ضریب تبخیر فرمون می‌باشد. پارامتر ρ کمک می‌کند تا از انباشت نامحدود مسیر خلاص شویم. بنابراین این فرآیند مانع می‌شود تا مورچه‌ها مسیرهای بدی را که قبلا کشف کردند فراموش کنند. اگر نقطه‌ای که توسط مورچه‌ها بدون استفاده ماند، سپس سطح فرومن بعد از هر تکرار به طور تعریفی (نمایی) کاهش می‌یابد. به منظور مد نظر قرار دادن تبخیر، نیاز به بروزرسانی مقدار فرمون‌های مورچه‌ها داریم. بنابراین حجم (فزونی) مسیر توسط فرمول زیر بروزرسانی می‌گردد.
که در این فرمول τ_ij^k∆ کمیت فرومون‌های قرار داده شده بر روی نقاط پیموده شده (i, j) توسط مورچه k ام می‌باشد. و با استفاده از رابطه زیر قابل محاسبه است.
که در این فرمول Q مقدار ثابت، که به طور ساختگی فرمون‌ها را اضافه می‌کند و L طول کلی مسیر می‌باشد هر چه مسیر بهتر باشد، فرومون‌های بیشتری در این مسیر قرار می‌گیرد. در کل، نقاطی که توسط بسیاری از مورچه‌ها مورد استفاده قرار می‌گیرد و بخشی از مسیرهای کوتاه را شامل می‌گردد، فرومن‌های بیشتری را دریافت کرده و به این ترتیب به احتمال بیشتری توسط مورچه‌ها در تکرار آینده این مسیر الگوریتم انتخاب می‌گردد. فرآیند تکرار زمانی متوقف می‌شود که حداقل یکی از نیازها برآورده گردد.
انواع مختلف الگوریتم کلونی مورچگان
در ادامه تعدادی از انواع الگوریتم کلونی مورچگان را معرفی می‌کنیم:
۱- سیستم کلونی مورچه Ant System
توضیحات مربوط به الگوریتم کلونی مورچگان است که در بخش های قبل توضیحات کافی داده شده است.
۲- سیستم مورچه نخبگان Elitist Ant System
در این روش بهترین راه حل کلی در هر تکرار فرمون آزاد می‌کند. همچنین این روش برای تمام مورچه‌های مصنوعی باید انجام شود.
۳- سیستم مورچه ماکس – مین Min-Max Ant System
یک مقدار کمینه و بیشینه برای فرمون تعیین کرده و فقط در هر مرحله بهترین جواب این مقدار را آزاد می‌کند و تمام گره‌های مجاوران به مقدار فرمون بیشینه مقدار دهی اولیه می‌شوند.
۴- سیستم مورچه بر اساس رتبه Ranked Ant System
تمام راه حل‌های بدست آماده بر اساس طول جواب رتبه‌بندی می‌شوند و بر اساس همین رتبه‌بندی مقدار فرمون آزاد سازی شده توسط آن‌ها مشخص خواهد شد و راه حل با طول کم‌تر از راه حل دیگر با طول بیشتر مقدار فرمون بیشتری آزاد می‌کند.
۵- سیستم مورچه متعامد مداوم Best-Worst Ant System
در این روش مکانیزم تولید فرمون به مورچه اجازه می‌دهد تا برای رسیدن به جواب بهتر و مشترک با بقیه مورچه‌ها جستجو انجام دهد با استفاده از روش طراحی متعامد مورچه می‌تواند در دامنه تعریف شده خود به صورت مداوم برای بدست آوردن بهترین جواب جستجو کند که این عمل به هدف رسیدن به جواب بهینه و صحیح ما را نزدیک می‌کند. روش طراحی متعامد می‌تواند به دیگر روش‌های جستجو دیگر گسترش پیدا کنند تا به مزیت‌های این روش‌های جستجو اضافه کند.
مزایای و معایب الگوریتم کلونی مورچگان
مزایا:
- همکاری گروهی میان مورچه‌ها برای تولید جواب‌های بهینه، طبیعت مبتنی‌بر «توازی» (Parallelism) و «همبستگی» (Solidarity) این روش فرا اکتشافی را نشان می‌دهد.
- بازخورد مثبت ایجاد شده از طریق انتشار فرومون در محیط، سبب همگرایی سریع به جواب‌های خوب برای مسأله بهینهسازی می‌شود.
- برای استفاده در کاربردهای پویا (کاربردهایی که نیاز به انطباق سریع با تغییرات محیطی ضروری است) مناسب است.
- همگرایی به جواب بهینه، تضمین شده است.
معایب:
- تجزیه و تحلیل نظری این روش بسیار سخت است.
- این روش، بر پایه دنباله‌ای از تصمیمات تصادفی ولی وابسته به هم بنا نهاده شده است.
- زمان لازم برای همگرایی به جواب بهینه نامشخص است.
کاربردهای الگوریتم کلونی مورچگان (ACO)
۱- بهینهسازی مسیر و مسیریابی
- مسأله فروشنده دوره‌گرد (TSP): یکی از معروف‌ترین کاربردها برای یافتن کوتاهترین مسیر بازدید از چندین نقطه.
- مسیریابی در شبکه‌های کامپیوتری: برای یافتن بهترین مسیر عبور بسته‌های اطلاعاتی در شبکه‌ها.
- مسیریابی ربات‌ها و پهپادها: برای طراحی مسیرهای بهینه و کم‌مصرف.
۲- برنامه‌ریزی و زمان‌بندی (Scheduling)
- زمان‌بندی پروژه‌ها (مانند مدل CPM و PERT)
- زمان‌بندی ماشین‌ها در تولید (Job Shop Scheduling)
- زمان‌بندی درس‌ها و امتحانات در مدارس و دانشگاه‌ها
۳- بهینهسازی ترکیبیاتی (Combinatorial Optimization)
- رنگ‌آمیزی گراف‌ها
- تقسیم‌بندی خوشه‌ها (Clustering)
- مسأله کوله‌پشتی (Knapsack Problem)
۴- بهینهسازی در شبکه‌های حمل‌ونقل
- طراحی شبکه‌های حمل‌ونقل عمومی یا لجستیک
- تعیین مسیرهای حمل بار یا بسته‌ها بهینه در شرکت‌های پستی
۵- بهینهسازی در یادگیری ماشین
- تنظیم پارامترها (Hyperparameter Tuning) در مدل‌های یادگیری ماشین
- انتخاب ویژگی (Feature Selection) برای انتخاب بهترین ویژگی‌های مؤثر در مدل
۶- کاربرد در سیستم‌های هوشمند
- سیستم‌های پیشنهادگر (Recommender Systems)
- کنترل ترافیک شهری
- بهینهسازی مصرف انرژی در خانه‌های هوشمند
۷- بهینهسازی در مهندسی برق و قدرت
- جایابی بهینه تولیدات پراکنده (DG) در شبکه‌های قدرت
- طراحی بهینه شبکه‌های توزیع برق
۸- کاربردهای پزشکی و زیستی
- دسته‌بندی داده‌های پزشکی (مثلاً تصاویر MRI)
- ردیابی مسیر در تصاویر پزشکی
- مدل‌سازی ژنوم و توالی DNA
سخن آخر
الگوریتم مورچگان، یکی از روش‌های متاهیوریستیک است که بر پایه رفتار گروهی مورچه‌ها برای یافتن منابع غذایی الهام گرفته شده است. مؤلفه اساسی الگوریتم کلونی مورچگان، مدل فرومون است. روش بهینهسازی کلونی مورچگان، یک مدل برای پیاده‌سازی الگوریتم‌های بهینهسازی ارائه می‌دهد.
تاکنون، الگوریتم‌های بهینهسازی متفاوتی بر پایه این روش بهینهسازی ارائه شده‌اند. از مهم‌ترین پیاده‌سازی‌های انجام شده می‌توان به الگوریتم‌هایی نظیر «سیستم مورچگان» (َAnt System)، «سیستم کلونی مورچگان» (Ant Colony System) و «سیستم مورچگان Min-Max» اشاره کرد. ویژگی مهم این روش، اثرگذاری و انعطاف‌پذیری فوق‌العاده آن در حل مسائل بهینهسازی است.
