X
تبلیغات
........................... - چگونه مورچه ها مسیر خود را پیدا می کنند؟؟

...........................

...............

چگونه مورچه ها مسیر خود را پیدا می کنند؟؟

الگوریتم مورچه برای اولین بار توسط دوریگو (Dorigo) و همکارانش به عنوان یک راه حل چند عامله برای مسائل مشکل بهینه سازی مثل فروشنده دوره گرد ارائه شد.

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

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

در دنیای واقعی مورچه‌ ها ابتدا به طور تصادفی به این سو و آن سو می‌روند تا غذا بیابند. سپس به لانه بر می‌گردند و ردّی از فرومون (Pheromone) به جا می گذارند. چنین ردهایی پس از باران به رنگ سفید در می‌آیند و قابل رویت اند. مورچه‌های دیگر وقتی این مسیر را می‌یابند، گاه پرسه زدن را رها کرده و آن را دنبال می‌کنند. سپس اگر به غذا برسند به خانه بر می‌گردند و رد دیگری از خود در کنار رد قبل می گذارند؛ و به عبارتی مسیر قبل را تقویت می‌کنند. فرومون به مرور تبخیر می‌شود که از سه جهت مفید است:

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

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

- سیستم مورچه نخبگان : در این روش بهترین راه حل کلی در هر تکرار فرمون آزاد میکند .همچنین این روش برای تمام مورچه های مصنوعی باید انجام شود.

- سیستم مورچه ماکسیمم – مینیمم : یک مقدار کمینه و بیشینه برای فرمون تعیین کرده و فقط در هر مرحله بهترین جواب این مقدار را آزاد میکند و تمام گره های مجاور ان به مقدار فرمون بیشینه به مقدار دهی اولیه میشوند.

 -سیستم کلونی مورچه : که قبلا در به آن پرداخته شد.

-سیستم مورچه بر اساس رتبه : تمام راه حل های بدست آمده بر اساس طول جواب رتبه بندی میشوند و بر اساس همین رتبه بندی مقدار فرمون آزاد سازی شده توسط آنها مشخص خواهد شد و راه حل با طول کمتر از راه حل دیگر با طول بیشتر مقدار فرمون بیشتری آزاد میکند .

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

+ نوشته شده در  شنبه بیست و دوم مهر 1391ساعت 15:16  توسط ساناز  |