حل مساله کوله پشتی 0 و 1 با الگوریتم ژنتیک موازی مبتنی بر GPU

یکی از مسایل مهم در زمینه مسایل تصمیم گیری و مهم تر از آن بهینه سازی، مساله کوله پشتی است. مخصوصا در مواردی که مساله زمان و سرمایه گذاری در یک زمینه جزو فاکتورهای بحرانی است و از درجه اهمیت بالایی برخوردار می باشد، حل دقیق و بهینه مساله کوله پشتی، ر اهگشا خواهد بود. از طرف دیگر در تخصیص منابع با محدودیت مالی، و مواردی از قبیل ترکیبات،نظریه پیچیدگی محاسباتی، رمز نگاری و ریاضیات کاربردی نیز با این مساله روبرو هستیم. الگوریتمهای مختلفی برای حل مساله کوله پشتی ارایهشدهاست، اما مرتبه زمانی بیشتر آنها، نمایی است. اخیرا روش دیگری به نام الگوریتم ژنتیک برای این مساله ارایه شده که پیچیدگی محاسباتی آن برای مساله کوله پشتی به صورت چند جملهای می باشد. با وجود اینکه الگوریتم ژنتیک برای تعداد دادههای کم بخوبی عملمیکند ولی اگر تعداد دادهها زیاد باشد الگوریتم ژنتیک نیز به کندی مسیله را حل می کند حتی ممکن است با تکرار کم بخواهیم سرعت اجرای الگوریتم را زیاد کنیم اما مشکل از اینجا شروع می شود که اگر تکرارها را کم کنیم الگوریتم ژنتیک احتمال دارد جواب های نیمه بهینه را پیداکند . اخیرا سبک نوینی از برنامه نویسی موازی توسط شرکت NVidia ارایهشده است . در این روش برنامه کاربر بر روی هزاران هسته ریزکارت گرافیک به شکل موازی اجرامیشود. این روش باعثمیشود سرعت بسیاری از الگوریتمها در GPU نسبت به اجرا در CPU بسیار زیاد شود . فریم ورکی که شرکت NVidia برای برنامه نویسی GPU تدارک دیده است CUDA نام دارد . در این مقاله مسیله کوله پشتی 0 و 1 با استفاده از الگوریتم ژنتیک توسط تکنولوژی CUDA حلشدهاست و موازیسازی اجرای این الگوریتم بر روی واحد پردازش گرافیکی را با حالتی که برنامه به صورت سریال بر روی پردازنده اجرا می شود را مقایسه میکند. نشانداده میشود که اجرای الگوریتم به صورت موازی بر رو ی واحد پردازش گرافیکی نسبت به روش سریال بر روی پردازنده در این مقاله بهتر عملکرده و امکانی را برای توسعهدهندگان فراهم می کند که از راه حل های مقیاس پذیر و کم هزینه برای اجرای موازی سازی پردازش های محاسباتی سنگین استفاده کنند.

کلیدواژه ها:

مسیله کوله پشتی 0 و 1 ، الگوریتم ژنتیک ، واحد پردازش گرافیکی ، CUDA ، موازی سازی