چرا الگوریتم‌های کلونی مورچگان و زنبور عسل از الگوریتم‌های مهم هستند؟

بهینه‌سازی ازدحام ذرات

قبل از آن‌که به معرفی دو الگوریتم یاد شده برویم، اجازه دهید توضیح کوتاهی در ارتباط با بهینه‌سازی ازدحام ذرات ارائه کنیم. روش «بهینه‌سازی ازدحام ذرات» (Particle swarm optimization) یک روش سراسری بهینه‌سازی است که با استفاده از آن می‌توان با مسائلی که جواب آن‌ها یک نقطه یا سطح در فضای n بعدی می‌باشد، برخورد نمود. در چنین فضایی، فرضیاتی مطرح می‌شود و یک سرعت ابتدایی به آن‌ها اختصاص داده می‌شود، همچنین کانال‌های ارتباطی بین ذرات در نظر گرفته می‌شود. سپس این ذرات در فضای پاسخ حرکت می‌کنند، و نتایج حاصله بر مبنای یک «ملاک شایستگی» پس از هر بازه زمانی محاسبه می‌شود. با گذشت زمان، ذرات به سمت ذراتی که دارای ملاک شایستگی بالاتری هستند و در گروه ارتباطی یکسانی قرار دارند، شتاب می‌گیرند. به‌رغم این‌که هر روش در محدوده‌ای از مسائل به خوبی کار می‌کند، این روش در حل مسائل بهینه‌سازی پیوسته، موفقیت بسیاری از خود نشان داده‌ است.

مطلب پیشنهادی

هوش مصنوعی ازدحامی (Swarm Intelligence) چیست؟

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

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

مسئله فروشنده دوره گرد یکی از مثال مهم و جالب دنیای هوش مصنوعی در این زمینه است. در این روش الگوریتم کلونی مورچگان، مورچه‌های مصنوعی به ‌وسیله حرکت روی نمودار مسئله و با باقی گذاشتن نشانه‌هایی روی نمودار، همچون مورچه‌های واقعی که در مسیر حرکت خود نشانه‌های باقی می‌گذارند، باعث می‌شوند که مورچه‌های مصنوعی بعدی بتوانند راه‌حل‌های بهتری را برای مسئله فراهم نمایند. همچنین در این روش می‌توان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت. الگوریتم کلونی مورچه الهام گرفته‌شده از مطالعات و مشاهدات روی کلونی مورچه‌ است. این مطالعات نشان داده که مورچه‌ها حشراتی اجتماعی هستند که در کلونی‌ها زندگی می‌کنند و رفتار آن‌ها بیشتر در جهت بقاء کلونی است تا در جهت بقاء یک جزء از آن. پروسه پیدا کردن کوتاه‌ترین مسیر توسط مورچه‌ها، ویژگی‌های بسیار جالبی دارد، اول از همه قابلیت تعمیم زیاد و خود- سازمانده بودن آن است. در ضمن هیچ مکانیزم کنترل مرکزی‌ای وجود ندارد. ویژگی دوم قدرت زیاد آن است. سیستم شامل تعداد زیادی از عواملی است که به‌تنهایی بی‌اهمیت هستند بنابراین حتی تلفات یک عامل مهم، تأثیر زیادی روی کارایی سیستم ندارد. سومین ویژگی این است که، پروسه یک فرایند تطبیقی است. از آنجا که رفتار هیچ‌کدام از مورچه‌ها معین نیست و تعدادی از مورچه‌ها همچنان مسیر طولانی‌تر را انتخاب می‌کنند، سیستم می‌تواند خود را با تغییرات محیط منطبق کند و ویژگی آخر این‌که این پروسه قابل توسعه است و می‌تواند به اندازه دلخواه بزرگ شود. همین ویژگی‌ها الهام بخش طراحی الگوریتم‌هایی شده‌اند که در مسائلی که نیازمند این ویژگی‌ها هستند کاربرد دارند. اولین الگوریتمی که بر این اساس معرفی شد، الگوریتم ABC بود، در ادامه الگوریتم‌های دیگری به‌نام‌های AntHocNet، PERA، ARA و AntNet ‌بر مبنای الگوریتم فوق پیاده‌سازی شدند.

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

