Методы многокритериальной целочисленной оптимизации, основанные на аппроксимации границы Парето




Скачать 79.57 Kb.
PDF просмотр
НазваниеМетоды многокритериальной целочисленной оптимизации, основанные на аппроксимации границы Парето
Поспелов Алексей Игоревич
Дата конвертации15.08.2012
Размер79.57 Kb.
ТипАвтореферат
СпециальностьМатематическое моделирование, численные методы и комплексы программ
Год2010
На соискание ученой степениКандидата<> физико-математических наук
На правах рукописи
Поспелов Алексей Игоревич
Методы многокритериальной целочисленной
оптимизации, основанные на аппроксимации
границы Парето
05.13.18 — Математическое моделирование, численные методы и комплексы
программ
Автореферат диссертации на соискание ученой степени кандидата
физико-математических наук
Москва — 2010

Работа выполнена в Учреждении Российской академии наук Вычислительный
центр им. А. А. Дородницына РАН
Научный руководитель:
доктор физико-математических наук,
профессор
Лотов Александр Владимирович
Официальные оппоненты:
доктор технических наук, профессор
Сигал Израиль Хаимович
кандидат физико-математических наук,
доцент
Морозов Владимир Викторович
Ведущая организация:
Учреждение Российской академии наук
Центральный экономико-математический
институт РАН
Защита состоится “

2010 года в
часов на заседании дис-
сертационного совета Д 002.017.04 Учреждения Российской академии наук Вы-
числительный центр им. А. А. Дородницына РАН по адресу: 119333 Москва,
улица Вавилова, дом 40, конференц-зал.
С диссертацией можно ознакомиться в библиотеке ВЦ РАН.
Автореферат разослан “

20
года.
Ученый секретарь диссертационного совета
доктор физико-математических наук,
профессор
Новикова Н. М.

Общая характеристика работы
Актуальность работы.
При моделирования сложных систем важным мо-
ментом является оценка стратегий с точки зрения различных критериев. При
большом числе решений сравнение их критериальных оценок и выбор подхо-
дящего решения становится крайне трудной задачей для лица, принимающего
решение (ЛПР). Важную роль в таких случаях играют методы поддержки при-
нятия решений, основанные на многокритериальной оптимизации.
Одним из основных подходов, используемых в многокритериальной опти-
мизации, является аппроксимация границы Парето множества достижимых
критериальных точек (т.е. множества всех недоминируемых по Парето крите-
риальных точек) и представление этой информации ЛПР (работы академика
П. С. Краснощёкова и его учеников В. В. Морозова, Н. М. Попова, В. В. Фе-
дорова и других, а также иностранных специалистов М. Зелены, Р. Штойера,
По-лунг Ю). Как показывает практика, наиболее удобным способом представ-
ления информации о границе Парето является ее визуализация. Такой под-
ход развивается исследованиях многокритериальных задач школы академика
А. А. Петрова, проводимых под руководством А. В. Лотова и Г. К. Каменева.
Для реализации подобного подхода при более чем двух критериях необходимо
предварительно решать задачу аппроксимации многомерной границы Парето в
форме, удобной для последующей визуализации. В зависимости от структуры
задачи для этого применяются разные методы. Так, для непрерывных задач
были разработаны методы, основанные на аппроксимации множества дости-
жимых критериальных точек с помощью относительно простых фигур (мно-
гогранников, объединения конечного числа конусов и т.д.).
В прикладных задачах множество допустимых решений часто является дис-
кретным. Такая ситуация встречается, например, в транспортных задачах, за-
дачах составления расписаний, телекоммуникационной маршрутизации, зада-
1

чах планирования инвестиций и производства и многих других задачах. В на-
стоящей диссертационной работе рассматривается случай, когда множество ре-
шений является подмножеством целочисленного куба. К такому случаю могут
быть сведены многие прикладные задачи дискретные оптимизации.
Проблема поиска или аппроксимации множества решений, эффективных
по Паретои, и соответствующей совокупности критериальных точек в много-
критериальных дискретных задачах изучалась ранее в работах И. Х. Сигала,
И. И. Меламеда, М. Эрготта. Был предложен широкий спектр методов, ис-
пользующих комбинаторную специфику рассматриваемых задач или сведение
их к решению серии однокритериальных задач оптимизации, для каждой из
которых можно найти решение.
В ряде прикладных задач дискретной оптимизации (в том числе многокри-
териальных) возникает необходимость решать комбинаторные задачи, которые
не относятся к изученным классам. К таким задачам, в частности, относятся
проблемы, в которых модель задана вычислительным модулем с закрытым
кодом (черным ящиком), предоставляющим возможность только для расчета
значений критериев по заданным решениям. В подобных случаях можно при-
менять, например, методы случайного поиска и методы, основанные на термо-
динамических и биологических аналогиях. Для многокритериальных дискрет-
ных задач эти методы получили развитие в работах К. Деба, Е. Цитцлера и его
коллег. В указанных методах число критериев не превосходит двух или трех,
а оценки точности аппроксимации границы Парето отсутствуют (обычно ка-
чество алгоритма оценивается на основе сравнения аппроксимации с заранее
известной точной границей Парето, которую удается построить лишь в простей-
ших случаях), так что эти методы, по существу, являются эвристическими.
Эффективным подходом к решению задач многокритериального выбора
из конечного числа вариантов (альтернатив) является метод разумных целей
2

