Введение к работе
Актуальность проблемы. Создание современных сложных технических систем представляет собой длительный процесс, включающий "несколько тесно взаимосвязанных зташв, среди koto^jx важнейшим является этап і:рт актирования. Проектирование ионы: рассматриваться как процесс принятия решений, т.е. постановки я реализации задачі: .ыбора соответствии с некоторой моделью.
В технических областях исторически сложились проверенные опытом практической деятельности правила оценки проектных разработок. Будучи формализованы в некоторые "разумные" правила выделения оптимальных в том или ином смысле вариантов иэ всего множества реализуемых технг зки альтерг, тив они легли в осі: -ву обаеЗ теории- выбора. Данные "классические" процедуры выбора достаточно глубока изучены как в теоретическом, так и в практическом плане при рулении разнообразных задач. " пс -еднее время в теории зыбора наметились тенденции перехода к исследовании нетрадиционных процедур, что позволяет расширить функциональные возможности моделей, повысить их практическую значимость. Помимо этого, обьеаіНі-.'нв различных эвристических методов на единой методологической основе должно способствовать и пр..внесе-ние в теоркэ- выбора идей "нечеткости" Заде Это объясняется те: , что в реальных ззлачах принятия1 решения цели, ограничения, критерии виборг. ъ большей части субъ< тивны и четко не. определены. Поэтому при построении теоретических моделей возникает необходимость использования нечетких множестз, отношений,- приводящих к понятно нэчеткого выбора.
Ознако попытки применения Данных теоретических моделей в-проектировании сложных многокошгонектнш: систем часто. о? *.зыва-ются неудачными. Складывается ситуация, когда на практике специалисты предпочитают жспольэозать проверенны спотом собственные эвристические и интуитивные процедуры анализа, не гарантируйвие математической: отгималькоста. Невозможность учета всего многообразия свойстз, присудил сложьой технической системе, ІГрИЕОДИТ к необходимости применения декожвзнцискяых методов анализа, 'С инаэнорной' точкк зрения наиболее стестззишм представляется подход, кслользувдяй иле» агрегирования.- перехода х новому, качественно отличкону уровни описаний, который соответствует более целостному взгляду аа проектируемую техническую) систему.
Теоретичесче чсследования в последнем направлении могут служить методологической .основой для разработки конкретных процедур декомпозиции применительно к разлив ж областям техники. Н?^?о"тельно требуется і ст латиэация предлагаемых де лшози — онньпг процедур, в частности, на основ' разработок теорий функций выбора и принятия решений.
Большая груп- .известных декомпозиционных схем включает в процедуры выбора на каадом из уровней агрегирования.решение оптимизационных задач с несколькими критериями. Это обусловлено прин-ципи-льной ішогокріїтериалькостью любой ело юй технической системы. Имея в виду, что многокритериальный выбор часто является первым этапом более общей и ле всегда математически точно формализуемой процедуры, достаточно важными представляются pas. ^ботки м~одов, поз» лляющих исследовать все множество решений многокритериальной задачи чмножество Парето). При численном решении многокритериальных задач возникает проблема учета погрешностей, присутствующие при реат-з^дии выбранного метода.
Цель работы состоит в разработке обобщенных декомпозиционных
процедур решения задачи выбора и их систематизации на основе еди
ного подхода, с учетом свойств применяемых механизмов выбора и
методов агрегирования; '
исследовании конкретного метода аппроксимации множества Парето
решений задач многокритериального выбора с помощью семейства
сверток, сохраняющего свойство дифференцируем .:ти частных кри-
теркев. .
Научная новизна полученных в раб<-~е результатов заключается в следующем:
-
В терминах функций выбора разработан- ряд новых формали-. зованных процедур'решения задачи выбора, основанных на многоуровневом агрегировании структур описаний проектных вариантов.
-
Сформулирована задача выбора в нечеткой постановке, введены и исследованы свойства «. .ераторов нечеткого выбора, понятие варьируемого выбора. Разработаны декомпозиционные процедуры решения задач нечеткого выбора.
-
.Декомпозиционный подход К' кретизироват на с/чай "классически-рационального выбора, в том чь^лв ь-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Р$ 6я числовая функция т)х , !о, |3 ) - эквивалентная исходной
функции ц х = Ф СХЭ, определяется следующим образок :
«"""«^-Л ч С/3*А
!
а . если х є XvC^; 1 , если х С^л; р „СхЭ,
<х>, если Ф є Sia/3) ;
(х; у), где у є Cg+<jt -произвольный вариант, если *'єК|а,р, ; .
С«А U С« «Ъ-аЛ
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 - совместимых компьпторов.