WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 |

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

БЕРЕЗКИН Вадим Евгеньевич МЕТОДЫ АППРОКСИМАЦИИ ГРАНИЦЫ ПАРЕТО В НЕЛИНЕЙНЫХ ЗАДАЧАХ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва – 2008

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

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

Научный консультант:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Каменевым).

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

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

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

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

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

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

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

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

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

Пусть связь между решениями и значениями критериев выбора устанавливается заданным отображением (вектор-функцией) n m n P P P f: RP RP. Пусть X RP – заданное множество допустимых решений. Тогда множество достижимых критериальных векторов (также называемое множеством достижимых целей) определяется как Y = f(X). Будем для определенности считать, что в задаче представляет интерес увеличение значения каждого из m критериев при неизменных значениях других (задача многокритериальной максимизации). В этом случае m P критериальная точка y' RP доминирует по Парето m P критериальную точку y RP, если y' y, т.е. y'B B yB B, i=1,…,m, и i i 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). ОЭП m P определяется как Y* = {yRP : yf(x), xX}. Альтернативное, может быть, более удобное представление ОЭП имеет * m m P P P следующий вид YP = Y + (-RB PB ), где RB PB – неотрицательный конус + + m P пространства RP. Аппроксимация ОЭП строится на основе m P объединения многомерных конусов доминирования (-RB PB ) с + вершинами в точках, близких к паретовой границе. Пусть T – конечное число точек из множества Y=f(X) (база аппроксимации).

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

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

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

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

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

T Проверка условия B B проводится эмпирически, на основе T генерирования случайных точек из X. Пусть используется выборка HB B = {xB B,…, xB B}, состоящая из N случайных равномерно N 1 N N P распределенных точек множества X. Пусть >0, B PB () = n() / N, H где n() – число таких элементов выборки, для которых выполняется включение f(x)(T*)B B. Тогда (Г.К. Каменев, 2001) N P P P(B B()>B PB ()–) *(,N), где *(,N)=1–exp(–2NP ).

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

Pages:     || 2 | 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»