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

ВВЕДЕНИЕ

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



1. Исходные данные и ограничения

Сформулируем совокупность исходных данных и ограничений для за-дачи распознавания случайных сигналов. Предположим, что распознаванию подлежат случайные сигналы X(t), наблюдаемые на интервале времени (0, T). Полагается, что сигналы представляются некоторыми конечномерными век-торами отсчетов некоторых статистик сигналов ξ, по которым будут прини-маться решения о принадлежности соответствующих образов. Вид этой ста-тистики зависит от вероятностной модели, выбранной для описания сигна-лов.
Введем M+ 1 гипотезы, которые могут быть сделаны в отношении на-блюдаемых сигналов: Hi, i = 1, M для заданных в статистическом смысле сигналов; HM+ 1 для неизвестных сигналов, объединенных в M+ 1-й класс. Предположим, что гауссовы плотности распределения вероятностей M сиг-налов W (ξ Hi /αi), i = 1, M заданы с точностью до неизвестных векторных параметров αi. Имеется классифицированная обучающая выборка заданных сигналов { γ , r=1, n, i=1, M} и априорные вероятности предъявления сигна-лов P H( i) = Pi, Pi i = 1
M 1 + Σ = 1 Для M+ 1- го класса сигналов плотность вероятности неизвестна и отсутствует обучающая выборка. Имеются лишь сведения качественного характера, что неизвестные сигналы определенным образом отличаются от M заданных сигналов.
Для формулирования условий требуется найти решения (структуры устройств распознавания сигнала), оптимизированные по совокупности пока-затели качества распознавания, быстродействия, а также затрат на проекти-рование и реализацию устройств с использованием ЭВМ.
Введем векторный показатель качества, который применительно к сформулированной задаче имеет вид:
Km =(K1(α), K2(α), K3, K4, K5), (1)
где K1(α) показатель неэффективности, характеризующий качество распознавания сигналов с учетом указанной специфики повышенной апри-орной неопределенности;
K2(α) показатель объема критической области отклонения гипотезы о сигнале из M+ 1 го класса;
α оценка векторного параметра, найденная по обучающей выборке для класса заданных сигналов;
K3 показатель быстродействия устройства распознавания, опреде-ляемый необходимым временем наблюдения сигналов и принятия решения;
K4 показатель затрат на реализацию устройств распознавания, вво-димый через объемы памяти и вычислений при реализации устройств на ЭВМ;
K5 показатель затрат на проектирование. В данном случае m = 5.
Понятие оптимальности решения для многокритериальной задачи оп-тимизации отличается от соответствующего понятия при использовании ска-лярного критерия оптимальности . Оптимальные решения многокритериаль-ных задач определяются задаваемым отношением предпочтения на множест-ве допустимых решений Γ. Решения γ(0) дельта Γ будем называть оптималь-ным по отношению строгого предпочтения >, если не существует других ре-шений γ дельта Γ, для которых справедливо отношение γ > γ(0) .
Иногда оптимальные решения удобнее искать в критериальном зада-ваемыми пространстве Rm, которое задается оценками векторного показате-лей качества (1), определяемыми значением соответствующих им целевых функций на множестве допустимых решений Γ (m число показателей). Ме-жду решениями на множествах Γ и существует тесная связь, определяемая аксиомой Парето, которая формулируется так: для двух оценок, удовлетво-ряющих неравенству Kl (γ) Kl γ(0) ≥ (γ), всегда выполняется соотношение γ > γ(0)
Векторное неравенство K(γ) K γ(0) ≥ (γ) означает, что выполняются система неравенств Kl γ(0) (γ) Kl ≥ (γ) для всех l = 1, m где хотя бы одно из неравенств является строгим.
В многокритериальных задачах отношение ≥, согласно аксиоме Парето играет важную роль. Решения, определяемые в соответствии с указанным отношением предпочтения образуют подмножество парето-оптимальных (оптимальных по Парето или эффективных) решений относительно вектор-ного показателя качества (1). Это подмножество обозначают через P(Γ), а в пространстве оценок через P Km (Γ) = opt≥(Γ). Включение K γ(0) (γ) = opt≥(Γ), а следовательно и γ0 дельта P(Γ) имеет место тогда и только тогда, когда не существует другой оценки γ дельта Γ, для которой было бы выпол-нено векторное неравенство K(γ) K γ(0) ≥ (γ).
В пространстве оценок могут быть также введены отношения строгого предпочтения >. Решения, определяемые в соответствии с этим отношением, образуют подмножество слабо оптимальных по Парето решений SRm(Γ), которые называют также решениями, оптимальными по Слейтеру . Для та-ких решений в пространстве оценок выполняется строгое векторное нера-венство K γ(0) (γ) > K(γ), то есть Kl γ(0) (γ) Kl > (γ), l = 1, m. При этом мно-жество S Rm (Γ)оказывается более широким, то есть имеет место включение PRm(Γ) SKm< (Γ). Таким образом, при исходном множестве допустимых решений Γ, отыскание оптимальных решений многокритериальной задачи распознавания сигналов сводится к отысканию подмножества Парето либо подмножества Слейтера в критериальном пространстве оценок Rm.






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

