автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Методы аппроксимации границы Парето в нелинейных задачах многокритериальной оптимизации

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

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

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

Специальность 05 13 18

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

АВТОРЕФЕРАТ диссертация на соискание ученой степени кандидата физико-математических наук

Москва - 2008 0031В7319

00316742J,

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

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

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

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

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

доктор технических наук,

профессор Подиновский Владислав Владимирович

кандидат физико-математических наук,

старший научный сотрудник Голиков Александр Ильич

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

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

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

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

РАН

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

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

НМ Новикова

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

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

др)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 1007 (шифр «ИТ-13 4/003»), а также в рамках сотрудничества РАН и Академии Финляндии

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

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

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

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

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

Содержание работы

Во введении обоснована актуальность темы диссертации, сформулированы цели работы, показана научная новизна результатов диссертации и дано краткое описание диссертации по главам Введение содержит математическую постановку задачи аппроксимации ОЭП Математически задача многокритериальной оптимизации, рассматриваемая в данной работе, формулируется следующим образом Пусть заданы п-мерное линейное пространство решений (параметров объекта) R" и от-мерное линейное пространство Rm критериальных векторов Пусть связь между решениями и значениями критериев выбора устанавливается заданным отображением (вектор-функцией) / Rn —> К" Пусть X а К1 - заданное множество допустимых решений Тогда множество достижимых критериальных векторов (также называемое множеством достижимых целей) определяется как Y=fiX) Будем для определенности считать, что в задаче представляет интерес увеличение значения каждого из m критериев при неизменных значениях других (задача многокритериальной максимизации) В этом случае критериальная точка у' е Rm доминирует по Парето критериальную точку у е Rm, если у' >у, те. у', >у„ z=l, ..,т, и у^фу Недоминируемая по Парето (в дальнейшем, просто недоминируемая или паретова) граница множества Y = f(X), определяемая как множество недоминируемых точек у е Y, в этом случае имеет вид P(Y) = {у е Y • (у' е Y. у > у, у' Ф у} = 0} Под множеством Р(Х) парето-эффективных решений понимается подмножество таких решений х е X, что fix) е P(Y) ОЭП определяется как Y* = {y^Rm У^/(х), хеХ} Альтернативное, может быть, более удобное представление ОЭП имеет следующий вид Y*= Y+(-R+m), где R+m - неотрицательный конус

пространства Rm Аппроксимация ОЭП строится на основе объединения многомерных конусов доминирования (-R+m) с вершинами в точках, близких к паретовой границе Пусть Т -конечное число точек из множества Y=f(X) {база аппроксимации). Тогда в качестве аппроксимации ОЭП берется множество

T* = \J{y + (-R™) уеТ}, являющееся объединением конечного

числа конусов с вершинами в точках множества Т

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

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

Показатели качества аппроксимации, предлагаемые в данной работе, базируются на понятии полноты аппроксимации (Г К. Каменев и Д Л Кондратьев, 1992) В рассматриваемом случае под полнотой некоторой аппроксимации множества Y* множеством Т* будем понимать вероятность того, что из хеХ следует fix) е Т* Полноту будем обозначать rj(T*) (или просто г)т) Условие т]т>т] означает, что в аппроксимации множества Y*, задаваемой базой Т представлена не менее чем rj-я доля прообраза. Рассмотрим ¿-окрестность Т*, которую обозначим

(Т*)е Рассмотрим полноту как функцию от е, те. рассмотрим функцию Г}7(£) = 7]((Т*)е), ё>0

Проверка условия 7]Т>г] проводится эмпирически, на основе генерирования случайных точек из X Пусть используется выборка Ядг= {х],...,хц}, состоящая из N случайных равномерно распределенных точек множества X Пусть ¿>0, т]цЫ{е) = п(е) / Ы, где п(е) - число таких элементов выборки, для которых выполняется включение Дх)е (Т*)£. Тогда (Г К Каменев, 2001)

Пгп{£)>ЫХс)-$) * Х*(8,Ы), где /=(^=1^хр(-2Ж2)

Величина %*{8,Ы) - надежность оценки полноты г}т величиной 77 На практике наиболее удобной характеристикой оказался радиус полного покрытия (<?тах) - минимальная величина а, для которой выборочная полнота равна единице (т е образы всех сгенерированных точек X принадлежат этой ¿-окрестности аппроксимации)

Однофазный метод аппроксимации ОЭП состоит в следующем На каждой итерации осуществляется оценка качества полученной ранее аппроксимации Т* на основе построения выборочной функции полноты т\н получаемой на основе образов выборки Ду При автоматической остановке метода проверяется, например, выполнение требований к радиусу полного покрытия £ках<£о, где ¿о - заданное положительное число В диалоговом режиме пользователю предоставляется график }][/(£), после чего он сам решает, останавливать ли процедуру Если процедура не останавливается, то из совокупности точек исходной базы аппроксимации и критериальных точек, полученных при оценке полноты, формируется промежуточная совокупность точек, из которой путем выделения недоминируемых точек создается новая база аппроксимации

При аппроксимации ОЭП в задачах большой размерности или со сложным поведением вектор-функции / оценки качества аппроксимации, полученные в ходе работы однофазного метода, становятся не действенными, т е перестают различать «плохие» и «хорошие» аппроксимации Поэтому вводится новое отображение Ф Х->Х, которое ставит в соответствие случайной

точке xsX некоторую такую «улучшенную» точку х'еХ, что вектор fix') «более близок» к P(Y), чем fix) Для суперпозиции функций / и Ф аналогичным образом определим обобщенную выборочную полноту Т]нф'м(е), равную доле точек хе HN, для которых ДФОс)) е (Т%

Двухфазные методы аппроксимации ОЭП состоят в следующем. На каждой итерации осуществляется оценка качества полученной ранее аппроксимации Г* на основе построения выборочной функции полноты 7]hn{£), получаемой на основе улучшенных с помощью отображения Ф X—>Х образов выборки HN В остальном двухфазные методы полностью аналогичны однофазному

Трехфазные методы отличаются от двухфазных тем, что выборка HN является объединением двух выборок, одна из которых генерируется на всем допустимом множестве, а вторая -только в окрестностях точек аппроксимации При этом первая выборка содержит малое число точек, а вторая - большое число

Помимо многофазных методов построения аппроксимации ОЭП рассматривается генетический метод («оштукатуривание»), который позволяет улучшить уже ранее построенную аппроксимацию Метод состоит в следующем Из прообразов имеющейся базы покрытия Т случайно (но с учетом некоторых ограничений) выбираются пары точек («родители») Между точками каждой такой пары проводится отрезок и на этом отрезке случайным образом выбирается заранее заданное или случайное число q> 1 новых точек множества допустимых решений («популяция наследников») Для всех точек-наследников вычисляются значения fix). Полученные критериальные точки используются для оценки качества имеющейся аппроксимации и пополнения базы покрытия.

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

Упрощенный однофазный алгоритм А1 Пусть заданы Г0 -конечное подмножество из У, N ~ объем контрольной выборки и вероятностная мера /л^) на 3(Х). Рассмотрим к-ую итерацию алгоритма Пусть имеется уже построенная база аппроксимации Ты

1) Генерируется выборка с!в соответствии с мерой ) и рассчитаются образы

2) Ищется точка х*еА^тахр(/(х),Тк_1*) и

хеНки

соответствующее ей максимальное отклонение рк = р (/(хк), Ты*)

3) Строится новое множество Тк = Р{Тк.\ и/(хк)) Упрощенный двухфазный алгоритм А2 Пусть заданы Т0 -

конечное подмножество из У, ) - вероятностная мера на %{Х), N - объем контрольной выборки. Пусть задано отображение Ф X X Обозначим У® =ДФ(Х)) Рассмотрим к-ую итерацию алгоритма Пусть имеется уже построенная база аппроксимации Ты

1) Генерируется выборка с!в соответствии с мерой ¡л^ ) и рассчитываются их образы ДФ( Я/))

2) Ищется точка хф,к е А^тах р{/(Ф(х)),Тк_1 *) и

хеНки

соответствующее ей максимальное отклонение

