پروژه کاربرد کلونی مورچگان در شبکه

دانشگاه فني حرفه اي دانشكده فني مهندسي شهيد جباريان
موضوع تحقيق :
                    كاربرد كلوني مورچگان در شبكه
                                            استاد راهنما :
                                                                        مهندس محمدي
                                                                گردآورنده :
                                                                                                       رضا عقيقي
                                                                                        تاريخ ارائه :
                                                                                                                                 اريبهشت 92
مقدمه انسان هميشه براي الهام گرفتن به جهان زنده پيرامونخود نگريسته است. يکي از بهترين طرح هاي شناخته شده، طرح پرواز انسان است که ابتدالئورناردو داوينچي(1519-1452) طرحي از يک ماشين پرنده را بر اساس ساختمان بدن خفاش رسم نمود. چهار صد سال بعد کلمان آدر ماشين پرنده اي ساخت که داراي موتور بود وبجاي بال از ملخ استفاده مي کرد. هم اکنون کار روي توسعه سيستم هاي هوشمند با الهام ازطبيعت از زمينه هاي خيلي پرطرفدار هوش مصنوعي است. الگوريتمهاي ژنتيک که با استفادهاز ايده تکاملي دارويني و انتخاب طبيعي مطرح شده، روش بسيار خوبي براي يافتن مسائلبهينه سازيست. ايده تکاملي دارويني بيانگر اين مطلب است که هر نسل نسبت به نسل قبلداراي تکامل است و آنچه در طبيعت رخ مي دهد حاصل ميليون ها سال تکامل نسل به نسل موجوداتي مثل مورچه است. الگوریتم کلونی مورچه ها در شبكه چیست؟ يک مورچه در حال حرکت، مقداري فرومون (در اندازههاي مختلف) از خود بر زمين باقي مي گذارد و بدين ترتيب مسير را بوسيله بوي اين ماده مشخص مي سازد. هنگامي که يک مورچه به طور تصادفي و تنها حرکت مي کند، با مواجه شدن با مسيري که داراي اثر فرومون بيشتري است، به احتمال زياد مسير فوق را انتخاب مي کند و با فروموني که از خود بر جاي مي گذارد، آن را در مسير مذکور تقويت مي نمايد الگوريتم کلوني مورچه الهام گرفته شده از مطالعات ومشاهدات روي کلوني مورچه هاست. اين مطالعات نشان داده که مورچه ها حشراتي اجتماعي هستند که در کلوني ها زندگي مي کنند و رفتار آنها بيشتر در جهت بقاء کلوني است تادرجهت بقاء يک جزء از آن. يکي از مهمترين و جالبترين رفتار مورچه ها، رفتار آنهابراي يافتن غذا است و بويژه چگونگي پيدا کردن کوتاهترين مسير ميان منابع غذايي وآشيانه. اين نوع رفتار مورچه ها داراي نوعي هوشمندي توده اي است که اخيرا مورد توجهدانشمندان قرار گرفته است.بايد تفاوت هوشمندي توده اي(کلوني) و هوشمندي اجتماعي راروشن کنيم. در هوشمندي اجتماعي عناصر ميزاني از هوشمندي را دارا هستند. بعنوان مثال درفرآيند ساخت ساختمان توسط انسان، زماني که به يک کارگر گفته ميشود تا يک توده آجررا جابجا کند، آنقدر هوشمند هست تا بداند براي اينکار بايد از فرغون استفاده کند نهمثلا بيل!!! نکته ديگر تفاوت سطح هوشمندي افراد اين جامعه است. مثلا هوشمندي لازمبراي فرد معمار با يک کارگر ساده متفاوت است. در هوشمندي توده اي عناصر رفتاريتصادفي دارند و بين آن ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غيرمستقيم و با استفاده از نشانه ها با يکديگر در تماس هستند. مثالي در اين مورد رفتارموريانه ها در لانه سازيست. جهت علاقه مند شدن شما به اين رفتار موريانه ها وتفاوتهوشمندي توده اي و اجتماعي توضيحاتي را ارائه مي دهم : فرآيند ساخت لانه توسط موريانهها مورد توجه دانشمندي فرانسوي به نام گرس قرار گرفت. موريانه ها براي ساخت لانه سهفعاليت مشخص از خود بروز مي دهند. در ابتدا صدها موريانه به صورت تصادفي به اين طرفو آن طرف حرکت مي کنند. هر موريانه به محض رسيدن به فضايي که کمي بالاتر از سطحزمين قرار دارد شروع به ترشح بزاق مي کنند و خاک را به بزاق خود آغشته مي کنند. بهاين ترتيب گلوله هاي کوچک خاکي با بزاق خود درست مي کنند. عليرغم خصلت کاملا تصادفياين رفتار، نتيجه تا حدي منظم است. در پايان اين مرحله در منطقه اي محدود تپه هايبسيار کوچک مينياتوري از اين گلوله هاي خاکي آغشته به بزاق شکل مي گيرد. پس از اين،همه تپه هاي مينياتوري باعث مي شوند تا موريانه ها رفتار ديگري از خود بروز دهند. در واقع اين تپه ها به صورت نوعي نشانه براي موريانه ها عمل مي کنند. هر موريانه بهمحض رسيدن به اين تپه ها با انرژي بسيار بالايي شروع به توليد گلوله هاي خاکي بابزاق خود مي کند. اين کار باعث تبديل شدن تپه هاي مينياتوري به نوعي ستون مي شود. اين رفتار ادامه مي يابد تا زماني که ارتفاع هر ستون به حد معيني برسد . در اين صورتموريانه ها رفتار سومي از خود نشان مي دهند. اگر در نزديکي ستون فعلي ستون ديگيرينباشد بلافاصله آن ستون را رها مي کنند در غير اين صورت يعني در حالتي که در نزديکياين ستون تعداد قابل ملاحظه اي ستون ديگر باشد، موريانه ها شروع به وصل کردن ستونهاو ساختن لانه مي کنند. تفاوتهاي هوشمندي اجتماعي انسان با هوشمندي توده ايموريانه را در همين رفتار ساخت لانه مي توان مشاهده کرد. کارگران ساختماني کاملا براساس يک طرح از پيش تعيين شده عمل مي کنند، در حالي که رفتار اوليه موريانه هاکاملا تصادفي است. علاوه بر اين ارتياط مابين کارگران سختماني مستقيم و از طريقکلمات و ... است ولي بين موريانه ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنهابصورت غير مستقيم و از طريق نشانه ها با يکديگر در تماس اند. گرس نام اين رفتار را Stigmergie گذاشت، به معني رفتاري که هماهنگي مابين موجودات را تنهااز طريق تغييرات ايجاد شده در محيط ممکن مي سازد. الگوریتم بهینه سازی کلونی مورچه ها، و یا به اختصار الگوریتم مورچه ها، از رفتار مورچه های طبیعی که در مجموعه ها بزرگ در کنارهم زندگی می کنند الهام گرفته شده است و یکی از الگوریتم های بسیار کارآمد در حل مسائل بهینه سازی ترکیبی است. الگوریتم های دیگری نیز بر اساس الگوریتم مورچه هاساخته شده اند که همگی سیستم های چند عاملی هستند و عامل ها مورچه های مصنوعی یا به اختصار مورچه هایی هستند که مشابه با مورچه های واقعی رفتار می کنند. الگوریتممورچه ها، یک مثال بارز از هوش جمعی هستند که در آن عامل هایی که قابلیت چندانبالایی ندارند، در کنار هم و با همکاری یکدیگر می توانند نتایج بسیار خوبی به دست بیاورند. این الگوریتم برای حل و بررسی محدوده وسیعی از مسائل بهینه سازی به کاربرده شده است. از این میان می توان به حل مسأله کلاسیک فروشنده دوره گرد و همچنینمسأله راهیابی در شبکه های مخابرات راه دور اشاره نمود. مساله فروشنده دورهگرد (Traveling Salesman Problem) و یا به اختصار TSP، يكي از مسائل مشهور بهينهسازي تركيبي است. در این مسأله، يك فروشنده دوره گرد مي خواهد به چند شهر سفر کند وكالاي خود را به فروش برساند. اما می بایست از تمام شهرها عبور کند، از هر شهر فقطيك بار عبور كند و با طی کوتاه ترین مسير، سفر خود را به پایان برساند. حل اینمساله کاربردهای وسیعی در حوزه های مختلف مهندسی دارد. از جمله مسائلی که از نظرریاضی با مسأله TSP معادل هستند، می توان به حل انواع مسایل زمانبندی، مسیریابی،جایابی کالا در انبار، جایابی ماشینها در کارگاه ها، و طراحی مدارات چاپی اشارهنمود. الگوریتم کلونی مورچه برای اولین بار توسط دوریگو (Dorigo) و همکارانش به عنوان یک راه حل چند عامله (Multi Agent) برای مسائل مشکل بهینه سازی مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائه شد. عامل هوشند(Intelligent Agent) موجودی است که از طریق حسگر ها قادر به درک پیرامون خود بوده و از طریق تاثیر گذارنده ها می تواند روی محیط تاثیر بگذارد. الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه ها حشراتی اجتماعی هستند که در کلونی ها زندگی می کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچه ها دارای نوعی هوشمندی توده ای است که اخیرا مورد توجه دانشمندان قرار گرفته است.باید تفاوت هوشمندی توده ای(کلونی) و هوشمندی اجتماعی را روشن کنیم. در هوشمندی اجتماعی عناصر میزانی از هوشمندی را دارا هستند. بعنوان مثال در فرآیند ساخت ساختمان توسط انسان، زمانی که به یک کارگر گفته میشود تا یک توده آجر را جابجا کند، آنقدر هوشمند هست تا بداند برای اینکار باید از فرغون استفاده کند نه مثلا بیل!!! نکته دیگر تفاوت سطح هوشمندی افراد این جامعه است. مثلا هوشمندی لازم برای فرد معمار با یک کارگر ساده متفاوت است. در هوشمندی توده ای عناصر رفتاری تصادفی دارند و بین آن ها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیر مستقیم و با استفاده از نشانه ها با یکدیگر در تماس هستند. مثالی در این مورد رفتار موریانه ها در لانه سازی است. جهت علاقه مند شدن شما به این رفتار موریانه ها وتفاوت هوشمندی توده ای و اجتماعی توضیحاتی را ارائه می دهم : فرآیند ساخت لانه توسط موریانه ها مورد توجه دانشمندی فرانسوی به نام گرس قرار گرفت. موریانه ها برای ساخت لانه سه فعالیت مشخص از خود بروز می دهند. در ابتدا صدها موریانه به صورت تصادفی به این طرف و آن طرف حرکت می کنند. هر موریانه به محض رسیدن به فضایی که کمی بالاتر از سطح زمین قرار دارد شروع به ترشح بزاق می کنند و خاک را به بزاق خود آغشته می کنند. به این ترتیب گلوله های کوچک خاکی با بزاق خود درست می کنند. علیرغم خصلت کاملا تصادفی این رفتار، نتیجه تا حدی منظم است. در پایان این مرحله در منطقه ای محدود تپه های بسیار کوچک مینیاتوری از این گلوله های خاکی آغشته به بزاق شکل می گیرد. پس از این، همه تپه های مینیاتوری باعث می شوند تا موریانه ها رفتار دیگری از خود بروز دهند. در واقع این تپه ها به صورت نوعی نشانه برای موریانه ها عمل می کنند. هر موریانه به محض رسیدن به این تپه ها با انرژی بسیار بالایی شروع به تولید گلوله های خاکی با بزاق خود می کند. این کار باعث تبدیل شدن تپه های مینیاتوری به نوعی ستون می شود. این رفتار ادامه می یابد تا زمانی که ارتفاع هر ستون به حد معینی برسد. در این صورت موریانه ها رفتار سومی از خود نشان می دهند. اگر در نزدیکی ستون فعلی ستون دیگیری نباشد بلافاصله آن ستون را رها می کنند در غیر این صورت یعنی در حالتی که در نزدیکی این ستون تعداد قابل ملاحظه ای ستون دیگر باشد، موریانه ها شروع به وصل کردن ستونها و ساختن لانه می کنند. تفاوتهای هوشمندی اجتماعی انسان با هوشمندی توده ای موریانه را در همین رفتار ساخت لانه می توان مشاهده کرد. کارگران ساختمانی کاملا بر اساس یک طرح از پیش تعیین شده عمل می کنند، در حالی که رفتار اولیه موریانه ها کاملا تصادفی است. علاوه بر این ارتیاط مابین کارگران سختمانی مستقیم و از طریق کلمات و … است ولی بین موریانه ها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیر مستقیم و از طریق نشانه ها با یکدیگر در تماس اند. گرس نام این رفتار را Stigmergie گذاشت، به معنی رفتاری که هماهنگی مابین موجودات را تنها از طریق تغییرات ایجاد شده در محیط ممکن می سازد. بهينه سازي مسائل بروش کلوني مورچه(ACO) : همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يکمسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوانمثال مسئله فروشنده دوره گرد(TSP). در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهايديگربرود و سپس به شهر مبدا بازگردد بطوريکه از هر شهرفقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. اگر تعداد اين شهرها n باشد در حالت کلي اين مسئلهاز مرتبه (n-1)! است که برايفقط 21 شهر زمان واقعا زيادي مي برد: روز1013*7/1 = S1016*433/2 = ms10*1018*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 در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترسقرار مي دهد. الگوريتم کلوني مورچه براي اولين بار توسط دوريگو (Dorigo) و همکارانش به عنوان يک راه حل چند عامله (Multi Agent) براي مسائل مشکل بهينه سازي مثل فروشنده دوره گرد ارائه شد. عامل هوشند(Intelligent Agent) موجودي است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد.. عامل هوشند(Intelligent Agent) موجودي است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد. الگوريتم کلوني مورچه الهام گرفته شده از مطالعات و مشاهدات روي کلوني مورچه هاست. اين مطالعات نشان داده که مورچه ها حشراتي اجتماعي هستند که در کلوني ها زندگي مي کنند و رفتار آنها بيشتر در جهت بقاء کلوني است تا درجهت بقاء يک جزء از آن. يکي از مهمترين و جالبترين رفتار مورچه ها، رفتار آنها براي يافتن غذا است و بويژه چگونگي پيدا کردن کوتاهترين مسير ميان منابع غذايي و آشيانه. اين نوع رفتار مورچه ها داراي نوعي هوشمندي توده اي است که اخيرا مورد توجه دانشمندان قرار گرفته است.بايد تفاوت هوشمندي توده اي(کلوني) و هوشمندي اجتماعي را روشن کنيم.استفاده از الگوریتم‌های ابتکاری در حل مسئله بهینه‌سازی امری ضروری و اجتناب‌ناپذیر است. این روش از توانایی مورچه‌ها در پیدا کردن کوتاه‌ترین مسیر بین لانه و یک منبع غذایی الهام گرفته است. وقتی مورچه‌ها در محیط اطراف حرکت می‌نمایند، اثری شیمیایی به نام فرومون از خود بجای می‌گذارند. وقتی جمعیتی از مورچه‌ها از چند مسیر بین لانه و یک منبع غذایی حرکت می‌کنند، پس از مدت زمان معینی مشاهده می‌شود که در مسیرهای متفاوت، فرومونهای برجای گذاشته شده متفاوت می‌باشد. این امر ناشی از این واقعیت است که مورچه‌هایی که در مسیر کوتاه حرکت می‌کنند، به علت کوتاه‌تر بودن مسیر در یک مدت زمان معین‌تردد بیشتری داشته‌اند چون مورچه‌ها، مسیر کوتاه‌تر را انتخاب کرده‌اند. با استفاده از روش مورچه‌ها، روش جستجوئی پیاده‌سازی می‌شود که در هر مرحله‌ای از اطلاعات مراحل قبلی برای رسیدن به هدف استفاده میگردد. در هوشمندي اجتماعي عناصر ميزاني از هوشمندي را دارا هستند. بعنوان مثال در فرآيند ساخت ساختمان توسط انسان، زماني که به يک کارگر گفته ميشود تا يک توده آجر را جابجا کند، آنقدر هوشمند هست تا بداند براي اينکار بايد از فرغون استفاده کند نه مثلا بيل!!! نکته ديگر تفاوت سطح هوشمندي افراد اين جامعه است. مثلا هوشمندي لازم براي فرد معمار با يک کارگر ساده متفاوت است. در هوشمندي توده اي عناصر رفتاري تصادفي دارند و بين آن ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و با استفاده از نشانه ها با يکديگر در تماس هستند. مثالي در اين مورد رفتار موريانه ها در لانه سازيست. جهت علاقه مند شدن شما به اين رفتار موريانه ها وتفاوت هوشمندي توده اي و اجتماعي توضيحاتي را ارائه مي دهم : فرآيند ساخت لانه توسط موريانه ها مورد توجه دانشمندي فرانسوي به نام گرس قرار گرفت. موريانه ها براي ساخت لانه سه فعاليت مشخص از خود بروز مي دهند. در ابتدا صدها موريانه به صورت تصادفي به اين طرف و آن طرف حرکت مي کنند. هر موريانه به محض رسيدن به فضايي که کمي بالاتر از سطح زمين قرار دارد شروع به ترشح بزاق مي کنند و خاک را به بزاق خود آغشته مي کنند. به اين ترتيب گلوله هاي کوچک خاکي با بزاق خود درست مي کنند. عليرغم خصلت کاملا تصادفي اين رفتار، نتيجه تا حدي منظم است. در پايان اين مرحله در منطقه اي محدود تپه هاي بسيار کوچک مينياتوري از اين گلوله هاي خاکي آغشته به بزاق شکل مي گيرد. پس از اين، همه تپه هاي مينياتوري باعث مي شوند تا موريانه ها رفتار ديگري از خود بروز دهند. در واقع اين تپه ها به صورت نوعي نشانه براي موريانه ها عمل مي کنند. هر موريانه به محض رسيدن به اين تپه ها با انرژي بسيار بالايي شروع به توليد گلوله هاي خاکي با بزاق خود مي کند. اين کار باعث تبديل شدن تپه هاي مينياتوري به نوعي ستون مي شود. اين رفتار ادامه مي يابد تا زماني که ارتفاع هر ستون به حد معيني برسد. در اين صورت موريانه ها رفتار سومي از خود نشان مي دهند. اگر در نزديکي ستون فعلي ستون ديگيري نباشد بلافاصله آن ستون را رها مي کنند در غير اين صورت يعني در حالتي که در نزديکي اين ستون تعداد قابل ملاحظه اي ستون ديگر باشد، موريانه ها شروع به وصل کردن ستونها و ساختن لانه مي کنند.
بهينه سازي مسائل بروش کلوني مورچه(ACO) :
همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يک مسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گرد(TSP). در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهاي ديگربرود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. اگر تعداد اين شهرها n باشد در حالت کلي اين مسئله از مرتبه (n-1)! است که براي فقط 21 شهر زمان واقعا زيادي مي برد:
روز1013*7/1 = S1016*433/2 = ms10*1018*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 به وسیله ی Marco Dorigoدر پایان نامه ی دکترایش معرفی شد،روشی مبتنی بر احتمال برای حل مسائل الگوریتمی که می تواندبرای مسیری در گراف به خوبی مقدار کمینه را ارائه دهد.این روش از رفتار مورچه ها در پیدا کردن مسیری از خانه به سمت غذا ، الهام گرفته شده است. در جهان واقعی مورچه ها{در ابتدا}به صورت تصادفی سرگردان هستند ، و به محض پیدا کردن غذا با به جای گذاشتن ردی از فرمون به سوی کلونی خود باز می گردند. اگر دیگر مورچه ها این ره{علامت گذارده شده با فرمون} را پیدا می کردند،خوشبختانه مجبور نبودندبه جستجوی تصادفی خود ادامه دهند، و در عوض دنبال
کردن رد {فرمون} وبازگشت به خانه{از همان مسیر رفتن}، باعث تقویت رد فرمون میشود و این در صورتی
است که در انتهای مسیر غذایی موجود باشد. در هر صورت ، پس از مدتی رد فرمون شروع به بخار شدن می کند، بدین سان نیروی جذب کننده اش کاهش میابد. زمان زیادی طول می کشد تا یک مورچه مسیر را به طور کامل طی کند ودوباره باز گردد ، پس زمان بیشتری طول می کشد تا فرمون تبخیر شود. یک را ه کوتاه در مقایسه با یک راه طولانی سریعتر پیموده می شود و بنا براین بقایای فرمونکه روی زمین باقی مانده ، به سرعت تبخیر می شود. تبخیر فرمون یک مزیت است چون از همگرایی به راه حل بهینه نسبی پیشگیری می کند. اگر هیچ گاه تبخیری رخ نمی داد،مسیر انتخابی مورچه های اولیه ، همین طور برای مورچه های پیرو خیلی جذب کننده باقی می ماند . در این صورت جستجوی فضای راه حل ها نیاز مند اعمال فشار {دستکاری} از خارج{انسان}است. پس هنگامی که یک مورچه راه خوب(کوتاهی)از کلونی به منبع غذا پیدا کند، دیگر مورچه ها خوشبختانه از آن مسیر پیروی می کنند و باز خورد مثبت{تقویت اثر شیمیایی فرمون}سرانجام همه ی مورچه ها را به پیروی از آن مسیر هدایت می کند. ایده ی الگوریتم کلونی مورچه این رفتار را با "مورچه های شبیه سازی شده"، پیرامون گرافی که مسئله را نمایش می دهد، تقلید می کند تا مسئله را حل کند. الگوریتم بهینه سازی کلونی مورچه برای تولید راه حل های نزدیک به بهینه در مسئله ی "فروشنده دوره گرد"{traveling salesman problem} استفده می شود. این الگوریتم نسبت به genetic algorithm و simulated annealing در حالتی که گراف ممکن است به صورت دینامیک تغییر کند، در روش نزدیک شدن به راه حل بهینه دارای مزیت است. اگوریتم مورچه می تواند بطور پیوسته و اجرا شود و در لحظه{ real time} با تغییرات مطابقت پیدا کند. ین ویژگی باعث شده است که اگوریتم مورچه مورد علاقه ی حل کنندگان مسائل مربوط به مسیر یابی شبکه و یا سیستم های حمل و نقل شهری باشد.

