کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
480678 1446128 2010 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A memetic algorithm for graph coloring
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
A memetic algorithm for graph coloring
چکیده انگلیسی

Given an undirected graph G=(V,E)G=(V,E) with a set V of vertices and a set E of edges, the graph coloring problem consists of partitioning all vertices into k independent sets and the number of used colors k is minimized. This paper presents a memetic algorithm (denoted by MACOL) for solving the problem of graph coloring. The proposed MACOL algorithm integrates several distinguished features such as an adaptive multi-parent crossover (AMPaX) operator and a distance-and-quality based replacement criterion for pool updating. The proposed algorithm is evaluated on the DIMACS challenge benchmarks and computational results show that the proposed MACOL algorithm achieves highly competitive results, compared with 11 state-of-the-art algorithms. The influence of some ingredients of MACOL on its performance is also analyzed.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 203, Issue 1, 16 May 2010, Pages 241–250
نویسندگان
, ,