(МРЦ), разработанный А. В. Лотовым и Д. В. Гусевым. МРЦ основан на сведе-
нии многокритериальной задачи выбора к анализу границы Парето выпуклой
оболочки критериальных точек — образов рассматриваемых альтернатив. В
рамках МРЦ происходит визуализация границы Парето этой выпуклой обо-
лочки (или более простого множества — оболочки Эджворта-Парето выпуклой
оболочки), на которой ЛПР выбирает цель, отвечающую его интересам; далее
компьютер находит оптимальные по Парето альтернативы, результаты выпол-
нения которых близки к цели, выбранной ЛПР. Практическое использование
МРЦ продемонстрировало его удобство при поддержке многокритериального
выбора из конечного, но относительно небольшого числа альтернатив при чис-
ле критериев от трех до восьми. Ограничение на применение МРЦ по числу
альтернатив обусловлено необходимостью их явного представления в критери-
альном пространстве, что оказывается затруднительным для большого числа
альтернатив.
Сказанное выше обосновывает актуальность разработки новых методов, ко-
торые применимы к широкому спектру задач дискретной многокритериальной
оптимизации, характеризующихся более чем двумя критериями и большим
числом альтернатив, причем позволяют оценивать точность аппроксимации
границы Парето.
Цель диссертационной работы.
Целью данной диссертации является по-
строение и изучение методов, обобщающих МРЦ на задачи многокритериаль-
ной целочисленной оптимизации, характеризующиеся большим числом альтер-
натив, в том числе заданных вычислительным модулем типа черного ящика.
Методы исследований.
В работе используется математический аппарат
теории дискретной оптимизации, теории многокритериальной оптимизации и
теории адаптивных методов полиэдральной аппроксимации выпуклых тел.
3

Достоверность
полученных результатов подтверждена доказательствами
теорем, экспериментальной проверкой алгоритмов и программ на модельных и
реальных данных.
Научная новизна.
Предложены два метода решения целочисленных задач
многокритериальной оптимизации с монотонными критериями и ограничени-
ями, являющиеся обобщениями МРЦ. Предложенные методы позволяют ра-
ботать с задачами, в которых исходный МРЦ уже неприменим из-за слиш-
ком большого числа альтернатив. Первый из предложенных методов — ме-
тод квазиразумных целей, основанный на аппроксимации оболочки Эджворта-
Парето релаксированной задачи. Метод может быть использован в том случае,
когда критерии и ограничения заданы явно. Второй — метод разумных це-
лей, основанный на непосредственной полиэдральной аппроксимации оболочки
Эджворта-Парето выпуклой оболочки множества достижимых критериальных
векторов. Метод применим в том случае, когда модель задана в виде черного
ящика.
Предложена и изучена схема наполнения, являющаяся обобщением извест-
ных адаптивных методов полиэдральной аппроксимации выпуклых компакт-
ных тел; полученные результаты использованы для теоретической оценки ско-
рости сходимости метода полиэдральной аппроксимации оболочки Эджворта-
Парето выпуклой оболочки критериальных векторов целочисленной задачи оп-
тимизации.
Практическая ценность работы.
Результаты, полученные в работе, могут
быть использованы для поддержки принятия решений в проблемах, моделиру-
емых целочисленными многокритериальными задачами с монотонными кри-
териями и ограничениям. В диссертации разработанные методы применены в
рамках двух проектов улучшения качества воды в больших и малых реках с
4

