الگوریتم بهینه‌سازی کلونی مورچگان (Ant Colony Optimization)

مدرس: مسعود کاویانی

MasoudKaviani.ir

مورچه‌ها در یک حرکتِ جمعی قادر هستند مسیرِ بهینه از کلونیِ خود به سمت غذا را به دست آورند. آن‌ها بدون داشتن بینایی می‌توانند با استفاده از قدرتِ اجتماعِ خود این مسیر را پیدا کنند. دانشمندان با تحقیق و بررسیِ نحوه‌ی کار مورچه‌ها، توانستند الگوریتمی را شناسایی کنند که می‌تواند با تقریب بسیاری خوبی، چیزی نزدیک به بهینه‌ی سراسری را در یک مسئله‌ی بهینه‌سازی بیابد.

اجازه بدهید ابتدا به این مسئله بپردازیم که مورچه‌های واقعی چگونه فاصله‌ی بهینه را بین کلونیِ خود و غذا کم می‌کنند. مورچه‌ها توسط ماده‌ای به نام فرومون (Pheromone) که در مسیر حرکت خود بر روی زمین به‌جای می‌گذارند با یکدیگر صحبت می‌کنند. یعنی اگر مورچه‌ای یک مسیری را بپیماید، با توچه به فرومونی که از خود بر روی زمین قرار داده است، می‌تواند مسیر بازگشت خود را شناسایی کند. همچنین مورچه‌های دیگر نیز می‌توانند، با حس کردن فرومون‌های دیگران بفهمند که یک مورچه‌ی دیگر از این مسیر حرکت کرده است. در واقع تبادل پیام با به‌جای گذاشتن فرومون بر روی زمین انجام می‌شود. ولی این فرومون‌ها همیشه بر روی زمین به جای نمی‌مانند و بعد از مدتی آرام آرام تبخیر می‌شوند. در واقع دو عمل اصلی، یعنی فرومون‌ریزی و تبخیرِ فرومون، اعمالی هستند که ایده‌ی اصلی در انجام الگوریتمِ بهینه‌سازی کلونی مورچگان را تشکیل می‌دهند.

برای شروع به شکل زیر نگاه کنید:

در این شکل مشاهده می‌کنید که از کلونیِ مورچه‌ها تا غذا دو مسیر وجود دارد (یعنی دو راه حل وجود دارد). مورچه‌ها ابتدا به صورت تصادفی یکی از راه‌حل‌های بالایی یا پایینی را انتخاب می‌کنند، به غذا رسیده و بر اساس فرومون‌هایی که به‌جای گذاشته‌اند، بعد از برداشتنِ غذا، به کلونیِ خود بازمی‌گردند. فرض کنید یک مورچه همیشه از سمت بالا (مسیر کوتاه‌تر) حرکت می‌کند و مورچه‌ی دیگر از سمت پایین (مسیر طولانی‌تر). اگر هر کدام از این مورچه‌ها بخواهند ۵ دقیقه مداوم مسیر را بروند و برگردند، کدام مورچه بیشتر این رفت‌و‌برگشت را انجام می‌دهد؟ مسلم است که مورچه‌ی بالایی به دلیل کوتاه بودنِ طول مسیر، سریع‌تر مسیر رفت‌و‌برگشت را طی کرده و در طول مدت ۵ دقیقه، تعداد بیشتری غذا به کلونی می‌آورد. گفتیم که مورچه‌ها در مسیر حرکت خود فرومون می‌ریزند، پس واضح است که مسیرِ بالایی، مقدار فرومونِ بیشتری دارد. زیرا تردد بیشتری داشته است. حال فرض کنید یک مورچه‌ی سوم، می‌خواهد شروع به حرکت کند، به دوراهی می‌رسد و حس می‌کند که در مسیر بالایی، فرومون بیشتری قرار دارد. پس احتمالاً مسیرِ بالا، مسیر کوتاه‌تر و بهینه‌تری است. بنابراین با احتمالِ بیشتری مسیر بالایی را انتخاب می‌کند. بعد از آن چندین مورچه‌ی دیگر هم همین‌کار را می‌کنند، آرام آرام مقدار فرومون‌های مسیرِ بالا (مسیرِ کوتاه‌تر) بیشتر می‌شود (چون احتمال انتخاب مسیر بالا بیشتر است) و کم کم مورچه‌ها به این جمع‌بندی می‌رسند که مسیر بالا کوتاه‌تر است. به این صورت کوتاه‌ترین مسیر توسط مورچه‌ها کشف می‌شود.

