На правах рукописи

БЕРЕЗКИН Вадим Евгеньевич

МЕТОДЫ АППРОКСИМАЦИИ ГРАНИЦЫ ПАРЕТО В

НЕЛИНЕЙНЫХ ЗАДАЧАХ МНОГОКРИТЕРИАЛЬНОЙ

ОПТИМИЗАЦИИ

Специальность 05.13.18

Математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ

Москва – 2008

Работа выполнена в Вычислительном центре им.

А.А.Дородницына Российской академии наук, отдел математического моделирования экономических систем.

Научный руководитель:

доктор физико-математических наук, старший научный сотрудник Каменев Георгий Кириллович

Официальные оппоненты:

доктор технических наук, профессор Подиновский Владислав Владимирович кандидат физико-математических наук, старший научный сотрудник Голиков Александр Ильич

Ведущая организация:

Факультет Вычислительной математички и кибернетики МГУ им. М.В.Ломоносова

Защита состоится «» 2008 г. в часов на заседании диссертационного совета Д 002.017.04 в Вычислительном центре им. А.А. Дородницына Российской академии наук по адресу: 119333 г. Москва, ул. Вавилова, д.40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан «» 2008 г.

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

Общая характеристика работы

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

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

Целью диссертационной работы является разработка и изучение методов аппроксимации оболочки Эджворта-Парето в нелинейных задачах многокритериальной оптимизации, а также их реализация и практическое применение.

Научная новизна. Результаты диссертации, полученные автором, являются новыми. Основные из этих результатов следующие:

1) В рамках метода достижимых целей предложены новые методы аппроксимации оболочки Эджворта-Парето для нелинейных задач многокритериальной оптимизации.

2) Теоретически изучены свойства предложенных многофазных методов аппроксимации оболочки Эджворта-Парето, доказана их сходимость, исследована скорость сходимости и оценена их эффективность.

3) Осуществлено экспериментальное изучение предложенных методов, выявлены их варианты, пригодные для практического применения.

Результаты, выносимые на защиту

, состоят в следующем.

1. В рамках метода достижимых целей предложен комплекс методов аппроксимации оболочки Эджворта-Парето для нелинейных многокритериальных задач принятия решений с 3– критериями, в том числе:

а) однофазный метод, сочетающий случайный поиск с оценкой качества аппроксимации б) двухфазные методы, в которых случайный поиск дополняется локальной оптимизацией рассматриваемых в) трехфазные методы, основанные на неравномерных недоминируемой границы и оценками их значимых окрестностей, построенных на основе использования экстремальных статистик;

направленностью на улучшение достаточно точной аппроксимации оболочки Эджворта-Парето;

д) гибридные методы, интегрирующие многофазные методы и генетический метод.

2. Теоретически изучены свойства предложенных многофазных методов, доказана их сходимость и оценена эффективность (совместно с научным руководителем Г.К.

Каменевым).

3. Разработаны три системы программного обеспечения на персональном компьютере реализующие метод достижимых целей для нелинейных многокритериальных задач в среде MS Excel, в среде MS Windows на основе Windows API, а также в рамках многомашинного программного комплекса «Метод достижимых целей».

предложенных методов, выявлены их варианты, пригодные для практического применения.

5. Разработанные методы применены в процессе решения прикладной задачи поиска разумных вариантов системы охлаждения стали в оборудовании для непрерывной разливки стали.

Практическая ценность работы состоит в том, что разработаны три системы программного обеспечения для персонального компьютера, реализующие комплекс методов аппроксимации оболочки Эджворта-Парето для нелинейных задач многокритериальной оптимизации с 3–7 критериями, позволяющий визуализировать паретову границу в прикладных задачах планирования и проектирования, описываемых нелинейными моделями большой размерности. Исследована прикладная задача многокритериального выбора параметров системы вторичного охлаждения стали в процессе ее непрерывной разливки. Результаты диссертации использованы исследованиях, проводимых в рамках проектов РФФИ № 01-01программы фундаментальных исследований РАН №14 "Фундаментальные проблемы информатики и информационные технологии", программы фундаментальных исследований ОМН РАН №3 и Государственного контракта «Технологии и программные средства создания систем автоматизации проектирования сложных технических объектов» с Федеральным агентством по науке и инновациям от 15 августа 2005 г. № 02.435.11. (шифр: «ИТ-13.4/003»), а также в рамках сотрудничества РАН и Академии Финляндии.

