Численные методы решения многокритеральных многоэкстремальных задач с особенностями тема автореферата и диссертации по математике, 01.01.11 ВАК РФ

нижегородский государственный университет

им. Н. И. ЛОБАЧЕВСКОГО

м

т п г "Н1 '' На правах рукописи

i ii • 1 - ;

МАРКИНА Марина Викторовна

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНЫХ МНОГОЭКСТРЕМАЛЬНЫХ ЗАДАЧ С ОСОБЕННОСТЯМИ

01.01.11 — Системный анализ и автоматическое управление

Автореферат

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

Нижний Новгород, 1994

Работа выполнена на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики Нижегородского государственного университета им. Н. И. Лобачевского.

Научный руководитель: доктор физико-математических наук, профессор, заслуженный деятель науки России Стронгин Р. Г.

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

доктор технических наук Ю. М. Максимов;

кандидат физико-математических наук А. Г. Коротченко.

Ведущая организация: Республиканский инженерный центр по автоматизации проектирования (г. Нижний Новгород).

Защита состоится с / > /¿/й^«^_1994 г. в час.

на заседании специализированного совета К 063.77.01 в Нижегородском государственном университете им. Н. И. Лобачевского по адресу: 603600, г. Нижний Новгород, пр. Гагарина, 23, корп. 2.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного университета.

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

1994 г.

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

В. И. Лукьянов.

СйШ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

Современный .уровень развития проектных и исследовательских работ характеризуется усложнением ооьектов проектирования исследования, э таю© возрастающей степенью автоматизации.

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

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

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

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

рассматриваться как введение специальной свертки (работы Подиновского В.В., Нопшэ Б.Д., Федорова В.В.). В этом случае возможна и непосредственная скаляризация, нзпримор с помощью метода последовательных уступок (рзботы Подиновского В.В.,Гаврилова В.М. .Вентцель Е.С.) Непосредственная скаляризация возможна тэга© с помощью метода Функция Лаграшка (работы Жадзна В.Г.).

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

В работах Соболя P.M., Статникова Р.Б. такие точки отфильтровываются из выборки равномерно распределенной в области поиска.

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

Необходимость .учета других особенностей процесов принятия решения (тит частичной вычислимости функционалов-характеристик модели,т.е. возможной неопределенности Последних вне области функционирования, возможная ' разрывность функционалов)

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

Цель и задачи исследования.

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

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

-строятся и теоретически обосновываются численные метода аппроксимации множества слабоэффективных решений;

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

Научная новизна.

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

областях.

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

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

4.Все предложенные численные методы исследованы на сходимость.

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

Практическая ценность работа.

"Практическая значимость работы определяется возможнстыо использования разработанных численных методов в подсистемах принятия оптимальных решений для САПР и АСНИ. Предложенные многомерные алгоритмы использованы для решения многокритериальных .прикладных задач оптимизации замковых соединений самораскрывающихся систем типа антенн и задачи оптимального проектирования передней подвески автомобиля. Результата работы внедрены на предприятии п/я в-8216.

Апробация работы.

Результаты работы докладывались на хп Всесоюзной

школе-семинаре по адаптивным системам (Могилев,1984),VI Всесоюзном совещании по автоматизации проектирования

электротехнических .устройств (Таллин,Шэ). Всесоюзных совещаниях-семинарах молода ученых "Использование вычислительных средств в экологии,экономике,медицине" (Горький, 1986, Саратйв, 1988), Всесоюзной конференции "Численная реализация физихо-механических задач прочности" (Горький.1887), Всесоюзной конференции "Современные проблемы информатики, вычислительной техники и автоматизации" (Горький,1988), VIи Всесоюзная конференции "Проблемы теоретической кибернетики" (Горький,1988), Межгосударственной научной -конференции "Экстремальные задачи и их приложения" (Нижний Новгород,1992).

Публикации.

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

С1-111.

Структура и обьем работа.

Диссертация состоит из введения, четырех глав, заключения, списка литературы из 98 наименования и прилояиния. Основной печатный текст занимает 114 страниц, В работе имеются 31 рисунок.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глзва-"Метод оценки множества полуэффектавных решения многокритериальных задач с невыпуклыми ограничениями" -посвящена описанию предлагаемого информационно-статистического

метода оценки слейтеровского множества. В §1.1 проводится построение' математической модели принятия решений, обобщающие постановки, описанные в литературе. Структура математической модели включает следующие компоненты:

-формальное описание, множества проектных решений, содеркащэе вектор конструктивных параметров

вектор-функцию характеристик

И(х|=(к <х),...,к (х)),

1 п

все координатные функции таковы,что их уменьшение соответствует улучшению проекта,

область вариации .управляемых параметров

0={хеВН:»1<х1£Ь1,1<1<н}.

определяемая заданными векторами начала и коащ,

а>(а1,...,а||), Ь»^,... ,Ь ),

