بخشی از مقاله
چکیده
یکی از مسائل مهم در زمینه مسائل تصمیم گیری و مهم تر از آن بهینه سازی، مساله کوله پشتی است. مخصوصا در مواردی که مساله زمان و سرمایه گذاری در یک زمینه جزو فاکتورهای بحرانی است و از درجه اهمیت بالایی برخوردار می باشد، حل دقیق و بهینه مساله کوله پشتی، راهگشا خواهد بود. از طرف دیگر در تخصیص منابع با محدودیت مالی، و مواردی از قبیل ترکیبات،نظریه پیچیدگی محاسباتی، رمز نگاری و ریاضیات کاربردی نیز با این مساله روبرو هستیم. الگوریتمهای مختلفی برای حل مساله کوله پشتی ارائهشدهاست، اما مرتبه زمانی بیشتر آنها، نمایی است. اخیرا روش دیگری به نام الگوریتم ژنتیک برای این مساله ارائه شده که پیچیدگی محاسباتی آن برای مساله کوله پشتی به صورت چند جملهای میباشد.
با وجود اینکه الگوریتم ژنتیک برای تعداد دادههای کم بخوبی عملمیکند ولی اگر تعداد دادهها زیاد باشد الگوریتم ژنتیک نیز به کندی مسئله را حلمیکند حتی ممکن است با تکرار کم بخواهیم سرعت اجرای الگوریتم را زیاد کنیم اما مشکل از اینجا شروع می شود که اگر تکرارها را کم کنیم الگوریتم ژنتیک احتمال دارد جواب های نیمه بهینه را پیداکند . اخیراً سبک نوینی از برنامه نویسی موازی توسط شرکت NVidia ارائهشدهاست . در این روش برنامه کاربر بر روی هزاران هسته ریزکارت گرافیک به شکل موازی اجرامیشود. این روش باعثمیشود سرعت بسیاری از الگوریتمها در GPU نسبت به اجرا در CPU بسیار زیاد شود .
فریم ورکی که شرکت NVidia برای برنامه نویسی GPU تدارک دیده است CUDA نام دارد . در این مقاله مسئله کوله پشتی 0 و 1 با استفاده از الگوریتم ژنتیک توسط تکنولوژی CUDA حلشدهاست و موازیسازی اجرای این الگوریتم بر روی واحد پردازش گرافیکی را با حالتی که برنامه به صورت سریال بر روی پردازنده اجرا می شود را مقایسهمیکند. نشاندادهمیشود که اجرای الگوریتم به صورت موازی بر روی واحدپردازش گرافیکی نسبت به روش سریال بر روی پردازنده در این مقاله بهتر عملکرده و امکانی را برای توسعهدهندگان فراهم می کند که از راه حل های مقیاس پذیر و کم هزینه برای اجرای موازی سازی پردازش های محاسباتی سنگین استفاده کنند.
واژه های کلیدی: مسئله کوله پشتی 0 و 1، الگوریتم ژنتیک ، واحد پردازش گرافیکی ، CUDA ، موازی سازی
مقدمه
الگوریتم ژنتیک و سایر الگوریتم های جستجوی تصادفی معمولا برای حل مسائل NP-Hard طراحی شده اند.[1] مسئله کوله پشتی به اختصار Knapsack یا Runksack نام دارد. در این مسئله تعدادی شی با وزن و ارزش مشخص داده می شود. یکی دیگر از اطلاعات این مسئله تعداد مورد نیاز هر شی است که با توجه به این تعداد و با در نظر گرفتن بیشترین ارزش باید از میان اشیای موردنظر انتخاب شوند. به عبارت دیگر نسخه مسئله تصمیم برای مسئله کوله پشتی به صورت زیر تعریف می شود : آیا ارزش V با انتخاب اشیایی با مجموع وزن کمتر مساوی W قابل دستیابی است؟ متدهای دقیق و اکتشافی متنوعی برای حل این مسئله وجود دارد.
از جمله این روشها می توان به الگوریتم پویا، الگوریتم عقبگرد، الگوریتم گریدی و الگوریتم مبتنی بر آتوماتای یادگیر اشاره کرد. با توجه به اینکه مسئله کوله پشتی یک مسئله NP-Complete است، الگوریتم های دقیق که معمولا از روش های برش و انشعاب یا روش های ترکیب با برنامه نویسی پویا استفاده می کنند، در بهترین حالت دارای پیچیدگی نمایی هستند و برای استفاده در کابردهای عملی مناسب نمی باشند. به همین دلیل الگوریتم های تقریبی برای حل مسئله کوله پشتی گزارش شده است. از جمله این الگوریتم ها می توان به الگوریتم های تکرار شونده اشاره کرد. الگوریتم ژنتیک و الگوریتم کلونی مورچه ها نمونه های از این الگوریتم های تکرار شونده هستند.
الگوریتم ژنتیک با الهام از مفاهیم علم زیست شناسی همچون وراثت، جهش ، انتخاب طبیعی و ترکیب ، بر مبنای جستجوی تصادفی ساختاریافته، می باشد. با استفاده از الگوریتم ژنتیک زمان رسیدن به یک جواب قابل قبول را نسبت به سایر روش ها تا حد قابل قبولی کاهش می دهد. پردازش موازی یک راه حل مقیاس پذیر را برای الگوریتم نزدیک ترین همسایه در حالتی که حجم داده ها بالا است ارائه می کند. واحد پردازش گرافیکی شامل صدها هسته پردازنده موازی می باشند که قادرند به طور همزمان هزاران نخ را مدیریت کنند و با این هدف بوجود آمده است تا محاسبات مورد نیاز برای گرافیک های سه بعدی را که اغلب محاسبات ساده ای می باشند به طور موثری انجام دهد. CUDA این امکان را فراهم می کند که از قدرت واحد پردازش گرافیکی برای اجرای موازی پردازش های محاسباتی غیرگرافیکی استفاده شود.
تکنولوژی CUDA را می توان به زبان C نوشت و بر روی واحد پردازش گرافیکی اجرا کرد تا از طریق راه حل های مقیاس پذیر و کم هزینه برای اجرای موازی پردازش های محاسباتی سنگین فراهم شوند. در این مقاله یک پیاده سازی موازی با CUDA برای حل مسئله کوله پشتی 0 و 1 با استفاده از الگوریتم ژنتیک ارائه شده است و انتظار می رود اجرای الگوریتم بر روی واحد پردازش گرافیکی به زبان CUDA موجب افزایش سرعت اجرای الگوریتم شود. الگوریتم هایی که توسط واحد پردازش گرافیکی اجرا می شوند به سخت افزارهای متعددی بستگی دارند. در ادامه مقاله در بخش 2 به توضیح استقرار الگوریتم ژنتیک در حل مسئله کوله پشتی 1 0 پرداخته میشود. بخش 3 مفهوم واحد پردازش گرافیکی و تکنولوژی CUDA توضیح داده می شود. بخش 4 شرح روش پیشنهادی حل مسئله کوله پشتی 0 و 1 با الگوریتم ژنتیک توضیح داده می شود. بخش 5 نتایج پیاده سازی روش پیشنهادی و مقایسه آن با روش سریال ذکر گردیده است. در بخش 6 نتیجه گیری آورده شده است.
الگوریتم ژنتیک
الگوریتم ژنتیک یک روش بهینه سازی الهام گرفته از طبیعت جاندار است که در طبقه بندی مسائل به عنوان یک روش عددی، جستجوی سیستم و تصادفی هم مطرح می شود. این الگوریتم، الگوریتمی مبتنی بر تکرار است و اصول اولیه آن از علم ژنتیک اقتباس گردیده است. اساس این الگوریتم قانون تکامل داروین "بقای بهترین" است که می گوید موجودات ضعیف تر از بین می روند و موجودات قوی تر باقی می مانند.مکانیزم الگوریتم ژنتیک بدین صورت است که با در نظر گرفتن مجموعه ای از نقاط فضای جواب در هر تکرار محاسباتی، به نحو موثری نواحی مختلف فضای جواب را جستجو می کند. این الگوریتم ها با تولید نسل آغاز می شوند که وظیفه ایجاد مجموعه نقاط جستجوی اولیه به نام جمعیت اولیه را بر عهده دارند و به طور انتخابی یا تصادفی تعیین می شوند.
از آنجا که الگوریتم ژنتیک، جستجو را به سمت نقطه بهینه انجام می دهد، در فرآیندی که به انتخاب طبیعی وابسته است، جمعیت موجود به تناسب برازندگی افراد آن برای نسل بعد انتخاب می شوند . سپس عملگرهای ژنتیکی شامل انتخاب ، ترکیب ، جهش و دیگر عملگرهای احتمالی اعمال شده و جمعیت جدید به وجود می آید. پس از آن جمعیت جدید جایگزین پیشین می شود و این چرخه ادامه می یابد.معمولا جمعیت جدید برازندگی بیشتری دارد. هنگامی جستجو نتیجه بخش خواهد بود که به حداکثر نسل ممکن رسیده باشیم یا همگرایی حاصل شده باشد و یا معیارهای توقف برآورده شده باشند.[2]
مسئله کوله پشتی 0 و 1
یک سری شی قیمتی داریم و همین طور یک کوله پشتی که می تواند یک وزن خاص را تحمل کند. حال میخواهیم تعدادی از این اشیا را طوری انتخاب کنیم که وزن آنها کمتر مساوی وزن کوله پشتی باشد و مجموع ارزش ها Max شود. پارامترهایی که برای این مسئله تعریف می شود به صورت زیر است: vi - ارزش آیتم iام - ، wi - وزن آیتم iام - ، - Wوزن کل قابل حمل - و xi - یک متغیر باینری که تعیین می کند آیا آیتم iام انتخاب شده است یا نه؟ - معروف ترین نوع از این مسله ، مسئله کوله پشتی 0 و 1 است. یعنی تعداد از هر شی، یا صفر است - آن شی را انتخاب نمیکنیم - یا یک - آن شی انتخاب می شود - . مسئله کوله پشتی 0 و 1 را به صورت زیر می توان فرموله نمود:
با توجه به این که مسئله کوله پشتی یک مسئله NP-complete می باشد و غالبا در تخصیص منابع با محدودیت های مالی مواجه می شود. مشابه این مسئله در ترکیبات ، نظریه پیچیدگی ، رمزنگاری و ریاضیات کاربردی مشاده می شود.در الگوریتم ژنتیک ، با حفظ جمعیتی از راه حل مناسب توسط فناوری هوشمند مختلف و یا برازش جریمه1 انجام داد.[3] برازش جریمه خطی ساده در تابع هدف به صورت زیر انتخاب شده است:هدف اصلی مقاله ترجیحا پیدا کردن راه حل بهینه کوله پشتی توسط الگوریتم ژنتیک نیست بلکه عملکرد اجرایی آن بر روی واحد پردازشگر می باشد.
برنامه نویسی موازی با کودا
واحدهای پردازش گرافیک مدرن برای تولید و پردازش گرافک های سه بعدی با کیفیت بالا طراحی شده اند. این واحدهای پردازش گرافیکی در کامپیوترهای شخصی بسیار رایج هستند و کارآیی کل سیستم را از نظر کاهش زمان اجرا بهبود میدهند.روند اجرا به این صورت است که حجم زیادی از محاسبات یکسان روی تعداد زیادی از آیتمهای داده متفاوت به صورت یکی پس از دیگری اجرا می شوند. به طور مثال ممکن است یک محاسبه برای تک تک پیکسلهای یک فریم یا هر رأس در یک صفحه
