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

لینک دانلود و خرید پایین توضیحات
دسته بندی : وورد
نوع فایل :  word (..doc) ( قابل ويرايش و آماده پرينت )
تعداد صفحه : 12 صفحه

 قسمتی از متن word (..doc) : 
 

‏الگوریتم اجتماع مورچه (Ant Colony Algorithm‏)
‏1- معرفی
‏یکی از مسائلی که به وسیله ی زیست شنا سان مورد مطالعه قرار گرفته است درك این موضوع است که چگونه موجودات تقریبا کور مانند مورچه ها کوتاه ترین مسیر را از لانه ی خود تا منبع غذا و بر عکس پیدا می کنند.آن ها پی بردند که یک رسانه براي ابلاغ اطلاعات بین تک تک مورچه ها مورد استفاده قرار می گیرد و براي تصمیم گیري درمورد این که کدام مسیر را انتخاب کنند به کار می رود که آن رسانه عبارت است از بو(اثر) ماده اي به نام فرومون.
‏ ‏الگوریتم های لانه ی مورچه از جمله روش های فرامکاشفه ای هستند که برای حل مسایل بهینه سازی سخت پیشنهاد شده اند. این الگوریتم ها در آغاز از رفتارهای اجتماعی پشت سرهم قرار گرفتن و تعقیب کردن الهام گرفته شد، که در جامعه ی مورچگان مشاهده گردید. یک اجتماع از عامل های ساده (‏مورچه ها‏) به طور غیر مستقیم از طریق تغییرات پویای (دینامیکی) محیط ارتباط برقرار می کنند (‏رد پاهایی از فرومون‏) و بنابراین بر اساس تجربه ی اجتماعی آن ها، یک راه حل برای یک مسئله ارائه می دهند.
‏در اين مطالعه مدل کاوش مورچه ها Meta-Heurestic‏ انتخاب شده است و درابتدا الگوريتمهای ساده شرح داده می شود و سپس به مطالعه سيستم AS‏ (ant system‏) و سيستمACS ‏(ant colony system‏) وMMAS‏(max-min ant system‏) و….. شرح داده می شود.
‏-2‏- رفتار طبیعی مورچه
‏یک مورچه در حال حرکت مقداري فرومون دراندازه هاي گوناگون از خود بر روي زمین باقی می گذارد و بدین ترتیب مسیر را به وسیله ی بوي این ماده مشخص می سازد. هنگامی که یک مورچه به طور تصادفی  و تنها حرکت می کند با روبه رو شدن با مسیري که توسط مورچه یا مورچه هاي قبلی انتخاب شده و داراي بوي فرومون است به احتمال زیاد آن را  انتخاب می کند و با فرومونی که خود بر جاي می گذارد بوي آن را در مسیر مذکور تقویت می نماید.
‏وقتی رفتار جمعی پدید می آید، گونه ای از رفتار خود تقویتی است، یعنی هرچه مورچه ها بو(اثر) ماده ی مذکور را دنبال کنند آن بو براي مورچه هاي پیرو آنها جذاب تر خواهد بود. فرایند گفته شده به وسیله ی یک حلقه توصیف می شود، یعنی احتمال این که یک مورچه یک مسیر را انتخاب کند متناسب باتعداد مورچه ها یی که قبلا آن مسیر را انتخاب کرده اند افزایش می یابد.
‏ایده این است که اگر در یک نقطه معین یک مورچه مجبور است از بین مسیرهاي مختلف یکی را انتخاب کند ، مسیرهایی را که توسط مورچه هاي قبلی بیش تر انتخاب شده اند، به عبارت دیگر سطح بوی آن ها بالاتر است، با احتمال بیش تري انتخاب خواهد کرد. به علاوه سطح فرمون بالاتر معادل مسیر هاي کوتاه تر خواهد بود.
‏الگوريتم هاي ACO ‏ ‏بر پايه مدل احتمال پارامتري(مدل فرومون) قرار دارند‏.
‏مورچه هاي مصنوعي به طور افزايشي با اضافه کردن به جا و مناسب مولفه هاي راه حل تعريف شده به راه حل جزئي مورد نظر راه حلهايي را مي سازند.
A
B
‏در تصوير بالا ‏مسيرهای متفاوت برای غذايابی ديده می شود.‏و ‏ تعداد مورچه ها و 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
Follow path A;
Breack ;
End
End
-3‏بهينه سازی کلونی مورچه ساده‏(SACO‏) :
‏براي انجام اين کار، مورچه هاي مصنوعي يک گام برداري تصادفي را روي گراف همبند کامل G=(C,L)‏ انجام مي دهند، که راسهاي آن مولفه هاي راه حل C‏ و مجموعهء L‏ ، اتصالات است.اين گراف، گراف ساخت Construction graph‏
‏ نام دارد.
‏ ‏وقتي يک مسئله CO ‏داراي محدوديت را در نظر مي گيريم، محدوديتهاي مسئله در رويه سازندهء مورچه ها ساخته مي شوند به نحوي که در هر مرحله از فرايند ساخت فقط مولفه هايي از راه حل که عملي هستند مي توانند به راه حل جزئي فعلي اضافه شوند. مولفه ‏هاي ci ЄC‏ با پارامتر رديابي فرومون Ti‏ متناظر مي شوند و اتصالات Lij ЄL‏ مي توانند با پارامتر رديابي فرومون Tij‏ متناظر گردند. مجموعهء کل اين پارامترها با T‏ نشان داده مي شود‏.
‏مقادير اين پارامترها ( مقادير فرومون) به ترتيب با ‏ نشان داده مي شوند.
‏به علاوه مولفه ها و اتصالات به ترتيب مي توانند با مقدار اکتشافي ‏ متناظر گردند.
‏مجموعهء همه مقادير را با H‏ نشان مي دهيم. . اين مقادير براي تصميمات احتمالي مورچه ها در مورد چگونگي حرکت در گراف ساخت استفاده مي گردند.‏احتمالات مربوط به گراف ساخت، احتمالات انتقال ناميده مي شود.
‏بعد از مقدار دهي اوليه به مقادير فرومون ، در هر مرحله ، هر مورچه يک راه حل را مي سازد. سپس اين راه حلها براي به روزرساني مقادير فرومون استفاده مي گردند
‏در ابتدا، کليهء مقادير فرومون با يک مقدار کوچک مشابه ph>0‏ مقداردهي مي شوند.‏ در فاز ساخت، يک مورچه با افزودن مولفه هايي به راه حل جزئي فعلي ، به تدريج يک راه حل را ايجاد مي کند.‏اگر هيچ نودی وجود نداشته باشد ‏=0 و در غير اينصورت فرآيند انجام و به ‏می رسد.ودر صورت افتادن در حلقه بايد ان مسير حذف و دوباره عمليات انجام گردد.‏ در مقادير بالا برای ‏ مقدار فرمون را تقويت میکندو دراین حال گره های اصلی بدست آمده وحلقه ها از بين می روند.وبرای فرمون اضافه شده استفاده می گردد.‏