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

الگوریتم بهینه سازی رقابت استعماری مانند بسیاری دیگر از الگوریتمهای فرا ابتکاری مبتنی بر جمعیت اولیه، ذاتاً موازیاست ومیتواند به طور کارآمدی بر روی واحدهای پردازش گرافیکی پیاده سازی شود. اخیرا پردازنده های گرافیکی به علت هزینه هایپایین، معماری موازی و بهبود دسترسی فراهم شده به وسیله محیط های برنامه نویسی مانند چارچوب کودا به عنوان یک دستگاهمحاسباتی همه منظوره مطرح شده اند. یکی از الگوهای موازی سازی الگوریتم های بهینه سازی الگوی ارباب - بنده می باشد. در این مقاله، موازی سازی الگوریتم رقابت استعماری روی واحدهای پردازش گرافیکی با استفاده از معماری دستگاه یکپارچهی محاسباتی و مبتنیبر الگوی ارباب- بنده، با تکنیک ریزدانه انجام شده است. توابع برازندگی (محاسبه هزینه)، همگون سازی(جذب) ، انقلاب و رقابت ازالگوریتم رقابت استعماری بر روی واحدهای پردازش گرافیکی پیاده سازی می شوند. در الگوریتم پیشنهادی علاوه بر توابع نام برده، از ایده ی عملیات prefix sum برای افزایش کارایی به الگوریتم استفاده گردیده است. برای افزایش کارایی الگوریتم موازی از حافظه ی اشتراکی، عملیات کاهش و عوامل دیگر تأثیر گذار استفاده شده است.کارایی الگوریتم پیشنهاد شده در این مقاله با مطالعه موردی برروی مقایسه ی زمان اجرای مساله فروشنده دوره گرد نشان داده شده است. نتایج آزمایشها افزایش بهره ی سرعت الگوریتم موازینسبت به سری را گزارش می دهند.

Keywords:

الگوریتم بهینه سازی رقابت استعماری (COA) , محاسبات موازی , واحدهای پردازش گرافیکی (GPU) , معماری دستگاه یکپارچه ی محاسباتی (CUDA) , مدل ارباب- بنده