ارائه و ارزیابی یک چارچوب برای پیاده سازی موازی الگوریتم های ژنتیک به کمک واحد پردازش گرافیکی
محل انتشار: هفتمین کنفرانس بین المللی فناوری اطلاعات و دانش
سال انتشار: 1394
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 1,492
فایل این مقاله در 6 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
این مقاله در بخشهای موضوعی زیر دسته بندی شده است:
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ICIKT07_149
تاریخ نمایه سازی: 22 مهر 1394
چکیده مقاله:
الگوریتم ژنتیک نوعی از الگوریتم های تکاملی قدرتمند و موثر در حل مسائل بهینه سازی و جستجو است که اجرای آن به علت حجم بالای محاسبات بسیار زمان بر می باشد. با افزایش اندازه پارامترهای مختلف این الگوریتم از جمله جمعیت اولیه، تعداد کروموزوم های شرکت کننده در عمل پیوند و جهش و نیز تعداد نسل، زمان اجرای الگوریتم ژنتیک افزایش می یابد. بنابراین، موازی سازی بخشی از محاسبات الگوریتم ژنتیک می تواند زمان اجرای آن را به طور قابل توجهی کاهش دهد. به عنوان مثال عملیات پیوند، جهش و محاسبه تابع برازندگی می توانند بصورت موازی اجرا شوند. می توانند بصورت موازی اجرا شوند. از طرفی، امروزه با پیشرفت فناوری کارتهای گرافیکی و به ویژه تعبیه پرازنده های متعدد در آنها، قابلیت اجرای موازی عملیات محاسباتی بر روی این کارتها فراهم آمده است. بر همین اساس، در این مقاله قصد داریم تا چارچوبی کلی برای اجرای موازی یک الگوریتم ژنتیک بر روی واحدهای پردازش گرافیکی ارائه نماییم. در این راستا دو مکانیسم پیشنهادی برای پیاده سازی موازی الگوریتمژنتیک ارائه می دهیم. در روش اول، برای اجرای الگوریتم ژنتیک، از امکانات پردازشی واحد پردازنده مرکزی و واحد پردازشگر گرافیکی، به صورت توامان استفاده می کنیم. بخشی از عملیات شامل توابع پیوند، جهش و محاسبه برازندگی نسل جدید به صورت موازی در واحد پردازش گرافیکی اجرا شده و عملیات دیگر نظیر توابع بررسی شرط اتمام نسل و انتخاب، توسط واحد پردازش مرکزی و بصورت سری اجرا می شود. در روش دوم تمامی عملیات الگوریتم بصورت موازی و توسط واحد پردازش گرافیکی اجرا میشود. به منظور ارزیابی عملکرد روشهای پیشنهادی، مساله فروشنده دوره گرد به عنوان مطالعه موردی انتخاب و بر اساس هر دو مکانیسم پیشنهادی در بستر Cuda پیاده سازی گردید. نتایج حاصله از ارزیابی ها نشان می دهد که به ازای تغییر در مقادیر پارامترهای مختلف نظیر طول کروموزوم، تعداد نسل ها، تعداد جمعیت اولیه و تعداد کروموزوم های شرکت کننده در عمل پیوند و جهش، روش های پیشنهادی باعث کاهش قابل توجه زمان اجرای الگوریتم ژنتیک می گردد. علاوه بر این، روش پیشنهادی مبتنی بر واحد پردازش گرافیکی نسبت به روش ترکیبی دارای عملکرد بهتری از نقطه نظر زمان اجرا می باشد.
کلیدواژه ها:
نویسندگان
میلاد رفیعی
دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران
مهدی عباسی
دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران
محمد نصیری
دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران
احسان شکوهمند
واحد بین الملل، دانشگاه شیراز، شیراز، ایران
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :