کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
380473 1437442 2015 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
General swap-based multiple neighborhood tabu search for the maximum independent set problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
General swap-based multiple neighborhood tabu search for the maximum independent set problem
چکیده انگلیسی


• The Maximum Independent Set problem (MIS) is a well known NP-hard problem.
• We present a general Swap-Based Local Search (SBLS) procedure for solving MIS.
• SBLS uses a unified (k,1)-swap operator to explore multiple neighborhoods.
• SBLS is assessed on three benchmark sets (DIMACS, BHOSLIB, CODE with 131 instances).
• Results are compared with seven state of the art algorithms.

Given a graph G=(V,E)G=(V,E), the Maximum Independent Set problem (MIS) aims to determine a subset S⊆VS⊆V of maximum cardinality such that no two vertices of S are adjacent. This paper presents a general Swap-Based Tabu Search (SBTS) for solving the MIS. SBTS integrates distinguished features including a general and unified (k,1)-swap operator, four constrained neighborhoods and specific rules for neighborhood exploration. Extensive evaluations on two popular benchmarks (DIMACS and BHOSLIB) of 120 instances show that SBTS attains the best-known results for all the instances. To our knowledge, such a performance was not reported in the literature for a single heuristic. The best-known results on 11 additional instances from code theory are also attained.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Engineering Applications of Artificial Intelligence - Volume 37, January 2015, Pages 20–33
نویسندگان
, ,