ркФ = р(ЛФ(хф'к)),Тк.1*)

3) Строится новое множество 7* = Р (Ты иДФ(хф'к))) Упрошенный трехфазный алгоритм АЗ Упрощенный

трехфазный алгоритм АЗ может быть построен на основе усложнения алгоритма А2 модификации метода генерации контрольной выборки Я/ Пусть заданы Т0 - конечное подмножество из У, ц^) - вероятностная мера на -%(Х), Ы- объем контрольной выборки Пусть задано отображение Ф X X Рассмотрим к-ую итерацию алгоритма АЗ Пусть имеется уже построенная база аппроксимации Ты

1) Генерируется выборка , где выборка Н^

имеет объем N1 точек и генерируется на всем множестве X в соответствии с мерой ц^) Выборка Нкм имеет объем М2 и

генерируется каким-либо определенным образом на подмножествах X. Считаются их образы ДФ(Ян*))

2) Ищется точка хф,к е Argr№x.p(f(ф(x)),тk_l*) и

соответствующее ей максимальное отклонение

Рк = Р(ДФ(*ФЛ)), Ты*)

3) Строится новое множество Ти = Р (Тк.\ и ДФ(хф'!)))

При исследовании свойств алгоритмов на отображения /и Ф накладываются следующие условия

Условие (*) Отображение /удовлетворяет условию (*), если для любого конечного множества Г из 7 и для любого ¿>0 справедливо /'\(Т*)епТ)еЗ(Х)

Условие (**). Отображения / и Ф удовлетворяют условию (**), если для любого конечного множества Т из I0 и для любого ¿>0 справедливо Ф~! [/_1 п 7Ф)] е.ВД

Доказаны следующие свойства алгоритмов Пусть {7*} -последовательность баз аппроксимации, порождаемая соответствующим алгоритмом Конечность

Теорема 2 (для А1) Для любого ¿>0 существует минимальный номер К(е) такой, что рдв)+х<е

Теорема 9 (для А2 и АЗ) Для любого ¿>0 существует минимальный номер К(е) такой, что рфц£)+1<£ Сходимость.

Теорема 3 (для А1) Пусть / удовлетворяет (*) Тогда для любых £>0, 0<?7<1 существует минимальный номер К(а,г;) такой, что надежность выборочной оценки полноты в виде ^х(гЯ)(е)>1? не меньшех*(г/,Ы)

Теорема 10 (для А2 и АЗ). Пусть /и Ф удовлетворяют (**) Тогда для любых ¿>0, 0<т}<1 существует минимальный номер К(е,т]) такой, что надежность выборочной оценки полноты в виде

ЧЪм ^ > 11 не меньше

Скорость сходимости Пусть А - произвольное множество У1к(е,А) - минимальное число точек метрической г-сети для множества А У1(е, А) - минимальное число множеств диаметра не

более чем 2s, покрывающих множество А. 3ÏÏ(s,A) -максимальное число точек г-различимого множества А (те такого множества, точки которого удалены друг от друга не менее, чем на s) (А H Колмогоров и В M Тихомиров, 1959) Пусть

Ще, А) = lim rnf Щ£ - v, А)

v->0+

Теорема 4 (для AI) Пусть ¿>0, тогда К(е)<Ш(е, Y)< Ш(рце)+\, Y), где К(е) определена в теореме 2

Следствие 2 теоремы 4 (для AI) Пусть dr (у', у") = шах{ | у[ - у" |} и объем Vol(f)>0, тогда

I

limsup K(s)sm < Vol(7)2m, где K(s) определена в теореме 2

Теорема 5 (для AI) Пусть/удовлетворяет условию (*), тогда для ¿>0, 0<77<1 К(£,ф< Ш(£, Y) < Ш(рк{е,т, Y), где К(е,ф определена в теореме 3

Следствие 2 теоремы 5 (для AI) Пусть dY(y',y") - max{\ у[ - у" \} и объем Vol(F)>0, тогда

I

limsupK(e,î])sm < Vol(7)2™, где K(s,rj) определена в теореме 3

г->+0

Теорема 11 (для А2 и A3) Пусть ¿>0, тогда

К(ё)<Ж(е,Уф)< Ш1(р®(г)+1,7Ф), где К(е) определена в теореме 9

Следствие 2 теоремы 11 (для А2 и A3) Пусть

dY(у',у") = шах{| у\ -у"|} и объем Уо1(У®)>0, тогда

I

limsupK(ß)8n' < Уо1(Уф)2"', где К(е) определена в теореме 9

ff-HO

Теорема 12 (для А2 и A3) Пусть / и Ф удовлетворяют условию (**), тогда для е>0, 0<?/<1 K(s,т])< Ш(£,¥ф )< Ш(рфКШ)+,, 7Ф), где K{s, ф определена в 10

Следствие 2 теоремы 12 (для А2 и A3) Пусть dY(y\y") = max{\y'l-y'\} и объем Vol^X), тогда

\\т?,Щ)К{Е,Г1)£т <Уо1(Гф)2'я, где К(£,г/) определена в

£->+0

теореме 10

Эффективность Полученные оценки позволяют сравнить построенные с помощью алгоритмов А1-АЗ аппроксимации с аппроксимациями, построенными с помощью любого другого (гипотетического) метода построения метрических е-сетей. Особый случай представляет собой Г® = Р(У), здесь алгоритм А2 позволяет построить не только аппроксимацию ОЭП для У, но и аппроксимацию паретовой границы Р(Т), заданную в виде конечной г-сети точек, принадлежащих Р(У) Сравним построенную таким образом с помощью алгоритма А2 аппроксимацию множества Р(У) с аппроксимацией, построенной с помощью любого другого (гипотетического) метода построения метрических ¿•-сетей для множества Р(У)

Теорема 17 (для А2) Пусть Б - произвольная //'ед н-сеть для Р(У), где К(ё) - минимальный номер итерации такой, что рФт+1<£ Тогда

саге!.?

сагсЦ^) Щрк( 1Щ

Следствие 1 теоремы 17 (для А2) Пусть Уо1(Р(У))>0 в В.'", Кт = Вт'@Кт"п' Пусть Б - произвольная рфвд+гсеть для Р(Г), где К(£) - минимальный номер итерации такой, что /Лад+1<£ Тогда

сагс! 5"

1шхпГ->

сагаТК(е)

В завершении главы на основе результатов исследования формулируются практические алгоритмы методов аппроксимации ОЭП, изучаемых в диссертации однофазного, многофазных и генетического метода «оштукатуривания»

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

Первая система реализована в среде MS Excel и основана на использовании однофазного метода аппроксимации Вектор-функция fix) здесь задается либо формулой на листе Excel, либо с помощью макроса на встроенном в MS Excel интерпретаторе Visual Basic Достоинством системы, являющимся следствием ее реализация в среде MS Excel, является простота ее использования для массового пользователя Система визуализации позволяет осуществить диалоговую визуализацию паретовой границы и дает возможность указать предпочтительную целевую точку нажатием компьютерной мыши

Вторая система написана на языке С++ и используется в среде Windows ХР Система реализует однофазный, двух- и трехфазные методы Вектор-функция fix) в системе может быть задана несколькими способами в виде DLL библиотеки или исполняемого ЕХЕ файла, а также в среде MatLab Наиболее простая возможность - реализация вектор функции / в среде MatLab 6 5 или выше, достоинство такого подхода в том, что с этой задачей может справиться широкий круг пользователей, знакомых со средой MatLab и умеющий использовать мощный математический пакет среды MatLab Недостатком такой реализации вектор функции / является невысокая скорость исполнения ее вычислений Этот недостаток отсутствует, когда вектор-функция fix) реализована в виде DLL библиотеки или исполняемого ЕХЕ файла В систему встроен удобный модуль визуализации паретовой границы и спецификации предпочтительной точки на этой границе

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

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

Первый класс задач сформулирован с использованием функции Шекеля, широко применяемой при тестировании методов нелинейной оптимизации s(x)-\!{(х-а)2+с). Эти модели характеризуются простым видом ОЭП, причем с помощью варьирования параметра с можно регулировать высоту и крутизну «пиков» критериальных функций, воздействуя тем самым на форму паретовой границы, что дает возможность сравнивать работу изучаемых методов аппроксимации в различных условиях Рассматривались задачи разной размерности (от п~2 и т~ 2 до п-\2 и т= 5) Далее методы аппроксимации ОЭП изучаются на многокритериальной задаче, построенной с использованием экспоненциальной функции

j(jc,,*2) = 3(l-jci)2e-3cii"(*2+1)2 -

и 1 1 2) 3