числом допустимых альтернатив до 1032 и числом критериев до пяти.
Апробация работы
прошла на следующих научных конференциях: на Меж-
дународной конференции студентов и аспирантов по фундаментальным наукам
“Ломоносов-2004”, секция “Вычислительной математики и кибернетики” (Рос-
сия, Москва, 12–15 апреля 2004), на 4-й Московской международной конфе-
ренции по исследованию операций (Россия, Москва, 21–24 сентября 2004), на
XIII Байкальской международной школе-семинаре “Методы оптимизации и их
приложения” (Россия, Северобайкальск, 2–8 июля 2005), на 7-й Международ-
ной конференции, посвященной многокритериальной оптимизации и целевому
программированию (Франция, Тур, 12–14 июня 2006), на V Московской меж-
дународной конференции по исследованию операций (Россия, Москва, 10–14
апреля 2007), на Всероссийской конференции ЭКОМОД (Россия, Киров, 6–12
июля 2009).
Публикации.
По теме диссертации опубликовано 9 работ, в том числе 3 ста-
тьи в журналах из списка ВАК.
Структура и объем диссертации.
Диссертационная работа объемом 150
страниц состоит из введения, четырех глав, заключения, библиографическо-
го списка. Библиографический список содержит 89 источников, из них 37 на
иностранных языках.
Содержание работы
Во введении
приведены основные понятия многокритериальной оптимиза-
ции, используемые в работе, обоснована актуальность рассматриваемой про-
блемы, введен класс исследуемых в работе задач многокритериальной цело-
численной оптимизации, описаны основные особенности МРЦ, приведены важ-
5

нейшие результаты теории и методы полиэдральной аппроксимации выпуклых
компактных тел, дано краткое описание диссертации по главам.
Математическая задача целочисленной многокритериальной оптимизации,
рассматриваемая в диссертационной работе, формулируется следующим обра-
зом:
f (x) → min,
(1)
x ∈ X = {x ∈ X0|wi (x)
0, i = 1, 2, . . . , k} ,
где X
n
m
0 = {0, 1...K }n — целочисленный куб, f (·) : R
→ R — векторнозначная
функция, задающая критерии оценки альтернатив, w(·) :
n
k
R
→ R — набор
функций, используемых для описания ограничений. Рассматривается случай
монотонных критериев, часто встречающийся в прикладных исследованиях —
предполагается, что
f (·) = (u (·) , v (·)) ,
где u(·) и v(·) — такие векторнозначные функции, что u(·) :
n
t
R → R и v(·) :
n
m−t
R → R
для некоторого целого t, 0
t
m, и при этом u и v монотонны в
следующем смысле:
для x
x , s = 1, 2, . . . , n, имеем
s
s
(2)
ui(x )
ui(x ), i = 1, 2, . . . , t, и vj(x )
vj(x ), j = 1, 2, . . . , m − t.
Кроме того, предполагается, что ограничения также монотонны, т.е.
для x
x , s = 1, 2, . . . , n, имеем
s
s
(3)
wl(x )
wl(x ), l = 1, 2, . . . , k.
В (1) под записью f (x) → min понимается, что желательным является
уменьшение каждого частного критерия fi, i = 1, 2, . . . m, при прочих рав-
ных условиях (задача многокритериальной минимизации). В этом случае го-
ворят, что решение x доминирует x по Парето, если fi(x )
fi(x ), i =
6

1, 2, . . . , m, и f (x ) = f (x ). Критериальная точка f (x ) называется оптималь-
ной по Парето, а соответствующее ей решение x ∈ X — эффективным
по Парето, если не существует решения x ∈ X, доминирующего x по Па-
рето. Множество всех оптимальных по Парето критериальных точек называ-
ется границей Парето. Для удобства визуализации границы Парето в работе
рассматривается аппроксимация двух объектов: оболочки Эджворта-Парето
(ОЭП), которая может быть определена как Y ∗ = f (X) +
m
R , и оболочки
+
Эджворта-Парето выпуклой оболочки (ВОЭП) критериальных точек, которая
может быть определена как Y ∗ = conv(f (X))+ m, где
m — неотрицательный
C
R+
R+
конус пространства
m
R .
В первой главе
описаны некоторые классические задачи целочисленной
многокритериальной оптимизации, такие как задача о многокритериальном
рюкзаке, задача о покрытии, сводящиеся к рассматриваемым в работе мо-
нотонным многокритериальным задачам целочисленной оптимизации. Также
описаны некоторые задачи экологического и экономического содержания, мо-
делирование которых приводит к задаче (1)-(3). Таким образом, показывается
практическая значимость работы.
Во второй главе
предложены методы решения задач типа (1)-(3).
В разделе 2.1 описан метод квазиразумных целей (МКРЦ). Метод пред-
полагает, что имеется возможность вычислять значения критериев и ограни-
чений задачи не только на множестве X0, но и на более широком множестве
˜
X0 = [0, K]n. В МКРЦ используется вспомогательная релаксированная задача
f (x) → min, x ∈ ˜
X ⊂ Rn,
(4)
˜
X = {x ∈ Rn | w (xi)
0, 0
xi
K, i = 1, . . . , n} ,
получаемая из (1)-(3) заменой дискретного множества X на непрерывное ˜
X и
7