Рассматриваемая многокритериальная задача распознавания случайных сигналов по своей постановке и содержанию является более сложной по сравнению с традиционными задачами в теории многокритериальной опти-мизации, в которых каждое решение γ определяется n-мерным вектором па-раметров y. При этом множество допустимых решений Γ является подмно-жеством евклидового пространства Rn Γ R( дельта n) и оптимизация произ-водится путем вариации n-мерного вектора параметров y .
Мы рассматриваем более сложную задачу многокритериальной опти-мизации, в которой решением γ является оператор (алгоритм работы) устрой-ства распознавания случайных сигналов, отображающий некоторое функ-циональное пространства сигналов на множество введенных гипотез RM+ 1.
При этом множество Γ заранее не задано и поэтому стоит дополни-тельная задача его формирования. К настоящему времени общего решения таких многокритериальных задач формирования и выбора оптимальных ва-риантов систем еще не существует .
Нахождение подмножества оптимальных по Парето (либо по Слейтеру) решений для поставленной многокритериальной задачи распознавания сиг-налов непосредственно по введенной совокупности показателей (1) пред-ставляет очень сложную оптимизационную задачу, для решения которой мо-жет быть использован комбинированный метод, включающий аналитические и численные методы оптимизации. Рассмотрим некоторые принципиальные особенности методологии такой оптимизации, которая основана на обобще-нии материалов работ многих авторов .

Введение.3
1. Исходные данные и ограничения.5
2. Принципы решения многокритериальной задачи распознавания
случайных сигналов..8
3. Основы распознавания сигналов при наличии класса неизвестных
сигналов11
4. Правила распознавания при разных вероятностных моделях сигналов13
Заключение..15
Литература...17

Список литературы

1. Васильев В. И. Распознавание системы. Справочник.
К.: Наукова думка, 1983. 424 с.
2. Фукунага К. Введение в статистическую теорию распознавания.
М.: Наука, 1979. 368 с.
3. Омельченко А. А. Основы спектральной теории распознавания
сигналов. Харьков: Вища школа, 1983. 156с.
4. Прикладная теория случайных процессов и полей /
Коллективная монография под ред. К. К. Васильева,
В. А. Омельченко. Ульяновск: УлГТУ, 1995. 256 с.
5. Подиновский В. В., Ногин В. Д., Физико-математическая литература 2007. - 255 с.
6. Березовский Б. А., Барышников Ю. М., Борзенко В. И.,
Кепнер Л. М. Многокритериальная оптимизация: Математические
аспекты. М.: Наука, 1986. 186 с.
7. Безрук В. М. Векторна оптимізація та статистичне
моделювання в автоматизованому проектуванні систем
звязку. Харків: ХНУРЕ, 2002. 164 с.
8. Омельченко В. А. Многокритериальные задачи распознавания
сигналов. Ч. 2. Распознавание сигналов в условиях
повышенной априорной неопределенности // Отбор и
передача информации. 1989. Вып. 4(80). С. 8485.
9. Омельченко В. А., Балабанов В. В., Безрук В. М.,
Омельченко А. В., Фефелов Н. А. Распознавание неполностью
описанных случайных сигналов при наличии
класса неизвестных сигналов //Отбор и обработка
информации. 1992. Вып. 8. С. 7180.
11. Безрук В. М. Методы многокритериальной оптимизации
информационных систем //Радиоэлектроника и
информатика. 1999. Вып. 2(07). С. 6368.
12. Безрук В. М. Синтез и анализ парето-оптимальных систем
распознавания случайных сигналов методом рабочих
характеристк // АСУ и приборы автоматики.
1999. Вып. 109. С. 2529.
13. Безрук В. М. Оптимизация авторегрессионных алгоритмов
распознавания сигналов по совокупности показателей
качества // Інформаційно-керуючі системі на
залізничному транспорті. 2001. № 2. С. 1013.
14. Омельченко В. А., Безрук В. М., Коваленко Н. П. Рас-познавание
заданных радиосигналов при наличии неизвестных
сигналов на основе авторегрессионной модели //
Радиотехника. 2001. Вып. 123. С. 195199.
15. Безрук В. М., Евсеев К. К., Чеботов А. В. Метод распознавания
видов модуляции радиосигналов, описываемых
вероятностной моделью в виде смеси распределений.
// Прикладная радиоэлектроника. 2003.
№ 1. С. 2631.