کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6854167 1437407 2018 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Tabu search with feasible and infeasible searches for equitable coloring
ترجمه فارسی عنوان
جستجوی تابو با جستجوهای امکان پذیر و غیرقابل اجرا برای رنگ صحیح
ترجمه چکیده
مشکل رنگ آمیزی صحیح یک نوع از مشکل رنگ آمیزی گرافیک کلاسیک است که از تعدادی از برنامه های کاربردی زندگی واقعی می آید که در آن توانایی کلاس های رنگ باید متعادل باشد. در این مقاله، یک روش جستجوی تابوبی هیبرید بسیار موثر برای مشکل ارائه شده است. بر اساس سه محله مکمل، الگوریتم جایگزین یک مرحله جستجوی محلی قابل اجرا است که در آن جستجو بر روی راه حل های مناسب ترین راه حل و فاز جستجوی محلی غیر قابل قبول تمرکز می شود که با کشف محدودیت حقوق صاحبان اکتشافی کنترل شده از راه حل های غیر قابل قبول امکان پذیر است. یک محله جدید مبادله چرخه ای نیز برای افزایش توان جستجو در الگوریتم جستجوی تابو ترکیبی پیشنهاد شده است. آزمایشات بر روی مجموعه ای از 73 نمونه معیار در ادبیات نشان می دهد که الگوریتم پیشنهادی قادر به یافتن بهترین راه حل های بهبود یافته برای 15 نمونه (مرزهای بالایی جدید) و مطابقت با راه حل های شناخته شده برای 57 نمونه است. تجزیه و تحلیل های اضافی نشان می دهد علاقه محله تبادل چرخه و طرح هیبرید ترکیبی از هر دو جستجو قابل اجرا و غیر قابل انجام محلی است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی
The equitable coloring problem is a variant of the classical graph coloring problem that arises from a number of real-life applications where the cardinality of color classes must be balanced. In this paper, we present a highly effective hybrid tabu search method for the problem. Based on three complementary neighborhoods, the algorithm alternates between a feasible local search phase where the search focuses on the most relevant feasible solutions and an infeasible local search phase where a controlled exploration of infeasible solutions is allowed by relaxing the equity constraint. A novel cyclic exchange neighborhood is also proposed in order to enhance the search ability of the hybrid tabu search algorithm. Experiments on a set of 73 benchmark instances in the literature indicate that the proposed algorithm is able to find improved best solutions for 15 instances (new upper bounds) and matches the best-known solutions for 57 instances. Additional analyses show the interest of the cyclic exchange neighborhood and the hybrid scheme combining both feasible and infeasible local searches.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Engineering Applications of Artificial Intelligence - Volume 71, May 2018, Pages 1-14
نویسندگان
, , ,