باعث می‌شود مسیر جذابیت کمتری برای مورچه‌های بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راه‌های کوتاه‌تر را بیش تر می‌پیماید و تقویت می‌کند هر راهی بین خانه و غذا که کوتاه‌تر (بهتر) باشد بیشتر تقویت می‌شود و آنکه دورتر است کمتر. اگر فرومون اصلاً تبخیر نمی‌شد، مسیرهایی که چند بار طی می‌شدند، چنان بیش از حد جذّاب می‌شدند که جستجوی تصادفی برای غذا را بسیار محدود می‌کردند. وقتی غذای انتهای یک مسیر جذاب تمام می‌شد رد باقی می‌ماند. لذا وقتی یک مورچه مسیر کوتاهی (خوبی) را از خانه تا غذا بیابد بقیه مورچه‌ها به احتمال زیادی همان مسیر را دنبال می‌کنند و با تقویت مداوم آن مسیر و تبخیر ردهای دیگر، به مرور همه مورچه‌ها هم‌مسیر می‌شوند. هدف الگوریتم مورچه‌ها تقلید این رفتار توسط مورچه‌هایی مصنوعی ست که روی نمودار در حال حرکت هستندد. مسئله یافتن کوتاه‌ترین مسیر است و حلالش این مورچه‌های مصنوعی‌اند. از کابردهای این الگوریتم، رسیدن به راهحل تقریباً بهینه در مسئله فروشنده دوره‌گرد است. به طوری که انواع الگوریتم مورچه‌ها برای حل این مسئله تهیه شده است. زیرا این روش عددی نسبت به روش‌های تحلیلی و genetic در مواردی که نمودار مدام با زمان تغییر کند یک مزیت دارد؛ و آن این که الگوریتمی‌ست با قابلیت تکرار؛ و لذا با گذر زمان می‌تواند جواب را به‌طور زنده تغییر دهد که این خاصیت در روتینگ شبکه‌های کامپیوتری و سامانه حمل‌ونقل شهری مهم است. با انجام یک الگوریتم برنامه‌سازی پویا برای این مسئله، زمان از مرتبه نمایی به‌دست می‌آید که آن هم مناسب نیست. البته الگوریتم‌های دیگری نیز ارائه شده ولی هیچ‌کدام کارایی مناسبی ندارند. ACO الگوریتم کامل و مناسبی برای حل مسئله TSP است.

الگوریتم کلونی مورچگان چه مزایایی دارد؟

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

الگوریتم زنبور عسل

در علوم کامپیوتر و عملیات تحقیق، الگوریتم زنبورعسل یک الگوریتم جستجو مبتنی بر جمعیت است که در سال ۲۰۰۵ میلادی توسط دکتر فام و دکتر افشین قنبرزاده توسعه یافت. این الگوریتم تقلید رفتار جستجوگری مواد غذایی زنبورهای عسل است. در نسخه اولیه این الگوریتم یک نوع جستجوی محلی همراه با جستجوی جهانی انجام می‌دهد و می‌تواند برای هر دو بهینه‌سازی ترکیبی و بهینه‌سازی مستمر مورد استفاده قرار گیرد. تنها شرط استفاده از الگوریتم زنبورعسل این است که برخی اندازه‌گیری‌های فاصله توپولوژیکی بین راه‌حل‌ها تعریف شده‌ است. اثربخشی و توانایی‌های خاص الگوریتم زنبور عسل در تعدادی از مطالعات ثابت شده‌ است.

