الگوریتم کلونی مورچگان

بهینه‌سازی گروه مورچه‌ها یا ACO همان‌طور که می‌دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. برای مثال مسئله فروشنده دوره گرد را نیز می‌توان مطرح کرد. در این روش (ACo)، مورچه‌ های مصنوعی به‌وسیله حرکت بر روی نمودار مسئله و با باقی گذاشتن نشانه‌هایی بر روی نمودار، همچون مورچه‌های واقعی که در مسیر حرکت خود نشانه‌های باقی می‌گذارند، باعث می‌شوند که مورچه‌های مصنوعی بعدی بتوانند راه‌حل‌های بهتری را برای مسئله فراهم نمایند. همچنین در این روش می‌توان توسط مسائل محاسباتی ـ عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت. ۳۰۰ px این روش که از رفتار مورچه‌ ها در یافتن مسیر بین محل لانه و غذا الهام گرفته شده؛ اولین بار در ۱۹۹۲ توسط مارکو دوریگو (Marco Dorigo) در پایان نامهٔ دکترایش مطرح شد … .

معرفی الگوریتم کلونی مورچه‌ ها:

نخستین سیستم کلونی مورچه، به وسیله “مارکو دوریگو” در رساله دکترایش در سال ۱۹۹۲ معرفی شد و سیستم مورچه ها نامیده شد. سیستم مورچه ها یکی از روش های فرا ابتکاری است که اولین بار به عنوان یک راه حل چند عامله برای حل مسائل مشکل بهینه سازی مثل فروشنده دوره گرد، ارائه شد.

عامل هوشمند:

موجودی است که از طریق حسگرها قادر به درک پیرامون خود بوده و از طریق تأثیرگذارنده ها می تواند روی محیط اثر بگذارد. آنچه بنیان فکری الگوریتم مورچگان بر آن بنا شده است را می توان بسادگی و در یک جمله بیان نمود: ” مورچه ها در بین موانع و محدودیت های موجود در طبیعت همیشه از بین جایگشت های متفاوت برای رسیدن به غذا، بهینه ترین راه را انتخاب می کنند”.

کاربردهای الگوریتم کلونی مورچگان:

از کاربردهای ACO می‌توان به بهینه کردن هر مسئله ای که نیاز به یافتن کوتاهترین مسیر دارد، اشاره نمود :

• مسیر یابی داخل شهری و بین شهری
• مسیر یابی بین پست های شبکه های توزیع برق ولتاژ بالا
• مسیر یابی شبکه های کامپیوتری
• بهینه سازی سکوهای دریایی
• طراحی شبکه های توزیع شعاعی
• ورود و خروج واحدهای نیروگاهی

مسیر یابی شبکه های کامپیوتری با استفاده از ACO J در ابتدا مقدمه ای از نحوه مسیر یابی در شبکه های کامپیوتری را توضیح خواهیم داد :

اطلاعات بر روی شبکه بصورت بسته های اطلاعاتی کوچکی (Packet) منتقل می شوند. هر یک از این بسته ها بر روی شبکه در طی مسیر از مبدا تا مقصد باید از گره های زیادی که مسیریاب (Router) نام دارند عبور می کنند. در داخل هر مسیریاب جدولی قرار دارد تا بهترین و کوتاهترین مسیر بعدی تا مقصد از طریق آن مشخص می شود، بنابر این بسته های اطلاعاتی حین گذر از مسیریاب ها با توجه به محتویات این جداول عبور داده می شوند.

توجه : فایل فوق از دو فایل مجزا ۳۱ و ۲۱ اسلایدی تشکیل شده است.