Достоверность полученных результатов подтверждена доказательствами теорем о свойствах предложенных методов, экспериментальной проверкой алгоритмов на модельных и реальных данных.

Апробация работы. Результаты работы докладывались на 3й Московской международной конференции по исследованию операций (2001 г.), 4-й Московской международной конференции по исследованию операций (2004 г.), 5-й Московской международной конференции по исследованию операций ( г.), на Тихоновской конференции, ВМК МГУ (2006 г.), на Международных семинарах «Практические подходы в многокритериальной оптимизации» (Германия, 2004 и 2006 г.), а также на семинарах в ВЦ РАН, Университета г. Ювяскюля, Университета г. Зиген (Германия).

Публикации. По материалам диссертации опубликовано печатных работ, в том числе две статьи в журналах РАН, три брошюры, изданные в ВЦ РАН, две статьи в международных журналах, а также три другие публикации за рубежом.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Содержит 185 страниц, включая список литературы из 61 наименований, 168 иллюстраций и шесть таблиц.

Во введении обоснована актуальность темы диссертации, сформулированы цели работы, показана научная новизна результатов диссертации и дано краткое описание диссертации по главам. Введение содержит математическую постановку многокритериальной оптимизации, рассматриваемая в данной работе, формулируется следующим образом. Пусть заданы nмерное линейное пространство решений (параметров объекта) RPn P и m-мерное линейное пространство RPm критериальных векторов.

Пусть связь между решениями и значениями критериев выбора устанавливается заданным отображением (вектор-функцией) f: RPn RPm Пусть X RPn – заданное множество допустимых решений. Тогда множество достижимых критериальных векторов (также называемое множеством достижимых целей) определяется как Y = f(X). Будем для определенности считать, что в задаче представляет интерес увеличение значения каждого из m критериев при неизменных значениях других (задача критериальную точку y RPm если y' y, т.е. y'Bi yBi i=1,…,m, и y' y. Недоминируемая по Парето (в дальнейшем, просто недоминируемая или паретова) граница множества Y = f(X), определяемая как множество недоминируемых точек y Y, в этом случае имеет вид P(Y) = {y Y : {y' Y : y' y, y' y} = }.

