تحقیق در مورد الگوریتم اجتماع مورچه

لینک دانلود و خرید پایین توضیحات

دسته بندی : وورد

نوع فایل :  .doc ( قابل ویرایش و آماده پرینت )

تعداد صفحه : 12 صفحه

 قسمتی از متن .doc : 

الگوریتم اجتماع مورچه (Ant Colony Algorithm)

1- معرفی

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

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

در این مطالعه مدل کاوش مورچه ها Meta-Heurestic انتخاب شده است و درابتدا الگوریتمهای ساده شرح داده می شود و سپس به مطالعه سیستم AS (ant system) و سیستمACS (ant colony system) وMMAS(max-min ant system) و..... شرح داده می شود.

-2- رفتار طبیعی مورچه

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

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

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

الگوریتم های ACO بر پایه مدل احتمال پارامتری(مدل فرومون) قرار دارند.

مورچه های مصنوعی به طور افزایشی با اضافه کردن به جا و مناسب مولفه های راه حل تعریف شده به راه حل جزئی مورد نظر راه حلهایی را می سازند.

در تصویر بالا مسیرهای متفاوت برای غذایابی دیده می شود.و تعداد مورچه ها و A و B مسیرهای در زمان t جستجو برای یافتن مسیر آغاز و در زمان t+1 مسیر پیدا شده و فرمول مورد استفاده :

C کمیتی غیر اکتشافی برای مقدار جذب فرمون است و تحت تاثیر فرمون ذخیره شده در فرآیند است.و باتعداد مورچه ها نسبت مستقیم دارد.در اثر تجربه مقدار برای =2 و c=20 است. اگر پس مسیر A بهتر از B است.

اگر دو مسیر یکسان باشند مسیر بصورت تصادفی و تعداد مورچه ها یکسان باشد در بیشتر موارد مسیر کوتاهتر بعد از مدتی پیدا می شودو مقدار فرمون مسیر کوتاهتر بیشتر از مسیر دیگر است.

و شاخه قویتر مورد استفاده قرار میگیرد.الگوریتم زیر برای ایجاد مسیر کوتاهتر است:

Let r~U(0,1)

For each potential path A do

Calculate Pa using ,e.g.,equation (1.1)

If r<=Pa then

Follow path A;

Breack ;

End

End

-3بهینه سازی کلونی مورچه ساده(SACO) :

برای انجام این کار، مورچه های مصنوعی یک گام برداری تصادفی را روی گراف همبند کامل G=(C,L) انجام می دهند، که راسهای آن مولفه های راه حل C و مجموعهء L ، اتصالات است.این گراف، گراف ساخت نام دارد.

وقتی یک مسئله CO دارای محدودیت را در نظر می گیریم، محدودیتهای مسئله در رویه سازندهء مورچه ها ساخته می شوند به نحوی که در هر مرحله از فرایند ساخت فقط مولفه هایی از راه حل که عملی هستند می توانند به راه حل جزئی فعلی اضافه شوند. مولفههای ci ЄC با پارامتر ردیابی فرومون Ti متناظر می شوند و اتصالات Lij ЄL می توانند با پارامتر ردیابی فرومون Tij متناظر گردند. مجموعهء کل این پارامترها با T نشان داده میشود.

مقادیر این پارامترها ( مقادیر فرومون) به ترتیب با نشان داده می شوند.

به علاوه مولفه ها و اتصالات به ترتیب می توانند با مقدار اکتشافی متناظر گردند.

مجموعهء همه مقادیر را با H نشان می دهیم. . این مقادیر برای تصمیمات احتمالی مورچه ها در مورد چگونگی حرکت در گراف ساخت استفاده می گردند.احتمالات مربوط به گراف ساخت، احتمالات انتقال نامیده می شود.

بعد از مقدار دهی اولیه به مقادیر فرومون ، در هر مرحله ، هر مورچه یک راه حل را می سازد. سپس این راه حلها برای به روزرسانی مقادیر فرومون استفاده می گردند

در ابتدا، کلیهء مقادیر فرومون با یک مقدار کوچک مشابه ph>0 مقداردهی می شوند. در فاز ساخت، یک مورچه با افزودن مولفه هایی به راه حل جزئی فعلی ، به تدریج یک راه حل را ایجاد می کند.اگر هیچ نودی وجود نداشته باشد =0 و در غیر اینصورت فرآیند انجام و به می رسد.ودر صورت افتادن در حلقه باید ان مسیر حذف و دوباره عملیات انجام گردد. در مقادیر بالا برای مقدار فرمون را تقویت میکندو دراین حال گره های اصلی بدست آمده وحلقه ها از بین می روند.وبرای فرمون اضافه شده استفاده می گردد.