روش بهینه‌سازی گروه مورچه‌ها

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

این روش که از رفتار مورچه‌ها در یافتن مسیر بین محل لانه و غذا الهام گرفته شده؛ اولین بار در 1992 توسط مارکو دوریگو (Marco Dorigo) در پایان نامهٔ دکترایش مطرح شد.

مقدمه

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

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

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

از کابردهای این الگوریتم، رسیدن به راه حل تقریباً بهینه در مسئله فروشنده دوره‌گرد است. به طوری که انواع الگوریتم مورچه‌ها برای حل این مساله تهیه شده. زیرا این روش عددی نسبت به روشهای تحلیلی و genetic در مواردی که نمودار مدام با زمان تغییر کند یک مزیت دارد؛ و آن این که الگوریتمی ست با قابلیت تکرار. و لذا با گذر زمان می‌تواند جواب را به طور زنده تغییر دهد. که این خاصیت در روتینگ شبکه‌های کامپیوتری و سامانه حمل و نقل شهری مهم است.
در مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. اگر تعداد اين شهرها n باشد در حالت کلي اين مسئله از مرتبه (n-1)! است که براي فقط 21 شهر زمان واقعا زيادي مي برد:

روز1013*7/1 = S1016*433/2 = ms10*1018*433/2 = !20
با انجام يک الگوريتم برنامه سازي پويا براي اين مسئله ، زمان از مرتبه نمايي بدست مي آيد که آن هم مناسب نيست. البته الگوريتم هاي ديگري نيز ارائه شده ولي هيچ کدام کارايي مناسبي ندارند. ACO الگوريتم کامل و مناسبي براي حل مسئله TSP است.

مساله فروشنده دوره گرد

مزيتهاي ACO

<تبخير شدن فرومون> و <احتمال-تصادف >به مورچه ها امکان پيدا کردن کوتاهترين مسير را مي دهد. اين دو ويژگي باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازي مي شوند. مثلا در گراف شهرهاي مسئله فروشنده دوره گرد، اگر يکي از يالها (يا گره ها) حذف شود الگوريتم اين توانايي را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا کند. به اين ترتيب که اگر يال (يا گره اي) حذف شود ديگر لازم نيست که الگوريتم از ابتدا مسئله را حل کند بلکه از جايي که مسئله حل شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها مي توانند پس از مدت کوتاهي مسير بهينه(کوتاهترين) را بيابند.

کاربردهاي ACO

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

1. مسير يابي داخل شهري و بين شهري.

2. مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا.

3. مسير يابي شبکه هاي کامپيوتري.

الگوریتم

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

انواع مختلف الگوريتم بهينه سازي مورچگان

در پايين تعدادي از انواع شناخته شده از الگوريتم بهينه سازي مورچگان را معرفي ميکنيم :

۱- سيستم مورچه نخبگان : در اين روش بهترين راه حل کلي در هر تکرار فرمون آزاد ميکند .همچنين اين روش براي تمام مورچه هاي مصنوعي بايد انجام شود.

۲- سيستم مورچه ماکسيموم – مينيمم : يک مقدار کمينه و بيشينه براي فرمون تعيين کرده و فقط در هر مرحله بهترين جواب اين مقدار را آزاد ميکند و تمام گره هاي مجاور ان به مقدار فرمون بيشينه به مقدار دهي اوليه ميشوند.

۳- سيستم کلوني مورچه : که در بالا توضيحات کافي داده شده است.

۴- سيستم مورچه بر اساس رتبه  : تمام راه حل هاي بدست آماده بر اساس طول جواب رتبه بندي ميشوند و بر اساس همين رتبه بندي مقدار فرمون آزاد سازي شده توسط آنها مشخص خواهد شد و راه حل با طول کمتر از راه حل ديگر با طول بيشتر مقدار فرمون بيشتري آزاد ميکند .

۵ - سيستم مورچه متعامد مداوم : در اين روش مکانيزم توليد فرمون به مورچه اجازه ميدهد تا براي رسيدن به جواب بهتر و مشترک با بقيه مورچه ها جستجو انجام دهد با استفاده از روش طراحي متعامد مورچه ميتواند در دامنه تعريف شده خود به صورت مداوم براي بدست آوردن بهترين جواب جستجو کند که اين عمل به هدف رسيدن به جواب بهينه و صحيح ما را نزديک ميکند . روش طراحي متعامد ميتواند به ديگر روش هاي جستجو ديگر گسترش پيدا کنند تا به مزيت هاي اين روش هاي جستجو اضافه کند.

منابع

• نسخه_فرانسوی_مقاله
• نسخه_انگلیسی_مقاله
• ] Frederick Ducatelle, Adaptive Routing in Ad Hoc Wireless Multi-hop Networks, Universita della Svizzera italiana, Lugano, Switzerland, 2007.