کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959774 | 1445961 | 2017 | 32 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
New genetic algorithm approach for the min-degree constrained minimum spanning tree
ترجمه فارسی عنوان
رویکرد الگوریتم ژنتیک جدید برای حداقل درخت حداقل درخت کم محصور
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بهینه سازی ترکیبی، درخت پانچ محدود شده الگوریتم ژنتیک، ابتکاری، کران پایین،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
A novel approach is proposed for the NP-hard min-degree constrained minimum spanning tree (md-MST). The NP-hardness of the md-MST demands that heuristic approximations are used to tackle its intractability and thus an original genetic algorithm strategy is described using an improvement of the Martins-Souza heuristic to obtain a md-MST feasible solution, which is also presented. The genetic approach combines the latter improvement with three new approximations based on different chromosome representations for trees that employ diverse crossover operators. The genetic versions compare very favourably with the best known results in terms of both the run time and obtaining better quality solutions. In particular, new lower bounds are established for instances with higher dimensions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 258, Issue 3, 1 May 2017, Pages 877-886
Journal: European Journal of Operational Research - Volume 258, Issue 3, 1 May 2017, Pages 877-886
نویسندگان
Rui Salgueiro, Ana de Almeida, Orlando Oliveira,