ارائه و ارزیابی یک چارچوب برای پیاده سازی موازی الگوریتم های ژنتیک به کمک واحد پردازش گرافیکی

سال انتشار: 1394
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 1,492

فایل این مقاله در 6 صفحه با فرمت PDF قابل دریافت می باشد

این مقاله در بخشهای موضوعی زیر دسته بندی شده است:

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

ICIKT07_149

تاریخ نمایه سازی: 22 مهر 1394

چکیده مقاله:

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

نویسندگان

میلاد رفیعی

دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران

مهدی عباسی

دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران

محمد نصیری

دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران

احسان شکوهمند

واحد بین الملل، دانشگاه شیراز، شیراز، ایران

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • National Traveling Salesman Problems, _ Online, March 201 5, Available ...
  • F. Ahmadizar, K. Soltanian, F. Akhlagh ianTab, and I. Tsoulos, ...
  • Intelligence, vol. 39, pp. 1-13, 2015. ...
  • C. N. Giap and D. T. Ha, "Parallel genetic algorithm ...
  • NVIDIA. NVIDIA CUDA Compute Unified Device Architecture Programming Guide, version ...
  • S. Cavuoti, M. Garofalo, M. Brescia, G. Longo, and G. ...
  • J. Jaros, "Multi-GPU island-based genetic algorithm for solving the knapsack ...
  • K. Wang and Z. Shen, "A GPU-based parallel genetic Transportation ...
  • F. Pinel, B. Dorronsoro, and P. Bouvry, "Solving very large ...
  • D. M. Chitty, "Fast parallel genetic programming: multi-core CPU versus ...
  • C. M. Yip and A. Asaduzzaman, "A promising CUDA- accelerated ...
  • S. Hougardy and _ Wilde" , On the nearest neighbor ...
  • C. Groba, A. Sartal, and X. H. Vazquez, "Solving the ...
  • نمایش کامل مراجع