Abstract
This paper focuses on solutions to two NP-Complete problems: k-SAT and the knapsack problem. We propose a new parallel genetic algorithm strategy on the CUDA architecture, and perform experiments to compare it with the sequential versions. We show how these problems can benefit from the GPU solutions, leading to significant improvements in speedup while keeping the quality of the solution. The best performance obtained in terms of speedup is 67 times. The solution presented in this paper suggests a general strategy for finding fast and robust solutions to complex problems.
چکیده
این مقاله بر راه حل های دو مساله ی NP-Complete تمرکز میکند: k-SAT (فروشنده ی دوره گرد با k لیترال در هر بند یاclause ) و مساله ی کوله پشتی. ما یک استراتژی الگوریتم ژنتیک موازی جدید برای معماری CUDA ارائه میکنیم و آزمایشها را انجام میدهیم تا این روش را با نسخه های ترتیبی مقایسه نماییم. نشان میدهیم که چگونه این مسائل میتوانند از راه حل های GPU سود ببرند که به بهبود قابل توجه در افزایش سرعت منجر میشود در حالی که کیفیت راه حل را حفظ میکند. بهترین کارایی که به دست آمده، از نظر افزایش سرعت 67 برابر بهتر است. راه حلی که در این مقاله ارائه شده، یک استراتژی سراسری برای پیدا کردن راه حل های سریع و پایدار برای مسائل پیچیده پیشنهاد مینماید.
1- مقدمه
در اوایل دهه ی 70، یک گروه از مسائل پیچیده (یا از نظر محاسباتی هزینه بر) مانند 3-SAT یا همریختی زیرگراف، به عنوان یک طبقهی جدید از نظر پیچیدگی محاسباتی، یعنی مسائل NP-Complete پدیدار شدند [2]. از زمان فرمالیزه کردن این مفهوم جدید توسط Richard Karp در سال 1972، نشان داده شده است که در زمینههای پژوهش بسیاری یک مجموعه از مسائل NP-Complete هستند. همه ی الگوریتم های شناخته شده برای مسائل NP-Complete به زمانی بالاتر از زمان چندجمله ای نیاز دارند و هنوز ثابت نشده که میتوان الگوریتم های سریعتری را توسعه داد. به هر حال، در عمل چند تکنیک وجود دارد که به طور کلی در مسائل محاسباتی به کار می روند...