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

دسته بندي : دانش آموزی و دانشجویی » دانلود تحقیق
لینک دانلود و خرید پایین توضیحات
دسته بندی : وورد
نوع فایل :  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 و در غير اينصورت فرآيند انجام و به ‏می رسد.ودر صورت افتادن در حلقه بايد ان مسير حذف و دوباره عمليات انجام گردد.‏ در مقادير بالا برای ‏ مقدار فرمون را تقويت میکندو دراین حال گره های اصلی بدست آمده وحلقه ها از بين می روند.وبرای فرمون اضافه شده استفاده می گردد.‏