X
تبلیغات
ComputerStop - رویکرد کلونی مورچه ها چیست؟

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

 

هوشمندی توده‌ای( Swarm Intelligence) :

AS (Ant System) یا سیستم توده ای مجموعه ای از عامل ها که با یکدیگر بصورت مستقیم ( سیگنال ، علائم و . . . ) یا بصورت غیر مستقیم ( از طریق تأثیر گذاری در محیط ) در تماسند . و از جمله مسائل مهم در مسئله مسیریابی در شبکه های کامپیوتری می باشد .

يك توده(Swarm) عبارت است از مجموعه‌ای از عامل‌ها(موجودات) كه با يكديگر يا به صورت مستقيم (كلمات، سيگنال‌ها، علائم...) يا به صورت غير مستقيم (از طريق تأثيرگذاری در محيط ) در تماس‌اند و همگی يك مسئله را به صورت گسترده حل می‌كنند.

عامل هوشند(Intelligent Agent) موجودي است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد.

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

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

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

1  مساله مورچه ها و رفتار آنها :

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

 

شبيه سازی شی گرای رفتار مورچه ها در پيدا کردن راه کوتاه

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

 

مورچه ها چگونه مي توانند کوتاهترين مسير را پيدا کنند؟

مورچه ها هنگام راه رفتن از خود ردي از ماده شيميايي فرومون(Pheromone) بجاي مي گذارند البته اين ماده بزودي تبخير مي شد ولي در کوتاه مدت بعنوان رد مورچه بر سطح زمين باقي مي ماند. يک رفتار پايه اي ساده در مورچه هاي وجود دارد :

آنها هنگام انتخاب بين دو مسير بصورت احتمالاتي( Statistical) مسيري را انتخاب مي کنند که فرومون بيشتري داشته باشد يا بعبارت ديگر مورچه هاي بيشتري قبلا از آن عبور کرده باشند. حال دقت کنيد که همين يک تمهيد ساده چگونه منجر به پيدا کردن کوتاهترين مسير خواهد شد

همانطور که در شکل 1-1 مي بينيم مورچه هاي روي مسير AB در حرکت اند (در دو جهت مخالف) اگر در مسير مورچه ها مانعي قرار ديهم(شکل 2-1) مورچه ها دو راه براي انتخاب کردن دارند. اولين مورچه ازA مي آيد و بهC مي رسد، در مسير هيچ فروموني نمي بيند بنابر اين براي مسير چپ و راست احتمال يکسان مي دهد و بطور تصادفي و احتمالاتي مسير CED را انتخاب مي کند. اولين مورچه اي که مورچه اول را دنبال مي کند زودتر از مورچه اولي که از مسير CFD رفته به مقصد مي رسد. مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرومون را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا) انتخاب مي کنند. در نهايت مسير CED بعنوان مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED کوتاهتر است زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد چون فرومون بيشتري در آن وجود دارد.
نکه بسيار با اهميت اين است که هر چند احتمال انتخاب مسير پر فرومون ت توسط مورچه ها بيشتر است ولي اين کماکان احتمال است و قطعيت نيست. يعني اگر مسير CED پرفرومون تر از CFD باشد به هيچ عنوان نمي شود نتيجه گرفت که همه مورچه ها از مسيرCED عبور خواهند کرد بلکه تنها مي توان گفت که مثلا 90% مورچه ها از مسير کوتاهتر عبور خواهند کرد. اگر فرض کنيم که بجاي اين احتمال قطعيت وجود مي داشت، يعني هر مورچه فقط و فقط مسير پرفرومون تر را انتخاب ميکرد آنگاه اساسا اين روش ممکن نبود به جواب برسد. اگر تصادفا اولين مورچه مسيرCFD(مسير دورتر) را انتخاب مي کرد و ردي از فرومون بر جاي مي گذاشت آنگاه همه مورچه ها بدنبال او حرکت مي کردند و هيچ وقت کوتاهترين مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در ACO بر عهده دارند.
نکته ديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير AB برداشته شود و فرومون تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرومون و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند.

+ نوشته شده در  چهارشنبه چهارم آذر 1388ساعت 14:20  توسط فرزاد  |