продолжением на ˜
X критериев и ограничений.
В МКРЦ предлагается аппроксимировать ОЭП релаксированной задачи.
Так как релаксированная задача (4) непрерывна, для аппроксимации ее ОЭП
могут быть использованы методы, разработанные для непрерывных задач: ме-
тод уточнения оценок (УО) в выпуклом случае и гибридные методы — в невы-
пуклом. Построенная аппроксимация визуализируется с помощью диалогового
изображения карт решений — совокупностей двумерных сечений аппроксима-
ции ОЭП. ЛПР предлагается указать желаемую цель ˆ
y (называемую квазира-
зумной) на границе Парето подходящего сечения аппроксимации ОЭП. Далее,
аналогично исходному МРЦ, по цели находится множество ˆ
X альтернатив та-
ких, что множество ˆ
Y = f ( ˆ
X) близко к ˆ
y. Для этого требуется разработать
метод поиска ˆ
X, применимый в случае большого числа альтернатив.
Задача поиска ˆ
X сводится в диссертации к нахождению всех оптимальных
по Парето решений многокритериальной задачи
ˆ
f (x) → min,
(5)
x ∈ X,
где ˆ
fi(x) = max {fi(x), ˆ
yi} для x ∈ X0. В случае когда мощность X0 велика,
задача (5) не может быть решена прямым перебором, поэтому для ее решения
в диссертации предлагается использовать метод, основанный на приложении
концепции ветвей и границ к многокритериальным задачам с монотонными
критериями. При этом предлагается разбивать множество X0 на подмножества
вида
Xα = {x ∈ X
s
0|xj = αj , j = 1, 2 . . . , s} ,
(6)
где s ∈ {1, 2, . . . , n}, а α = (α1, . . . , αs) — некоторый элемент целочисленного
куба {0, 1, . . . , K}s. В качестве вектора нижних оценок подмножеств Xα пред-
s
8

лагается использовать
d (Xα) = ˆ
u x0 (Xα) , ˆ
v xK (Xα)
,
(7)
s
s
s
а в качестве верхних оценок — векторы из множества
Λ (Xα) = xi (Xα) , i = 0, 1, . . . , K w xi
0 ,
(8)
s
s
где xi (Xα) = (α
s
1, α2, . . . , αs, i, . . . , i), i = 0, 1, . . . , K .
Предлагаемый метод основан на последовательно разбиение множества X0
на подмножества вида Xα, построении оценок для этих подмножеств, выде-
s
лении альтернатив, являющихся кандидатами на вхождение в ˆ
X, сравнении
найденных альтернатив и оценок и исключении подмножеств, заведомо не со-
держащих альтернатив из ˆ
X.
В конце раздела 2.1 приводятся результаты применения МКРЦ для при-
кладной задачи с числом альтернатив порядка 1013 и числом критериев от
двух до пяти.
Одним из важных классов проблем многокритериальной целочисленной оп-
тимизации являются линейные задачи. В таких проблемах релаксированная
задача (4) представляет собой задачу линейной многокритериальной оптими-
зации. В линейном случае аппроксимация ОЭП осуществляется в МКРЦ с по-
мощью метода УО. В методе УО при m > 2 на каждой итерации обычно при-
ходится решать значительное число задач скалярной оптимизации, которые
в рассматриваемом случае являются задачами линейного программирования
(ЛП). Решение этих задач может быть решена, в частности, с использовани-
ем симплекс-метода. В том случае, когда решение каждой задачи ЛП требует
существенных вычислительных затрат, для построения достаточно точной ап-
проксимации ОЭП может потребоваться значительное время. В разделе 2.2
предложена модификация метода УО, предназначенная для уменьшения тру-
доемкости построения аппроксимации многогранных множеств, в том числе, в
9