где «1<ь1,1<1<н.

При этом предполагается,что все управляемые параметры непрерывны

и не зависят от времени;'

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

определяемых набором .....л номеров

координатных функций »i(x), для которых заданы продельные

значения в виде допусков <w4l.....qj.

Неравенства выделяют допустимое множество

Q={xSD!8i(x)<0 ,1<1<в|.

Предполагается,что все функщи g^xMsi^« могут быть частично вычислимыми (т.е. любая функция п.<х> определена и вычислила в точке х-о .если только яЛх><о,i<j<i-i) и гаюгозкстремалышми;

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

f(x)*(f,(x).....f U>). f,<x)*w <х), i«SF,

1 я J i j

определяемого множеством f*^,....! в области о.

В задаче минимизации векторного критерия эффективности г(х) нэ подмножестве допустишх точек q

f(x>-> ain

частные критерии обычно противоречивы.Замена вектора х1 вектором 2

х может приводить одновременно к уменьшению частного критерия г. и к увеличению другого частного критерия t . В связи с этим для характеристики различных решения многокритериальной задачи используются понятия эффективного и полуэффектавного решений.

В §1.2 рассматриваются принципы построения одномерного алгоритма.Подход к оценке недокинируемых решений основывается

на трех следующих принципах:

I. Сведение задачи многокритериальной оптимизации к задаче условной оптимизации. Известно,что решение задач вида

■1п{Гв<х)!хеа}, (1)

ГДР Ч={х€[а,Ъ):ГМх)<д^1<.1<8-1, (х >20, 1<1<«} ,

является слабо эффективным решением многокритериальной задачи

<*1(х).....Г (х) -> в!п , 0={хе1»,Ы: в <*)£<>}.

хеО

2.Одновременное решение нескольких задач условной оптимизации

Для решения одной задачи условной минимизации при фиксированном векторе ч«,(ч1....»чв_1) можно воспользоваться

информационно-стзтистаческш алгоритмом условной минимизации,

описанным в работах Стронгина Р.Г. и Маркина Д.Л.

Данный алгоритм предполагает разбиение области поиска на

подынтервалы и проведение очередной итерации в том из них,которому

соответствует наибольшая характеристика. В работе предлагается

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

соответствующих задачам различным задачам. -

Сформулированы достаточные условия сходимости такого алгоритма.

3.Одновременное решение бесконечного числа задач условной минимизации, к который сводится многокритериальная задача.

Если в задачах условной минимизации, к которым сводится многокритериальная задача, возможное изменение каждой компоненты вектора ч^ч,.....! ,) задать правилом

ч

Г.+(р-ПЬ, где (2)

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

В §1.3 дается описание одномерного алгоритма

зппроксимзщм мноякства полуэффективных решений

многокритериальных задач с ограничениями.

§1.4 посвящен теоретическому обоснованию сходимости

предложенного одномерного алгоритма. Достаточные условия сходимости алгоритма сформулированы в следующей теореме: Теорема.

Пусть:

I множество б - есть множество решений задата < 1 > при всем множестве векторов ч=<ч1.•••.пя_1). задаваемым условиями <21;

2)ф.уякши й (х>,1<1£и, удовлетворяют условию Липшица с

соответствующими константами к] и вырззакгг непустую допустимую область;

функции г^(х), удовлетворяет условию Липшица с

соответствующими константами к^;

3) начиная с некоторого шага работы алгоритма выполняется условия:

где г>1 параметр алгоритма, оценки алгоритмом констант

Липшица соответствуюпщ функция;

Тогда

Множество предельных точек последовательности порожденной алгоритмом при точности £=о в условии остановки содержит в себе множество Кроме множества множество предельных точек может еще содержать лишь точки локальных минимумов критериев ^««».....г (х).

Во второй главе-"Метод уступок для многоэкстремальных лексикографических задач" рассматривается другая схема решения многокритериальных задач.

