الگوریتم کلونی مورچه ها (ACO) یک الگوریتم بهینه سازی مبتنی بر مفهوم رفتار مورچه ها در جمع آوری غذا و ایجاد مسیرهای بهینه است. در ACO، مورچه ها به ترشح فرمون ها میپردازند که نشانگر مسیرهای پیشین است. سایر مورچهها این فرمونها را شناسایی کرده و مسیرهای بهینه را بر اساس میزان فرمون در آنها انتخاب میکنند. این الگوریتم در مسائل مختلف از جستجو و مسیریابی تا بهینهسازی مسائل پیچیده با موفقیت استفاده میشود و توانایی ایجاد راه حلهای بهینه را داراست.
مقدمه
کلونی های مورچه و سایر جوامع حشرات اجتماعی، از جمله معماری های شگفت انگیزی هستند که با وجود سادگی فیزیکی، ساختارهای اجتماعی بسیار پیچیده و منظمی را برقرار میکنند. این نظم و تنظیم، مورچهها را قادر میسازد تا وظایفی بسیار پیچیده و متنوع را به کار بگیرند که به تنهایی از ظاهری چندان پیچیده برخوردار نیستند.
الهام از طبیعت
حوزه الگوریتم های مورچه مطالعهای است که به اساس مشاهده و تحلیل رفتارهای واقعی مورچهها تأسیس شده است. از این تحلیلها، مدل هایی برای شبیه سازی رفتارهای مورچهها تولید میشود. این مدلها به عنوان یک منبع انگیزشی برای طراحی الگوریتمهای جدید در مسائل بهینه سازی و کنترل توزیع شده مورد استفاده قرار میگیرند.
آذوقه جویی و تقسیم کار در حمل و نقل دو نمونه واضح از همکاری و تعامل در مواقع مختلف هستند.
یکی از نمونههای برجسته و معروف از الگوریتمهای مبتنی بر مورچه، ACO (Ant Colony Optimization) است. این الگوریتم به بهینهسازی در مسائل بهینهسازی گسسته مشغول است و الهام اصلیاش از رفتار جمعآوری آذوقه توسط مورچهها گرفته شده است. به وسیلهی تعامل و همکاری مورچهها برای جمعآوری منابع غذایی، ACO به حل مسائل پیچیده بهینهسازی کمک کرده و به عنوان یکی از الگوریتمهای موفق در این حوزه شناخته میشود.
رفتار کاوشگرایانه مورچه ها و بهینه سازی
بسیاری از گونههای مورچه، با وجود بینایی ابتدایی و محدود خود، توانایی پیدا کردهاند که کوتاهترین مسیر برای رفتن به منبع غذایی و بازگشت به خانه را پیدا کنند. در واقع، تحقیقات اخیر نشان میدهد که بیشترین تعامل میان مورچهها یا مورچه و محیط اطرافشان، از طریق استفاده از مواد شیمیایی به نام “فرمون” (Pheromone) صورت میگیرد.
اصطلاح “استیگمرژی” توسط گراس برای توصیف نوعی ارتباط غیرمستقیم از طریق تغییراتی که در محیط اطراف ایجاد میشود، معرفی شده است. او این رفتار را از روی موریانههای کارگر مورچهها مشاهده کرد. این استیگمرژی به معنای استفاده از فرمونها و ترکیب آنها به عنوان یک زبان ارتباطی جهت هدایت مسیریابی مورچهها میباشد. به این ترتیب، مورچهها از اطلاعاتی که توسط همکارانشان ایجاد شده استفاده میکنند تا به بهبود و بهینهسازی مسیرهای خود برای جستجوی غذا بپردازند. این نوع ارتباط و همکاری نشانگر یکی از نمونههای جالب هماهنگی در دنیای طبیعت میباشد.
تاریخچه
الگوریتم مورچگان برای اولین بار در سال 1991 توسط مارکو دوریگو (Dorigo) معرفی شد و برای حل مسائل بهینه سازی چالش برانگیزی مانند مسأله فروشنده دوره گرد (Traveling Salesperson Problem) به کار گرفته شد. این الگوریتم مبتنی بر رفتار مورچهها در جمعآوری غذا و ترکیب آن با تعامل با ردپای فرمون (Trail Pheromone) است که مورچهها از مواد شیمیایی به جا مانده از سایر مورچهها استفاده میکنند. این ردپای فرمون نشان دهنده مسیرهای پیشینی است که مورچهها طی کردهاند و تأثیر بسزایی در تصمیمگیری مورچهها برای انتخاب مسیر بهینه دارد. به این ترتیب، الگوریتم مورچگان به شکلی هماهنگ و هوش مصنوعی از تعامل و همکاری میان اعضای یک جمعیت الهام گرفته و به بهینهسازی مسائل پیچیده کمک میکند.
آزمایشات پل دو راهه
یکی از آزمایشات برجستهای که توسط دنوبورگ و همکارانش طراحی و اجرا شد، شامل اتصال لانه گونهای از مورچههای آرژانتینی به نام آی .هیومیلی به یک منبع آذوقه از طریق یک پل دوراهه بود. آنها آزمایشات خود را با استفاده از پلهای با طولهای مساوی و نامساوی انجام دادند.
فهرست مطالب
مقدمه
الهام از طبیعت
رفتار کاوشگرایانه مورچه ها و بهینه سازی
تاریخچه
آزمایشات پل دو راهه
پل های مساوی
نتایج آزمایش پل های مساوی(آزمایش اول)
پل های نامساوی
نتایج آزمایش پل های نامساوی(آزمایش دوم)
یک مدل احتمالی
به سمت مورچه های مصنوعی
ابزارهای مورچه های مصنوعی
الگوریتم های ACO
جستجوی محلی چیست؟
رفتار جستجوی مسیر مورچه ها
فراابتکاری ACO
مزیت ACO برای TSP
مسیریابی شبکه های کامپیوتری با استفاده از ACO
منابع و مأخذ