Author: مجید طاهری

الگوریتم کلونی مورچه‌ها Ant Colony 

 مجید طاهری

 
مقدمه

 انسان هميشه براي الهام گرفتن به جهان زنده پيرامون خود نگريسته است. يکي از بهترين طرح هاي شناخته شده، طرح پرواز انسان است که ابتدا لئورناردو داوينچي(1519-1452) طرحي از يک ماشين پرنده را بر اساس ساختمان بدن خفاش رسم نمود. چهار صد سال بعد کلمان آدر ماشين پرنده اي ساخت که داراي موتور بود و بجاي بال از ملخ استفاده مي کرد.

هم اکنون کار روي توسعه سيستم هاي هوشمند با الهام از طبيعت از زمينه هاي خيلي پرطرفدار هوش مصنوعي است. الگوريتمهاي ژنتيک که با استفاده از ايده تکاملي دارويني و انتخاب طبيعي مطرح شده، روش بسيار خوبي براي يافتن مسائل بهينه سازيست. ايده تکاملي دارويني بيانگر اين مطلب است که هر نسل نسبت به نسل قبل داراي تکامل است و آنچه در طبيعت رخ مي دهد حاصل ميليون ها سال تکامل نسل به نسل موجوداتي مثل مورچه است.

الگوريتم کلوني مورچه براي اولين بار توسط دوريگو (Dorigo) و همکارانش به عنوان يک راه حل چند عامله (Multi Agent) براي مسائل مشکل بهينه سازي مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائه شد.

عامل هوشند(Intelligent Agent) موجودي است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد.

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

در هوشمندي اجتماعي عناصر ميزاني از هوشمندي را دارا هستند. بعنوان مثال در فرآيند ساخت ساختمان توسط انسان، زماني که به يک کارگر گفته ميشود تا يک توده آجر را جابجا کند، آنقدر هوشمند هست تا بداند براي اينکار بايد از فرغون استفاده کند نه مثلا بيل!!! نکته ديگر تفاوت سطح هوشمندي افراد اين جامعه است. مثلا هوشمندي لازم براي فرد معمار با يک کارگر ساده متفاوت است.

در هوشمندي توده اي عناصر رفتاري تصادفي دارند و بين آن ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و با استفاده از نشانه ها با يکديگر در تماس هستند. مثالي در اين مورد رفتار موريانه ها در لانه سازيست.

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

تفاوتهاي هوشمندي اجتماعي انسان با هوشمندي توده اي موريانه را در همين رفتار ساخت لانه مي توان مشاهده کرد. کارگران ساختماني کاملا بر اساس يک طرح از پيش تعيين شده عمل مي کنند، در حالي که رفتار اوليه موريانه ها کاملا تصادفي است. علاوه بر اين ارتياط مابين کارگران سختماني مستقيم و از طريق کلمات و ... است ولي بين موريانه ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و از طريق نشانه ها با يکديگر در تماس اند. گرس نام اين رفتار را Stigmergie گذاشت، به معني رفتاري که هماهنگي مابين موجودات را تنها از طريق تغييرات ايجاد شده در محيط ممکن مي سازد.

 

بهينه‌سازي مسائل بروش کلوني مورچه (ACO):

 همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يک مسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گرد(TSP). در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. اگر تعداد اين شهرها n باشد در حالت کلي اين مسئله از مرتبه (n-1)! است که براي فقط 21 شهر زمان واقعا زيادي مي برد:

 روز10¹³*7/1 =  S10¹⁶*433/2 = ms10*10¹⁸*433/2 = !20

 با انجام يک الگوريتم برنامه سازي پويا براي اين مسئله ، زمان از مرتبه نمايي بدست مي آيد که آن هم مناسب نيست. البته الگوريتم هاي ديگري نيز ارائه شده ولي هيچ کدام کارايي مناسبي ندارند. ACO الگوريتم کامل و مناسبي براي حل مسئله TSP است.

 

 

مورچه‌ها چگونه مي‌توانند کوتاهترين مسير را پيدا کنند؟

 

 مورچه ها هنگام راه رفتن از خود ردي از ماده شيميايي فرومون(Pheromone) بجاي مي گذارند البته اين ماده بزودي تبخير مي شد ولي در کوتاه مدت بعنوان رد مورچه بر سطح زمين باقي مي ماند. يک رفتار پايه اي ساده در مورچه هاي وجود دارد :

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

