کد آماده کلوني مورچه ها - WEBSITE X5 UNREGISTERED VERSION - Matlab Pajooh

Go to content

Main menu:

بخش ويژه
 (Ant Colony Optimisation) الگوريتم كلوني مورچه ها

انسان هميشه براي الهام گرفتن به جهان زنده پيرامون خود نگريسته است. يكي از بهترين طرح هاي شناخته شده، طرح پرواز انسان است كه ابتدا لئورناردو داوينچي(1519-1452) طرحي از يك ماشين پرنده را بر اساس ساختمان بدن خفاش رسم نمود. چهار صد سال بعد كلمان آدر ماشين پرنده اي ساخت كه داراي موتور بود و بجاي بال از ملخ استفاده مي كرد.
هم اكنون كار روي توسعه سيستم هاي هوشمند با الهام از طبيعت از زمينه هاي خيلي پرطرفدار هوش مصنوعي است. الگوريتمهاي ?نتيككه با استفاده از ايده تكاملي دارويني و انتخاب طبيعي مطرح شده، روش بسيار خوبي براي يافتن مسائل بهينه سازيست. ايده تكاملي دارويني بيانگر اين مطلب است كه هر نسل نسبت به نسل قبل داراي تكامل است و آنچه در طبيعت رخ مي دهد حاصل ميليون ها سال تكامل نسل به نسل موجوداتي مثل مورچه است
الگوريتم كلوني مورچه براي اولين بار توسط دوريگو  و همكارانش به عنوان يك راه حل چند عامله براي مسائل مشكل بهينه سازي مثل فروشنده دوره گرد ارائه شد.
 
عامل هوشند موجودي است كه از طريق حسگر ها قادر به درك پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد.الگوريتم كلوني مورچه الهام گرفته شده از مطالعات و مشاهدات روي كلوني مورچه هاست. اين مطالعات نشان داده كه مورچه ها حشراتي اجتماعي هستند كه در كلوني ها زندگي مي كنند و رفتار آنها بيشتر در جهت بقاء كلوني است تا درجهت بقاء يك جزء از آن. يكي از مهمترين و جالبترين رفتار مورچه ها، رفتار آنها براي يافتن غذا است و بويژه چگونگي پيدا كردن كوتاهترين مسير ميان منابع غذايي و آشيانه. اين نوع رفتار مورچه ها داراي نوعي هوشمندي توده اي است كه اخيرا مورد توجه دانشمندان قرار گرفته است.بايد تفاوت هوشمندي توده اي(كلوني) و هوشمندي اجتماعي را روشن كنيم.در هوشمندي اجتماعي عناصر ميزاني از هوشمندي را دارا هستند. بعنوان مثال در فرآيند ساخت ساختمان توسط انسان، زماني كه به يككارگر گفته ميشود تا يك توده آجر را جابجا كند، آنقدر هوشمند هست تا بداند براي اينكار بايد از فرغون استفاده كند نه مثلا بيل!!! نكته ديگر تفاوت سطح هوشمندي افراد اين جامعه است. مثلا هوشمندي لازم براي فرد معمار با يك كارگر ساده متفاوت است.در هوشمندي توده اي عناصر رفتاري تصادفي دارند و بين آن ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و با استفاده از نشانه ها با يكديگر در تماس هستند. مثالي در اين مورد رفتار موريانه ها در لانه سازيست.جهت علاقه مند شدن شما به اين رفتار موريانه ها وتفاوت هوشمندي توده اي و اجتماعي توضيحاتي را ارائه مي دهم :فرآيند ساخت لانه توسط موريانه ها مورد توجه دانشمندي فرانسوي به نام گرس قرار گرفت. موريانه ها براي ساخت لانه سه فعاليت مشخص از خود بروز مي دهند. در ابتدا صدها موريانه به صورت تصادفي به اين طرف و آن طرف حركت مي كنند. هر موريانه به محض رسيدن به فضايي كه كمي بالاتر از سطح زمين قرار دارد شروع به ترشح بزاق مي كنند و خاك را به بزاق خود آغشته مي كنند. به اين ترتيب گلوله هاي كوچك خاكي با بزاق خود درست مي كنند. عليرغم خصلت كاملا تصادفي اين رفتار، نتيجه تا حدي منظم است. در پايان اين مرحله در منطقه اي محدود تپه هاي بسيار كوچك مينياتوري از اين گلوله هاي خاكي آغشته به بزاق شكل مي گيرد. پس از اين، همه تپه هاي مينياتوري باعث مي شوند تا موريانه ها رفتار ديگري از خود بروز دهند. در واقع اين تپه ها به صورت نوعي نشانه براي موريانه ها عمل مي كنند. هر موريانه به محض رسيدن به اين تپه ها با انرژي بسيار بالايي شروع به توليد گلوله هاي خاكي با بزاق خود مي كند. اين كار باعث تبديل شدن تپه هاي مينياتوري به نوعي ستون مي شود. اين رفتار ادامه مي يابد تا زماني كه ارتفاع هر ستون به حد معيني برسد. در اين صورت موريانه ها رفتار سومي از خود نشان مي دهند. اگر در نزديكي ستون فعلي ستون ديگيري نباشد بلافاصله آن ستون را رها مي كنند در غير اين صورت يعني در حالتي كه در نزديكي اين ستون تعداد قابل ملاحظه اي ستون ديگر باشد، موريانه ها شروع به وصل كردن ستونها و ساختن لانه مي كنند.تفاوتهاي هوشمندي اجتماعي انسان با هوشمندي توده اي موريانه را در همين رفتار ساخت لانه مي توان مشاهده كرد. كارگران ساختماني كاملا بر اساس يك طرح از پيش تعيين شده عمل مي كنند، در حاليكه رفتار اوليه موريانه ها كاملا تصادفي است. علاوه بر اين ارتياط مابين كارگران سختماني مستقيم و از طريق كلمات و ... است ولي بين موريانه ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و از طريق نشانه ها با يكديگر در تماس اند. گرس نام اين رفتار را
  Stigmergie
