Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Декомпозиция и многокритериальный выбор в проектировании систем Шафранский, Сергей Викторович

Данная диссертационная работа должна поступить в библиотеки в ближайшее время
Уведомить о поступлении

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Шафранский, Сергей Викторович. Декомпозиция и многокритериальный выбор в проектировании систем : автореферат дис. ... кандидата физико-математических наук : 05.13.16 / Черновиц. гос. ун-т им. Ю. Федьковича.- Черновцы, 1991.- 12 с.: ил. РГБ ОД, 9 91-4/1747-2

Введение к работе

Актуальность проблемы. Создание современных сложных технических систем представляет собой длительный процесс, включающий "несколько тесно взаимосвязанных зташв, среди koto^jx важнейшим является этап і:рт актирования. Проектирование ионы: рассматриваться как процесс принятия решений, т.е. постановки я реализации задачі: .ыбора соответствии с некоторой моделью.

В технических областях исторически сложились проверенные опытом практической деятельности правила оценки проектных разработок. Будучи формализованы в некоторые "разумные" правила выделения оптимальных в том или ином смысле вариантов иэ всего множества реализуемых технг зки альтерг, тив они легли в осі: -ву обаеЗ теории- выбора. Данные "классические" процедуры выбора достаточно глубока изучены как в теоретическом, так и в практическом плане при рулении разнообразных задач. " пс -еднее время в теории зыбора наметились тенденции перехода к исследовании нетрадиционных процедур, что позволяет расширить функциональные возможности моделей, повысить их практическую значимость. Помимо этого, обьеаіНі-.'нв различных эвристических методов на единой методологической основе должно способствовать и пр..внесе-ние в теоркэ- выбора идей "нечеткости" Заде Это объясняется те: , что в реальных ззлачах принятия1 решения цели, ограничения, критерии виборг. ъ большей части субъ< тивны и четко не. определены. Поэтому при построении теоретических моделей возникает необходимость использования нечетких множестз, отношений,- приводящих к понятно нэчеткого выбора.

Ознако попытки применения Данных теоретических моделей в-проектировании сложных многокошгонектнш: систем часто. о? *.зыва-ются неудачными. Складывается ситуация, когда на практике специалисты предпочитают жспольэозать проверенны спотом собственные эвристические и интуитивные процедуры анализа, не гарантируйвие математической: отгималькоста. Невозможность учета всего многообразия свойстз, присудил сложьой технической системе, ІГрИЕОДИТ к необходимости применения декожвзнцискяых методов анализа, 'С инаэнорной' точкк зрения наиболее стестззишм представляется подход, кслользувдяй иле» агрегирования.- перехода х новому, качественно отличкону уровни описаний, который соответствует более целостному взгляду аа проектируемую техническую) систему.

Теоретичесче чсследования в последнем направлении могут служить методологической .основой для разработки конкретных процедур декомпозиции применительно к разлив ж областям техники. Н?^?о"тельно требуется і ст латиэация предлагаемых де лшози — онньпг процедур, в частности, на основ' разработок теорий функций выбора и принятия решений.

Большая груп- .известных декомпозиционных схем включает в процедуры выбора на каадом из уровней агрегирования.решение оптимизационных задач с несколькими критериями. Это обусловлено прин-ципи-льной ішогокріїтериалькостью любой ело юй технической системы. Имея в виду, что многокритериальный выбор часто является первым этапом более общей и ле всегда математически точно формализуемой процедуры, достаточно важными представляются pas. ^ботки м~одов, поз» лляющих исследовать все множество решений многокритериальной задачи чмножество Парето). При численном решении многокритериальных задач возникает проблема учета погрешностей, присутствующие при реат-з^дии выбранного метода.

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

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

Научная новизна полученных в раб<-~е результатов заключается в следующем:

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

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

  3. .Декомпозиционный подход К' кретизироват на с/чай "классически-рационального выбора, в том чь^лв ь-uopa по не"чт-ким отношениям предпочтен 1. . ..' . .. '

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

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

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

Апробация и публикации. По результатам делались сообщения и"доклады на

научно-исследовательской очминаре кзфетры исследований опер-щий факультета ВМиК МГУ; ;

научно-проблемном семинаре в Институте, проб лем кибернетики,' г. Москва;

специализированных семинарах НПО "Квант", г. Киеь;

научно-исследовательских и проблемных семинарах кафедр численных методов математической физики, моделирования словных систем, теории программирования "Т.

республиканском семинара Черновицкого университета.