حال اجازه بدهید به سراغ الگوریتم کامپیوتریِ این روش برویم. الگوریتمِ کلونی مورچه‌ها یا همان Ant Colony Optimization که به صورت مخفف به ACO هم معروف است با استفاده از فرومون‌ریزی و تبخیرِ فرومون، امیدوار است که به یک بهینه‌ی خوب برای یک مسئله‌ی بهینه‌سازی برسد. برای شروع با یک مثال می‌خواهیم ببینیم که چگونه می‌توان با الگوریتم کلونی مورچگان یک مسیرِ بهینه را پیدا کنیم. شکل زیر را نگاه کنید:

در این شکل یک مورچه می‌خواهد با شروع از خانه‌ی کلونی شروع کرده، به همه‌ی غذاهای مختلف سر بزند و بعد دوباره به خانه بازگردد. دو مورچه شروع به حرکت می‌کنند و با استفاده از مسیرهای مختلف، به غذاهای ۱ تا ۳ سر زده و بعد به خانه بازمی‌گردد. برای شروع فرض کنید دو مورچه همزمان شروع به حرکت می‌کنند. شکل زیر دو مسیر که این دو مورچه رفته‌اند را نمایش می‌دهد:

همان‌طور که می‌بینید، مورچه‌ی سبز رنگ مسیری با اندازه‌ی ۱۴متر را طی کرده است (این مورچه از کلونی به سمت غذای ۱، سپس غذای ۲، سپس ۳ می‌رود و در آخر به خانه بازمی‌گردد). مورچه‌ی آبی‌ رنگ نیز، مسیر ۳۱ متری را طی کرده است (از کلونی به سمت غذای ۲، سپس ۱، سپس ۳ و بعد از آن به کلونی بازگشته است). پس مشخص می‌شود که مورچه‌ی سبز رنگ مسیر بهتر و بهینه‌تری پیدا کرده است.

حال بایستی عملیات فرومون‌ریزی را انجام دهیم. هر مورچه به اندازه‌ی معکوس مسیری که رفته است فرومون می‌ریزد (یعنی هرچقدر مورچه مسیر بیشتری رفته باشد، کمتر در آن مسیر فرومون می‌ریزد). شکل زیر را نگاه کنید:

مشاهده می‌کنید که مورچه‌ی سبز برای هر یال (یعنی هر مسیر – مثلاً از کلونی به غذای ۱ یک یال است) به اندازه ۱/۱۴ فرومون می‌ریزد، زیرا طول کل مسیر ۱۴ متر شده شده و مورچه‌ی آبی به اندازه‌ی هر مسیر ۱/۳۲ فرومون می‌ریزد، زیرا طول کل مسیر برای او ۳۲ متر شده بود. مشخص است که مسیرهایی که مورچه‌ی آبی رنگ رفته‌است، فرومون کمتری ریخته شده است. حال بایستی تمامیِ فرومون‌ها را در هر یال را با هم جمع کنیم. این کار را در شکل زیر انجام داده‌ایم:

مثلاً یالی که غذای ۱ را به غذای ۲ وصل کرده است باید حاصل جمع ۱/۱۴ و ۱/۳۲ شود، زیرا هر دو مورچه از این مسیر رد شده‌اند ولی یالی که غذای ۲ را به غذای ۳ وصل کرده است، فقط مورچه‌ی سبز رنگ از آن رد شده است. حال فرض کنید یک مورچه‌ی قرمز رنگ با توجه به فرومون‌های گذاشته شده توسط مورچه‌های قبلی می‌خواهد مسیر حرکت را شروع کند. این مورچه‌ی قرمز رنگ در ابتدا در “کلونی” قرار دارد و می‌خواهد یکی از سه مسیر را به غذای ۱ یا ۲ یا ۳ انتخاب کند (یکی از یال‌های مرتبط با کلونی – یعنی محل فعلی مورچه). در شکل بالا مشخص است که احتمالِ انتخاب مسیر به غذای ۳ بیشتر است (زیرا جمع فرومون‌ها در آن‌جا بیشتر شده است). یعنی مورچه‌ی قرمز با توجه به پیام‌هایی که مورچه‌های قبلی از طریق فرومون برای اون به جای گذاشته‌اند، بایستی با احتمال بیشتری از کلونی به سمت غذای ۳ حرکت کند. ولی این احتمال انتخاب توسط فرمول زیر محاسبه می‌شود:

