کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959182 | 1445469 | 2017 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A box decomposition algorithm to compute the hypervolume indicator
ترجمه فارسی عنوان
یک الگوریتم تجزیه ی جعبه برای محاسبه شاخص هیپرولووم
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We propose a new approach to the computation of the hypervolume indicator, based on partitioning the dominated region into a set of axis-parallel hyperrectangles or boxes. We present a nonincremental algorithm and an incremental algorithm, which allows insertions of points, whose time complexities are O(nâpâ12â+1) and O(nâp2â+1), respectively, where n is the number of points and p is the dimension of the objective space. While the theoretical complexity of such a method is lower bounded by the complexity of the partition, which is, in the worst-case, larger than the best upper bound on the complexity of the hypervolume computation, we show that it is practically efficient. In particular, the nonincremental algorithm competes with the currently most practically efficient algorithms. Finally, we prove an enhanced upper bound of O(npâ1) and a lower bound of Ω(nâp2âlogn) for pâ¥4 on the worst-case complexity of the WFG algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 79, March 2017, Pages 347-360
Journal: Computers & Operations Research - Volume 79, March 2017, Pages 347-360
نویسندگان
Renaud Lacour, Kathrin Klamroth, Carlos M. Fonseca,