فرادرسالگوریتم بهینه سازی کلونی مورچگان در جاوا – راهنمای کاربردی
در این مقاله به توضیح مفهوم «بهینه‌سازی کلونی مورچگان» (ant colony optimization) یا به اختصار ACO می‌پردازیم و کدهای نمونه آن را نیز ارائه می‌کنیم.
طرز کار الگوریتم کلونی مورچگان چگونه است؟
ACO یک الگوریتم ژنتیک است که از رفتار طبیعی مورچه‌ها الهام گرفته است. برای درک کامل الگوریتم ACO باید با مفاهیم مقدماتی آن آشنا باشیم.
- مورچه‌ها از «فرمیون» (pheromone) برای یافتن کوتاه‌ترین مسیر بین خانه و منبع غذایی استفاده می‌کنند.
- فرمیون‌ها به سرعت تبخیر می‌شوند.
- مورچه‌ها مسیرهای کوتاه‌تر با فرمیون‌های چگال‌تر را ترجیح می‌دهند.
در ادامه مثال ساده‌ای از الگوریتم کلونی مورچگان را که به صورت مسئله فروشنده دوره‌گرد مطرح شده، مورد بررسی قرار می‌دهیم. در مثال زیر باید کوتاه‌ترین مسیر بین همه گره‌های گراف را بیابیم.
مورچه‌ها با پیروی از رفتار طبیعی‌شان شروع به جستجوی مسیرهای جدید در مرحله کاوش می‌کنند. مسیرهای آبی پررنگ نشان‌دهنده مواردی هستند که نسبت به بقیه بیشتر استفاده شده‌اند؛ در حالی که مسیرهای سبزرنگ نماینده کوتاه‌ترین مسیر کنونی پیدا شده است:
در نتیجه به کوتاه‌ترین مسیر بین همه گره‌ها دست پیدا کرده‌ایم:
برای مشاهده یک ابزار زیبای مبتنی بر GUI برای آزمودن ACO می‌توانید به این آدرس (+) مراجعه کنید.
پیاده‌سازی جاوا
در این بخش به بررسی روش موردنیاز برای پیاده‌سازی بهینه‌سازی کلونی مورچگان در زبان برنامه‌نویسی جاوا می‌پردازیم.
پارامترهای ACO
ابتدا پارامترهای الگوریتم ACO را که در کلاس AntColonyOptimization اعلان شده‌اند، بررسی می‌کنیم:
پارامتر c نشان‌دهنده عدد اولیه «مسیرها» (trails) در ابتدای شبیه‌سازی است. به علاوه، alpha به کنترل اهمیت فرمیون می‌پردازد؛ در حالی که beta اولویت مسافت را کنترل می‌کند. به طور کلی در بهترین نتایج پارامتر بتا باید بزرگ‌تر از آلفا باشد.
سپس متغیر «تبخیر» (evaporation) نشان می‌دهد که چه درصدی از فرمیون در هر تکرار تبخیر می‌شود؛ در حالی که Q اطلاعاتی در مورد مقدار کلی فرمیون باقی‌مانده روی مسیر از سوی هر مورچه و antFactor نیز تعداد مورچه‌های هر شهر را نشان می‌دهد. در نهایت باید مقداری تصادفی بودن به شبیه‌سازی‌های خود اضافه کنیم که این وظیفه نیز به پارامتر ranfomFactor محول شده است.
ایجاد مورچه‌ها
هر مورچه امکان بازدید از یک شهر خاص را دارد، همه شهرهای بازدید شده را به خاطر می‌سپارد و رد طول مسیر را نگه می‌دارد:
تنظیم مورچه‌ها
در ابتدای کار، باید پیاده‌سازی کد ACO خود را از طریق ارائه ماتریس‌های مسیرها و مورچه‌ها، مقداردهی اولیه بکنیم:
سپس باید ماتریس مورچگان را با یک شهر تصادفی مقداردهی بکنیم:
در هر تکرار این حلقه، عملیات زیر اجرا می‌شوند:
جابجایی مورچه‌ها
کار خود را با متد ()moveAnts آغاز می‌کنیم. به این منظور باید شهر بعدی را برای همه مورچه‌ها تنظیم کنیم و مسیر هر مورچه را برای پیمودن از سوی مورچه‌های دیگر به خاطر بسپاریم:
مهم‌ترین بخش، انتخاب مناسب شهر بعدی برای بازدید است. ما باید شهر بعدی را بر مبنای منطق احتمال انتخاب کنیم. ابتدا بررسی می‌کنیم که آیا مورچه باید از یک شهر تصادفی بازدید کند یا نه:
اگر هیچ شهر تصادفی را انتخاب نکرده باشیم، باید احتمال‌های انتخاب شهر بعدی را نیز محاسبه کنیم و به خاطر داشته باشیم که مورچه ترجیح می‌دهد، مسیر قوی‌تر و کوتاه‌تر را بپیماید. این کار از طریق مرتب‌سازی احتمال رسیدن به هر شهر در آرایه ممکن است:
پس از آن که احتمال‌ها را محاسبه کردیم، می‌توانیم با کد زیر در مورد این که به کدام شهر باید برویم تصمیم‌گیری کنیم:
به‌روزرسانی مسیرها
در این مرحله، باید مسیرها و میزان فرمیون باقی‌مانده را به‌روزرسانی کنیم:
به‌روزرسانی بهترین انتخاب
این آخرین مرحله برای هر تکرار است. ما باید بهترین انتخاب را به‌روزرسانی کنیم تا ارجاع آن را حفظ کنیم:
پس از اجرای همه تکرارها، نتیجه نهایی بهترین مسیر مشخص شده از سوی ACO را نشان خواهد داد. توجه داشته باشید که با افزایش تعداد شهرها، احتمال یافتن کوتاه‌ترین مسیر کاهش می‌یابد.
نتیجه‌گیری
در این راهنما به معرفی الگوریتم بهینه‌سازی کلونی مورچگان پرداختیم. شما می‌توانید با مطالعه این مقاله بدون هیچ دانش قبلی و صرفاً به کمک مهارت‌های ابتدایی برنامه‌نویسی رایانه، با الگوریتم‌های ژنتیک آشنا شوید.
کد کامل این راهنما را می‌توانید در این ریپوی گیت‌هاب (+) ملاحظه کنید.
اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزش‌های شبکه‌های عصبی مصنوعی
- مجموعه آموزش‌های الگوریتم مورچگان در متلب
- مجموعه آموزش‌های الگوریتم ژنتیک و محاسبات تکاملی
- آموزش 2۵ الگوریتم بهینه‌سازی تکاملی و هوشمند در فرادرس
- مقدمه‌ای بر بهینه‌سازی به کمک الگوریتم‌های فراابتکاری و محاسبات تکاملی
==
با سلام
مشابه همین کاربرد مورچگان در زمانبندی وظایف در رایانش ابری را ندارید؟