تبلیغات
پایگاه مجازی برق الکترونیک - حل مسائل بهینه سازی با الگوریتم کولونی مورچگان
1392/05/30  12:24    ویرایش: 1392/05/30 12:28
 
نوع مطلب: مقالات آموزشی ،
 

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

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

الگوریتم کلونی مورچه برای اولین بار توسط دوریگو (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 برداشته شود و فرومون تبخیر نشود مورچه ها همان مسیر قبلی را طی خواهند کرد. ولی در حقیقت این طور نیست. تبخیر شدن فرومون و احتمال به مورچه ها امکان پیدا کردن مسیر کوتاهتر جدید را می دهند.

1-1

 

2-1

 

3-1

 

4-1

مزیتهای ACO :

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

کاربردهای ACO :

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

1. مسیر یابی داخل شهری و بین شهری
2. مسیر یابی بین پست های شبکه های توزیع برق ولتاژ بالا

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

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

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

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

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

   


نظرات()  
کدباکس
1393/09/17 21:11
دم شما گرم. خسته نباشید با سایت خوبتون
فنی مهندسی رامتین
1393/04/10 15:01
با سلام لطفا از سایت ما دیدن فرمایید و با گذاشتن لینک ما در صفحه خود از لینک شدن خود در سایت اصلی شرکت مطمئن شوید
با تشکر
www.automat.ir
www.automat.mihanblog.com
فریال
1393/01/24 23:25
بسیار ممنون واقعا استفاده کردم
srv
1392/12/12 10:58
با سلام خدمت شما
سایت خیلی خوب و پر محتوایی دارید.اگر مایل به تبادل لینک هستید به سایت ما سری بزنید و به ما خبر دهید.باعث افتخار ماست بتوانیم سایت های هم موضوع خود را لینک کنیم و حامی و مبلغ انها باشیم.
با تشکرsrv
======================
www.robotic-technology.ir
======================
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر

پایگاه مجازی برق الکترونیک