مقاله #129

چکیده

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