рамках работы МКРЦ, и основанная на следующих соображениях.
Работа симплекс-метода обычно разбивается на два этапа. Первый состо-
ит в поиске допустимой вершины и соответствующего базисного разложения.
Второй — в последовательном переходе от одной вершины к другой до тех пор,
пока не будет достигнуто оптимальное решение задачи. Поскольку метод УО
требует многократного решения задач ЛП на одном и том же многограннике,
оптимальные вершины, найденные при решении предыдущих задач ЛП, мож-
но использовать в качестве начальных при решении последующих задач. Идея
использования результатов предыдущих вычислений широко применяется при
решении задач линейной оптимизации, в том числе и многокритериальных.
Так, в работах Р. Штойера и М. М. Смирнова эта идея использовалась в неадап-
тивных методах поиска недоминируемых вершин. В методе, предложенном в
разделе 2.2, на основе вершин, полученных при решении задач ЛП, формиру-
ется база, каждым элементом которой является пара (направление, вершина).
При решении новой задачи ЛП на аппроксимируемом теле в качестве началь-
ной вершины используется вершина из базы, ближайшая по направлению. При-
ведено экспериментальное сравнение трудоемкости исходной УО и указанной
его модификации на нескольких специально сгенерированных модельных телах
и на ОЭП реальной задачи при использовании различных систем пакетов для
решения задач ЛП. Эксперименты показали целесообразность использования
подобной модификации. Время построения аппроксимации ОЭП для трудоем-
ких задач сокращалось в три-пять раз.
В разделе 2.3 предлагается метод, который полностью переносит идеи ис-
ходного МРЦ на задачу (1)-(3) и может быть применен и тогда, когда модель
задана в виде черного ящика. Для аппроксимации ВОЭП в диссертационной
работе предложен метод, основанный на синтезе идей метода ветвей и границ и
методов адаптивной полиэдральной аппроксимации выпуклых тел. Идея пред-
10

лагаемого метода основана на последовательном разбиении множества X0 на
подмножества Xα вида (6), вычислении векторов d (Xα) (см. (7)) и множеств
s
s
Λ (Xα) (см. (8)), построении на их основе очередных внешних и внутренних
s
полиэдральных аппроксимаций Y ∗ и отсеивании таких подмножеств вида Xα,
C
s
вектор оценок которых d (Xα) принадлежит построенной внутренней аппрок-
s
симации Y ∗. Перейдем непосредственно к строгому описанию алгоритма.
C
На нулевой итерации строим начальные аппроксимирующие Y ∗ внешнее
C
и внутреннее многогранные множества P0 и Q0; полагаем начальный набор
активных подмножеств Ξ0 = {X0}. В общем случае начальные аппроксимации
могут быть построены, например, в виде
P
m
0 = conv (f (Λ (X0))) + R ,
+
Q
m
0 = d(X0) + R .
(9)
+
Построение conv (f (Λ (X0))) не вызывает трудностей, поскольку число точек
Λ (X0) невелико.
Рассмотрим произвольную l-ю итерацию. Перед ее началом должны быть
заданы внутренняя аппроксимация Pl−1 и набор Ξl−1 активных подмножеств
X0 вида Xα, порожденный на предыдущих итерациях.
s
1. Из набора Ξl−1 выбираем множество Xαl, для которого оценка d Xαl
sl
sl
наиболее удалена от построенной аппроксимации Pl−1, т.е.
Xαl ∈ Argmax ρ (d (A) , P
s
l−1) .
l
A∈Ξl−1
Способ формирования Ξl−1 позволяет гарантировать, что у всех A ∈ Ξl−1
расстояние до Pl−1 будет больше нуля.
2. Разбиваем Xαl на K + 1 подмножество X(αl,i), i = 0, 1, . . . , K.
sl
sl+1
11

3. Для каждого X(αl,i) находим множество Λ X(αl,i)
и вычисляем оценку
sl+1
sl+1
d X(αl,i) .
sl+1
4. Строим Pl на основе имеющегося многогранного множества Pl−1 и вычис-
ленных оценок:
K
P
m
l = conv
f Λ X(αl,i)
+
P
s
R
l−1
.
l+1
+
i=0
α
5. Строим набор Ξ
l
l. Для этого берем объединение Ξl−1\
Xs
и совокуп-
l
ности множеств X(αl,i), для которых Λ X(αl,i)
непусто; из этого объ-
sl+1
sl+1
единения исключаем множества, для которых нижняя оценка d X(αl,i)
sl+1
попадает внутрь построенного многогранного множества Pl. Заметим, что
для множеств Xα, которые содержат единственный вектор, вектор d (Xα)
n
n
принадлежит Λ (Xα), поэтому для таких множеств d (Xα) всегда будет
n
n
оказываться внутри Pl, и они будут исключаться из дальнейшего рас-
смотрения.
6. На основе построенного многогранного множества Pl строим Ql:
Q
m
l = conv
{d(A) + R } ∪ P
+
l
.
(10)
A∈Ξl
7. Если Ξl не пусто, переходим к шагу 1 итерации (l + 1). Если Ξl пусто,
завершаем работу алгоритма.
В данном методе на каждой итерации может быть получена оценка достиг-
нутой точности:
δH (Y ∗, P
ρ (d (A) , P
C
l)
εl = max
l) ,
A∈Ξl
где δH (·, ·) — метрика Хаусдорфа. Для метода аппроксимации ВОЭП показана
корректность и монотонность (Pl−1 ⊂ Pl ⊂ Y ∗ ⊂ Q
C
l ⊂ Ql−1), проведено экспе-
риментальное изучение работы метода на модельных и прикладных задачах,
12