Задача имеет размерность п~2 и т=5, а паретова граница -довольно сложную форму Последние эксперименты проводятся на задачах, построенной с использованием функции типа

е~ах 5ш —, а>0, х>§, где 5 - малое положительное число. Эта х

функция ведет себя сложным образом в окрестности нуля Данный эксперимент показывает, как ведут себя различные методы аппроксимации с «неудобными» критериальными вектор-функциями

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

• Трехфазный метод в большинстве задач оказался менее экономичным по числу расчетов вектор-функции / по сравнению с двухфазным

• Трехфазные методы сами по себе часто имеют медленную сходимость Причиной этого может оказаться медленное выявление новых точек, в окрестностях которых также следует искать эффективные решения Комбинирование двух-и трехфазных методов позволяет устранить этот недостаток

В пятой главе описываются эксперименты с многофазными методами аппроксимации ОЭП в многокритериальной задаче выбора параметров вторичного охлаждения стали в процессе ее непрерывной выплавки Как было уже сказано, задача имеет 325 управлений и 5 критериев (Л-^), первый из которых (/0 не учитывается при решении задачи

Исследовались следующие проблемы

• Сравнение аппроксимации паретовой границы с использованием двух- и трехфазных методов

• Изучение комбинаций двухфазных и трехфазных методов

• Применение генетического метода

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

Наилучший результат дало следующее сочетание методов

1 Двухфазный метод проделано 4 итерации с объемом выборки N=149 точек

2 Трехфазный метод с N=149 Метод сошелся уже на третьей итерации

3 В заключение к построенной аппроксимации были применены две итерации генетического метода Найденные с помощью построенной аппроксимации

приемлемые сочетания критериев сравниваются с достижимой точкой, полученной финскими специалистами, также исследовавшими данную задачу

/1 = 2 11708, Л = 0,73 = 0, /4 = 0,75 = 0 20727

Применение МДЦ позволило найти набор альтернатив, показанных в таблице

h Ji /3 /4 /5

m. 2374 2 1734 0 0 0 01525

m. 3242 2 1624 0 0 00001 0 0 0994

m. 150 2 1742 0 0 0002 0 0 0933

m. 47 2.4226 0 0 0219 0 0 0431

m. 3626 2 4051 0 0 0145 0 0 0488

Как можно видеть, точка 2374 доминирует точку, найденную финскими учеными Кроме того, приводятся некоторые разумные альтернативы, позволяющие за счет маленького послабления критерия J$ в полтора раза улучшить значение J5 Приводится обсуждение одного из полученных нами решений

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

В заключении приводятся основные результаты диссертации

Основные результаты диссертации опубликованы в работах

1 Березкш BE., Каменев ГК, Лотов А В Реализация метода достижимых целей для нелинейных моделей в MS Excel, М. ВЦ РАН, 2000

2 Miettinen К, Beriozhn V, Kamenev G, and Lotov A (2000) Graphical and interactive decision support tool for nonlinear multiobjective optimization Reports of Dept of Math Information Technology, N В15/2000, Jyvaskyla, Finland University of Jyvaskyla, 2000,16p

3. Lotov A V, Kamenev GK, Berezkin VE (2001) Conceptual Design of Future Aircrafts Using New Graphic Method for Mathematical Model Analysis // Working Paper N33, Fachbereich

Wirtschaftwissenschaften, Institute fuer Wirtschaftsinformatik University of Siegen, Germany, 2001, 23 p

4 Berezhn VE, Kamenev GK, Lotov A V (2001) Experimental Software of Nonlinear Feasible Goals Method // Тез докл 3-й Моек междун конф по исследованию операций М. ВЦ РАН, 2001 С 17-18

5. A Lotov, G Kamenev, V Berezkin Software for Visualization of the Feasible Set in Criterion Space m Nonlinear MCDA Problems // European Working Group "Multicriteria Aid for Decisions", Series 3, n4, Fall 2001

6 Лотов AB, Каменев ГК, Березкин BE Аппроксимация и визуализация паретовой границы для невыпуклых многокритериальных задач // Доклады Академии наук, 2002, том 386, N6, с 738-741

7 Березкин BE Анализ и реализация методов аппроксимации паретовой границы для нелинейных систем, М ВЦ РАН, 2002

8 Miettinen К, A Lotov, G Kamenev, and V Berezhn Integration of Two Multi-objective Optimization Methods for Nonlinear Problems Optimization Methods and Software. V 18, no 1, 63-80 (2003).

9 Berezkin V, Kamenev G, Lotov A, Miettinen K. (2003) Application of Pareto Frontier Visualization for Analysing Cooling Strategies in Continuous Casting of Steel Reports of Dept of Math Information Technology, N В 8/2003, Jyvaskyla, Finland University of Jyvaskyla, 22 p

10 VE Berezkin and A V Lotov (2004) Two-phase Method for Approximating the Edgeworth-Pareto Hull for Non-linear Models, Proc of the 4th Moscow International Conference on Operations Research (ORM2004), Maks Press, Moscow, 34-38

11 Lotov, V Berezkin, G Kamenev, Miettinen К (2005) Optimal Control of Cooling Process m Continuous Casting of Steel Using a Visualization-Based Multi-Criteria Approach // Applied Mathematical Modelling, 29(7), 653-672

12 Березкин BE (2005) Эксперименты по аппроксимации паретовой границы для нелинейных систем М.- ВЦ РАН, 52 стр

13 Березкин В Е, Каменев Г К, Лотов А В (2006) Гибридные адаптивные методы аппроксимации невыпуклой

многомерной паретовой границы // ЖВМиМФ 2006 Т 46(11) С 2009-2023 14 Березкин В.Е, (2007) Экспериментальный анализ аппроксимации оболочки Эджворта-Парето для нелинейных моделей // Труды V Московской межд конф. по исследованию операций (Москва, 10-14 апреля 2007), М изд МАКС Пресс, 2007, стр 138-139

Основные результаты диссертации представлены в работах [6, 7, 9, 11, 12, 13]. В работе [6, 13] концепции одно- и двухфазной оценки качества аппроксимации разработаны совместно с зав сектором д.ф.-м н А.В Лотовым и научным руководителем д ф.-м.н Г К Каменевым Разработка и реализация алгоритмов и проведение экспериментов проведены автором самостоятельно Трехфазный и генетические методы разработаны, реализованы и экспериментально исследованы автором самостоятельно Теоретический анализ одно- и двухфазных методов осуществлены совместно с научным руководителем Г.К Каменевым. В работах [2, 8, 9, 11] разработка модели в задаче непрерывной выплавки стали принадлежит финским ученым, разработка двухфазного метода - совместно с А.В Лотовым и Г.К Каменевым, реализация и проведение расчетов осуществлены автором самостоятельно Работы [7, 12] выполнены автором самостоятельно

Напечатано о готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписано к печати 15 04 2008 г Формат 60x90 1/16 Услпечл 1,25 Тираж 100 экз Заказ 174 Тел 939-3890 Тел/Факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им МВ Ломоносова, 2-й учебный корпус, 627 к

Оглавление.

Введение.

Глава 1. Некоторые проблемы предпроектной стадии проектирования технических систем.

1.1. Предпроектная стадия процесса проектирования.

1.2. Пример проблемы, возникающей на предпроектной стадии.

1.2.1 Краткое описание модели процесса охлаждения стальной полосы.

1.2.2. Функции потерь.

1.2.3 Проектные решения. Параметры процесса охлаждения.

1.3. Аппроксимация оболочки Эджворта-Парето в нелинейном методе достижимых целей.

Глава 2. Изучение методов аппроксимации оболочки Эджворта-Парето.

2.1. Полнота аппроксимации.

2.1.1. Основные обозначения.

2.1.2. Полнота аппроксимации.

2.2. Упрощенный однофазный алгоритм А1.

2.3. Свойства алгоритма А1.

2.3.1. Конечность А1.

2.3.2. Сходимость А1.

2.3.3. Скорость сходимости А1.

2.3.4. Эффективность А1.

2.4. Упрощенный двухфазный алгоритм А2.

2.5. Полнота аппроксимации для А2.

2.6. Свойства алгоритма А2.

2.6.1. Конечность А2.

2.6.2. Сходимость А2.

2.6.3. Скорость сходимости А2.

2.6.4. Эффективность А2.

2.7. Алгоритм А2 в случае Y°=P(Y).

2.7.1. Скорость сходимости.

2.7.2. Эффективность.

2.8. Упрощенный трехфазный алгоритм A3.

2.9. Полное описание методов аппроксимации.

2.9.1. Однофазный алгоритм.

2.9.2. Двухфазные алгоритмы.

2.9.3. Трехфазные алгоритмы.

2.9.4. Генетический метод «оштукатуривания».

Глава 3. Программное обеспечение метода достижимых целей для нелинейных моделей.

3.1. Реализация однофазного метода в MS Excel.

3.2. Реализация однофазных, двух- и трехфазных методов на языке С++.

3.3. Программный комплекс «Метод достижимых целей».

Глава 4. Эксперименты с модельными задачами.

4.1. Методика проведения экспериментов.

4.1.1. Сравнение методов по результатам аппроксимации.

4.1.2. Попарное сравнение аппроксимаций ОЭП.

4.2. Исследование методов на основе использования функции Шекеля.

4.2.1. Исследования методов на двухкритериальных задачах.

4.2.2. Исследования трех- и пятикритериальных задач.

4.2.3. Сравнение однофазного и трехфазного методов.

4.3. Исследования многоэкстремальной задачи.

4.4. Исследование на функции с многочисленными локальными экстремумами.

4.4.1. Модель с параметром а= 1.

4.4.2. Модель с параметром а= 10.

Математическое моделирование широко используется для поддержки поиска эффективных решений сложных проблем, в том числе проблем планирования и проектирования. При анализе математических моделей в процессах планирования и проектирования важную роль играют многокритериальные методы, позволяющие учесть противоречивые требования, предъявляемые к рассматриваемым планам, проектным и конструкторским решениям. Среди таких методов важнейшую роль играют методы многокритериальной оптимизации, в которых заранее известно направление улучшения значений отдельных (частных) критериев. В рамках этих методов изучается множество решений, эффективных по Парето, и соответствующая недоминируемая (паретова) граница множества достижимых критериальных векторов [1, 7, 31]. Один из главных подходов современной многокритериальной оптимизации представлен методами, направленными на аппроксимацию паретовой границы множества достижимых критериальных векторов и на дальнейшее информирование лица, принимающего решение (ЛПР) о недоминируемых критериальных векторах ([2, 3, 5, 7, 8, 9, 10, 13, 14).

Одним из методов, основанных на аппроксимации паретовой границы, является метод достижимых целей. Этот метод базируется на идее, сформулированной в работах Н.Н. Моисеева [15] и Г.С. Поспелова [16]: для поддержки выбора наиболее перспективных вариантов в задачах проектирования сложных систем предлагалось использовать визуализацию множества реализуемых характеристик объекта проектирования. Компьютерная визуализация этих многомерных множеств должна помочь конструкторам и проектировщикам оценить потенциальные возможности объекта проектирования, выявить связь различных характеристик объекта и найти его перспективные варианты. В методе достижимых целей [25, 26, 27] описанная идея реализуется с использованием интерактивной визуализации и анимации паретовой границы. Такая визуализация оказывается возможной при предварительной аппроксимации множества достижимых критериальных векторов (или другого, более широкого множества — оболочки Эджворта-Парето (ОЭП) множества достижимых критериальных векторов, являющейся максимальным множеством, имеющим ту же паретову границу) с помощью относительно простых фигур (многогранников, конечного числа конусов и т.д.). Интерактивная визуализация и анимация паретовой границы осуществляется путем расчета и изображения двумерных сечений аппроксимации. ЛПР на основе визуального изучения паретовой границы осознанно выбирает предпочтительное достижимое сочетание значений критериев (достижимую цель), а последующий расчет соответствующего парето-эффективного решения осуществляется компьютером автоматически.

Применение метода достижимых целей (МДЦ) для поиска парето-эффективных решений экономических задач началось еще в семидесятых годах прошлого века [17]. С середины восьмидесятых годов МДЦ используется для поиска парето-эффективных стратегий улучшения состояния окружающей среды (см., например, [22, 23, 24, 25]). Дальнейшее развитие МДЦ может быть связано с его применением в компьютерных сетях, где метод может быть использован как в системах электронной торговли, так и для поддержки коллективного выбора экологических и других индивидуальных и коллективных решений.

Надо подчеркнуть, что результаты, полученные в 1980-1990-х годах были основаны на анализе выпуклых, в том числе и линейных моделей; для этого были разработаны адаптивные итеративные методы полиэдральной аппроксимации выпуклых множеств, асимптотически оптимальные по скорости сходимости и сложности описания аппроксимации, в которых аппроксимирующие многогранные множества строятся с помощью расчета значений опорной функции аппроксимируемого множества ([25, 26, 27]).

В нелинейном невыпуклом случае в [46, 47] был предложен и исследован стохастический адаптивный метод аппроксимации множества всех достижимых критериальных векторов системой шаров. Такой подход, однако, не был предназначен для аппроксимации самой паретовой границы и давал о ней лишь общее представление.

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

Математически задача многокритериальной оптимизации, рассматриваемая в данной работе, формулируется следующим образом. Пусть заданы «-мерное линейное пространство решений (параметров объекта) R11 и т-мерное линейное пространство Rm критериальных векторов. Пусть связь между решениями и значениями критериев выбора устанавливается заданным отображением (вектор-функцией) /: R" —» Rm, заданным, может быть, алгоритмически. Пусть Хс~R" - заданное множество допустимых решений. Тогда множество достижимых критериальных векторов (также называемое множеством достижимых целей) определяется как Y=J(X). Будем для определенности считать, что в задаче представляет интерес увеличение значения каждого из т критериев при неизменных значениях других (задача многокритериальной максимизации). В этом случае критериальная точка/ б R'" доминирует по Парето критериальную точку у е R'", если / >у, т.е. у\ >у„ i=\,.,m, и у'&у. Недоминируемая по Парето (в дальнейшем, просто недоминируемая или паретова) граница множества Y =j{X), определяемая как множество недомииируемых точек у е Y, в этом случае имеет вид

P(Y)={ye Y: {/ б У:У>у,У*у}=0}.

Под множеством Р(Х) парето-эффективных решений понимается подмножество таких решений х е X, что/(х) е P(Y).

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

Y* = {yeRm:y<Ax),xeX}.

Альтернативное, может быть, более удобное представление ОЭП имеет следующий вид

Y*- Y+ (~R+m), где R+m— неотрицательный конус пространства R"1 (здесь под суммой некоторых множеств А и В подразумевается сумма по Минковскому, т.е. множество {у=а+Ь | аеА, ЬеВ}). Важным свойством множества Y* является то, что оно является максимальным (по включению) множеством, таким что P(Y)= P(Y*). При этом остальные границы ОЭП имеют достаточно простой вид. Таким образом, задача аппроксимации ОЭП близка по своему содержанию к задаче аппроксимации паретовой границы. Аппроксимация ОЭП, в рамках которой паретова граница аппроксимируется как часть границы ОЭП, а не самой паретовой границы — одно из важных отличий МДЦ от остальных методов, направленных непосредственно на аппроксимацию паретовой границы (хотя в некоторых из них, как будет видно далее, уже строили аппроксимацию ОЭП, не формулируя это явно).

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

К первому подходу относятся методы покрытия допустимого множества X шарами, радиусы которых зависят от констант Липшица критериальных функций. Методы такого типа были предложены в [2] на основе обобщения ставшего уже классическим однокритериального метода покрытия, разработанного Ю.Г.Евтушенко в конце 1960х [53, 4]. Метод покрытия требует выполнения условия Липшица для вектор-функции / на всем X с некоторой константой L. Аппроксимация Р(Х) ищется в виде такого внутренне устойчивого (т.е. не содержащего точек, доминируемых другими точками этого множества) конечного множества АаК, называемого е-оптимальным решением, что для любой точки х*еР(Х) найдется точка из А, не худшая ее по всем критериям более чем на е. Отметим, что этот подход предназначен для решения задач относительно малых размерностей пространства решений («<10). Отметим, что множество А порождает две аппроксимации паретовой границы: множество {f{A)+(-R+m)} является внутренней аппроксимацией ОЭП, а множество {(Ду1)+£)+ (-R+"')} - его внешней аппроксимацией, где s - вектор с координатами е.

Ко второму подходу относятся методы, основанные на свертывании критериев в единственный параметрический критерий оптимизации и последующем решении большого числа задач глобальной скалярной оптимизации при различных значениях параметров [8, 13]. Этот подход широко используется в практических задачах. В качестве свертки обычно берется либо расстояние от идеальной точки в метрике Чебышева [13], либо свертка Гермейера [31], либо какие-то их модификации [32]. На основе использования постоянных Липшица можно оценить неточность аппроксимации ([33, 34, 35, 36, 37, 5, 6, 7, 8). Отметим, что, согласно этим оценкам точности аппроксимации, в прикладных задачах для достижения разумной точности требуется решить не реализуемое практически число задач глобальной скалярной оптимизации из-за того, что используемые глобальные оценки постоянных Липшица обычно очень неточны. Кроме того, решение каждой из таких задач глобальной скалярной оптимизации зачастую представляет собой сложную проблему из-за многоэкстремальности оптимизируемых функций. Отметим также примыкающий к этой группе методов теоретический алгоритм второго порядка [38], [39], позволяющий с помощью модифицированной функции Лагранжа учесть сложные функциональные ограничения на множество решений.

К третьему подходу относятся методы случайного поиска - расчет критериальных векторов в случайных (или квазислучайных) точках изХи отбор педоминируемых векторов и соответствующих решений (Parameter Space Investigation, PSI-метод: [10, 11, 12]). Ясно, что при расчете критериальных векторов для достаточно большого числа точек, равномерно распределенных в

X, можно получить аппроксимацию паретовой границы с любой степенью точности. С другой стороны, ясно, что для получения достаточно точной аппроксимации паретовой границы число таких точек в многокритериальных задачах должно быть нереализуемым на практике, если размерность пространства решений велика, а значения вектор-функции /(х) подвержены колебаниям. В таких методах случайного поиска оценка качества аппроксимации обычно не осуществляется.

К этим методам примыкают методы типа «имитированного охлаждения (отжига)», в которых на основании аналогии с физическим процессом остывания строится алгоритм случайного поиска решения, причем поиск лучшего решения осуществляется во все более узкой окрестности текущего решения. Этот подход был распространен на задачи многокритериальной оптимизации [28, 29, 30]. Как и во всех методах случайного поиска, в этом подходе анализ сходимости, за исключением тривиальных утверждений, также не производится.

К четвертому подходу относятся эволюционные методы одновременного поиска большого числа точек, близких к паретовой границе. Методы основаны на биологических аналогиях. В настоящее время активно изучаются и развиваются три основные подгруппы эволюционных методов -генетические методы, методы, имитирующие поведение стаи птиц (Particles Swarm Optimization), и методы, имитирующие поведение колонии муравьев (Ant Colony Optimization).

Начало применению генетических алгоритмов для решения задач оптимизации положил Д.Холланд в 1975 г. [40]. Фундаментальный вклад в развитие генетических методов внес Д.Гольдберг [41]. Генетические алгоритмы применялись для решения различных задач оптимизации, в том числе для конструирования технических систем, составления расписаний, маршрутизации транспортных средств, компоновки оборудования, раскроя материалов и др. Идея генетических методов основана на рассмотрении ансамбля хромосом, совершенствующихся в процессе многошаговой процедуры. На каждом шаге происходят случайные изменения (мутации) хромосом, формируются новые хромосомы на основе случайного сочетания пар хромосом, а затем по некоторым правилам отбирается заданное число хромосом, составляющих новое поколение. В последние годы эта идея была использована в задачах многокритериальной оптимизации [14, 43]. В эволюционных методах обычно используются только сравнительные оценки качества аппроксимации для нескольких аппроксимаций паретовой границы или численно построенная аппроксимация сравнивается с уже известной паретовой границей (см. [14, 43]).

Подчеркнем, что к первому классу методов (с использованием постоянной Липшица) относятся методы первых двух подходов, а ко второму классу (без использования постоянной Липшица) - методы третьего и четвертого подходов. В данной работе предлагаются и изучаются методы аппроксимации ОЭП, относящиеся ко второму классу методов - в них не используются постоянные Липшица критериальных функций. Более того, предполагается, что вектор-функция / может быть задана с помощью вычислительного модуля («черного ящика»), структура которого не известна или не может быть использована при решении задачи многокритериальной оптимизации. Вычислительный модуль может, скажем, осуществлять имитацию динамического процесса или решать краевую задачу математической физики. Так, в данной работе в качестве приложения методов исследуется задача оптимизации параметров оборудования, предназначенного для охлаждения стали в процессе ее непрерывной разливки. В этой задаче требуется найти оптимальные краевые условия в задаче, решение которой (в том числе и значения вектор-функции f) находятся с помощью некоторого имеющегося вычислительного модуля, который по заданным краевым условиям решает краевую задачу в частных производных и рассчитывает значения критериев. В таком случае уже не приходится надеяться на получение информации о величине или даже наличии констант Липшица. Поэтому в методах, разрабатываемых в данной работе, предположения о константах Липшица критериальных функций рассматриваемых моделей в дальнейшем не делаются. Это является важнейшим требованием к разрабатываемым методам, определяющим многие их черты, в частности, использование статистических методов оценки качества аппроксимации.

Разрабатываемые нами методы являются развитием стохастического адаптивного метода аппроксимации неявно заданных невыпуклых множеств, предложенного в [46] и [47], на случай задачи аппроксимации ОЭП (однофазный метод). Для этой задачи, однако, оказалось эффективным использовать комбинирование стохастического метода с локальной оптимизацией и сжатием области поиска (многофазные подходы), распространенные в задачах невыпуклой однокритериальной оптимизации. Синтез предложенных многофазных стохастических адаптивных методов аппроксимации ОЭП с генетическим подходом позволяет строить гибридные методы аппроксимации ОЭП, также рассматриваемые в настоящей работе.

В методах, разрабатываемых в данной работе, присутствуют основные черты всех четырех подходов к аппроксимации паретовой границы, описанных выше. По аналогии с работой [2], а также с более поздней работой [45] используется идея аппроксимации ОЭП объединением многомерных конусов доминирования с вершинами в точках, близких к паретовой границе. Пусть Т -конечное число точек из множества Y-J(X) (база аппроксимации). Тогда в качестве аппроксимации ОЭП берется множество r* = U {y + i-R+y-yzT}, являющееся объединением конечного числа конусов с вершинами в точках множества Т. Главное отличие разрабатываемых методов от методов [2] состоит в том, что нами не используется информация о значениях или наличии констант Липшица и не осуществляется покрытие множества X.

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

Сочетание стохастических методов поиска оптимального решения с методами локальной однокритериальной оптимизации сверток критериев дополняется адаптивным случайным поиском, развивающим идеи многокритериального «имитированного охлаждения» [28, 29, 30] и состоящем в сжатии области поиска на основе обработки информации о прообразах точек паретовой границы.

Подчеркнем, что использование статистического оценивания качества построенной аппроксимации ОЭП, основанного на генерировании случайных точек множества X, является важной особенностью разработанных методов. Именно применение статистических оценок позволяет отказаться от использования оценки качества аппроксимации паретовой границы на основе постоянных Липшица. Пригодная для использовании на практике оценка качества аппроксимации множества достижимых критериальных векторов в невыпуклых нелинейных задачах многокритериальной оптимизации впервые была предложена в работе [46]. В настоящей работе используются более сильные оценки качества аппроксимации, предложенные в [47]. Для оценки качества аппроксимации ОЭП потребовалась модернизация этой оценки на основе решения задач скалярной оптимизации.

Наконец, в гибридных методах, наряду с другими методами, используется новый генетический метод аппроксимации ОЭП, называемый методом «оштукатуривания». В отличии от обычных многокритериальных генетических методов [14, 43], которые начинают процесс аппроксимации с неэффективных решений и требуют проведения огромного объема вычислительной работы прежде чем будут найдены решения, близкие к парето-оптимальным, метод «оштукатуривания» направлен на улучшение достаточно хорошей аппроксимации, построенной с помощью методов локальной оптимизации и характеризуемой малым числом недоминируемых точек. Одновременно метод «оштукатуривания» придает аппроксимации графически более выразительную форму за счет дополнения исходной аппроксимации большим числом новых промежуточных недоминируемых точек, что делает паретову границу более гладкой.

Последнее свойство метода «оштукатуривания» особенно важно в связи с тем, что центральным шагом метода достижимых целей является визуализация паретовой границы. Насколько нам известно, вопрос о визуализации паретовой границы как целого (а не ее отдельных точек) в невыпуклом случае при более чем двух-трех критериях даже не ставился. В данном исследовании визуализация использует синтез идей, предложенных в [25] для визуализации паретовой границы в выпуклом случае, и идеи об использовании набора конусов для визуализации паретовой границы конечного числа точек [45]. Заранее построенная аппроксимация ОЭП используется для быстрого расчета и изображения на дисплее всевозможных наборов двумерных сечений этого множества в диалоге с пользователем. При этом наложение сечений дает представление о паретовой границе для трех критериев, а возможность анимации трехкритериальной картины позволяет оцепить влияние и других критериев. Пользователь получает представление не только о возможных предельных значениях характеристик объекта, но и о связи величин критериев на паретовой границе (о так называемых критериальных, или эффективных, замещениях).

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

Диссертация состоит из введения, пяти глав, заключения и списка литературы.

Вывод

Генетический метод «оштукатуривания» позволил существенно обогатить вид паретовой границы, и как следствие найти на ней и проанализировать новые точки, дающие хорошие сочетания значений критериев.

Заключение. Основные результаты диссертации, выносимые на защиту

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

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

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

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

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

4.5. Заключение

На основе проведенных экспериментов на модельных задачах можно сделать следующие выводы:

1. Даже при удовлетворительных показателях сходимости методов (скажем, радиуса полного покрытия или полноты аппроксимации) качество аппроксимации может отличаться существенно, что подтверждают графики функций включения.

2. Трехфазные методы обычно строят более качественную аппроксимацию, чем двухфазные или однофазный.

3. Для задач малой размерности (2x2) экономичнее применять однофазный метод вместо многофазных, может быть, за исключением задач со сложным поведением вектор-функции / (например, как в последней задаче).

4. Трехфазный метод в большинстве задач оказался менее экономичным по числу расчетов вектор-функции/по сравнению с двухфазным.

5. Преимущество одних сверток над другими в проведенных экспериментах однозначно выявлено не было. В примерах с функцией Шекеля существенно лучше показала себя свертка Гермейера, а в примерах с синусами обе свертки уступили по качеству квадратичной свертке.

6. Показатель «General Distance» оказался мало эффективен для сравнения баз аппроксимации. Из-за усреднения расстояний, используемых в формуле его расчета, далекие, и тем самым более ценные точки не принимаются в расчет, если они оказываются в меньшинстве. Поэтому в рассмотренных примерах показатель «General Distance» не выявил серьезных отличий между сравниваемыми аппроксимациями.

7. Трехфазные методы сами по себе часто имеют медленную сходимость. Такой эффект особенно существенен в задачах большой размерности. Причиной этого может оказаться выявление новых точек, в окрестностях которых следует искать эффективные решения. Поэтому важно комбинировать двух- и трехфазные методы. Этот вопрос подробно рассмотрен в главе 5.

Глава 5. Использование метода достижимых целей для анализа проблемы выбора параметров оборудования

В данной главе описывается применение МДЦ в задаче многокритериального выбора параметров системы вторичного охлаждения стали в процессе ее непрерывной разливки. При этом экспериментально сравнивалась эффективность аппроксимации ОЭП на основе однофазных, двух-и трехфазных методов и была разработана разумная стратегия сочетания методов. В завершении процесса аппроксимации был применен генетический метод «оштукатуривания» после чего рассмотрены некоторые недоминируемые точки и проанализировано одно из решений.

5.1. Построение аппроксимации однофазным методом

Итак, рассматривается задача выбора параметров процесса вторичного охлаждения стали в процессе ее непрерывной выплавки. Как было сказано в первой главе, задача имеет пять критериев (J[,.,J5), при этом критерий J\ при поиске параметров не учитывается. Приведем еще раз смысл каждого из критериев:

• J\ - функция отклонения температуры на поверхности стальной полосы от желаемой температуры;

• Ji — ограничение на температуру поверхности стальной полосы;

• J3 - ограничение на скорость охлаждения поверхности полосы;

• J4 — ограничение на длину жидкой сердцевины полосы;

• J5 — ограничение на минимальное значение в точке разгиба стальной полосы.

Задача имеет 325 управлений (параметров), соответствующих величине напора водяных струй, использующихся для охлаждения полосы стали.

Отметим, что ранее над задачей охлаждения стальной полосы работали K.Miettinen, M.Makela и T.Mannikko [52]. Задача решалась с помощью метода NIMBUS (Nondifferentiable Interactive Multiobjective BUndle-based optimization System) ([59, 60, 61]) и в результате было найдено следующее сочетание критериев:

Jr=2.11708, J2=0, J3=0, J4=0, J5=0.20727. (5.1)

В данной работе мы сравним наши результаты с точкой (5.1), которую будем условно называть точкой Миеттннен,

Прежде, чем описывать аппроксимацию ОЭП на основе многофазных и генетических методов, продемонстрируем результаты применения однофазного метода. В процессе аппроксимации было сделано 40 итераций с объемом контрольной выборки N~ 100 000 точек, итого 4 миллиона точек. Выборочная полнота полученной аппроксимации близка к единице. Точность построенного множества на каждой итерации находится в пределах = 0.02-0.05, причем расстояние до идеальной точки практически не уменьшается. Результаты аппроксимации показаны на рис. 5.1 и 5.2. ё

5.

4.

3.

Qz: у4

11585 ю.зеа 9.013 7 724 6.43? 5.15 3.863 2.57J 1.187 0

Рис. 5.1. Аппроксимация ОЭП, построенная однофазным методом, и точка Миеттинен (помечена на рисунке кружочком). Критерии J2 (у2 на рисунке) и J3 (уЗ) изображены на координатных осях, а критерий J4 (у4) - на цветовой шкале

Как можно видеть на рис. 5.1 и 5.2, построенная аппроксимация расположена слишком далеко как от идеальной точки задачи (начало координат), так и от точки Миеттинен (5.1). Таким образом, дальнейшая аппроксимация ОЭП однофазным методом была признана неразумной. Поскольку однофазный метод в задаче такой большой размерности несостоятелен, поэтому перейдем к описанию работы многофазных методов. л.

-3. О 3. 6, 9.

Рис. 5.2. Аппроксимация ОЭП, построенная однофазным методом, и точка Миеттинен (помечена на рисунке кружочком). Критерии J5 (у5 на рисунке) и J* (у4) изображены на координатных осях, а критерий Уз (уЗ) - на цветовой шкале

5.2. Построение аппроксимации двухфазными и трехфазными методами

5.2.1. Построение предварительной аппроксимации

База исходной аппроксимации Г0 строилась в два этапа. Сначала была сгенерирована выборка из 10 случайных точек множества X. Для каждой из этих точек были решены четыре задачи локальной минимизации частных критериев J2-J $ в отдельности, т.е. всего 40 задач локальной оптимизации. Из найденных критериальных точек были выбраны недоминируемые, из которых была составлена база предварительной аппроксимации 7оо> содержащая 12 критериальных точек. Были также найдены характерные размеры паретовой границы. В процессе решения 40 указанных задач локальной оптимизации потребовалось рассчитать 111 градиентов целевой функции, т.е. в среднем менее трех расчетов на одну задачу. Кроме того, потребовалось дополнительно рассчитать около 2500 значений оптимизируемых функций, т.е. около 60 расчетов на задачу. Найденные характерные размеры паретовой границы имеют следующую величину: 0£Л<10Д 0<Уз<3.3, 0sA<5.4 и OS/sSl 53. В дальнейшем в функциях полноты и принадлежности использовались относительные величины отклонения от паретовой границы, в качестве которых брались величины, полученные делением исходных значений соответствующих координат на эти диапазоны.

Далее, была проведена одна итерация двухфазного метода, в рамках которой были сгенерирована и локально оптимизирована (с использованием квадратичной свертки) случайная выборка, состоящая из 126 точек. При решении этих задач локальной оптимизации было рассчитано 2092 градиентов оптимизируемых функций, т.е. в среднем несколько менее 17 расчетов градиента на одну задачу оптимизации. Кроме того, потребовалось дополнительно рассчитать около 58 тысяч значений оптимизируемых функций, т.е. около 460 расчетов на задачу. Как видно, локальная оптимизация квадратичной свертки является в среднем значительно более трудоемкой задачей, чем оптимизация одного частного критерия.

Обобщенная двухфазная выборочная полнота т]НФ'М(0) множества (Too)* оказалась равной 0.5 (см. рис. 5.3), а максимальное отклонение полученных критериальных точек от (Too)* составило около 1% от размеров паретовой границы. Оно оказалось равным по порядку величине отклонения найденных точек от идеальной точки. Это показывает, множество (Too)* является весьма посредственной аппроксимацией ОЭП. Базу аппроксимации То составили те недоминируемые критериальные точки, которые отклонялись от (Too)* не менее чем на 70% от максимальной величины отклонения. Таких точек оказалось 17.

Рис. 5.3. График обобщенной выборочной полноты т]нФ'и(е) множества (7оо)*

5.2.2. Анализ влияния параметра Q на процесс аппроксимации двухфазным методом

Параметр Q характеризует условие включения получаемых критериальных точек в новую базу аппроксимации по их отдаленности от аппроксимации ОЭП, полученной на предыдущей итерации. При Q=0 в базу включаются все найденные недоминируемые точки, а при Q=S, где 0<<5<1, в базу включаются только те из найденных точек, которые не ближе к аппроксимации ОЭП, чем брг где р - максимальная величина отклонения выборочных точек от аппроксимации ОЭП (радиус полного покрытия). Были рассмотрены два значения параметра Q, а именно, Q=0 и 6=0.7. За исходную была взята база аппроксимации 7о. Для Q=0 было проведено четыре итерации с выборкой в 149 точек. На рис. 5.4 приведены графики обобщенной двухфазной выборочной полноты TjH^^ie) для построенных множеств (Т\)*, (7г)* и (7з)*. Как видно, выборочная полнота г}нФ'М(0) с каждой итерацией монотонно растет от 0.947 до 0.968, причем для £=0.001 (т.е. £=0.1% от размеров паретовой границы) наблюдается рост величины г}нФ'м(е) от 0.97 до 1. При этом радиус полного покрытия падает от 0.009 на первой итерации (т.е. для множества (Го)*) до 0.001 к четвертой итерации (т.е. для множества (7з)*). Достижение величины е=0.001 было выбрано как условие завершения процесса в связи с тем, что эта величина достаточно мала: она составляла около 20% расстояния до идеальной точки от построенных паретовых границ. Таким образом, аппроксимация (7з)* была признана вполне пригодной для завершения расчета. База аппроксимации 7з состояла из 37 точек, а полученная в процессе оценки аппроксимации (7з)* еще более точная база Г4 - из 41 точки.

