کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
496689 862866 2011 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نرم افزارهای علوم کامپیوتر
پیش نمایش صفحه اول مقاله
An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem
چکیده انگلیسی

The minimum weight vertex cover problem is an interesting and applicable NP-hard problem that has been investigated from many different aspects. The ant colony optimization metaheuristic is a relatively new technique that was successfully adjusted and applied to many hard combinatorial optimization problems, including the minimum weight vertex cover problem. Some kind of hybridization or exploitation of the knowledge about specific problem often greatly improves the performance of standard evolutionary algorithms. In this article we propose a pheromone correction heuristic strategy that uses information about the best-found solution to exclude suspicious elements from it. Elements are suspicious if they have some undesirable properties that make them unlikely members of the optimal solution. This hybridization improves pure ant colony optimization algorithm by avoiding early trapping in local convergence. We tested our algorithm on numerous test-cases that were used in the previous research of the same problem and our algorithm uniformly performed better, giving slightly better results in significantly shorter time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Soft Computing - Volume 11, Issue 8, December 2011, Pages 5360–5366
نویسندگان
, ,