دانلود مقاله ISI انگلیسی شماره 137860
ترجمه فارسی عنوان مقاله

یک الگوریتم تکاملی تابعی دو مرحله ای برای مشکل پیچیده چند بعدی چند بعدی

عنوان انگلیسی
A two-phase tabu-evolutionary algorithm for the 01 multidimensional knapsack problem
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
137860 2018 32 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Information Sciences, Volumes 436–437, April 2018, Pages 282-301

ترجمه کلمات کلیدی
بهینه سازی ترکیبی، مشکل پیچیده چند بعدی، جستجوی تابو مبتنی بر راه حل، متا اورویری،
کلمات کلیدی انگلیسی
Combinatorial optimization; Multidimensional knapsack problem; Solution-based tabu search; Meta-heuristics;
پیش نمایش مقاله
پیش نمایش مقاله  یک الگوریتم تکاملی تابعی دو مرحله ای برای مشکل پیچیده چند بعدی چند بعدی

چکیده انگلیسی

The 0–1 multidimensional knapsack problem is a well-known NP-hard combinatorial optimization problem with numerous applications. In this work, we present an effective two-phase tabu-evolutionary algorithm for solving this computationally challenging problem. The proposed algorithm integrates two solution-based tabu search methods into the evolutionary framework that applies a hyperplane-constrained crossover operator to generate offspring solutions, a dynamic method to determine search zones of interest, and a diversity-based population updating rule to maintain a healthy population. We show the competitiveness of the proposed algorithm by presenting computational results on the 281 benchmark instances commonly used in the literature. In particular, in a computational comparison with the best algorithms in the literature on multiple data sets, we show that our method on average matches more than twice the number of best known solutions to the harder problems than any other method and in addition yields improved best solutions (new lower bounds) for 4 difficult instances. We investigate two key ingredients of the algorithm to understand their impact on the performance of the algorithm.