показывающее возможность использовать метод для задач с числом вариантов
порядка 109 − 1013 и числом критериев от двух до пяти.
После построения аппроксимации ВОЭП, дальнейшая работа метода анало-
гична исходному МРЦ, т.е. построенная аппроксимация ВОЭП визуализирует-
ся с помощью карт решений и ЛПР предлагается указать желаемую разумную
цель на границе Парето подходящего сечения аппроксимации ВОЭП. Далее,
с помощью метода, предложенного в разделе 2.1, находится множество таких
альтернатив ˆ
X, что множество ˆ
Y = f ( ˆ
X) близко выбранной цели.
В третьей главе
рассматриваются теоретические вопросы скорости сходи-
мости. Раздел 3.1 посвящен разработке методики, предназначенной для теоре-
тического анализа скорости сходимости метода полиэдральной аппроксимации
ВОЭП, предложенного в разделе 2.3. Как обычно, методика разрабатывается
для задачи аппроксимации выпуклых компактных тел; далее она переносится
на методы аппроксимации ВОЭП. В разделе 3.1 предложена схема наполнения
— итерационная схема аппроксимации, порождающая для тела C из множе-
ства всех выпуклых компактных тел C в пространстве Rm последовательность
многогранников {Pl}, удовлетворяющих свойству
Pl−1 ⊂ Pl ⊂ C,
l = 1, 2, . . . .
Эта схема является обобщением изученной Г. К. Каменевым схемы восполне-
ния, отличаясь от нее тем, что вершины многогранника могут располагаться не
только на границе, но и внутри аппроксимируемого тела. Необходимость рас-
смотрения новой схемы связана с тем, что метод полиэдральной аппроксимации
ВОЭП порождает многогранные множества, вершины которых не обязательно
лежат на границе аппроксимируемой ВОЭП.
На основе схем наполнения по аналогии с хаудорфовыми последователь-
ностями восполнения введено понятие хаусдорфовых последовательностей на-
13

полнения.
Опpеделение 3.6 Последовательность многогранников {Pl}∞ , порождае-
l=0
мая для C ∈ C некоторой реализацией схемы наполнения, называется ха-
усдорфовой последовательностью наполнения (или GH(γ, C) -последо-
вательностью), если существует константа γ > 0 такая, что для любого
l = 0, 1, . . . справедливо
δH (Pl, Pl+1)
γδH (Pl, C).
В диссертации для хаусдорфовых последовательностей наполнения доказа-
на сходимость.
Теоpема 3.1 Пусть {Pl}∞ есть хаусдорфова последовательность наполне-
l=0
ния для C ∈ C . Тогда
lim δH (Pl, C) = 0.
l→∞
Основными результатами раздела 3.1 являются оценки скорости сходимости
хаусдорфовых последовательностей наполнения.
Теоpема 3.2 Пусть {Pl}∞ есть GH(γ, C)-последовательность для C ∈ C и
l=0
0 < γ
1. Тогда для любого ε > 0 существует N (ε) такое, что при l
N (ε)
справедливо
δH (Pl, C)
(1 + ε)λ2(γ, C)l1/(1−m).
Здесь
m
σ(C) 1/(m−1)
λ2(γ, C) =
ω(C),
(m − 1)πm−1 γm
где πm−1 — объем (m − 1)-мерного единичного шара, ω(C) — асферичность
тела C, а σ(C) — его поверхностный объем.
14