В §2.1 рассматривается идея использования метода уступок при решении многоэкстремальных лексикографических задач.

Лексикографическая задача опташащи ^является частным видом об¡цэй задачи оптимизации, когда все частные критерии

г (*),...f u>,образующие векторный критерий,строго упорядочены

по важности.Лексикографическая задача оптимизации заключается в

отыскании лексикографически-оптимальных решений.

Решение лексикографической задачи - точка,в которой

достигается наименьшее значение самого важного критерия и значение

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

незначительная уступка по значению более важного 'критерия может

дать существенное улучшение менее важного.Лексикографическое

решение при заданных уступках - решение последней задачи из следующей последовательности задач:

1) нэйти f* «Bin fх),xeD;

2) найти f* »ain f2lx),xeD,- f^xlifj *£ t;

в) найти f* =ein t <X),X€D, f.(x)<r* 1S1<«-1;

es Iii

D={x€|a,b): g^xliO}.

Предлагаемый способ выбора решения основывается на: 1) схеме сведения многокритериальной задачи к семейству однокритериальных

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

Схема сведения многокритериальной задачи к семейству однокритериальных:

Г. = В1п( Г .(я <х)Ю; 1<1<рЬ О 1 Л 1 1

где

Ь . ( х ) = х

Г. (х)-Г * -¿г, ,«(1<1<р.

1-И 1-Ю 1-Ю

Таким образом„нахождение оптимального решения ** можно

свести к последовательному решению в задач минимизации

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

Необходимые при таком подходе, оценки значений г*.....г* (

обеспечиваются последовательным решением предшествующих задач.

Функции ид{х) удовлетворяют условию Липшица в силу лишидавости

всех характеристик модели.

Решение такой задачи алгоритмом условной оптимизации,

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

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

Таким образом,решение задачи по следующему критерию продолжает

решение предшествующей задачи.

■ В §2.2 описывается алгоритм решения одномерных

лексикографических задач с ограничениями и приводятся достаточные

.условия его сходимости.

Глава 3 -"Многозкстремэльнэя оптимизация разрывных функций" посвящена разработке алгоритмов оптимизации функций1, имеющих разрывы гврвго родз (типа.конечного скачка).

SB §3.1 рассматривается постановка задачи и классификация причин разрывов первого рода, возникающих в задачах механики.

Пусть г(х)-однозначная,действительнзя функция одного переменного,определенная на отрезке и.ы вещественной оси имеет конечное число точек разрывов первого рода wt гi<i<n).Функция г<х> имеет лишишвые дуги в интервалах (w |,1<1<п+г,*0»»,*пИ«ь, может быть многоэкстремальной,экстремум мо:кэт совпадать с точкой разрыва.

Требуется найти х».такое что

f (х* )=■ jn{ f {х):х€[а,Ы}.

Разрывы функций первого рода могут отражать свойства характеристик расчетных моделей реальных обьекгов.Возникновение таких разрывов мо:гот быть следствием:

-скачкообразных изменений геометрических характеристик.

-скачкообразных изменений физико-механических свойств материалов.

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

В §3.2 рассматривается подход к решению задачи оптимизации разрывных функция на основе информационно-статистических алгоритмов.

Любой численный метод оптимизации предполагает возможность

проведения некоторого числа испытаний в точках области

поиска (под испытанием понимается вычисление значения функции).При

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

проводить испытания.

В случае,когда разности значении функции ограничены

некоторой мерой разноствй аргумента,этот выбор определяется строго

формализуемыми далями,что позволяет ставить задачи построения

оптимальных процедур. Алгоритм глобального поиска Стронгина Р.Г.

является одной из реализаций такого подхода. Применение его к

разрывным функциям не всегда возможно. Это связано с тем,что

плотность точек испытаний зависит от опенки алгоритмам константы

Липшица функции.

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

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

Если концы интервала не являются точками разрывов, то характеристика подынтервала совпадает с характеристикой алгоритма

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

следствием звивалентности моделей, лежащих в основе обоих алгоритмов на таких подынтервалах области поиска.

В случае, когда определено, что один из концов подынтервала является точкой разрыва предложен способ вычисления

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

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

В §3.3 описан алгорита минимизации одномерных много экстремальных функция, имеющих разрывы первого рода в заданных точках и сформулированы достаточные условия сходимости алгоритма.

В §3.4 описан алгоритм, минимизации одномерных многоэкстремальных функция „ имеющих разрывы первого рода в как в известных так и неизвестных точках и также приведены достаточные условия его сходимости. Теорема.

Пусть:

I) минимизируемая функция г(*),хе1«,ы имеет конечное число точек разрыва первого рода и липшицевые (сконстантоя К) дуги в открытых подынтервалах из разбиения <«,ы,порождаемого точками разрыва;

/

Г(Ь-О), х»Ь,

я!п|«(х-0),Г(х+О), х€(а,Ь), Г(ыО), х»а;

Г(хН

3) {хк} -есть последовательность точек .порождаемая алгоргаом; 1) начиная с некоторого шага для величины р, являющейся оценкой константы Липшица функции на участках непрерывности выполняется неравенство

гр>2К,

где r>i параметр метода;

5) точка х* глобального минимумз функции ?<*) отделена от соседней точки разрыва хотя бы одной точкой последовательности {*к\. Тогда:

а) тачка **-есть предельная точка последовательности