Вычислительные затраты были следующими. На одну итерацию, т.е. на оптимизацию 149 точек требовалось в среднем около 2500 расчетов градиента, т.е. в среднем около 17 расчетов градиента на одну задачу локальной оптимизации. Кроме того, потребовалось дополнительно рассчитать около 35 тысяч значений оптимизируемых функций, т.е. около 240 расчетов на задачу. Как видно, локальная оптимизация квадратичной свертки оказалась в среднем столь же трудоемка, что и при построении исходной базы аппроксимации Tq. О

X /

4 000<-004 8 OOOt 004

Рис. 5.4. Графики выборочной полноты т]нФ^(е) для множеств (Ti)*, (7г)* и (7з)* при Q=0

Для Q^O.7 было проведено пять итерации с выборкой в 149 точек. На рис. 5.5 приведены графики обобщенной выборочной полноты т]пФ^(е) для множеств (Г/)*, (Г?)*, (Тз)* и (Т4)*. Как видно, выборочная полнота т]цф'М(0) медленно увеличивается от итерации к итерации с 0.74 до 0.8, причем для £=0.001 выборочная полнота растет от 0.88 до 0.93. При этом радиус полного покрытия падал от 0.09 на первой итерации (т.е. для множества (То)*) до 0.005 к пятой итерации (т.е. для множества (Т4)*). Дальнейшая аппроксимация с 6=0.7 была признана бесперспективной и расчет завершен. База аппроксимации Т4 состояла из 23 точек. Вычислительные затраты оказались приближенно такими же, как и в случае с Q=0. у