همانطور که در شکل 1-1 مي بينيم مورچه هاي روي مسير AB در حرکت اند (در دو جهت مخالف) اگر در مسير مورچه ها مانعي قرار ديهم(شکل 2-1) مورچه ها دو راه براي انتخاب کردن دارند. اولين مورچه ازA  مي آيد و بهC  مي رسد، در مسير هيچ فروموني نمي بيند بنابر اين براي مسير چپ و راست احتمال يکسان مي دهد و بطور تصادفي و احتمالاتي مسير CED را انتخاب مي کند. اولين مورچه اي که مورچه اول را دنبال مي کند زودتر از مورچه اولي که از مسير CFD رفته به مقصد مي رسد. مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرومون را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا) انتخاب مي کنند. در نهايت مسير CED بعنوان مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED کوتاهتر است زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد چون فرومون بيشتري در آن وجود دارد.

 

نکته بسيار با اهميت اين است که هر چند احتمال انتخاب مسير پر فرومون ت توسط مورچه ها بيشتر است ولي اين کماکان احتمال است و قطعيت نيست. يعني اگر مسير CED پرفرومون تر از CFD باشد به هيچ عنوان نمي شود نتيجه گرفت که همه مورچه ها از مسيرCED  عبور خواهند کرد بلکه تنها مي توان گفت که مثلا 90% مورچه ها از مسير کوتاهتر عبور خواهند کرد. اگر فرض کنيم که بجاي اين احتمال قطعيت وجود مي داشت، يعني هر مورچه فقط و فقط مسير پرفرومون تر را انتخاب ميکرد آنگاه اساسا اين روش ممکن نبود به جواب برسد. اگر تصادفا اولين مورچه مسيرCFD(مسير دورتر) را انتخاب مي کرد و ردي از فرومون بر جاي مي گذاشت آنگاه همه مورچه ها بدنبال او حرکت مي کردند و هيچ وقت کوتاهترين مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در ACO بر عهده دارند.

نکته ديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير  AB برداشته شود و فرومون تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرومون و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند.

 

 

مزيت‌هاي ACO:

 

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

 

کاربردهاي ACO:

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

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

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

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

 

 

مسيريابي شبکه‌هاي کامپيوتري با استفاده از ACO:

 

 در ابتدا مقدمه اي از نحوه مسير يابي در شبکه هاي کامپيوتري را توضيح خواهيم داد:

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

روشي بنام ACR : Ant Colony Routering پيشنهاد شده که بر اساس ايده کلوني مورچه به بهينه سازي جداول مي‌پردازيد و در واقع به هر مسيري با توجه به بهينگي آن امتياز مي دهد. استفاده از ACR به اين منظور داراي برتري نسبت به ساير روش هاست که با طبيعت ديناميک شبکه سازگاري دارد، زيرا به عنوان مثال ممکن است مسيري پر ترافيک شود يا حتي مسير يابي (Router) از کار افتاده باشد و بدليل انعطاف پذيري که ACO در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترس قرار مي دهد.

 

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

 

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

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

 

 

 

 

مقدمه

 

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

   

- باعث می‌شود مسیر جذابیت کمتری برای مورچه‌های بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راه های کوتاه‌تر را بیش تر می‌پیماید و تقویت می‌کند هر راهی بین خانه و غذا که کوتاه‌تر(بهتر) باشد بیشتر تقویت می‌شود و آنکه دورتر است کمتر

- اگر فرومون اصلاً تبخیر نمی شد، مسیرهایی که چند بار طی می‌شدند، چنان بیش از حد جذّاب می‌شدند که جستجوی تصادفی برای غذا را بسیار محدود می‌کردند.

- وقتی غذای انتهای یک مسیر جذاب تمام می‌شد رد باقی می‌ماند.

 

 

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

 

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

 

 

 

استفاده پژوهشگران از الگوي کلوني مورچه‌ها جهت اداره ترافيک

 

 پژوهشگران سوييسي به تازگي براي تهيه نرم افزاري جهت اداره ترافيک و شبکه هاي جاده اي از الگوي کلوني مورچه ها استفاده مي کنند.به گزارش  باشگاه خبرنگاران  به نقل از شبکه يورونيوز، کلني مورچه ها قادر است هم زمان تعداد زيادي از فعاليتهاي روزمره را اداره کند که عبارتند از رسيدگي به تخمها ، ساخت تونل و رفت و امد براي يافتن اذوقه.همه اين فعاليتها به دقت سازماندهي شده است.

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