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

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

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

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

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

مساله فروشنده دورهگرد (Traveling Salesman Problem) و یا به اختصار TSP، يكي از مسائل مشهور بهينهسازي تركيبي است. در این مسأله، يك فروشنده دوره گرد مي خواهد به چند شهر سفر کند وكالاي خود را به فروش برساند. اما می بایست از تمام شهرها عبور کند، از هر شهر فقطيك بار عبور كند و با طی کوتاه ترین مسير، سفر خود را به پایان برساند. حل اینمساله کاربردهای وسیعی در حوزه های مختلف مهندسی دارد. از جمله مسائلی که از نظرریاضی با مسأله TSP معادل هستند، می توان به حل انواع مسایل زمانبندی، مسیریابی،جایابی کالا در انبار، جایابی ماشینها در کارگاه ها، و طراحی مدارات چاپی اشارهنمود.

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

روز10137/1 = S1016433/2 = ms101018433/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) موجودي است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد.
الگوريتم کلوني مورچه الهام گرفته شده از مطالعات و مشاهدات روي کلوني مورچه هاست. اين مطالعات نشان داده که مورچه ها حشراتي اجتماعي هستند که در کلوني ها زندگي مي کنند و رفتار آنها بيشتر در جهت بقاء کلوني است تا درجهت بقاء يک جزء از آن. يکي از مهمترين و جالبترين رفتار مورچه ها، رفتار آنها براي يافتن غذا است و بويژه چگونگي پيدا کردن کوتاهترين مسير ميان منابع غذايي و آشيانه. اين نوع رفتار مورچه ها داراي نوعي هوشمندي توده اي است که اخيرا مورد توجه دانشمندان قرار گرفته است.بايد تفاوت هوشمندي توده اي(کلوني) و هوشمندي اجتماعي را روشن کنيم.

در هوشمندي اجتماعي عناصر ميزاني از هوشمندي را دارا هستند.

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

عليرغم خصلت کاملا تصادفي اين رفتار، نتيجه تا حدي منظم است.

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

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

مطالب مشابه :

دانلود پایان نامه رنگ آمیزی گراف با الگوریتم ژنتیک

رنگ آمیزی گراف با الگوریتم گراف با الگوریتم ژنتیک. رنگ آمیزی گراف ان

الگوریتم رنگ آمیزی آزمند

معمولا الگوریتم رنگ آمیزی آزمند دارد که گراف را با کمتر از k رنگ، رنگ الگوریتم ژنتیک.

كاربرد گراف دررياضي گسسته

نظریه رنگ آمیزی یالی توسط گراف علم ژنتیک است که توسط گراف به الگوریتم با یک

کاربردهای گراف

، n با این قاعده رنگ نظریه رنگ آمیزی یالی توسط گراف گراف در علم ژنتیک

مقالات شبیه سازی شده رشته برق در متلب MATLAB

خوشه بندی با الگوریتم ژنتیک سال ارائه: پروژه پردازش تکاملی بر روی مسئله رنگ امیزی گراف

پروژه ها و مقالات شبیه سازی شده در متلب- پردازش سیگنال و هوش مصنوعی

درونیابی طرح رنگ با استفاده از با الگوریتم ژنتیک. بر روی مسئله رنگ امیزی گراف.

نتایج داوری مقالات

بهبود کارایی الگوریتم ژنتیک با بندی گراف وظایف ژنتیک در رنگ آمیزی گراف.