Г

J г а. f

О 0 001 0 002 0 003 О ОСИ 0 005 0 006 0.007 0 00$ 0.009 0 02

Рис. 5.5. Графики выборочной полноты 7]/ф'Ы(е) для (Г1)*, (7г)*, (7з)* и (Г4)* при 6=0.7

Проведем теперь непосредственное сравнение аппроксимаций ОЭП, полученных после проведения четырех итераций, т.е. множеств (Г4)*, построенных при 0=0 и <2=0.7. Рассмотрим функции включения, описывающие долю точек одной из аппроксимаций, принадлежащие е-окрестности другой аппроксимации. На рис. 5.6 верхний график описывает функцию включения множества (74)*, построенного при <2=0.7, в £-окрестность множества (/4)*, построенного при Q=0. Нижний график — наоборот, функцию включения множества (Т4)* , построенного при Q=0, в е-окрестность множества (74)*, построенного при Q=0.7.

Г г*

J

1

0 0 002 0 004 0 006 0.008

Рис 5.6. Функции включения для множеств (Г4)* , построенных при Q=0.7 и

Q=0.

Как видно из верхнего графика, множество (/4)*, построенное при Q=0, уже при е, близком к нулю, содержит около 80% точек базы аппроксимации Тц, построенной при Q=0.7, а при £=0.0045 целиком содержит множество (Г4)*, построенное при Q—0.7. В то же время, из нижнего графика следует, что множество (/4)*, построенное при <2=0.7, при £=0 содержит только около 35% точек базы аппроксимации Г4, построенной при <2=0, а целиком содержит множество (Г4)*, построенное при Q=0, только при е=0.0076. Этот анализ также подтверждает, что аппроксимация, построенная при <2=0, значительно превосходит аппроксимацию, построенная при <2=0.7.

1. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. Москва: Наука. 1982.

2. Евтушенко Ю.Г., Потапов М.А. Методы численного решения многокритериальных задач // Доклады АН, 1986, том 291 №1. С. 25-29.

3. Евтушенко Ю. Г., Потапов М. А. Численные методы решения многокритериальных задач // Кибернетика и вычислит, техника. 1987. Вып. 3. М.: Наука, С. 209 - 218.

4. Ю. Г. Евтушенко. Численный метод поиска глобального экстремума (перебор на неравномерной сетке). Журнал вычислительной математики и математической физики, Т. 11, N 6, С. 1390-1403.

5. Краснощёкое П. С., Фёдоров В. В., Флёров Ю. А. Элементы математической теории принятия проектных решений // Автоматизация проектирования, 1997, № 1. С. 15-23.

6. Краснощекое П.С., Петров А.А. Принципы построения моделей. Москва: МГУ. 1983.

7. Краснощекое П.С., Петров А.А., Федоров В.В. Информатика и проектирование. Москва: Знание. 1986.

8. Краснощекое П.С., Морозов В.В., Федоров В.В. Декомпозиция в задачах проектирования // Известия АН. Серия Техн. Киб., 1979. № 2. С. 7-17.

9. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. Москва: Наука. 1981.

10. Соболь И.М., Статников Р.Б. Наилучшие решения где их искать // Математика и кибернетика, 1/82.

