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