یک کلونی از زنبورهای عسل می‌توانند در طول فواصل بلند (بیش از ۱۴ کیلومتر) و در جهات مختلف به‌طور هم‌زمان به برداشت شهد یا گرده از منابع غذایی متعدد پراکنده شوند. بخش کوچکی از این کلونی به‌طور مداوم محیط زیست را برای پیدا کردن تکه‌های گل جدید جستجو می‌کنند. این زنبورهای دیده‌بان به‌طور تصادفی در منطقه اطراف کندو حرکت می‌کنند و به ارزیابی سودآوری (عملکرد خالص انرژی) منابع غذایی واردشده می‌پردازند. وقتی آن‌ها به کندو باز می‌گردنند، دیده‌بان‌ها مواد غذایی برداشت‌شده را ذخیره می‌کنند. آن دسته از زنبورهایی که منبع غذایی بسیار سودآوری پیدا کردند به یک منطقه در کندو به نام «پیست رقص» رفته و آیینی به نام «رقص حرکتی» را اجرا می‌کنند. در حین این رقص زنبوردیده بان در مورد محلی که کشف کرده با تماشچیان بیکار صحبت می‌کند که به بهره‌برداری از گل‌ها بپیوندند. از آن‌جا که طول رقص متناسب با امتیاز دیده‌بان از منبع غذایی است، کاوشگرهای بیشتری برای برداشت تکه‌های گل با بهترین امتیاز استخدام می‌شوند. بعد از رقص دیده‌بان برای جمع‌آوری بیشتر غذا به محلی که کشف کرده‌ است می‌رود. تا زمانی که این محل‌ها سودآور تلقی شوند، موقع برگشت این منابع غذایی غنی توسط دیده‌بان‌ها تبلیغ می‌شوند. کاوشگرهای استخدام‌شده نیز ممکن است این رقص را انجام دهند، تا میزان استخدام برای پیدا کردن گل‌های پرارزش افزایش یابد. با تشکر از فرایند اتوکاتالیزوری این کلونی زنبور عسل قادر است سریع تمرکز را به جستجو برای گل‌های سودآور تغییر دهد. الگوریتم زنبورعسل تقلید استراتژی جستجوی غذای زنبورعسل به دنبال بهترین راه حل برای مشکل بهینه‌سازی است. هر راه‌حل کاندید، به‌عنوان یک منبع غذایی (گل) است و جمعیت (کلنی) n عوامل (زنبور) برای جستجوی فضای راه‌حل استفاده می‌شود. هر بار زنبور عسل مصنوعی به دیدار گل می‌رود (به یک راه حل رسیده)، سود آن را ارزیابی می‌کند (سازگاری). الگوریتم زنبور عسل شامل روش اولیه نصب یک چرخه جستجوی اصلی که برای تعداد داده‌شده T بار تکرار می‌شود یا تا زمانی که یک راه‌حل سازگار و قابل قبول پیدا شود. هر چرخه جستجو متشکل از پنج روش:استخدام، جستجوی محلی، کوچک شدن محله، متروکه شدن محل و جستجوی کلی است. الگوریتم زنبورها کاربردهای زیادی در مهندسی پیدا کرده که از آن جمله باید به بهینه‌سازی طبقه/سیستم‌های خوشه‌بندی، ساخت، کنترل مهندسی زیست، سایر مسائل بهینه‌سازی و بهینه‌سازی چند هدفه اشاره کرد.

‌کلام آخر

در حالت کلی، الگوریتم‌ها عمدتا با هدف پیدا کردن کوتاه‌ترین مسیر استفاده می‌شوند. به‌طور مثال، مسئله یافتن کوتاه‌ترین مسیر برای یافتن مسیرهای میان مکان‌های واقعی از قبیل راه‌های عبور و مرور در نقشه‌های اینترنتی مانند نقشه گوگل استفاده می‌شود. اگر یک ماشین مجازی غیرواقعی را به‌صورت گرافی در نظر بگیریم که در آن رأس‌ها بیان‌کننده حالت‌ها و یال‌ها بیان‌کننده گذار از حالتی به حالتی دیگر باشند، می‌توان از الگوریتم یافتن کوتاه‌ترین مسیر به‌عنوان ابزاری برای یافتن دنباله‌ای بهینه از انتخاب‌ها به‌منظور رسیدن به یک حالت ویژه استفاده کرد. همچنین می‌توان این الگوریتم را به‌منظور دست یابی به یک کران پایین از زمان مورد نیاز برای رسیدن به یک حالت مشخص به کار برد. برای مثال اگر رأس‌ها بیان‌گر حالت‌های یک پازل مانند مکعب رابیک و هر یک از یال‌های جهت دار بیانگر یک حرکت یا چرخش باشند، می‌توان از الگوریتم‌های کوتاه‌ترین مسیر بهره برد، به‌گونه‌ای که این الگوریتم‌ها به راه‌حلی با کمترین تعداد حرکت منجر شوند. گاهی در ساختار شبکه‌های ارتباطی یا شبکه‌های مخابراتی از این مسئله با عنوان مسئله یافتن کم‌تاخیرترین مسیر یاد می‌کنند که اغلب ارتباط تنگاتنگی با مسئله یافتن عریض‌ترین مسیر دارد. این مسئله در رباتیک، حمل‌و‌نقل و طراحی مدارهای VLSI نیز کاربرد دارد.