По результатом диссертационной работьт опубликованы 4 рабо"*;.

На запиту выносятся следующие результаты:

обобщенные декомпозиционные процедуры решения задачи выбора при проектировании Сдля выбора общего вида, классически-рационального и нечеткого выбора);

обоснование применения специального семейства сверток для решения задач многокритериального ЕКбора в виде:

неулучааемых оценок параметра семейства, гарантируввих задан
ный уровень погрешности; '

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

оценок относительной точности аппроксимации множества Парето при наличии реальных вычислительных погрешностей;

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

Объег ч труктура диссертации. Диссертация, объемом 142 CTP- состоит из введения, четырех глав, заключения .я списка литературы, включающего ; кэжмэнованай.

СОДЕРЗШШЕ ?AF"U

Рассмотрена задач в работе проводится по схеме от общего к частному: решение общей задач.» выбора (глава D, классически-рациональный выбор Сглава 2), многокритериальный выбор Сглава 3). В .лаве 4 рассматриваются приложения і ории к проектированию антенных систем.

В главе 1."Декомпозиция задачи выбора при проектировании сложных систем" рассмотрены вопросы разработки , дехоыгоэ"",ионных пр цедур реализации выбора оптимальных проектных решений при проектировании слогяых систем. Выбор описывается как 'рзулътат применения функцит» С к множеству проектных альтернатив .X.

В ' 1 приводеьы краткие сведенг- из теории выбора, сформулированы основные характеристические условия для функции выбора г Ссумыаторности $, константности В> наследования &* независимости от отвергнутых вариантов ф, согласил С и ДР.). Дано понятие агрегирования структгі описаний элементов мужества X» приводящего к построен иерархии описаний .сложной, системы, с целы) упрощения решения задачи вибора. Одноуровневый процесс агрегирования описывается уравне..лем

X и F С X V ID

где F - оператор агрегирования, для которого сущестаует обратный оператор F "', X -новое базі'-чое множество . проектов. Пусть С - функция выбора агрегированного уровн? .

Выделим условия согласования фун: ий выбора исходного
и агрегированного уровней и оператора агрегирования, которые
определяют степень эффективности выбранного способа агрегиро
вания. ' '

Определение 1.1. Для ф. лкций выбора С,. С и оператора агрегирования F имеет место первое условие согласования, если выполняется:

F -' СССХЭЭ S CCF 'СХЭ); ^J имеет место второе условие согласования, если выполняется f -* сссх: 2 CCF -ЧХ)}. . СЗ)

Обозначим С < F -'СССЙЮ, ССХ'.Х ) « ССХ) л X' .

і 2 посвяяен рассмотрели» декомпс. лционных процедур, базиру-воихся на агрегировании структур описаний элемехов множества X. Данныэ проаедуры организовывается таким сбразои, чтобы основная часть вариантов окончательно принималась,, либо отвергалась упрс щеннш выбором агрегированного уровня, а для винесення реше -ля по оставшимся осуществлялся дополнительный внбор на подмнохест-вах X. Приведенн: здесь результаты обобщает следующая Теорема 1.1.

1. Пусть для функций выбора С, С я оператора агрегирова
ния F выполняется условия согласования С2), СЗ), тогда

ССХ) = С.

2. При выполнении условия согласования С23 справедливы
следующие декомпозиционные соотношения

С п СССх», если .С є S ;

С U ССХЧС'Э,

С CXD в \ если С є К и включение С2) - строгое,

С UCCX4C'; С UCCXVJC'D),

если С 6 И п О; С U ССХ -'; X ), в противном случае.

3. При выполнении условия согласования СЗ) справедливы ,
следующие декомпозиционные соотношения

ССС), если СО;

С ОС)

, ССС ; П, в противном случае.

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

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

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

ФСХ) »{ Сх, хСхЭ), х X , у к ! X -> С0;11 >

где f - оператор нечеткого выбора. X' S X И СХ'З а ^ ^ 'Значение характеристической функции ц хСх) mosho интерпретировать как степень принадлегности элемента множеству, являвшим-'

ел решением задачи выбора.

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

С „..X) " < х е v | ' ц хСх) > v У

уровня v из некоторого интервала варьирования [ а 5 р ), заданного априори.

Определение' 1.2. Числовые функции р, 7) : X -> 10; 11 называются I а; " ) - эквивалентными на Х' X , если выполняется: -

V х є X' і? СхЗ 5 а, если у. (хЗ і а ;

7? СхЭ в juCxJ , если а'< у СяЭ < р ; .

