کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6854167 | 1437407 | 2018 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Tabu search with feasible and infeasible searches for equitable coloring
ترجمه فارسی عنوان
جستجوی تابو با جستجوهای امکان پذیر و غیرقابل اجرا برای رنگ صحیح
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ترجمه چکیده
مشکل رنگ آمیزی صحیح یک نوع از مشکل رنگ آمیزی گرافیک کلاسیک است که از تعدادی از برنامه های کاربردی زندگی واقعی می آید که در آن توانایی کلاس های رنگ باید متعادل باشد. در این مقاله، یک روش جستجوی تابوبی هیبرید بسیار موثر برای مشکل ارائه شده است. بر اساس سه محله مکمل، الگوریتم جایگزین یک مرحله جستجوی محلی قابل اجرا است که در آن جستجو بر روی راه حل های مناسب ترین راه حل و فاز جستجوی محلی غیر قابل قبول تمرکز می شود که با کشف محدودیت حقوق صاحبان اکتشافی کنترل شده از راه حل های غیر قابل قبول امکان پذیر است. یک محله جدید مبادله چرخه ای نیز برای افزایش توان جستجو در الگوریتم جستجوی تابو ترکیبی پیشنهاد شده است. آزمایشات بر روی مجموعه ای از 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
Journal: Engineering Applications of Artificial Intelligence - Volume 71, May 2018, Pages 1-14
نویسندگان
Wenyu Wang, Jin-Kao Hao, Qinghua Wu,