Под множеством P(X) парето-эффективных решений понимается подмножество таких решений x X, что f(x) P(Y). ОЭП определяется как Y* = {yRPm yf(x), xX}. Альтернативное, может быть, более удобное представление ОЭП имеет следующий вид YP* Y + (-RB+ m где RB+ m – неотрицательный конус пространства RPm Аппроксимация ОЭП строится на основе объединения многомерных конусов доминирования (-RB+ m с P) вершинами в точках, близких к паретовой границе. Пусть T – конечное число точек из множества Y=f(X) (база аппроксимации).

Тогда в качестве аппроксимации ОЭП берется множество T * = U{ y + ( R+ ) : y T }, являющееся объединением конечного числа конусов с вершинами в точках множества T.

В главе 1 рассматривается проблема поддержки принятия конструкторских решений на предпроектной стадии процесса проектирования и роль многокритериальных методов в этом процессе. Далее приводится пример многокритериальной задачи, которая должна быть решена в процессе проектирования: дается представление о задаче охлаждения стали в процессе разработки и оптимизации установки для ее непрерывной разливки. В главе показывается, что задача выбора параметров системы охлаждения является нелинейной задачей многокритериальной оптимизации, в которой математическая модель реализована в виде вычислительного модуля. Рассматриваемая задача является задачей многокритериальной оптимизации с четырьмя критериями и 325 параметрами решения.

В первой главе дается качественное описание стохастических адаптивных методов аппроксимации ОЭП, предлагаемых в диссертации и включающих в себя однофазный, двухфазные, трехфазные и генетический методы аппроксимации.

Рассматривается также их сочетание в форме так называемых гибридных методов.

Показатели качества аппроксимации, предлагаемые в данной работе, базируются на понятии полноты аппроксимации (Г.К.Каменев и Д.Л.Кондратьев, 1992). В рассматриваемом случае под полнотой некоторой аппроксимации множества Y* множеством T* будем понимать вероятность того, что из x X следует f(x) T*. Полноту будем обозначать (T*) (или просто BT Условие BT означает, что в аппроксимации множества Y*, задаваемой базой T представлена не менее чем -я доля прообраза. Рассмотрим -окрестность T*, которую обозначим (T*)B Рассмотрим полноту как функцию от, т.е. рассмотрим функцию BT = ((T*)B >0.

Проверка условия BT проводится эмпирически, на основе генерирования случайных точек из X. Пусть используется выборка HBN = {xB1 xBN состоящая из N случайных равномерно где n() – число таких элементов выборки, для которых выполняется включение f(x)(T*)B Тогда (Г.К. Каменев, 2001) B.

. На практике наиболее удобной характеристикой оказался радиус полного покрытия (Bmax – минимальная величина, для B) которой выборочная полнота равна единице (т.е. образы всех сгенерированных точек X принадлежат этой -окрестности аппроксимации).

UОднофазный следующем. На каждой итерации осуществляется оценка качества полученной ранее аппроксимации T* на основе основе образов выборки HBN При автоматической остановке B.

метода проверяется, например, выполнение требований к радиусу полного покрытия Bmax 0 где B0 – заданное положительное решений («популяция наследников»). Для всех точекнаследников вычисляются значения f(x). Полученные критериальные точки используются для оценки качества имеющейся аппроксимации и пополнения базы покрытия.

Во второй главе осуществляется теоретическое изучение свойств предложенных методов аппроксимации ОЭП. Анализ методов основан на применении теории аппроксимации многомерных тел, разработанной Г.К. Каменевым (2001) и называемой «Метод глубоких ям». Теоретическое изучение свойств методов осуществляется с помощью упрощенных алгоритмов аппроксимации.

конечное подмножество из Y, N – объем контрольной выборки и вероятностная мера µBX на B(X). Рассмотрим k-ую итерацию алгоритма. Пусть имеется уже построенная база аппроксимации TBk-1 B.

конечное подмножество из Y, µBX – вероятностная мера на B(X), N – объем контрольной выборки. Пусть задано отображение : X X. Обозначим YP = f((X)). Рассмотрим k-ую итерацию алгоритма. Пусть имеется уже построенная база аппроксимации TBk-1 B.

Bk = (f((xP,k трехфазный алгоритм A3 может быть построен на основе усложнения алгоритма A2 модификации метода генерации контрольной выборки HBN k Пусть заданы TB0 – конечноеP.

подмножество из Y, µBX – вероятностная мера на B(X), N – объем контрольной выборки. Пусть задано отображение : X X.

Рассмотрим k-ую итерацию алгоритма A3. Пусть имеется уже 1) Генерируется выборка HBN k = H N1 H N 2, где выборка H N имеет объем NB1 точек и генерируется на всем множестве X в При исследовании свойств алгоритмов на отображения f и накладываются следующие условия:

для любого конечного множества T из Y и для любого > (**), если для любого конечного множества T из YP и для любого >0 справедливо 1 f 1 (T *) Y B(X).

последовательность баз аппроксимации, порождаемая соответствующим алгоритмом.

Конечность.

UТеорема K() M (, Y ) M(BK()+1 Y), где K() определена в теореме 2.

UСледствие UТеорема для >0, 00, тогда UТеорема теореме 9.

UСледствие lim sup K ( ) m Vol(Y )2 m, где K() определена в теореме 9.

UТеорема