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

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

کلیدواژه ها:

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