Теоpема 3.3 Пусть {Pl}∞ есть GH(γ, C)-последовательность для C ∈ C ,
l=0
0 < γ
1 и пусть r, R и z таковы, что Br(z) ⊂ P0 ⊂ C ⊂ BR(z). Тогда для
любого l
1 справедливо
δH (Pl, C)
λ0(γ, C, P
2
0)l−1/m,
где
(m−1)/m
mδS(C, P0)
R + δH (C, P0)
λ0(γ, C, P
,
2
0) =
γπm−1
r
Bs(z) — m-мерный шар с центром в z и радиусом s, δS(·, ·) — метрика объема
симметрической разности.
В разделе 3.2 результаты, полученные для схем наполнения, применены
для анализа метода полиэдральной аппроксимации ВОЭП в монотонных мно-
гокритериальных задачах. Введена экономичная модификация, особенностью
которой является то, что шаг 4 метода полиэдральной аппроксимации ВОЭП
разбивается на подшаги, на каждом из которых выбирается очередная точка
p из множества верхних оценок всех имеющихся на итерации подмножеств, на
которые разбито X0. Для этой точки p проверяется условие
ρ(p, P )
τ max ρ(P , d(Xα)),
l
l
s
Xα∈Ξ
s
l
где 0 < τ
1 — заданный параметр, P — многогранное множество, полу-
l
ченное из Pl на предыдущих подшагах. Если условие выполнено, то точка p
присоединяется к P , тем самым улучшая аппроксимацию.
l
Доказано, что для экономичной модификации метода полиэдральной ап-
проксимации выпуклой оболочки Эджворта-Парето с параметром 0 < τ
1
справедливы оценки аналогичные оценкам теорем 3.2 и 3.3 не только по чис-
лу итераций, но и по числу вершин аппроксимирующих многогранников. При
этом константы, входящие в соответствующие оценки, могут быть выражены
через τ , размерность m и диапазон изменения критериев на множестве X.
15

Четвертая глава
посвящена использованию методов, предложенных в дис-
сертации, при решении прикладных задач.
В разделе 4.1 описаны принципы функционирования программного ком-
плекса, разработанного диссертантом для реализации МРЦ в задачах много-
критериальной целочисленной оптимизации. Программный комплекс реализо-
ван на основе предложенных методов и состоит из трех компонентов: компо-
нента аппроксимации ВОЭП, компонента визуализации ВОЭП в виде карт ре-
шений, компонента выделения малого числа альтернатив по выбранной цели.
Комплекс рассчитан на работу под управлением ОС семейства Windows.
Для работы с комплексом пользователь должен представить интересующую
его задачу многокритериальной оптимизации в виде динамически подключае-
мой библиотеки. Библиотека подгружается программным комплексом и долж-
на осуществлять вычисление значений критериев и ограничений для передачи
их значений в программный комплекс. В разделе описаны программные ин-
терфейсы, которые необходимо реализовать для создания такой библиотеки.
Описана организация работы компонента аппроксимации ВОЭП, графического
интерфейса, позволяющего вводить описание задачи, компонентов осуществля-
ющих визуализацию ВОЭП и поиск альтернатив по цели, выбранной пользо-
вателем.
В разделе 4.2 приводится использование предложенных в диссертации мето-
дов для решения задачи поиска стратегии улучшения качества воды в бассейне
крупной реки. В конкретной рассматриваемой задаче изучается бассейн реки
Ока. Бассейн разбит на 14 участков, в каждом из которых возможно уста-
новить одну из 9 технологий очистки различной интенсивности и стоимости.
Таким образом, в задаче около 1013 различных вариантов. В задаче изучает-
ся взаимосвязь между затратами и экологической обстановкой для различных
решений, задаваемых набором технологий, установленных на участках. Мо-
16

дель была описана в виде системы уравнений, что позволило применить как
МРЦ, так и МКРЦ. В диссертации описано решение этой задачи для трех и
пяти критериев, приведены карты и матрицы карт решений, а также резуль-
таты, получаемые при выборе различных точек на границах Парето. Проведе-
но сравнение использования МРЦ и МКРЦ. Оказалось, что МКРЦ позволяет
строить аппроксимацию существенно быстрей, однако цели, выбираемые в этом
методе, оказываются дальше от достижимых точек задачи, что приводит к су-
щественному замедлению поиска альтернатив, близких к выбранной цели, и
увеличению их числа.
В разделе 4.3 описано использование МРЦ в задаче поиска стратегии улуч-
шения качества воды на основе детального описания бассейна небольшой реки.
Изучается бассейн реки Муга (Каталония, Испания). Основным возможным
мероприятием по улучшению качества воды является установка очистных со-
оружений в некоторых из 42-х пунктов выброса загрязнений. Всего рассматри-
валось 7 различных типов очистных сооружений. С учетом ограничений, общее
число вариантов в задаче было порядка 1032. Так как модель была задана в ви-
де вычислительного модуля, способного вычислять значения критериев только
в целых точках, применить МКРЦ оказалось невозможно. Поэтому применял-
ся только МРЦ. Была построена аппроксимация ВОЭП для пяти критериев с
относительной точностью 0.2 за 200 итераций (50 часов). В работе приведены
матрицы карт решений и результаты, получаемые при выборе разумной цели
на границе Парето аппроксимации ВОЭП.
Заключение
Результаты диссертационной работы, выносимые на защиту.
Разра-
ботаны и исследованы методы решения задач многокритериальной целочислен-
ной оптимизации с монотонными критериями и ограничениями, разработано
17

