کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6856636 | 1437967 | 2018 | 32 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A two-phase tabu-evolutionary algorithm for the 0-1 multidimensional knapsack problem
ترجمه فارسی عنوان
یک الگوریتم تکاملی تابعی دو مرحلهای برای یک مشکل حلقه چند بعدی 0-1
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بهینه سازی ترکیبی، مشکل پیچیده چند بعدی، جستجوی تابو مبتنی بر راه حل، متا اورویری،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volumes 436â437, April 2018, Pages 282-301
Journal: Information Sciences - Volumes 436â437, April 2018, Pages 282-301
نویسندگان
Xiangjing Lai, Jin-Kao Hao, Fred Glover, Zhipeng Lü,