11. Statnikov R. В., Matusov J. Multicriteria Optimization and Engineering. -New Jersey: Chapman and Hall, 1995.

12. Соболь KM. О распределении точек в кубе и сетках интегрирования. // Успехи матем. наук, 1966, 21, №5, С. 271-272.

13. Штойер Р. Многокритериальная оптимизация. М.: Радио и связь, 1992.

14. Deb К. Multi-objective optimization using evolutionary algorithms. -Chichester: Wiley, 2001.

15. Моисеев H.H. Математические задачи системного анализа. Москва: Наука. 1981.

16. Поспелов Г.С., Ириков В.А. Программно-целевое планирование и управление. Москва: Советское радио. 1976.

17. Лотов А.В. Исследование экономических систем с помощью множеств достижимости // Труды международной конференции «Моделирование экономических процессов» (Ереван, апрель 1974). Москва: ВЦ АН СССР. 1975.

18. Лотов А.В. О понятии обобщенных множеств достижимости и их построении для линейных управляемых систем // Доклады АН СССР, 250(5). 1980.

19. Лотов А.В. Анализ потенциальных возможностей экономических систем // экономика и матем. методы, 17(2). 1981.

20. Лотов А.В. Согласование математических моделей с использованием множеств достижимости // Математические методы анализа взаимодействия отраслевых и региональных систем. Москва: Наука. 1983.

