کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
7541231 1489048 2018 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A robust and cooperative parallel tabu search algorithm for the maximum vertex weight clique problem
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مهندسی صنعتی و تولید
پیش نمایش صفحه اول مقاله
A robust and cooperative parallel tabu search algorithm for the maximum vertex weight clique problem
چکیده انگلیسی
The maximum vertex weight clique problem (MVWCP) is a challenging NP-Hard combinatorial optimization problem that searches for a clique with maximum total sum of vertices' weights. In this study, we propose a robust and cooperative parallel tabu search algorithm (PTC) for the MVWCP. Our proposed algorithm uses a dedicated tabu search algorithm with a multistart strategy for the diversification of search space on a parallel computation environment. An effective seeding mechanism is developed with respect to the rank of the processors to choose diversified starting points for a better exploration of the search space. Classical add, swap and drop operators of tabu search are improved with parallel computation and a combined neighborhood approach. The PTC algorithm is evaluated on a set of 120 problem instances from DIMACS-W and BHOSLIB-W benchmarks. Computational results show that the PTC algorithm competes with state-of-the-art heuristic algorithms by reporting average best (optimal) result hit ratios up to 99.0%.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Industrial Engineering - Volume 118, April 2018, Pages 54-66
نویسندگان
, ,