7) Сх) г: р , если ц (х) 2: р . В і 4 Со-оеделен: 1.4) введены следующие обобщенные характеристические условия для операторої «четкого выбора: сумматорности, Ф. є S ш о, , если у X' с X

цх и рх, I а ; {3 ) -эквивалентны на X' ; константности, Ф К ,а д, ,'. если у X' с X из у ^ . Э > а

следует Іа; иіпС уСХ'Э; р> Э -эквивалентность м х и М х- и из у СХ'Э < р > ух,СхЭ < в?хС сх; уСХ) ) у х е X';

независимости от отвергнутых ва^лантов, Ф е О » , если

V Х'с X, yCX'D > уСХ\Х'), КХ'З > а, yCXVXD S р . =>
ImaxC а; уСХ\Х')Э; minC уСХ'); р)Э ^эквивалентность ^ и ^, .

sup fi хСхЗ, X' f 0- ,

Здесь у(Х') - , "

О, X' »"0

6 работе определена взаимосвязь обобщенных характеристических условий для операторов нечеткого выбора с характеристическими условиями для функций вьібої— (теорема 1.43-. ... Доказан ряд лемм,, устанавливавших конкретный вид подмножеств. fa; р) - варьируемый выбор на которых эквивалентен вь'"ару ни всем множестве X.

В S 5 рассмотрены вопросы, касаориюся решэняя зада нечеткого выбора.. Вв ,ено следувдео бае условие.

Определение 1.5. Для операторов нечеткого выбора Ф j Ф и оператора агрегирования F выполнено условие ограниченного рассогласования OPq g , если для любого х X, х F"' Сх)

справедливо:

гсахС 0; Д Сх) - б"і З і м „СхЭ < rainC 1; Д _СхЗ + б* 3.
х * х

Здесь Ф - оператор выбора агрегированного уровня, процесс

агрегирования описывается уравнением CD, р ^ = Ф СХЭ, F -

взаимно-однозначный оператор. Обозначим С F "'СС^СХЗЗ.

Основным результатом является следуюаая

Теорема!.5. При выполнении условия 0Р$ числовая функция т)х , !о, |3 ) - эквивалентная исходной

функции ц х = Ф СХЭ, определяется следующим образок :