программное обеспечение и решены прикладные задачи. В частности:
1. разработан метод квазиразумных целей, позволяющий для случая явного
задания критериев и ограничений решать монотонные многокритериаль-
ные задачи целочисленной оптимизации с большим числом альтернатив;
2. разработан вариант метода разумных целей, основанный на аппрокси-
мации оболочки Эджворта-Парето выпуклой оболочки критериальных
точек и позволяющий решать задачи монотонной многокритериальной
целочисленной оптимизации с большим числом альтернатив, заданных
вычислительным модулем;
3. разработана и экспериментально изучена модификация метода уточнения
оценок, которая может быть использована в рамках метода квазиразум-
ных целей в том случае, когда исследуемая многокритериальная задача
линейна;
4. предложена и изучена схема наполнения, являющаяся обобщением из-
вестных адаптивных схем полиэдральной аппроксимации выпуклых ком-
пактных тел; полученные результаты использованы для теоретической
оценки скорости сходимости по числу вершин метода полиэдральной ап-
проксимации оболочки Эджворта-Парето выпуклой оболочки критери-
альных точек;
5. разработан программный комплекс, реализующий метод разумных целей
в задачах многокритериальной целочисленной оптимизации с монотон-
ными критериями и большим числом альтернатив;
6. программный комплекс применен в рамках двух проектов улучшения ка-
чества воды в больших и малых реках.
18

Основные результаты опубликованы в работах
[1] А. В. Лотов, А. И. Поспелов. Метод квазиразумных целей для целочис-
ленных задач многокритериальной оптимизации // Доклады Акад. наук. —
2007. — Т. 414, № 3. — С. 317–319.
[2] А. В. Лотов, А. И. Поспелов. Модифицированный метод уточнения оце-
нок для полиэдральной аппроксимации выпуклых многогранников //
Журн. вычисл. матем. и матем. физ. — 2008. — Т. 48, № 6. — С. 990–
998.
[3] А. И. Поспелов. Аппроксимация выпуклой оболочки Эджворта-Парето в
многокритериальных задачах с монотонными критериями // Журн. вы-
числ. матем. и матем. физ. — 2009. — Т. 49, № 10. — С. 1765–1778.
[4] А. И. Поспелов. Аппроксимация выпуклой оболочки Эджворта-Парето в
целочисленных задачах многокритериальной оптимизации // Материалы
Международной конференции студентов и аспирантов по фундаменталь-
ным наукам “Ломоносов-2004”, секция “Вычислительной математики и ки-
бернетики”. — М.: Издательский отдел ВМиК МГУ, 2004. — С. 25.
[5] A. I. Pospelov. About Polyhedral Approximation of Edgeworth-Pareto Convex
Hull for the Special Class of Integer Multicriteria Optimization Problems //
Труды 4-й Московской международной конференции по исследованию опе-
раций. — М.: МАКС Пресс, 2004. — С. 185–188.
[6] А. И. Поспелов. Алгоритм аппроксимации выпуклой оболочки Эджворта-
Парето в некоторых задачах целочисленной многокритериальной оптими-
зации // Труды XIII Байкальской международной школы-семинара “Ме-
тоды оптимизации и их приложения”. — Т. 1. — Иркутск: ИСЭМ СО РАН,
2005. — С. 359–363.
19

[7] A. I. Pospelov, A. V. Lotov. Application of Convex Pareto Frontier
Approximation and Visualization in Integer Multicriteria Optimization
Problems. — Loire Valley (old city hall of Tours), France: 2006.
[8] А. В. Лотов, А. И. Поспелов. Метод разумных целей для целочисленных
задач многокритериальной оптимизации // Труды V Московской между-
народной конференции по Исследованию операций. — М.: МАКС Пресс,
2007. — С. 149–151.
[9] А. И. Поспелов. Аппроксимация границы Парето выпуклой оболочки
критериальных векторов в целочисленных задачах с монотонными кри-
териями // Сборник тезисов IV Всероссийской научной конференции
“Математическое моделирование развивающейся экономики и экологии”
ЭКОМОД-2009 (Киров, 6-12 июля). — Киров: ГОУ ВПО “ВятГУ”, 2009. —
С. 56.
20


Добавить документ в свой блог или на сайт
Разместите кнопку на своём сайте:
поделись


База данных защищена авторским правом ©dis.podelise.ru 2012
обратиться к администрации
АвтоРефераты
Главная страница