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

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

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

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

Как правило, распознавание образов обычно производится при непол-ных априорных сведениях о распознаваемых сигналах или, как часто говорят, в условиях априорной определенности, которая преодолевается с использо-ванием обучающих выборок сигналов. В ряде прикладных задач на распозна-вание могут предъявляться сигналы, которые не относятся к 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) пред-ставляет очень сложную оптимизационную задачу, для решения которой мо-жет быть использован комбинированный метод, включающий аналитические и численные методы оптимизации. Рассмотрим некоторые принципиальные особенности методологии такой оптимизации, которая основана на обобще-нии материалов работ многих авторов .