6) каждая предельная точна х последовательности есть точка глобального минимума функции Г(х>;

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

В §4.1 рассматривается многошаговая схема редукции размерности и обсуждается ее применение к алгоритмам мимнимизашта разрывных функций.

В §4.2 рассматривается применение схемы редукцт» п^т «ртп?

Пеано к алгоритмам, решающим многокритериальные задачи.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

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

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

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

4.Сформулированы достаточные условия сходимости предложенных алгоритмов.

5.Рассмотрены схемы редукции размерности.

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

По материалам диссертации опубликованы следующие работы:

1.Маркина М.В. Метод оценки множества полуэффективных решет бикритериэльных ' задач выбора //Проблемы теоретической кибернетики: в-я Всесоюзная научная конференция: Гез.докл.:Горький,1988.ч.И, с.зг-зз. г.Мзркина М.В..Стронгин Р.Г.Лексикографический подход к решению многокритериальных физико-механических задач выбора // Всес.конф. "Численная реализация физико-мехзничесих задач прочности". Тез.докл. Горький.

ИЗД-ВО ГГУ,1987.с.142.

з.Маркина М.В. Численный метод решения бикригериалыш многоэкстремальных задач. Сб.ст.- Математическое моделирование,-управление и оптимизация ".Деп.в ВИНИТИ

16.07.88 N 57-14.

4.Отчет по научно-исследовательской работе: Геометрическая модель зеркала.Оптимизация замковых соединений.-Горький, НИИ механики при ГГУ, н г.р.01850005294,1984. 6.Отчет по научно-исследовательской работе: Адаптивное .управление, принятие решений и оптимизация. Решение многоэкстремзльных,лексикографических задач с уступками (промежуточный отчет).Горький,НИИ ПМК при ГТУ, м г.р.

01860136674,1987.

е.Стронгин Р.Г.,Маркина М.В. Многоэкстремальные лексикографические задачи выбора. // Системное моделирование прононсов интенсификации общественного производства: Всесоюзная школа-семинар: Тез.докл./Горьк.

гос. ун-т. Горький,1987. с.т-по. 7.Стронгин Р.Г..Маркина М.В. Многоэкстремальная минимизация разрывных функций. // Методология проектирования САПР. ч. II: Тез.докл./ Таллин.1986.

с.119-121.

в.Стронгин Р.Г. .Маркина М.В. Огггимизация разрывных многоэкстремалыш характеристик конструкций. // Всес.конф. Проблемы снижения материалоемкости сотовых

конструкций.Тез.ДОКЛ.ГОРЬКИЙ: ИЗД-В0 ГГУ,1984.с,д04-105.

э.Стронгин Р.Г..Маркина М.В. Многоэкстремальная оптимизация разрывных функций при расчете и проектировании конструкций. Межвуз.сб. "Математическое моделирование и метода оптимизации", ГГУ, 19вэ. ю.Стронгин Р.Г.,Маркина М.В. Численный метод оценки множества поду эффективных решений бикритеризльных задач. В кн."Использование вычислительных средств в экономике, экологии,медицине".Изд-во Саратовского ун-та.1 зев. и.Маркин Д.Л.,Маркина М.В..Стронгин Р.Г. Информационно-статистические алгоритмы многоэкстремальной многокритериальной оптимизации. //Межгосударственная научная конференция "Экстремальные задачи и их приложения". Тез.докл. Нижний Новгород,1992.