گذاشت، به معني رفتاري كه هماهنگي مابين موجودات را تنها از طريق تغييرات ايجاد شده در محيط ممكن مي سازد.
 
 
بهينه سازي مسائل بروش كلوني مورچه
همانطور كه مي دانيم مسئله يافتن كوتاهترين مسير، يك مسئله بهينه سازيست كه گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گرد. در اين مسئله فروشنده دوره گرد بايد از يك شهر شروع كرده، به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريكه از هر شهر فقط يكبار عبور كند و كوتاهترين مسير را نيز طي كرده باشد. اگر تعداد اين شهرها
n
باشد در حالت كلي اين مسئله از مرتبه (
n-1
)! است كه براي فقط 21 شهر زمان واقعا زيادي مي برد:روز1013*7/1 =
S1016*433/2 = ms10*1018*433/2 = !20
با انجام يك الگوريتم برنامه سازي پويا براي اين مسئله ، زمان از مرتبه نمايي بدست مي آيد كه آن هم مناسب نيست. البته الگوريتم هاي ديگري نيز ارائه شده ولي هيچ كدام كارايي مناسبي ندارند. الگوريتم كلوني مورچه ها، الگوريتم كامل و مناسبي براي حل مسئله فروشنده دوره گرد است.
مورچه ها چگونه مي توانند كوتاهترين مسير را پيدا كنند؟
مورچه ها هنگام راه رفتن از خود ردي از ماده شيميايي فرومون  بجاي مي گذارند البته اين ماده بزودي تبخير مي شد ولي در كوتاه مدت بعنوان رد مورچه بر سطح زمين باقي مي ماند. يك رفتار پايه اي ساده در مورچه هاي وجود دارد :آنها هنگام انتخاب بين دو مسير بصورت احتمالاتي(
Statistical
) مسيري را انتخاب مي كنند كه فرومون بيشتري داشته باشد يا بعبارت ديگر مورچه هاي بيشتري قبلا از آن عبور كرده باشند. حال دقت كنيد كه همين يك تمهيد ساده چگونه منجر به پيدا كردن كوتاهترين مسير خواهد شد :همانطور كه در شكل 1-1 مي بينيم مورچه هاي روي مسير
AB
در حركت اند (در دو جهت مخالف) اگر در مسير مورچه ها مانعي قرار ديهم(شكل 2-1) مورچه ها دو راه براي انتخاب كردن دارند. اولين مورچه از
A
مي آيد و به
C
مي رسد، در مسير هيچ فروموني نمي بيند بنابر اين براي مسير چپ و راست احتمال يكسان مي دهد و بطور تصادفي و احتمالاتي مسير
CED
را انتخاب مي كند. اولين مورچه اي كه مورچه اول را دنبال مي كند زودتر از مورچه اولي كه از مسير
CFD
رفته به مقصد مي رسد. مورچه ها در حال برگشت و به مرور زمان يك اثر بيشتر فرومون را روي
CED
حس مي كنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا) انتخاب مي كنند. در نهايت مسير
CED
بعنوان مسير كوتاهتر برگزيده مي شود. در حقيقت چون طول مسير
CED
كوتاهتر است زمان رفت و برگشت از آن هم كمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند كرد چون فرومون بيشتري در آن وجود دارد.نكه بسيار با اهميت اين است كه هر چند احتمال انتخاب مسير پر فرومون ت توسط مورچه ها بيشتر است ولي اينكماكان احتمال است و قطعيت نيست. يعني اگر مسير
CED
پرفرومون تر از
CFD
باشد به هيچ عنوان نمي شود نتيجه گرفت كه همه مورچه ها از مسير
CED
عبور خواهند كرد بلكه تنها مي توان گفت كه مثلا 90% مورچه ها از مسير كوتاهتر عبور خواهند كرد. اگر فرض كنيم كه بجاي اين احتمال قطعيت وجود مي داشت، يعني هر مورچه فقط و فقط مسير پرفرومون تر را انتخاب ميكرد آنگاه اساسا اين روش ممكن نبود به جواب برسد. اگر تصادفا اولين مورچه مسير
CFD
(مسير دورتر) را انتخاب مي كرد و ردي از فرومون بر جاي مي گذاشت آنگاه همه مورچه ها بدنبال او حركت مي كردند و هيچ وقت كوتاهترين مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در
ACO
بر عهده دارند.نكته ديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير
AB
برداشته شود و فرومون تبخير نشود مورچه ها همان مسير قبلي را طي خواهند كرد. ولي در حقيقت اين طور نيست. تبخير شدن فرومون و احتمال به مورچه ها امكان پيدا كردن مسير كوتاهتر جديد را مي دهند.

 
ACOمزيتهاي
 