21. Лотов А.В. Введение в экономико-математическое моделирование. Москва: Наука. 1984.

22. Лотов А.В. Методы анализа математических моделей управляемых систем на основе построения множества достижимых значений показателей качества управления. Дис. на соискан. учен. степ. докт. физ.-мат. наук. Москва: ВЦ АН СССР. 1986.

23. Lotov A.V., Chernykh O.L., Hellman О. Multiple Objective Analysis of Long-Term Development Strategies for a National Economy // European Journal of Operational Research. 1992. V.56. No.2.

24. Lotov A., Bushenkov V., Chernykh O. Multi-criteria DSS for River Water Quality Planning // Microcomputers in Civil Engineering. 1996.

25. Лотов A.B., Бушенков B.A., Каменев Г.К., Черных О.Л. Компьютер и поиск компромисса. Метод достижимых целей. М.: Наука, 1997.

26. Лотов А.В., Бушенков В.А., Каменев Г.К. Метод достижимых целей. -Lewiston, NY: Mellen Press, 1999.

27. Lotov A. V., Bushenkov V. A., Kamenev G. K. Interactive Decision Maps. Approximation and Visualization of Pareto Frontier. Boston: Kluwer Academic Publishers, 2004.2829,3033,34,353839,40,

28. Chipperfield A. J., Whideborn J. F., Fleming P. J. Evolutionary algorithms and Simulated Annealing for MCDM // Multieriteria Decision Making: Advances in MCDM Models, Algorithms, Theory, and Applications. -Boston: Kluwer Academic Publishers, 1999.

29. Suppaptnarm A., Steffen К .A., Parks G. 71, and Clarkson P. J. Simulated Annealing: An alternative approach to true multiobjective optimization // Engineering Optimization. 2000. V. 33(1). P. 59 85.

30. Kubotani H., Yoshimura K. Performance evaluation of acceptance probability functions for multiobjective simulated annealing // Computers and Operations Research. 2003. V. 30, P. 427 442.

31. Гермейер Ю.Б. Исследование операций. M.: Наука, 1970.

32. Wierzbicki А. (1981) A mathematical basis for satisficing decision making //

33. Organizations: Multiple Agents with Multiple Criteria, ed. by J. Morse. Berlin:1. Springer.

34. Нефедов B.H. Методы регуляризации многокритериальных задач оптимизации // М. МАИ, 1984.

35. Нефедов В. Н. Об аппроксимации множества Парето // ЖВМиМФ. 1984. Т. 24(7). С. 993- 1007.

36. Нефедов В. Н. Об аппроксимации множества оптимальных по Парето решений //ЖВМиМФ. 1986. Т. 26(2). С. 163 176.

37. Жадан В.Г. Метод параметризации целевых функций в условной многокритериальной оптимизации // Ж. вычисл. матем. и матем. физ. 1986, Т.26, №2, 177-189.

38. Жадан В.Г. Метод модифицированной функции Лагранжа для задач многокритериальной оптимизации // Ж. вычисл. матем. и матем. физ. 1988, Т.28, №11, С. 1603-1618.

39. Holland J. "Adaptation in Natural and Artificial Systems", Univ. of Michigan Press, 1975.

40. Goldberg, D. E. "Genetic Algorithms in Search, Optimization, and Machine Learning", Addison-Welsey, 1989.

41. Schott J. "Fault tolerant design using single and multi-criteria genetic algorithm optimization." Master's thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology. 1995.

42. Zitzler, E., L. Thiele, M. Laumanns, С. M. Fonseca, and V. Grunert da Fonseca (2003). Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation 7 (2), 117-132.

43. Бушепков B.A., Гусев Д.И., Каменев Г.К., Лотов А.В., Черных O.JI. Визуализация множества Парето в многомерной задаче выбора // Доклады Академии наук. 1994. Т.335. N 5. С. 567-569.

44. Каменев Г.К., Кондратьев Д.Л. Об одном методе исследования незамкнутых нелинейных моделей // Математическое моделирование, 1992, №3, 105-118.

45. Каменев Г. К. Аппроксимация вполне ограниченных множеств методом глубоких ям // Ж. вычисл. матем. и матем. физ. 2001. Т. 41. № 11. С. 1751-1760.

46. А.Н. Ширяев Вероятность. М. «Наука». 1980.

47. Колмогоров А.Н., Тихомиров В.М. ^-энтропия и ^-емкость множеств в функциональных пространствах // Успехи мат. наук. 1959, Т. 14, No. 2, С. 3-86.

48. А.Н.Колмогоров, С.В.Фомин Элементы теории функций и функционального анализа. М.: Наука, 1976.

49. Е. Laitinen and P. Neittaanmaki. "On Numerical Solution of the Problem Connected with the Control of the Secondary Cooling in the Continuous Casting Process", Control Theory and Adv. Tech., vol. 4, pp. 285-305, 1988.

50. К. Miettininen., M.M. Makela, and T. Mannikko. "Optimal Control of Continuous Casting by Nondifferentiable Multiobjective Optimization", Computational Optimization and Applications, vol. 11, pp. 177-194, 1988.

51. Horst, R., and Pardalos, P.M. Handbook on Global Optimization. Dordrecht, NL: Kluwer, 1995.

52. Жиглявский А. А., Жилинскас А.Г. Методы поиска глобального экстремума. М.: Наука, 1991.

53. Хохлов М.А. «Информационная технология и инструментальная система математического моделирования экономики "Экомод"», диссертация на соискание ученой степени кандидата физико-математических наук, М.: ВЦ РАН, 2007.

54. Ю.Н. Павловский, Н.В. Белотелое, Ю.И. Бродский Имитационное моделирование. Москва. Издательский центр «Академия». 2008.

55. Лотов А.В., Каменев Г.К, Березкин В.Е. Аппроксимация и визуализация паретовой границы для невыпуклых многокритериальных задач. // ДАН. Т. 386. №6. с.с. 1-4. 2002.

56. Zitzler, Е., L. Thiele, М. Laumanns, С. М. Foneseca, andV. Grunert da Fonseca (2003). Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation 7 (2), 117-132.

57. K.Miettinen and M.M.Makela "Interactive Bundle-Based Method for Nondifferentiable Multiobjective Optimization: NIMBUS", Optimization, vol. 34, pp. 231-246, 1995.

58. K.Miettinen and M.M. Makela "Interactive Method NIMBUS for Nondifferentiable Multiobjective Optimization Problems", in Multicriteria Analysis, J.Climaco (Ed.), Springer-Verlag: Berlin-Heidelberg, pp. 310-319, 1997.

59. K.Miettinen, M.M.Makela and R.A.E. Makinen "Interactive Multiobjective Optimization System NIMBUS applied to Nonsmooth Structural Design Problems", in System Modelling and Optimization, J. Dolezal, J.Fidler (Eds.), pp. 397-385, 1996.