Algorithmic aspects to analysis of decision maker's preferences structure with standard aggregative functions.pdf В задаче определения условий оптимальности некоторой альтернативы из дискретного множества, рассмотренной в предыдущем докладе авторов, решаются две нетривиальные подзадачи. Первая подзадача решается для определения потенциальной оптимальности альтернативы и заключается в определении её принадлежности convP(Y) - Парето-оболочке множества Y, получаемой объединением 2n множеств Парето YP для всех возможных сочетаний направлений оптимизации n критериев. Здесь Y -множество векторных оценок множества альтернатив X: y(x) = (/i(x), f2(x), ..., fn(x)), x e X, y(x) e Y, | Y | = | X | = N. Тогда векторная оценка представляет собой точку в n-мерном пространстве (если все f(x) -числовые, то Y с R). Точки, входящие в convP(Y), принадлежат поверхности тела (необязательно выпуклого) минимального объема, заключающего в себе множество Y целиком. В простейшем случае это тело представляет собой невыпуклый многогранник, вершинами которого являются точки convP(Y). Вторая подзадача решается для определения типа обобщающей функции FO(w; y) и вектора весовых коэффициентов w, применение которых делает альтернативу у оптимальной, и заключается в определении принадлежности альтернативы conv^Y) - линейной выпуклой оболочке Y, которая представляет собой выпуклый многогранник минимального объема, обрамляющий Y. При этом в обе оболочки как минимум входят все точки yex, имеющие экстремальное значение хотя бы одной координаты: yex e convL(T) n convp(Y) ^ 3j = 1, ..., n: fj(x) = maxxex fj(x)) v f(x) = minxex (f(x))), кроме того, convi(Y) с convP(Y). Тогда возникает вопрос, как выбрать вершины и определить геометрические параметры этих многогранников и можно ли использовать их и методы аналитической геометрии для определения потенциальной оптимальности альтернативы, типа обобщающей функции и вектора весовых коэффициентов. Рассмотрению данных вопросов и уделяется внимание в данной статье. 1. Формирование Парето-оболочки Авторы считают, что построение Парето-оболочки не может быть осуществлено алгоритмом меньшей сложности, чем сокращенный. 1. Для каждого из 2n вариантов направлений оптимизации n критериев нужно рассчитать множество YP Парето-точек путем их попарного сравнения. Вычислительная сложность определения множества Парето в худшем случае, при необходимости полного попарного сравнения, составляет n • N• (N - 1)/2 ~ n • N2, где N = | Y |. Это предполагает несравнимость всех имеющихся точек по Парето, и в результирующее множество YP при этом войдут все N точек. Однако в общем случае возможно сокращение перебора: если одна точка доминирует над другой, то доминируемую точку имеет смысл исключить из дальнейшего перебора и не использовать для сравнения с остальными. Таким образом, в лучшем случае вычислительная сложность составит n • (N-1) ~ n • N. При этом только одна доминирующая альтернатива будет сравниваться с остальными. Для максимального сокращения рекомендуется начинать перебор с точек, вошедших в множество {yex}, т.е. имеющих экстремальные значения хотя бы по одной координате. 2. Объединить множества YP. Вычислительной сложностью (N-1) • n ~ n • N можно пренебречь. Таким образом, вычислительная сложность предлагаемого алгоритма построения convP(Y) составляет в худшем случае 2n • n • N2, а в лучшем - 2n • n • N. 2. Определение потенциальной оптимальности альтернативы Чтобы некоторая альтернатива обладала потенциальной оптимальностью, она должна принадлежать Парето-оболочке convP(Y), т.е. находиться либо в одной из вершин, либо лежать на одной из её граней. В первом случае определение оптимальности тривиально и заключается в последовательном сравнении точки с вершинами, формирующими оболочку. Во втором случае следует определить уравнение каждой грани (гиперплоскости) и, подставляя координаты точки, выяснить, удовлетворяют ли они одному из них. Задача осложняется тем, что не каждые n точек convP(Y) формируют её грань и не каждая грань лежит только с одной стороны многогранника, так как он невыпуклый. Поэтому алгоритмически проще во время формирования многогранника Парето не исключать из множества вершин точки, лежащие точно на гранях. В этом случае оба варианта определения потенциальной оптимальности сводятся к однократному перебору вершин convP(Y). 3. Формирование линейной выпуклой оболочки Для построения выпуклой линейной оболочки convL(Y) в двумерном пространстве используют алгоритм Грэхема, Чана и Джарвиса (алгоритм «заворачивания подарка») и их модификации [1, 2], но в пространствах более высокой размерности они неприменимы. В литературе отсутствуют описания обобщения алгоритмов поиска выпуклых оболочек для случая Rn при n > 2. Если бы заранее не была построена оболочка Парето convP(Y), то, поскольку convL(Y) является минимальным выпуклым многогранником, содержащим Y, для его поиска следовало бы перебрать все гиперплоскости, проходящие через n точек из Y, т. е. сочетания по n точек из Y. После выбора очередной n-ки точек из Y необходимо проверить каждую из оставшихся N - n точек на то, с какой стороны от выбранной гиперплоскости она находится. Если для текущей гиперплоскости все точки Y находятся с одной стороны, то образующая её n-ка точек входит в convL(Y). Взаимное положение гиперплоскости, проходящей через n точек, и n + 1-й определяется знаком определителя n-го порядка, построенного из разностей этих n + 1 точек. Если все проверяемые N - n точек расположены с одной стороны от рассматриваемой гиперплоскости, то эти определители имеют одинаковый знак. Если же для n + 1-й точки этот определитель равен 0, то это означает, что она лежит в этой же гиперплоскости. При этом в самом худшем случае для построения convL( Y) необходимо вычислить C"N ■ (N - n) определителей порядка n, а сложность вычисления каждого определителя ~ n3. Поэтому для построения convL(Y) предлагается алгоритм сокращенного перебора вершин многогранника convP(Y), использующий тот факт, что convL(Y) с convP(Y). 1. Для каждого из 2n вариантов направлений оптимизацииfj(x) ^ {min, max}, j = 1, ..., n: a. Выбирается n точек из convP(Y), имеющих экстремальные значения хотя бы по одному критерию, и строится гиперплоскость L, проходящая через них. Сложность - n • (N + n2) ~ n3. Кубическая компонента появляется в связи с необходимостью вычисления определителя для построения гиперплоскости. b. Выбирается (или формируется искусственно) «предельная» точка yextr, имеющая экстремальные значения по всемf(x), и определяется её ориентированное расстояние d до гиперплоскости L [3]. Сложность - n • (N + 1) ~ N • n. c. Путем перебора формируется множество точек Y* с convp(Y), ориентированное расстояние от которых до гиперплоскости имеет тот же знак, что d, а остальные отбрасываются. Сложность - N• п. d. Множество Yt с ^Сформируется путем повторения пунктов a-c для всех наборов по п точек из Y*. Если | Y* | < п + 1, то Yt = Y. Сложность в худшем случае составляет CnN • (п + N• п), а в лучшем - 0. 2. Для получения conv^(Y) множества Yt объединяются. Вычислительной сложностью можно пренебречь. Получается, что вычислительная сложность предлагаемого алгоритма построения conv^(Y) в худшем случае составляет 2п • CN • п • (п2+N), а в лучшем - 2п • п • (п2+N). 4. Поиск вектора весовых коэффициентов, обеспечивающих оптимальность альтернативы Для аддитивной и мультипликативной обобщающих функций, как показано в предыдущей работе, задача определения вектора весовых коэффициентов включает в себя поиск вектора, перпендикулярного гиперплоскости, являющейся гранью conv^(Y) или convi(ln(T)). Известно, что всякая гиперплоскость в Rп проходит через п точек [3]. Уравнение гиперплоскости определяется как C1-y1 + ... + Сп-уп + D = 0, где C1, ..., Сп - координаты нормали данной гиперплоскости. = 0, где ab ... ап С другой стороны, гиперплоскость также описывается уравнением (y - a1 - a п_1 - a1) - точки, входящие в гиперплоскость, а y - произвольная точка пространства, тоже находящаяся на гиперплоскости. Разрешив это уравнение относительно у, найдем С1, ..., Сп. Для этого необходимо разложить указанный определитель по первой строке: Уп - a1,; У - a1 У1 - a1,1 = (У1 - a1,1) • A1,1 + - + (Уп - au) • А1,п = ап-1, п a1,t 1 - a1 2п-1,1 - a1,1 = У1 • A1,1 + - + Уп • A1,п - (a1,1 • A1,1 + - + a1,п • A1,п ) = 0 Следовательно, алгебраические дополнения первой строки и есть компоненты нормального вектора. При этом они вычисляются через координаты точек ai, ..., a^. Далее обратим внимание, что у всякой гиперплоскости существует не один нормальный вектор, а целое семейство векторов, задаваемое выражением а• n, где а Ф 0, а n - любой из векторов, перпендикулярный гиперплоскости (например, вектор с координатами (A1,1, ..., А1п), как показано выше). Однако для правильного определения направления, важного для определения направлений оптимизации, нас интересует не всякий вектор, нормальный к указанной грани, а только такой, который выходил бы изнутри многогранника наружу перпендикулярно к указанной плоскости. Таким образом, встают две задачи: 1) найти точку у0, принадлежащую внутренности многогранника; 2) найти точку yg, принадлежащую указанной грани, такую, что вектор (yg - у0) был бы перпендикулярен грани. Первую часть задачи можно решить двумя способами: если множество Y \ conv^(Y) не пусто, в качестве y0 можно взять любую точку из него. В противном случае в качестве y0 можно взять точку, являющуюся арифметическим средним всех точек из conv^(Y): в силу выпуклости многогранника она будет всегда принадлежать его внутренности. Для нахождения точки yg нужно решить систему уравнений (поиск точки пересечения прямой и гиперплоскости, при условии что прямая задана в параметрической форме, а ее направляющий вектор является нормальным вектором гиперплоскости): ' У81 = У01 + A1,1 •t, вектора гиперплоскости, найденные выше. Найдя число t, найдем и координаты искомой точки yg, а вычитанием (yg - y0) найдем искомый вектор. Однако всякая вершина многогранника принадлежит одновременно k > 1 гиперплоскостям. Поэтому если нас интересует такой вектор w, который доставляет этой точке наибольшее значение, то этот вектор должен находиться во внутренности конуса, образованного нормальными векторами этих гиперплоскостей. Но тогда w должен представляться как их выпуклая комбинация. В простейшем случае будем брать средний вектор, т.е. для k граней w = (wigr1 + ... + wlgrk) / k. Тем самым мы можем перейти от систем неравенств к уравнениям, ищущим для каждой гиперплоскости нормальный вектор, а зная для точки, в какие грани она входит, образовать из них конус и взять «средний» внутренний вектор-луч этого конуса. Заключение В работе показано, что задача поиска вектора весовых коэффициентов w, оптимизирующего указанную альтернативу по значению аддитивной или мультипликативной обобщающей функции (при условии ее принадлежности паретовской или линейной оболочке множества), алгоритмически разрешима. Кроме того, приведены алгоритмы, позволяющие построить эти оболочки для произвольного конечного множества в Rn эффективнее, чем полным перебором.

Скачать электронную версию публикации