همانطور كه گقته شد «تبخير شدن فرومون» و «احتمال-تصادف» به مورچه ها امكان پيدا كردن كوتاهترين مسير را مي دهند. اين دو وي?گي باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازي مي شوند. مثلا در گراف شهرهاي مسئله فروشنده دوره گرد، اگر يكي از يالها (يا گره ها) حذف شود الگوريتم اين توانايي را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا كند. به اين ترتيب كه اگر يال (يا گره اي) حذف شود ديگر لازم نيست كه الگوريتم از ابتدا مسئله را حل كند بلكه از جايي كه مسئله حل شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها مي توانند پس از مدت كوتاهي مسير بهينه(كوتاهترين) را بيابند
 
 
ACOكاربردهاي
 
ACOاز كاربردهاي
:مي توان به بهينه كردن هر مسئله اي كه نياز به يافتن كوتاهترين مسير دارد ، اشاره نمود
 
 مسير يابي داخل شهري و بين شهري
 مسير يابي بين پست هاي شبكه هاي توزيع برق ولتاژ بالا
 مسير يابي شبكه هاي كامپيوتري
 
 
 
ACOمسير يابي شبكه هاي كامپيوتري با استفاده از
:در ابتدا مقدمه اي از نحوه مسير يابي در شبكه هاي كامپيوتري را توضيح خواهيم داد
 
اطلاعات بر روي شبكه بصورت بسته هاي اطلاعاتي كوچكي (
Packet
) منتقل مي شوند. هر يك از اين بسته ها بر روي شبكه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي كه مسيرياب (
Router
) نام دارند عبور مي كنند. در داخل هر مسيرياب جدولي قرار دارد تا بهترين و كوتاهترين مسير بعدي تا مقصد از طريق آن مشخص مي شود، بنابر اين بسته هاي اطلاعاتي حين گذر از مسيرياب ها با توجه به محتويات اين جداول عبور داده مي شوند.
 
روشي بنام
ACR : Ant Colony Routering
پيشنهاد شده كه بر اساس ايده كلوني مورچه به بهينه سازي جداول مي پردازيد و در واقع به هر مسيري با توجه به بهينگي آن امتياز مي دهد. استفاده از
ACR
به اين منظور داراي برتري نسبت به ساير روش هاست كه با طبيعت ديناميك شبكه سازگاري دارد، زيرا به عنوان مثال ممكن است مسيري پر ترافيك شود يا حتي مسير يابي (
Router
) از كار افتاده باشد و بدليل انعطاف پذيري كه
ACO
در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترس قرار مي دهد.
 
 
Back to content | Back to main menu