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