МЕТОД ОПРЕДЕЛЕНИЯ ПАРЕТО-ОПТИМАЛЬНЫХ ПРОЕКТНЫХ РЕШЕНИЙ В АВИОНИКЕ
Ю.А. Гатчин, П.П. Парамонов
УДК 681.324
МЕТОД ОПРЕДЕЛЕНИЯ ПАРЕТО-ОПТИМАЛЬНЫХ ПРОЕКТНЫХ РЕШЕНИЙ В АВИОНИКЕ
Ю.А. Гатчин, П.П. Парамонов
Рассматриваются методологические основы формирования на множестве проектных решений в авионике подмножества эффективных по Парето решений и выбора наиболее эффективного проектного решения в векторном пространстве частных критериев качества. Ключевые слова: бортовое оборудование, многопараметрическая оптимизация, множество Парето.
Введение
В работе [1] сформулирована задача параметрического синтеза бортового радиоэлектронного оборудования (БРЭО) по множеству частных показателей качества ξ1, ξ2, …, ξς ∈Ξ , задаваемых в тактико-техническом задании (ТТЗ) на его разработку и составляющих вектор Ξ параметров проекта для каждой проектной альтернативы Si.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
63
МЕТОД ОПРЕДЕЛЕНИЯ ПАРЕТО-ОПТИМАЛЬНЫХ ПРОЕКТНЫХ РЕШЕНИЙ В АВИОНИКЕ
Поскольку основная аксиома оценки по нескольким показателям утверждает невозможность строгого математического доказательства существования максимально предпочтительного объекта по всем критериям ξ1, ξ2, …, ξς одновременно (рис. 1), то любое проектное решение из числа недоминирующих (т.е. не являющихся менее предпочтительными по всем показателям сразу) может быть признано в качестве искомого варианта проектирования.
Таким образом, сложность проблемы выбора проектного решения по совокупности показателей связана не столько с трудностями вычислений при генерации проектных решений, сколько с концептуальной обоснованностью методологии выбора «наилучшего» проектного решения при одновременном ξ1 → min, ξ2 → min, …, ξζ → min. В этой связи актуальным является решение задачи [1] параметрического синтеза БРЭО на множестве эффективных по Парето проектных решений.
ξ1
S2 S4
S1 S3
ξζ
0
ξ2
Рис.1. Геометрическое представление вектора параметров БРЭО для четырех различных вариантов Si проектных решений
Принцип формирования множества эффективных по Парето проектных решений
Способ многокритериальности выбора состоит в отказе от выделения единствен-
ной наилучшей альтернативы и соглашении о том, что предпочтение одной альтерна-
тиве перед другой можно отдавать, только если первая альтернатива оказывается луч-
ше второй по всем частным показателям. Если предпочтения хотя бы по одному част-
ному критерию расходятся с предпочтениями по другому, то такие альтернативы явля-
ются несравнимыми.
В результате попарного сравнения альтернатив все худшие по всем критериям
альтернативы отбрасываются, а все оставшиеся несравнимые между собой (недомини-
руемые) принимаются. Если все минимально достижимые значения частных критериев
не относятся к одной и той же альтернативе, то принятые альтернативы образуют мно-
жество Парето.
Актуальность приближенного построения множества Парето обусловлена прин-
ципом Эджворта [2], согласно которому при «разумном» поведении лица, принимаю-
щего решение – главного конструктора проектной организации – выбор решения сле-
дует производить на основе множества Парето [3]. Пусть ξi = fi (Ψ) ,i = 1,2,...,ζ – зна-
{ }чение
i-го
параметра
БРЭО
в
точке
Ψj =
ψ1j
,ψ2j
,...,
ψ
j ψ
, j = 1,2,...,ψ ,
полагая,
что
64 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
Ю.А. Гатчин, П.П. Парамонов
{ } { }ξ1j
,ξ
j 2
,...,ξ
j ζ
=
ξ1k
,ξ
k 2
,...,
ξ
k ζ
тогда и только тогда, когда j=k. Упорядоченный список (в
порядке убывания) всех проектных решений критериального множества составляет
{ }кортеж по предпочтениям ξij , j = 1,2,...,NS . В результате такого отображения точкам
множества допустимых проектных решений соответствует множество точек К с коор-
{ }динатами k1,k 2 ,...,kζ , каждая из которых принимает целочисленное значение на ин-
тервале [1,2,...,NS ] . При этом в каждой из гиперплоскостей размерности ζ −1, парал-
лельных координатам, лежит одна и только одна из точек множества К.
Множество К лежит в ζ -мерном кубе размером ( NS −1)× ( NS −1)× ...× ( NS −1) . В
силу построения любая точка множества К расположена на пересечении ζ гиперпло-
скостей размерности ζ −1, параллельных координатным гиперплоскостям и проходя-
{ }щих через точки
k1 ,k 2 ,...,k ζ
. По той же причине из
ξ1i ,ξi2 ,...,ξiζ
≥
ξ1j
,ξ
j 2
,...,ξ
j ζ
следу-
ет, что
ki1 ,ki2 ,...,kiζ
≤
k
1 j
,k
2 j
,...,
k
ζ j
, а значит, выявление точек, оптимальных по Парето,
на множестве значений критериев оптимизации Ξ эквивалентно аналогичной операции
на числовом множестве К по правилам сравнения ≤ . Тогда среди всех точек множества
К, принадлежащих множеству Парето по условию (ζ −1) NS +1 ≥ ki1 + ki2 + ...+ kiζ , пред-
ζζ
почтительными являются те варианты проектных решений, для которых ∑ ki > ∑ k j . =1 =1
Таким образом, решение задачи параметрического синтеза, сформулированной в [1], для случая многопараметрической оптимизации [4] проектных решений, составляет
( ) { }F* Ξ* = min F (Ξ(Ψ)) , где Ψ − вектор варьируемых параметров аппаратуры, вхоΨ ⊂GΨ
дящей в БРЭО, принадлежащий непустому множеству допустимых значений GΨ ⊂ G g1 ;
F (Ξ) =F(ξ1(Ψ), ξ2(Ψ), …, ξζ(Ψ)) − векторный критерий оптимальности, осуществляю-
щий отображение множества GΨ в непустое критериальное множество GF ⊂ G g2 ; Ξ* − искомое решение задачи проектирования БРЭО; G g1 и G g2 − арифметические вектор-
{ }ные пространства размерности
g1 ≥ 1 и
g2 ≥ 1 соответственно. Запись
min
Ψ⊂GΨ
F (Ξ(Ψ))
предполагает, что лицо, принимающее решение, – главный конструктор проектной ор-
ганизации – стремится уменьшить значения частичных критериев оптимальности ξ1(Ψ),
ξ2(Ψ), …, ξζ(Ψ) ∈Ξ , полагаемых однозначными функциями вектора Ψ параметров подсистем, входящих в БРЭО в качестве элементов агрегатной базы.
Рассматривая критерии ξ1(Ψ), ξ2(Ψ), …, ξζ(Ψ) ∈Ξ как аддитивно-сепарабельные
при F = F (Ξ) , можно записать: F1 ≤ F 2 , если ξ1i ≤ ξi2 , i=1, 2, …,ζ. В этом случае век-
торное решение F1 из критериального множества доминирует по Парето решение F 2 из того же множества.
Неформально, множество Парето GF* задачи многокритериальной оптимизации
(GF* − эффективное по Парето множество, порождаемое множеством векторов Ψ ∈GΨ ,
( ))GF* = F GΨ* можно определить как совокупность векторов F ∈GF , среди которых
{ { } }нет доминирующих. Формально, G*F = F* ∈GF : F' ∈GF : F' ≤ F = 0 .
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
65
МЕТОД ОПРЕДЕЛЕНИЯ ПАРЕТО-ОПТИМАЛЬНЫХ ПРОЕКТНЫХ РЕШЕНИЙ В АВИОНИКЕ
Заключение
Применение метода выявления Парето-оптимальных вариантов проектных решений апробировано на практике в разработках ФГУП «СПб ОКБ «Электроавтоматика» им. П.А. Ефимова». При проектировании изделий класса БЦВМ (бортовых цифровых вычислительных машин), состоящих из различных модулей авионики, было сформировано (рис. 2) множество эффективных по Парето модулей-вычислителей, составивших агрегатную базу построения БЦВМ семейства БЦВМ90-6ХХ.
Рис. 2. Технико-экономические показатели различных модулей-вычислителей, используемых при проектировании БЦВМ
Литература
1. Гатчин Ю.А., Видин Б.В., Жаринов И.О., Жаринов О.О. Модели и методы проектирования интегрированной модульной авионики // Вестник компьютерных и информационных технологий. – 2010. – №1. – С. 12–20.
2. Ногин В.Д. Принятие решения в многокритериальной среде: количественный подход. – М.: Физматлит, 2002. – 176 с.
3. Белокуров С.В. Эффективный алгоритм выбора недоминируемых решений в численных векторных схемах // Вестник Воронежского института МВД России. – 2008. – № 2. – С. 86–90.
4. Карпенко А.П., Котов И.О. Распараллеливание некоторых методов приближенного построения множества Парето в задачах многокритериальной оптимизации / Сб. трудов 9-ой международной конференции «Наукоемкие технологии и интеллектуальные системы», 18.03.2007. – М.: МГТУ им. Н.Э. Баумана, 2007. – Ч. 2, с. 194–197.
Гатчин Юрий Арменакович Парамонов Павел Павлович
– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, доктор технических наук, профессор, http://faculty.ifmo.ru/csd/
– СПб ОКБ «Электроавтоматика» имени П.А. Ефимова», директор – генеральный конструктор, доктор технических наук, профессор, postmaster@elavt.spb.ru
66 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
УДК 681.324
МЕТОД ОПРЕДЕЛЕНИЯ ПАРЕТО-ОПТИМАЛЬНЫХ ПРОЕКТНЫХ РЕШЕНИЙ В АВИОНИКЕ
Ю.А. Гатчин, П.П. Парамонов
Рассматриваются методологические основы формирования на множестве проектных решений в авионике подмножества эффективных по Парето решений и выбора наиболее эффективного проектного решения в векторном пространстве частных критериев качества. Ключевые слова: бортовое оборудование, многопараметрическая оптимизация, множество Парето.
Введение
В работе [1] сформулирована задача параметрического синтеза бортового радиоэлектронного оборудования (БРЭО) по множеству частных показателей качества ξ1, ξ2, …, ξς ∈Ξ , задаваемых в тактико-техническом задании (ТТЗ) на его разработку и составляющих вектор Ξ параметров проекта для каждой проектной альтернативы Si.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
63
МЕТОД ОПРЕДЕЛЕНИЯ ПАРЕТО-ОПТИМАЛЬНЫХ ПРОЕКТНЫХ РЕШЕНИЙ В АВИОНИКЕ
Поскольку основная аксиома оценки по нескольким показателям утверждает невозможность строгого математического доказательства существования максимально предпочтительного объекта по всем критериям ξ1, ξ2, …, ξς одновременно (рис. 1), то любое проектное решение из числа недоминирующих (т.е. не являющихся менее предпочтительными по всем показателям сразу) может быть признано в качестве искомого варианта проектирования.
Таким образом, сложность проблемы выбора проектного решения по совокупности показателей связана не столько с трудностями вычислений при генерации проектных решений, сколько с концептуальной обоснованностью методологии выбора «наилучшего» проектного решения при одновременном ξ1 → min, ξ2 → min, …, ξζ → min. В этой связи актуальным является решение задачи [1] параметрического синтеза БРЭО на множестве эффективных по Парето проектных решений.
ξ1
S2 S4
S1 S3
ξζ
0
ξ2
Рис.1. Геометрическое представление вектора параметров БРЭО для четырех различных вариантов Si проектных решений
Принцип формирования множества эффективных по Парето проектных решений
Способ многокритериальности выбора состоит в отказе от выделения единствен-
ной наилучшей альтернативы и соглашении о том, что предпочтение одной альтерна-
тиве перед другой можно отдавать, только если первая альтернатива оказывается луч-
ше второй по всем частным показателям. Если предпочтения хотя бы по одному част-
ному критерию расходятся с предпочтениями по другому, то такие альтернативы явля-
ются несравнимыми.
В результате попарного сравнения альтернатив все худшие по всем критериям
альтернативы отбрасываются, а все оставшиеся несравнимые между собой (недомини-
руемые) принимаются. Если все минимально достижимые значения частных критериев
не относятся к одной и той же альтернативе, то принятые альтернативы образуют мно-
жество Парето.
Актуальность приближенного построения множества Парето обусловлена прин-
ципом Эджворта [2], согласно которому при «разумном» поведении лица, принимаю-
щего решение – главного конструктора проектной организации – выбор решения сле-
дует производить на основе множества Парето [3]. Пусть ξi = fi (Ψ) ,i = 1,2,...,ζ – зна-
{ }чение
i-го
параметра
БРЭО
в
точке
Ψj =
ψ1j
,ψ2j
,...,
ψ
j ψ
, j = 1,2,...,ψ ,
полагая,
что
64 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
Ю.А. Гатчин, П.П. Парамонов
{ } { }ξ1j
,ξ
j 2
,...,ξ
j ζ
=
ξ1k
,ξ
k 2
,...,
ξ
k ζ
тогда и только тогда, когда j=k. Упорядоченный список (в
порядке убывания) всех проектных решений критериального множества составляет
{ }кортеж по предпочтениям ξij , j = 1,2,...,NS . В результате такого отображения точкам
множества допустимых проектных решений соответствует множество точек К с коор-
{ }динатами k1,k 2 ,...,kζ , каждая из которых принимает целочисленное значение на ин-
тервале [1,2,...,NS ] . При этом в каждой из гиперплоскостей размерности ζ −1, парал-
лельных координатам, лежит одна и только одна из точек множества К.
Множество К лежит в ζ -мерном кубе размером ( NS −1)× ( NS −1)× ...× ( NS −1) . В
силу построения любая точка множества К расположена на пересечении ζ гиперпло-
скостей размерности ζ −1, параллельных координатным гиперплоскостям и проходя-
{ }щих через точки
k1 ,k 2 ,...,k ζ
. По той же причине из
ξ1i ,ξi2 ,...,ξiζ
≥
ξ1j
,ξ
j 2
,...,ξ
j ζ
следу-
ет, что
ki1 ,ki2 ,...,kiζ
≤
k
1 j
,k
2 j
,...,
k
ζ j
, а значит, выявление точек, оптимальных по Парето,
на множестве значений критериев оптимизации Ξ эквивалентно аналогичной операции
на числовом множестве К по правилам сравнения ≤ . Тогда среди всех точек множества
К, принадлежащих множеству Парето по условию (ζ −1) NS +1 ≥ ki1 + ki2 + ...+ kiζ , пред-
ζζ
почтительными являются те варианты проектных решений, для которых ∑ ki > ∑ k j . =1 =1
Таким образом, решение задачи параметрического синтеза, сформулированной в [1], для случая многопараметрической оптимизации [4] проектных решений, составляет
( ) { }F* Ξ* = min F (Ξ(Ψ)) , где Ψ − вектор варьируемых параметров аппаратуры, вхоΨ ⊂GΨ
дящей в БРЭО, принадлежащий непустому множеству допустимых значений GΨ ⊂ G g1 ;
F (Ξ) =F(ξ1(Ψ), ξ2(Ψ), …, ξζ(Ψ)) − векторный критерий оптимальности, осуществляю-
щий отображение множества GΨ в непустое критериальное множество GF ⊂ G g2 ; Ξ* − искомое решение задачи проектирования БРЭО; G g1 и G g2 − арифметические вектор-
{ }ные пространства размерности
g1 ≥ 1 и
g2 ≥ 1 соответственно. Запись
min
Ψ⊂GΨ
F (Ξ(Ψ))
предполагает, что лицо, принимающее решение, – главный конструктор проектной ор-
ганизации – стремится уменьшить значения частичных критериев оптимальности ξ1(Ψ),
ξ2(Ψ), …, ξζ(Ψ) ∈Ξ , полагаемых однозначными функциями вектора Ψ параметров подсистем, входящих в БРЭО в качестве элементов агрегатной базы.
Рассматривая критерии ξ1(Ψ), ξ2(Ψ), …, ξζ(Ψ) ∈Ξ как аддитивно-сепарабельные
при F = F (Ξ) , можно записать: F1 ≤ F 2 , если ξ1i ≤ ξi2 , i=1, 2, …,ζ. В этом случае век-
торное решение F1 из критериального множества доминирует по Парето решение F 2 из того же множества.
Неформально, множество Парето GF* задачи многокритериальной оптимизации
(GF* − эффективное по Парето множество, порождаемое множеством векторов Ψ ∈GΨ ,
( ))GF* = F GΨ* можно определить как совокупность векторов F ∈GF , среди которых
{ { } }нет доминирующих. Формально, G*F = F* ∈GF : F' ∈GF : F' ≤ F = 0 .
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
65
МЕТОД ОПРЕДЕЛЕНИЯ ПАРЕТО-ОПТИМАЛЬНЫХ ПРОЕКТНЫХ РЕШЕНИЙ В АВИОНИКЕ
Заключение
Применение метода выявления Парето-оптимальных вариантов проектных решений апробировано на практике в разработках ФГУП «СПб ОКБ «Электроавтоматика» им. П.А. Ефимова». При проектировании изделий класса БЦВМ (бортовых цифровых вычислительных машин), состоящих из различных модулей авионики, было сформировано (рис. 2) множество эффективных по Парето модулей-вычислителей, составивших агрегатную базу построения БЦВМ семейства БЦВМ90-6ХХ.
Рис. 2. Технико-экономические показатели различных модулей-вычислителей, используемых при проектировании БЦВМ
Литература
1. Гатчин Ю.А., Видин Б.В., Жаринов И.О., Жаринов О.О. Модели и методы проектирования интегрированной модульной авионики // Вестник компьютерных и информационных технологий. – 2010. – №1. – С. 12–20.
2. Ногин В.Д. Принятие решения в многокритериальной среде: количественный подход. – М.: Физматлит, 2002. – 176 с.
3. Белокуров С.В. Эффективный алгоритм выбора недоминируемых решений в численных векторных схемах // Вестник Воронежского института МВД России. – 2008. – № 2. – С. 86–90.
4. Карпенко А.П., Котов И.О. Распараллеливание некоторых методов приближенного построения множества Парето в задачах многокритериальной оптимизации / Сб. трудов 9-ой международной конференции «Наукоемкие технологии и интеллектуальные системы», 18.03.2007. – М.: МГТУ им. Н.Э. Баумана, 2007. – Ч. 2, с. 194–197.
Гатчин Юрий Арменакович Парамонов Павел Павлович
– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, доктор технических наук, профессор, http://faculty.ifmo.ru/csd/
– СПб ОКБ «Электроавтоматика» имени П.А. Ефимова», директор – генеральный конструктор, доктор технических наук, профессор, postmaster@elavt.spb.ru
66 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)