25
правок
Изменения
м
Нет описания правки
== Алгоритм LebMeasure ==
Алгоритм LebMeasure<ref>Bringmann K., Friedrich. T.: An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation, Vol. 18, No. 3, MIT Press, 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>.
Под ''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> частей, внутри каждой из которых при движении вдоль первой координаты форма ''разреза'' (гиперплоскости), проходящего перпендикулярно оси первой координаты, не меняется. Таким образом, для подсчета объема каждой части необходимо найти объем разреза, и умножить на длину части вдоль первой координаты. При этом получившийся разрез имеет на единицу меньшую размерность.
Задача 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>Beume N.: S-Metric calculation by considering dominated hypervolume as Klee’s measure problem. Evolutionary Computation, 17(4), pp 477–492. (2009)</ref><ref>Beume N., Rudolph G.: 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>.