مزيتهايACO : همانطور که گقته شد «تبخير شدن فرومون» و «احتمال-تصادف» به مورچه ها امکان پيدا کردن کوتاهترين مسير را مي دهند. اين دو ويژگي باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازي مي شوند. مثلا در گراف شهرهاي مسئله فروشنده دوره گرد، اگر يکي از يالها (يا گره ها) حذف شود الگوريتم اين توانايي را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا کند. به اين ترتيب که اگر يال (يا گره اي) حذف شود ديگر لازم نيست که الگوريتم از ابتدا مسئله را حل کند بلکه از جايي که مسئله حل شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها مي توانند پس از مدت کوتاهي مسير بهينه(کوتاهترين) را بيابند.
کاربردهاي ACO :
از کاربردهاي ACO مي توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد ، اشاره نمود: 1. مسير يابي داخل شهري و بين شهري 2.مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا 3.مسير يابي شبکه هاي کامپيوتري مسير يابي شبکه هاي کامپيوتري با استفاده از ACO : در ابتدا مقدمه اي از نحوه مسير يابي در شبکه هاي کامپيوتري را توضيح خواهيم داد : اطلاعات بر روي شبکه بصورت بسته هاي اطلاعاتي کوچکي (Packet) منتقل مي شوند. هر يک از اين بسته ها بر روي شبکه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي که مسيرياب (Router) نام دارند عبور مي کنند. در داخل هر مسيرياب جدولي قرار دارد تا بهترين و کوتاهترين مسير بعدي تا مقصد از طريق آن مشخص مي شود، بنابر اين بسته هاي اطلاعاتي حين گذر از مسيرياب ها با توجه به محتويات اين جداول عبور داده مي شوند مسیر یابی شبکه های کامپیوتری با استفاده از ACO اطلاعات بر روی شبکه بصورت بسته های اطلاعاتی کوچکی (Packet) منتقل می شوند. هر یک از این بسته ها بر روی شبکه در طی مسیر از مبدا تا مقصد باید از گره های زیادی که مسیریاب (Router) نام دارند عبور می کنند. در داخل هر مسیریاب جدولی قرار دارد تا بهترین و کوتاهترین مسیر بعدی تا مقصد از طریق آن مشخص می شود، بنابر این بسته های اطلاعاتی حین گذر از مسیریاب ها با توجه به محتویات این جداول عبور داده می شوند. روشی بنام ACR : Ant Colony Routering پیشنهاد شده که بر اساس ایده کلونی مورچه به بهینه سازی جداول می پردازید و در واقع به هر مسیری با توجه به بهینگی آن امتیاز می دهد. استفاده از ACR به این منظور دارای برتری نسبت به سایر روش هاست که با طبیعت دینامیک شبکه سازگاری دارد، زیرا به عنوان مثال ممکن است مسیری پر ترافیک شود یا حتی مسیر یابی (Router) از کار افتاده باشد و بدلیل انعطاف پذیری که ACO در برابر این تغییرات دارد همواره بهترین راه حل بعدی را در دسترس قرار می دهد. روشي بنامACR : Ant Colony Routeringپيشنهاد شده که بر اساس ايده کلوني مورچه به بهينه سازي جداول مي پردازيد و در واقع به هر مسيري با توجه به بهينگي آن امتياز مي دهد. استفاده از ACR به اين منظور داراي برتري نسبت به ساير روش هاست که با طبيعت ديناميک شبکه سازگاري دارد، زيرا به عنوان مثال ممکن است مسيري پر ترافيک شود يا حتي مسير يابي(Router) از کار افتاده باشد و بدليل انعطاف پذيري که ACO در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترس قرار مي دهد. تفاوتهاي هوشمندي اجتماعي انسان با هوشمندي توده اي موريانه را در همين رفتار ساخت لانه مي توان مشاهده کرد. کارگران ساختماني کاملا بر اساس يک طرح از پيش تعيين شده عمل مي کنند، در حالي که رفتار اوليه موريانه ها کاملا تصادفي است. علاوه بر اين ارتياط مابين کارگران ساختماني مستقيم و از طريق کلمات و ... است ولي بين موريانه ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و از طريق نشانه ها با يکديگر در تماس اند. گرس نام اين رفتار را Stigmergie گذاشت، به معني رفتاري که هماهنگي مابين موجودات را تنها از طريق تغييرات ايجاد شده در محيط ممکن مي سازد.

: Refrence

www.prozhe.com
مقاله ارشد سید صابر ناصر ا سدی دانشکده علم وصنعت ایران مقاله ارشد سید صادق ناصر علوی دانشکده شهید باهنر کرمان
http://farhanian.blogsky.com

پروژه کاربرد کلونی مورچگان در شبکه

مطالب مشابه :

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

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

الگوریتم AS از کلونی مورچگان :

فیلم آموزشی جامع الگوریتم مورچگان کلاسیک یا ACO در متلب

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

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

بهینه سازی الگوریتم کلونی مورچه ها

الگوریتم کلونی مورچگان (Ant Colony Algorithm)

پروژه کاربرد کلونی مورچگان در شبکه

الگوریتم ها فرا ابتکاری در متلب