+ الگوریتم بهینه سازی کلونی مورچه ها 1 و مقالات لاتین آن

هر روز با پیشرفت علوم ، رشته تحقیق در عملیات نیز پیشرفت نموده و تکنیکهای جدیدی ارائه می گردد. اینبار قصد داریم شما را با تکنیک کلونی مورچه ( Ant Colony ) آشنا نمائیم. این تکنیک در دو بخش تقدیم خواهد شد. در ادامه مطلب بعد از مطالعه تئوری کلی می توانید مقالات لاتین مربوط به  این تکنیک را دانلود نمائید. نظرات شما می تواند ما را در ارائه بهتر تکنیکهای جدید تحقیق در عملیات یاری نماید...


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

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

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

 

 

 

 

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

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


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


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

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

 

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

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

 


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

حال مقالات لاتین مربوط به این تکنیک را از اینجا دانلود کنید.

 

نویسنده : محسن محمدلو ; ساعت ۱٠:٥٠ ‎ب.ظ ; شنبه ۳٠ دی ،۱۳٩۱
comment نظرات () لینک