حل مسأله كوله پشتي 0 و 1 با الگوريتم ژنتيك موازي مبتني بر GPU

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