25
правок
Изменения
Нет описания правки
== Постановка задачи ==
<tex>x = (x_1, x_2, ..., x_d; x_i \ge 0) \in \mathbb{R}^d</tex> - точка в <tex>d</tex>-мерном пространстве.
Точка <tex>x</tex> доминирует точку <tex>y</tex> (<tex>x \succ y</tex>), если <tex>\forall i : x_i \ge y_i, \exists j : x_j > y_j</tex>.
<tex>X = (\{x^1, x^2, ..., x^n) \} \subset \mathbb{R}^d</tex> - множество из <tex>n</tex> точек в <tex>d</tex>-мерном пространстве таких, что <tex>\nexists i \neq j : x_i \succ x_j</tex> - никакая точка не доминируется другой точкой из этого множества.
<tex>S(X) = \mu (\bigcup \limits_{x \in X} \{y | x \succ y\}) </tex> - гиперобъем множества <tex>X</tex>, где <tex>\mu</tex> - мера Лебега.
В частности, если <tex>X = \{x\}</tex>, то <tex>S(X) = \prod \limits_{i=1}^{d} x_i</tex>.
== Алгоритм LebMeasure ==
Алгоритм LebMeasure <ref>K. Bringmann, T. Friedrich.: An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation, Vol. 18, No. 3, pp 383-402, MIT Press. (2010)</ref> обрабатывает точки множества <tex>X</tex> по очереди. Для каждой очередной точки <tex>x</tex> находится объем некоторого максимального по включению гиперкуба, доминируемого эксклюзивно только этой точкой <tex>x</tex> и она заменяется на некоторое множество ''порожденных'' точек, которые доминируют оставшуюся область, доминировшуюся до этого точкой <tex>x</tex>.
Например, если изначально было четыре точки в трехмерном пространстве <tex>(6, 7, 4), (9, 5, 5), (1, 9, 3), (4, 1, 9)</tex>, то точка <tex>(6, 7, 4)</tex> эксклюзивно доминирует куб с одним концов в <tex>(6, 7, 4)</tex>, а другим - в <tex>(4, 5, 3)</tex>. После добавления объема этого куба к ответу, точка <tex>(6, 7, 4)</tex> порождает три точки: <tex>(4, 7, 4), (6, 5, 3), (6, 7, 3)</tex>. При этом точка <tex>(6, 5, 4)</tex> доминируется точкой <tex>(9, 5, 5)</tex> и сразу удаляется из множества <tex>X</tex>.
Обработка точек продолжается, пока все точки не будут обработаны. Таким образом, время работы алгоритма напрямую зависит от количества порожденных точек. Легко заметить, что таких точек не более, чем <tex>n^d</tex>, поскольку каждая координата каждой порожденной точки равна соответствующей координате некоторой точки исходного множества <tex>X</tex>.
К сожалению, эта верхняя оценка является достижимой. Например, если исходное множество <tex>X</tex> имеет вид: <tex>(1, n, n, ..., n), (2, n - 1, n - 1, ..., n - 1), ..., (n, 1, 1, ..., 1)</tex>, и точки обрабатываются именно в этом порядке, то всего будет обработано <tex>n^{d-1}</tex> точка, что показано в [1]. Правда, если в этом примере точки обрабатываются в обратном порядке, то суммарное количество обработанных точек линейно зависит от <tex>n</tex> и <tex>d</tex>. Тем не менее, существуют примеры, для которых любой порядок обработки приводит к экспоненциальной зависимости числа порожденных точек от размерности пространства <tex>d</tex> и эта зависимость близка к <tex>n^d</tex> [<ref name="while">While, L., Hingston, P., Barone, L., Huband, S.: A Faster Algorithm for Calculating Hypervolume. IEEE Transaction on Evolutionary Computation, Vol.10, No. 1], pp 29–38 (2006)</ref>.
== Алгоритм Hypervolume by Slicing Objectives (HSO) ==
Под ''Objectives'' в названии данного алгоритма имеются в виду координаты пространства <tex>\mathbb{R}^d</tex>.
Если алгоритм LebMeasure по очереди рассматривает все точки, то алгоритм HSO <ref>Zhou X., Sun C., Mao N., Li W.: Generalization of HSO algortihms for computing hypervolume for mutiobjective optimization problems, IEEE Congress on Evolutionary Computation (2007)</ref> рассматривает по очереди все координаты, сводя задачу к меньшей на единицу размерности.
Изначально все точки сортируются по первой координате. Значения этой координаты используются для ''расслоения'' (разрезания) всего множества на <tex>n</tex> частей, внутри каждой из которых при движении вдоль первой координаты форма ''разреза'' (гиперплоскости), проходящего перпендикулярно оси первой координаты, не меняется. Таким образом, для подсчета объема каждой части необходимо найти объем разреза, и умножить на длину части вдоль первой координаты. При этом получившийся разрез имеет на единицу меньшую размерность.
}}
Таким образом, на этот алгоритм получена более низкая оценка времени работы, чем на предыдущий, и это подтверждается на практике [1]<ref name ="while"/>.
== Сведение к задаче KMP (Klee's Measure Problem) ==
Задача KMP состоит в нахождении объема объединения прямоугольных гиперпараллелепипедов в <tex>d</tex>-мерном пространстве. Как показано в описании алгоритма IEA, исходная задача легко сводится к этой, если каждой точке поставить в соответствие гиперкуб с одной вершиной в центре координат, а противоположной - в этой точке.
Существует несколько алгоритмов решения задачи KMP<ref name = "overmars">Overmars, M.H., Yap, C.K.: New upper bounds in Klee’s measure problem. SIAM Journal on Computing 20(6), pp 1034–1045. (1991)</ref><ref>N. Beume.: S-Metric calculation by considering dominated hypervolume as Klee’s measure problem. Evolutionary Computation, 17(4), pp 477–492. (2009)</ref><ref>N. Beume, G. Rudolph.: Faster S-metric calculation by considering dominated hypervolume as Klee’s measure problem. In Proc. Second International Conference on Computational Intelligence (IASTED ’06), pp 233–238. (2006)</ref>, самый оптимальный из которых использует идеи сканирующей гиперплоскости, [[Статистики на отрезках. Корневая эвристика|корневой эвристики]] и КД-дерево, и позволяет решать задачу за время <tex>O(n^{d/2}\log n)</tex>. Рассмотрим его.
Для начала изложим идею сканирующей гиперплоскости. Рассмотрим всевозможные значения <tex>d</tex>-ой координаты у точек множества <tex>X</tex>.
Теперь изложим идею алгоритма на примере трехмерного пространства.
В трехмерном пространстве сканирующая гиперплоскость превращается в обычную плоскость. Будем считать, что сканирующая плоскость двигается она всегда располагается перепендикулярно оси <tex>OZ</tex>и двигается от минимальных значений по этой оси до максимальных. В каждый момент проекция всех параллелепипедов на эту плоскость предствляет представляет собой множество прямоугольников и необходимо уметь обрабатывать следующие три запроса:
# добавить прямоугольник
# удалить прямоугольник
== Источники ==
