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

الگوریتم جستجوی گرانشی(GSA)از سری الگوریتم های بهینه یابی است که با الهام از قانون جاذبه و نیرو نیوتون شکل یافته است. الگوریتم جستجوی گرانشی کارایی قابل قبولی در حل مسائل بهینه سازی دارد؛ اما زمان اجرای طولانی مرتبط با آن، به دلیل محاسبات زیاد، از استفاده از آن در بسیاری از حوزه ها جلوگیری می نماید. در این مقاله، روش جدیدی برای پیاده سازی موازی الگوریتم جستجوی گرانشی در واحد پردازش گرافیکی(GPU) با استفاده از مدل برنامه نویسی CUDA ارائه شده است. توجه این نکته که بسیاری از محاسبات مربوط به این الگوریتم به یکدیگر وابسته نمی باشند، پیاده سازی آن به صورت موازی تاثیر چشم گیری در سرعت اجرای آن دارد. در این روش گام هایی از الگوریتم که محاسبات مربوط به هر عامل را انجام می دهند به صورت موازی پیاده سازی شده اند و علاوه بر آن ها گام مربوط به یافتن بهترین و بدترین برازندگی در بین عامل های موجود و همچنین جمع کردن جرم عامل ها به صورت موازی انجام می گیرد. مقایسه نتایج حاصل از پیاده سازی روش پیشنهادی با روش ترتیبی بر روی چند تابع استاندارد نشان می دهد که زمان اجرا برای مسائلی با تعداد عامل های 1024،512، 256 به طور متوسط 36،40،44 برابر تسریع می شود.