«"""«^-Л ч С/3*А

!

а . если х є XvC^; 1 , если х С^л; р „СхЭ,

<х>, если Ф є Sia/3) ;

(х; у), где у є Cg+<jt -произвольный вариант, если *'єК,р, ; .

С«А U С« «Ъ-аЛ 3» «"* ф е Wa п га.|3> '

Ci-cV > "*» ;t«,|3, .

X , в- противном случае.- )

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

Основные понятия классически-рационального (к.-р.) выбора изложены в 1. Здесь і :ае приведены утверждения, устанавливающие взаимосвязь топологических свойств бинарных отношений, . заданных на базисном множестве, с характеристическими свойствами реализуемых ими функций выбора.. В 2 предложенный ранее з главе 1 декомпозиционный подход развит применительно к-случаю к. -р. механизмов выбора. Введены условия согласования отношений смежных уровней иерархии и оператора агрегирования, ' отрагакдае некоторые основные случаи "трансформации" парных

предпочтений:

условие сохранения строгой доминируемости : V х,у с X, Су,хЗ є F, х F "'СхЗ »>

3 у е F "'Су) Су,хЗ Р ; условие необрацения строгого доминирования :

V х, у еХ, Су хЗ є Р, х F"' СхЗ, у є F "' СуЗ «>

Су,х) є R ; условие сохранения эквивалентности:

V х,у є X, Су,хЭ е I, х е F "4x3, у е F "' СуЭ »> Су,хЭ є I,

где Р R4 R"', I « R п R"'; R, R - рефлексивные отношения предпочтения соответственно исходного и агрегированного уровней. Установлена связь данных условий с введенными ранее услови-- . яки С2) и (3). Приведены.декомпозиционные процедуры, соответствуете "кахдоиу из рассмотренных условий согласования. Некоторые важные для практики частные случаи организации агрегирования и соответсгвувзще им эмпирические процедуры собраны в .f 3.

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

Дальнейшим сугонием множества рассматриваемых задач является класс многокритериальных задач выбора, изучению -

'которых посвяаена глава 3 "Численные методы решения задач многокритериального выбора".

. 1 данной главы дает основные сведения из теории многокритериального выбора. Рассматривается задача аппроксимации по векторному функционалу множества Парето СрСУЗ ревоний многокритериальной задачи f(x3 » С f СхЗ, ... ,f „СхЭЗ «> ніп, х )., ' У » f СХЗ с Е s , с помоаыз реализации конечного чгсла опти-

шзационных задач с Функцией-сверткой частных критериев - гида

в
( V < .а 1 і/о

Fa С,К ГСхЭ 3 L j2 С \ ftCx 3) J , а і І.

« (43

X ЛСа,ЬЭ » і X Е * | 0 < а < X. S Ь. , У X. = і >,

1 l l ISi Данное семейство сверток, зависящих от векторного параметра X,

является обобщением известной линейной свертки Карлина (случай

a = 13 и минимаксной свертки Герыейера (в пределе при а ->)

В отличии от последнего семейства свертки ,С43 сохраняют

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

В 2 (определение 3.1) введено понятие регулярности множества оптимальных оценок: СрШ равномерно регулярно с параметром ц, если для у У є срС*Э существует и > 0 такое, что выполняется

ух / у? і 1 + t -> у, / у 2 1 - t/ц,

у t 2 0, у Ср CY). Доказана

Лемма 3.1. Если множество С CY) равномерно регулярно

о константой ц >т-1, то выполняется:

С С Y Э U Arg Hin F, С \, у ).

р X. Є Л(о,1 > у Y !*

Использование линейного семейства сверток позволяет выделить лишь некоторое узкое подмножество в CpCYD, для расширения которого следует использовать в (4) значение степенного параметра а>1. Однако при увеличении значения а растут и вычислительные затраты на оптимизацию. В работе получека неулучшаемая нижняя оценка величины степенного параметра, гарсиггиругаая заданный уровень погрешности определения точек

Ср CY). Введем обозначение q. СуЭ = 1 у, У 1/у,

* * j=i J J

Теорема 3.1. Пусть у Ср CYD, Х'« q. і/),

сг > 0, у' е Arg nin F„ С \, У )

. у И

Тог*а условие у' /у < 1 + с, і 1,п , будет выполнено при

а > о' г. 1, а' In n / In CI + оО. Если CpCY3 регулярно в точке у с константой /j, сг < ц а-1, то требуемое значение а' определяется как решение уравнения:

С 1 + о- )а + Са-1) С 1 - ог/м )а -.и. '

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

ляется численными' расчетами.

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

j> 5 посвяаек обсуждению области применимости методов различных типов к -эшению многокритерилышх задач. Предлагается ряд "гибридных" алгоритмов, объединявших полезные свойства различных методов.

Глава 4 "Проектирование антенных систем" демонстрирует применение теоретических результатов работы к проектирование дискретных антенных систем.

В 1 кратко обоснован выбор для рассмотрения антенных решеток, дано описание особенностей предметной областа.

2 посвящен применению методов сверток многокритериальной оптимизации в задачах синтеза параметров антенных систем. Рассмотрены три постановки задач синтеза линейных антенных решеток при наличия нескольких критериев эффективности. В ІЗ данные оптимизационные методы использозаны в рамках декомпозиционных процедур, призванных упростить задачу синтеза. Две предложенные здеоь "гибридные"- декомпозиционные процедуры объединяют."сверточные" градиентные оптимизационные методы, ' рассмотренные в главе 3, и известные сеточные методы решения ' ' задач выбора.- Данные процедуры полностью вкладывается в формализованные декомпозиционные схемы, изученные в предыдущих главах работы.

Конкретно решены задачи синтеза диаграмм направленности антен- ' ной системы, входяцей в состав ИВК, работающего в условиях на-.яичия активно действующих помех в области видимых углов, в пределах некоторых угловых секторов. Ставится.задача распределения ресурса модности по. элементарным излучателям с цельо формирования провалов в ЛН в данных угловых секторах. В качестве критериев рассматривались среднее значение модности излучения в секторе помех) ширина диаграммы направленности„ уровень бокового излучения, коэффициент направленного действия антенной решетки. Приведенные в тексте результаты проектирования включают числовые данные синтеза и графические представления диаграмм направленности синтезируемых антенных систем.

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

"сверточных" градиентных методов оптимизации, ряд известных сеточных методов выделения множества отимальных решений, а также вспомогательные модули расчета точностных оценок, диалогового взаимодействия, выдачи результатов в графическом виде и т.п. Программы реализованы на языке Си (версия 2.0 Typdo-Си) в среде операционной системы KS-D0S для IBM PC - совместимых компьпторов.

Похожие диссертации на Декомпозиция и многокритериальный выбор в проектировании систем