فرمول بسیار ساده است. نحوه‌ی محاسبه به این صورت است که تصمیمِ یک مورچه در انتخاب یک مسیر به دو چیز بستگی دارد. اول فکری که خودش می‌کند یعنی نظر شخصیِ خود مورچه، دوم مقدار فرومونی که بر روی زمین حس می‌کند، یعنی پیام‌هایی که مورچه‌های دیگر برای او گذاشته‌اند. در فرمول بالا ۲ پارامتر آلفا و بتا (توان‌ها) وجود دارد که کاربر به الگوریتم به عنوان مقدار اولیه می‌دهد. اگر پارامتر آلفا بیشتر از بتا باشد، یک مورچه بیشتر به مقدار فرومون‌ها یعنی پیام‌های بقیه‌ی مورچه‌ها توجه می‌کند تا نظرِ شخصیِ خودش! و اگر مقدار بتا بیشتر از آلفا باشد، نظرِ شخصیِ یک مورچه بیشتر از مقدار فرومون‌ها (تجربه‌ی مورچه‌های قبلی) در انتخاب مسیر تاثیر می‌گذارد.

فرض کنید مورچه‌ی قرمز رنگ، در خانه ایستاده و می‌خواهد برای شروع یکی از مسیرها به غذای ۱ یا ۲ یا ۳ را انتخاب کند. خودش می‌خواهد به ترتیب با احتمال ۰.۳ به سمت غذای ۱،با احتمال ۰.۳ به سمت غذای ۲ و با احتمال ۰.۴ به سمت غذای ۳ حرکت کند (برای مثال مورچه با مشاهده‌ی این‌که کدام مسیر احتمالاً نزدیک‌تر است یک تصمیمِ تخمینی و شخصی – بدون توجه به فرومون‌ها – می‌گیرد). اما اگر بخواهد بر اساس فرومون‌های موجود حرکت کند، باید با احتمال بیشتری به سمت غذای شماره‌ی ۳ برود. چون مقدار فرومون آنجا بیشتر است. بنابراین این مورچه با توجه به فرمولِ بالا به یک توازن بین نظر شخضی خود و پیام‌هایی که مورچه‌های قبلی توسط فرومون برای او گذاشته‌اند، می‌رسد و تصمیم خود را می‌گیرد. اجازه دهید برای هر کدام از مسیرهای ابتدا، احتمالِ انتخاب را محاسبه کنیم:

در مثال بالا، آفا و بتا را برای سادگی برابر ۱ قرار دادیم. همان‌طور که مشخص است، این مورچه با احتمال بیشتری به سمت غذای ۳ حرکت می‌کند (البته شانس انتخاب مسیر به غذای ۱ یا ۲ هم وجود دارد).

توجه داشته‌باشید که با هر بار که الگوریتم جلو می‌رود، مقداری از فرومون‌ها تبخیر می‌شود. مثلاً با حرکت مورچه‌ی قرمز یک مسیر جدید ایجاد می‌شود و بایستی این مسیر جدید با فرومون‌های قبلی جمع گردد. این در حالی است که فرومون‌های قبلی مقداری تبخیر داشته‌اند. این تبخیر می‌تواند توسط فرمولِ ساده‌ی زیر محاسبه شود:

مقدار پارامتر “رو” یک پارامتر تبخیر بین ۰ و ۱ است که توسط کاربر به الگوریتم داده می‌شود. اگر این پارامتر مقدار ۱ داشته باشد، یعنی تمامی فرومون‌ها در دور‌های قبلی تبخیر می‌شوند و اگر مقدار ۰ داشته باشد یعنی هیچی فرومونی تبخیر نمی‌شود. این عدد معمولاً یک مقدار بین ۰ و ۱ (مثلا ۰.۵) است که میزان تبخیر فرومون را برای هر دور مشخص می‌کند.

همان‌طور که مشاهده کردید، الگوریتمِ بهینه‌سازی کلونیِ مورچگان با شبیه‌سازیِ دو عمل فرومون‌ریزی و تبخیر می‌تواند راه‌حل‌هایی را برای مسئله انتخاب کند که به تدریج این راه‌حل‌ها می‌توانند به راه‌حل بهینه‌ی سراسری نزدیک شوند. در واقع این نوعی از بهینه‌سازی مبتنی بر جمعیت (Population Based Optimization) است که با ارسال پیام توسط هر فرد از جامعه (مثلاً ارسال پیام از یک مورچه به یک مورچه‌ی دیگر) آرام آرام یک جمعیت، می‌تواند راه‌حل بهینه را پیدا کند.

برای تبدیل مسئله‌ی خود به مسئله‌ی قابل حل توسط الگوریتم مورچگان بایستی فضای حالت خود را طوری طراحی کنید که بتوانید از قوانین فرومون‌ریزی و تبخیر فرومون استفاده کنید. مثلاً می‌توانید مسئله‌ی خود را به یک گراف تبدیل کنید و هر یال گراف، رفتن از حالت فعلی به حالت بعدی باشد.