دانلود مقاله ترجمه شده حل مسائل NP-Complete در معماری CUDA با استفاده از الگوریتم های ژنتیک

 این مقاله بر راه­ حل­ های دو مساله ­ی NP-Complete  تمرکز می­کند: k-SAT (فروشنده­ ی دوره ­گرد با k لیترال در هر بند یاclause ) و مساله­ ی کوله­ پشتی. ما یک استراتژی الگوریتم ژنتیک موازی جدید برای معماری CUDA ارائه می­کنیم و آزمایش­ها را انجام می­دهیم تا این روش را با نسخه ­های ترتیبی مقایسه نماییم. نشان می­دهیم که چگونه این مسائل می­توانند از راه­ حل­ های GPU سود ببرند که به بهبود قابل توجه در افزایش سرعت منجر می­شود در حالی که کیفیت راه ­حل را حفظ می­کند. بهترین کارایی که به دست آمده، از نظر افزایش سرعت 67 برابر بهتر است. راه­ حلی که در این مقاله ارائه شده، یک استراتژی سراسری برای پیدا کردن  راه حل های سریع و پایدار برای مسائل پیچیده پیشنهاد می­نماید.

در اوایل دهه ی 70، یک گروه از مسائل پیچیده (یا از نظر محاسباتی هزینه­ بر) مانند 3-SAT یا هم­ریختی زیرگراف، به عنوان یک طبقه­ی جدید از نظر پیچیدگی محاسباتی، یعنی مسائل NP-Complete پدیدار شدند [2]. از زمان فرمالیزه کردن این مفهوم جدید توسط Richard Karp در سال 1972، نشان داده شده است که در زمینه­های پژوهش بسیاری یک مجموعه از مسائل NP-Complete هستند. همه­ ی الگوریتم­ های شناخته­ شده  برای مسائل NP-Complete به زمانی بالاتر از زمان چندجمله ­ای نیاز دارند و هنوز ثابت نشده که می­توان الگوریتم­ های سریع­تری را توسعه داد. به هر حال، در عمل چند تکنیک وجود دارد که به طور کلی در مسائل محاسباتی به­ کار می­ روند...