الگوریتم موازی بهینه سازی کلونی مورچگان

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

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

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

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

 40صفحه

ورد

فهرست مطالب

 

پیشگفتار. 5

 

فصل اول. 7

 

1_ بهینه سازی کلونی مورچگان به روش ترتیبی.. 7

 

مقدمه. 7

 

1_ 2انواع مختلف الگوريتم بهينه سازي مورچگان. 9

 

1_3 مزيتهاي ACO.. 10

 

1_5 مسيريابي شبکه هاي کامپيوتري با استفاده از ACO.. 10

 

فصل دوم. 12

 

2 _ بهینه سازی کلونی مورچگان به روش موازی.. 12

 

مقدمه. 12

 

1-2 راهبردهای موازی سازی به طور کلی.. 12

 

2_2 تبادل اطلاعات.. 13

 

3_2 کار مربوط.. 14

 

4_2 بهینه سازی کلونی مورچگان به صورت موازی.. 14

 

5_2 نتایج آزمایشات.. 17

 

1_5_2 مقایسه الگوریتم موازی کلونی مورچگان با الگوریتم ترتیبی کلونی مورچگان. 17

 

2_5_2  نتیجه گیری.. 21

 

فصل سوم. 23

 

3_کاربرد کلونی مورچگان. 23

 

مقدمه. 23

 

1_3 : کاربرد در فروشنده دوره گرد. 23

 

1_1_3  فروشنده دوره گرد. 24

 

الگوريتم كلوني مورچگان. 28

 

الگوريتم ژنتيك.. 30

 

تبادل جواب ها 31

 

2_1_ 3 تحليل حساسيت پارامترها 31

 

3_1_ 3  تجزيه وتحليل نتايج. 33

 

2_3  کاربرد  در ANTNET. 36

 

1_2_3 الگوريتم مسيريابي مبتني بر لانه مورچه Antnet. 36

 

مراجع. 40