автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Оптимизационные и игровые задачи распределения ресурсов в системах распознавания

РГ8 ОЯ

На правах рукописи

О 3 ОЕО 1337

МУНАСЫПОВ Наши, Амировпч

ОПТИМИЗАЦИОННЫЕ И ИГРОВЫЕ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В СИСТЕМАХ РАСПОЗНАВАНИЯ

Специальность 05.13.17 - теоретические основы информатики

АВТО РЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-матсматических паук

Москва 1997

Работа выполнена в Московском педагогическом государственном университете имени ГШ. Ленина на кафедре информатики и дискретной математики.

Научный руководитель:

академик Международной Академии информатизации, доктор физико-математических наук, профессор ГОРЕЛИК В А.

Официальные оппоненты:

академик РАЕН, доктор физико-математических наук, профессор РУДАКОВ КВ.

кандидат технических наук, доцент ПЕРЕПЕЛ ИЦЫН Е.Г.

Ведущая организация: Московский авиационный институт.

Защита диссертации состоится и 997 г. в 15. часов

на заседании Диссертационного Совета К 053.01.16 в Московском педагогическом государственном университете имени В.И. Ленина но адресу: 107140, Москва, ул. Краснопрудная, д. 14, математический факультет МПГУ имени В.И. Ленина, ауд. 301.

С диссертацией можно ознакомиться в библиотеке МПГУ имени В.И. Ленина но адресу: 119435, Москва, Малая Пироговская ул, д. 1.

Автореферат разослан «..ЗД...». года.

Ученый секретарь Диссертационного Совета КУЗНЕЦОВ Э.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Теория распознавания образов (РО) зародилась в 60-е года 20-го века. За сравнительно короткий промежуток времени она добилась больших успехов и продолжает успешно развиваться. В настоящее время существует много направлений в теории РО. Постановки задач и методы их решения отличаются большим разнообразием. При решении задач распознавания применяются методы из разных областей математики, в частности, статистические, логические, структурные и геометрические методы. Важные теоретические и прикладные результаты по проблеме РО в нашей стране представлены в работах Айзермана М.А., Бонгарда М.М., Бравермана Э.М., Вапника В.Н., Васильева В.И., Горелика А.Л., Журавлева Ю.И., Загоруйко Н.Г., Матросова В.Л., Рудакова К.В., Скрипкина В.А. и ряда других авторов. Большое число исследований имеется и за рубежом.

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

В данной диссертационной работе используется системотехнический подход к проблеме РО, который состоит в целостном рассмотрении процесса распознавания, включающего этап проектирования СР (определение набора создаваемых технических средств, т.е. признакового пространства, в условиях ограничений

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

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

В работе рассматривается также задача оптимального распределения ограниченных ресурсов при измерении признаков и находится решение задачи для некоторых частных случаев. Проблема функционирования СР при наличии ресурсных ограничений является актуальной, так как в большинстве практических случаев процесс распознавания происходит в условиях жестких ограничений либо на время, либо на энергетические и материальные ресурсы.

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

хорошие результаты.

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

Для реализации поставленной цели потребовалось решить следующие задачи:

- рассмотреть некоторые виды оптимизационных задач построения признакового пространства при наличии ограничений на ресурсы, предназначенные для создания технических средств измерения;

- исследовать оптимизационную задачу распределения ограниченных ресурсов при измерении признаков в СР;

- сформулировать ряд задач построения оптимального признакового пространства в условиях конфликта при различных предположениях относительно информированности сторон и эффективности мер распознавания и противодействия;

- рассмотреть функционирование СР б условиях конфликта и исследовать игровую задачу распределения ограниченных ресурсов при измерении признаков.

Объектами исследования являются системы распознавания, предназначенные для решения задач распознавания.

Предметом исследования является построение и функционирование СР при наличии ресурсных ограничений, а также в условиях конфликта.

Методологическую основу работы составляют методы теории распознавания образов, теории оптимизации, исследования операций, математического анализа, понятия и аппарат теории игр.

Научная новизна. Оптимизационные задачи при наличии ограничений в теории РО являются недостаточно изученными. В работе рассматриваются некоторые новые постановки задач с ограничениями. Исследуется задача распределения ограниченных ресурсов в СР и предлагается метод ее решения. Задачи распознавания образов в условиях конфликта тоже малоисследован!!. Предлагается теоретико-игровой подход для решения некоторых задач в области РО.

Практическая значимость работы. Предложенные способы применения оптимизационных и теоретико-игровых методов в теории РО могут быть использованы в различных прикладных задачах. Например, при создании систем медицинской и технической

диагностики, в геологическом прогнозировании и при решении различных других задач, где применяются традиционные методы РО, необходимо учитывать ограничения на ресурсы (время, энергетические затраты, финансы и т.п.). Модель распознавания в условиях конфликта может быть применена во многих областях, например, в военной разведке, где сторона, ведущая разведку, неизбежно сталкивается с противодействием получению важной информации, в средствах радиосвязи, когда передаваемые и принимаемые радиосигналы подвержены влиянию различных шумов (естественного и искусственного происхождения), в рыночной экономике, где ведется большая конкурентная борьба, и т.д.

Основные положения, выносимые на защиту:

- новые формулировки задачи построения оптимального признакового пространства при наличии ограничений на ресурсы, предназначенные для создания СР, и методы ее исследования;

- постановка оптимизационной задачи распределения ограниченных ресурсов при измерении признаков в СР; решение задачи для случая экспоненциального закона распределения вероятностей точного определения признаков;

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

- формулировка и решение ряда теоретико-игровых задач построения оптимального признакового пространства в условиях конфликта при различных критериях качества функционирования СР и различных предположениях относительно информированности сторон, эффективности СР и мерах противодействия;

- постановка игровой задачи распределения ограниченных ресурсов при измерении признаков в СР, исследование случая, когда функции зависимости вероятностей определения признаков от количества вкладываемых ресурсов имеют экспоненциальное распределение, и доказательство существования цены игры при некоторых предположениях относительно параметров распределения.

Апробация работы. Результаты исследования докладывались на научно-практической конференции "Содержание и технологии разноуровневого образования" (Новокузнецк, декабрь 1995 г.), на V Международном форуме информатизации (Москва, ноябрь 1996 г.), на научно-методическом семинаре кафедры информатики и дискретной

математики ЖГУ им.В.И.Ленина, на аспирантском объединении.

Структура и объем диссертации. Работа состоит из введения, трех глав, заключения и списка использованной литературы. Диссертация содержит 121 страницу, из них 114 страниц основного текста, 7 страниц - список использованной литературы, включающий 71 наименование.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе рассматриваются некоторые оптимизационные задачи в теории распознавания образов.

В §1.1 вводятся основные понятия, использующиеся в дальнейшем при изложении материала диссертации. Формулируется основная задача РО.

Пусть объекты характеризуются набором N числовых признаков

х1.....х . Тогда каждый объект со можно представить как /^-мерный

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

классов). Будем предполагать, что классы являются непересекающимися, т.е. Ор П = 0, где р Ф д, р=1 ,т, q=ТТт. Обозначим через со й-ый объект р-го класса, т.е. и £ С ,

Р с5 РхЗ р

й=Т7лр, где К - число объектов класса Пр, описанием вектора сорЬ

является вектор (х1рЬ.....где ~~ значение /-го признака

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

В §1.2 рассматривается задача построения оптимального признакового пространства при наличии ограничений на ресурсы. Пусть Г - технические средства, предназначенные для определения соответствующих признаков х , С. - ресурсы,

предназначенные для создания соответствующих средств Т , С0 -общее количество ресурсов, выделяемых на построение СР. Ограничения имеют вид

N

где

S А. О СО . (I)

3=1

{ I, если признак д: используется

Xj = j при распознавании объекта, (2)

I 0, в противном случае. Критерии качества функционирования СР могут быть введены, например, следующим образом:

1) V = min £ XJx3.-^,)г. (3)

p.q.k.l 3=1 J pR ql

2) W = min 2 X-x3 f, (4)

p.q 3=1 J p Q

кр

где x =(x1,xN) - центр класса ü , p=1 ,m, ^=-4- У x*..

P P P r P 1 P Л jf pk

p k=1

3) FT = Min. У ■ , (5)

p.q j=/ j

где

1 к к

7 p q

=- У У (х5,-х> -,)г (6)

К К ¿1 1 =1 рк

Р ч

есть информативность признака х^ для пары классов Пр и О .

4) П = I Х.р1, (7)

3=1 -3

где

-тЬ^ (3)

Г=1

есть средняя информативность признака я , г - номер пары классов,

1 ^ г ^ п, п = ) - число пар классов.

При заданном общем количестве ресурсов С , выделяемых на создание СР, требуется найти набор Х°, максимизирующий значение критерия эффективности (У. Набор Х° является оптимальной стратегией стороны, осуществляющей разработку СР. На конкретном числовом примере проиллюстрирован способ нахождения оптимальных стратегий и значений критерия эффективности. Показано, что функция ^тах(С0) является неубывающей, кусочно-постоянной и разрывной в некоторых точках С . Расширение признакового пространства (путем добавления к набору X новых признаков) приводит к увеличению значения критерия эффективности СР.

В §1.3 рассматривается задача оптимального распределения ограниченных ресурсов при определении признаков. Допустим, что выбрано оптимальное признаковое пространство и созданы технические средства, предназначенные для определения признаков. Обозначим через Т количество времени, отводимого для распознавания объекта, ? - время, затрачиваемое для определения признака х , J=T7R, причем

* N

з=1

Требуется распределить это время оптимальным образом, т.е. так, чтобы критерий эффективности СР (вводимый определенным образом) принял экстремальное значение. Пусть - вероятность

измерения признака х , если на измерение этого признака выделяется время в количестве Допустим, что функции Pj(tj) имеют экспоненциальный закон распределения, т.е.

Pj(tjb1-e

"И-141 ___

J J, [i.>0, J=T~J¡.

Рассматривается следующая постановка задачи:

W(t)= Y, PJ( 1-е J J) - max J=i

при ограничениях

E t.=T, t.zo, J=ttk. j=i J J

Для этого случая методом множителей Лагранжа следующая теорема.

Теорема. Решением задачи (10),(II) является вектор

О)

(Ю)

(II) доказывается

t*=(t

1" •

,,t* j, компоненты которого t* определяются по формуле

г =

п, In V,

где v =pJ|j, ,

ln v,

О,

а п

т- 2 -j=I

ТЬ А

J=T7ñ,

J=ñTT7R,

такое число, что v >Q , v . .(íQ

ТЬ TI Пг 7 n+ 7

(12)

Qk есть

переменный порог, который определяется по формуле

■ N Хп v .

3=1 ^з

к

Е ц

J

= е

При этом предполагается, что значения г^ расположены в порядке убывания, т.е. V ..зф^. . .

Устанавливается зависимость решения от параметров распределения и величины ресурсов.

Лемма. Пусть ц =..р'=...=рг7=р. Тогда

Г.('Т) = Т/И, /=ТХ 3 _

Ш(Х*(Т)) = N р (1-е * ).

Функция Ш(Х*(Т)) является возрастающей, вогнутой и имеет горизонтальную асимптоту у=Щ-

Можно также показать, что при фиксированном Т0 функция И(Х*(И)) увеличивается с ростом N и ограничена сверху, причем приращение функции на каждом шаге уменьшается с ростом

N.

Б §1.4 дается определение алгоритма распознавания. Задача оптимизации алгоритмов распознавания формулируется как задача нахождения в определенном классе алгоритмов такого алгоритма,на котором целевая функция достигает оптимума. Приводятся примеры целевых функций. Вводятся понятия устойчивости и корректности алгоритма. Рассматриваются новые постановки задач, а именно, задачи нахождения оптимального алгоритма при погрешностях в измерении признаков. Рассматривается также задача нахождения алгоритма с минимальным радиусом ^-неустойчивости в классе линейных решающих функций и устанавливается зависимость величины е от параметров линейной решающей функции.

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

В первых двух параграфах рассматривается конфликт двух сторон в процессе распознавания, одна из которых создает систему распознавания объектов, а другая - систему противодействия с целью воспрепятствовать распознаванию объектов. Рассматривается следующая ситуация.

Пусть сторона II создает некоторую совокупность объектов, которые описываются набором признаков Сторона I

разрабатывает систему распознавания (СР) этих объектов, сторона II стремится с помощью системы противодействия (СП) максимально снизить эффективность СР, причем обе стороны имеют ограниченное количество ресурсов. Стратегиями стороны I являются вектора Л.,

определяемые выражением (2). Стратегии стороны II

.. - ,\хя), где причем полагаем если сторона

II противодействует определению признака х}, и 11=1 - в противном случае. Ограничения!™ на множества стратегий сторон I и II являются соответственно выражения

я т т тт тт

Е с^ « с1, Е с^и-ц,; «с11,

где С* ~ затраты ресурсов стороны I (стороны II) для

создания технических средств Г^ (противодействия определению признака г- ), С1 и С11 - общие величины ресурсов сторон I и II.

Постановки задач и получаемые результаты будут различными в зависимости от различных предположений и ограничений, накладываемых на условие задачи. Эти предположения могут иметь следующий характер:

1. Предположения об информированности сторон.

11. Сторона I при создании СР знает всю совокупность объектов стороны II, но не знает ее СП. Сторона II при выборе СП не знает СР стороны I.

12. Информированность стороны I та же, а сторона II при выборе-СП знает СР стороны I.

Возможны и другие случаи. Заметим, что во втором случае дополнительная информация позволяет добиться стороне II лучшего результата.

2. Предположения об эффективности СР стороны I.

21. Создание каждого технического средства СР обеспечивает полное и точное определение соответствующего признака.

. Каждое техническое средство обеспечивает определение соответствующего признака с некоторой вероятностью Ру Р,€_[0;1], 1=1,N. Под вероятностью определения можно понимать вероятность измерения значения признака.

3. Предположения об эффективности СП стороны II.

31. Если сторона II противодействует определению /-го признака объектов стороной I, то измерение этого признака стороной I полностью невозможно, даже если сторона I создает соответствующее техническое средство для измерения признака х . 30. Если сторона II противодействует определению /-го признака объектов стороной I, то этот признак определяется соответствующим средством стороны I с вероятностью <2 , <2^(0;11, /=7777.

4. Выбор критерия эффективности СР. В качестве критерия можно рассматривать следующие выражения:

41. Минимум квадрата расстояния меж®' возможными параш классов

W = min R2.

r

42. Среднее значение среднеквадратичного расстояния между парами классов

^ = е е

г= i

Ау Минимум отношения среднеквадратичного расстояния между

парами классов к среднеквадратичным разбросам этих классов

Нг(П ,0 ) W = min-9-

р.а S2(Qp)Sz(üq)'

В §2.1 предполагается, что обе стороны одинаково оценивают информативность признаков (т.е. одни и те же признаки для обеих сторон имеют одинаковую информативность). Рассмотрим совокупность предположений (11,21,31,41 ). Тогда критерий эффективности СР равен

W(\,\l) = min £ А.ЛА.р-'. (13)

14r$nJ=1 J J r

Сторона I стремится максимизировать функцию W(X,\x), сторона II -минимизировать Получается антагонистическая матричная

игра Т={МгМг,т(Х,\х)}, где

= 0^(\r...,\s)\\Je(0;1}, /=7777; ZG1}, (14)

Мг = .....\iN)\\XjdCOH), J=77N; icfd-^j) < С11;, (15)

f7f)\,,|jj - выигрьпп стороны I. Как известно, в антагонистической игре оптимальное поведение игроков основывается на принципе гарантированного результата. Оптимальная гарантирующая стратегия стороны I - к°=(Х°1,...,\°):

11 о I N i

min min 2 = шх win min 2 Л.,^ p -y.

y. J J г "А ц J=1 J J r

Оптимальная гарантирующая стратегия стороны II - .

N Г 1 N 1 -

mar min £ ^iM^P = maj: min Z -y«

% l^r^n J=1 J J г а. /<г<гг j = 1 J J Г

Здесь v и v - соответственно нижняя и верхняя цена игры. Стратегии А.0 и обеспечивают соответственно сторонам I и II максимальный гарантированный результат. Цена этой игры в чистых стратегиях, как показано на примерах, может не существовать (по определению, цена игры v существует, если v=v=v).

Аналогично рассматриваются другие случаи, которые также приводят к необходимости рассмотрения матричной игры.

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

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

В §2.2 предполагается, что информативности признаков оцениваются обеими сторонами, вообще говоря, по-разному. Поэтому цели сторон не являются в общем случае противоположными. Получаемая игра является биматричной (мы рассматриваем конечное число стратегий сторон). В качестве принципа оптимальности рассматривается обобщенный принцип гарантированного результата. Предполагается, что сторона I знает обе функции выигрыша и й'2 (т.е. функции выигрыша сторон I и II соответственно) и передает информацию о выборе своей стратегии стороне II. Поведение стороны I основывается на разумности стороны II, а именно, сторона I может считать, что сторона II будет выбирать свою стратегию так, чтобы максимизировать свою функцию \Чг при известной стратегии стороны I. Как известно из теории игр, передача информации о выборе стратегии стороны I стороне II гарантирует первой стороне получение выигрыша, не меньшего, чем обычный максимин.

Пусть и я - множества допустимых чистых стратегий сторон

I и II соответственно, определяемые по формулам (14), (15).

Определение. Гарантирующей стратегией стороны I называется стратегия ... Д^р, такая, что

т1п У/1Скг,\1) = таг т1п Щ1^,^)- (16)

Это случай наименьшей информированности сторон. Если же сторона

II знает выбор стратегии А, стороны I, то она выберет свою стратегию ц не из всего множества М2, а из множества

М (К) = йр. ^СА-.М.'; = т1п Пг(Х,[1)}. (17)

Ии

Оптимальной стратегией стороны I в этом случае является стратегия А.ог, такая, что

т1п = таг тШ \У1(Х,\х). (18)

ц£М2слог; Л€М; цеи ГЛ.;

Решение биматричной игры можно определить и как множество точек (ситуаций) равновесия.

Определение. Ситуация называется ситуацией (точкой)

равновесия (в чистых стратегиях) в биматричной игре, если У?1(Х*,\х*) >

Р , „ р „ V ХеИ., V (19)

На конкретном примере из области РО проводится сравнение обычного гарантированного результата с результатом, который может получить сторона I при передаче информации второй стороне о выборе своей стратегии, а также с точками равновесия.

В §§ 2.3-Е.4 задача обобщается на случай конфликта двух сторон, каждая из которых наряду с распознаванием образов осуществляет меры противодействия (каждая из сторон имеет СР и СП). Обозначим через и Зг системы распознавания, П1 и Пг -системы противодействия сторон 1" и II соответственно. Пусть ^ГА,1,)!11;, 'г^гл11,^;, ф1^11,^1;, ф11^1,^11; - критерии эффективности систем Б1, £ , П и П соответственно (причем полагаем Ф1^11,^1; = -РГ11^1,^;, Ф^СА1,^11) = -Г^А.1,)!11,)). Обе стороны стремятся по возможности максимизировать каждый показатель эффективности своих систем. Возникает проблема выбора общего критерия Р1=Г1СИг1,Ф1; и РТ1=Р11(Ш11,Ф1Х) для сторон I и II соответственно. Используем свертки критериев

Р1 (X, ц 1П1 (А.1 .ц11)+С2ФХ (А11, ц1),

где С?» С2> и £ - весовые коэффициенты критериев, причем | =7. Эти формулы можно переписать следующим образом:

р1 сл.,1л;=с (Xх .р.11 )-^21Г1Х (к11 .ц1;, {20)

В §2.3 рассматриваются свертки критериев с равными весовыми коэффициентами (С,=С2> ВСЛ8ДСТБие чего, как и в §2.1,

получается модель антагонистической матричной игры. Функция выигрыша равна Р(Х,\1)=Р1(Х,\1), а стратегиями сторон I и II являются соответственно ("ЭД-мерные вектора

(г1=<з1а1,ц.1>^........

и ... д^1.....

В §2.4, в отличие от предыдущего параграфа, рассматриваются свертки критериев с разными коэффициентами, что приводит к модели неантагонистической игры. Так же как и в §2.2, аналогично определяются гарантирующие стратегии сторон, гарантированный результат при передаче информации, ситуации равновесия.

В главе 3 рассматривается функционирование системы распознавания в условиях конфликта.

В §3.1 рассматривается игровая задача распределения ресурсов при определении признаков в СР. Предположим, что вероятность Р определения признака х^ зависит от величины ресурсов С затрачиваемых на определение данного признака,, причем эта зависимость такова, что с ростом С^ величина увеличивается, т.е. функции являются возрастающими." Это

допущение естественно, так как с ростом вкладов вероятность определения признака увеличивается. Пусть 00 - общая величина ресурсов, выделяемых на распознавание объекта. Тогда

Пусть имеется некая сторона, противодействующая процессу распознавания, причем для создания мэр противодействия выделено общее количество ресурсов В0. Обозначил через 1) величину ресурсов, выделяемых на противодействие определению признака х , причем

3=1 17

Предположим, что выделение средств д^ на противодействие определению признака хприводит к тому, что признак х} определяется системой СР с вероятностью (3 (Б^). Естественно, что величина ) уменьшается с ростом I) .

С учетом вероятностей ^¿(Ср и О^(^) критерий эффективности СР может принимать следующий вид:

Обозначим

ЩС,В) = Е Е (¿Р.(С,)Я,(0,). (21)

4- 2 Рг-

г=1

Тогда

Решением задачи является нахождение цены игры (если она

ЩС.О) = Е (22)

^ _ ^ ч) о о

существует) и оптимальных стратегий обеих сторон. В зависимости от конкретного вида функций и аналитические

выражения для функции выигрыша могут иметь различный вид.

Функции Р^(О^) обычно являются вогнутыми, - выпуклыми для

любого j, J=1Вогнутость и выпуклость соответственно функций и 0,(0^) имеет естественную физическую интерпретацию: с ростом затрат ресурсов С^ вероятность Р^ будет увеличиваться, однако эффективность затрат при приближении Р^ к I уменьшается; аналогично с ростом вероятность уменьшается, эффективность затрат на противодействие при приближении ^ к О также падает. Функции и часто либо подчиняются некоторому закону

распределения, в частности, экспоненциальному, либо могут быть аппроксимированы функциями специального вида.

Пусть функции Р (С ) и 0Л1> ) являются экспоненциальными: ¿р.й, 3 3 -7,1), Р}(С})=1-е 3 3; е 33; (3}>0, т}>0.

Если в качестве критерия рассматривается выражение (22), то получаем

Ш(С,0) = £ р3(1- е 3 3) е 3 3 . (23)

3 = 1

Множества стратегий сторон I и II имеют соответственно вид

*,=СС|С=ГС,,... ,су; Д (24)

Возможны различные предположения относительно информированности сторон о параметрах распределения и значениях р3. Пусть обе стороны имеют полную информацию о значениях информативностей р3 и параметрах распределения и 7 .

Оптимальными стратегиями сторон I и II являются соответственно

V,

'7= V.

с з=1 в с 3=1

Цена игры при произвольных значениях р3, р^, 7^ может не

существовать. Это проиллюстрировано на конкретном числовом

примере.

При некоторых предположениях относительно параметров р3, 7^ можно показать, что цена игры существует. Рассмотрим случай, когда р?=..(3?=...=рн=р, 7,=..-=7К=7- в этом

стратегии С*=(С*г и Б* такие , что

т1п 2 Р С 1-е ьзсз)е~Ьвз= тюх т1п Т, р3 (1-е 5 С 3 3 )е

в з=1 с в 3=1

N , -I тах 2 Р (1-е Ъзсз)е-Ь»*з= ш1п тах „< -Р Е Р3(1-е 3 3 )е

случае имеем

N „ -рс. -уV.

ЩО,В)= 2 р(1- е *) е •>. (26)

3=1

Лемма. Непрерывная игра с функцией выигрыша (26) и пространствами стратегий (24),(25) имеет цену игры в чистых стратегиях.

В §3.2 рассматривается интенсивность использования технических средств в системе распознавания. В отличие от предыдущего, здесь предположения относительно возможностей технических средств распознавания носят более общий характер, а именно, каждое средство распознавания позволяет определить, вообще говоря, некоторую совокупность признаков (аналогичное предположение выдвигается и относительно средств противодействия). В качестве метода решения задачи оптимального распределения интенсивностей используется метод сведения решения матричной игры к решению пары двойственных задач линейного программирования.

В заключении перечисляются основные результаты, полученные в диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИЙ

1) Рассмотрены некоторые новые формулировки задачи построения оптимального признакового пространства при наличии ограничений на ресурсы, предназначенных для создания технических средств измерения признаков. Проведены численные эксперименты, иллюстрирующие зависимость значения критерия эффективности и оптимальной стратегии от количества вкладываемых ресурсов.

2) Исследована оптимизационная задача распределения ограниченных ресурсов при измерении признаков в процессе функционирования СР. Найдено решение задачи для случая, когда функции зависимости вероятности определения признаков от количества вкладываемых ресурсов имеют экспоненциальный вид. Исследована зависимость решения от параметров задачи.

3) Описаны некоторые новые постановки задач оптимизации алгоритмов распознавания, а именно, в классе линейных решающих правил рассмотрены задачи нахождения оптимального алгоритма при неточных измерениях признаков и алгоритма с минимальным радиусом неустойчивости (возникающей вследствие неопределенности в измерении признаков), установлена зависимость радиуса

неустойчивости от параметров линейной решающей функции.

4) Сформулирован ряд теоретико-игровых задач построения оптимального признакового пространства в условиях конфликта. Рассмотрены различные критерии качества функционирования СР и различные предположения относительно информированности сторон, эффективности СР и мер противодействия. Показано, что в зависимости от исходных предположений конфликт может носить как антагонистический, так и неантагонистический характер. На конкретных примерах проиллюстрировано нахождение цены игры и оптимальных стратегий.

5) Рассмотрена игровая задача распределения ограниченных ресурсов при измерении признаков. Исследован случай, когда функции зависимости вероятностей определения признаков от количества вкладываемых ресурсов имеют экспоненциальный вид. Доказано существование цены игры при некоторых предположениях относительно параметров распределения.

Основные положения диссертации нашли отражение в следующих работах:

1. Горелик В.А., Мунасыпов H.A. Задача распределения ограниченных ресурсов в системе распознавания //Моделирование, оптимизация и декомпозиция сложных динамических процессов. - М.: ВЦ РАН, 1996. - С. 105-122.

2. Горелик В.А., Мунасыпов H.A. Использование теоретико-игровых методов при решении задачи построения оптимального признакового пространства //Моделирование, оптимизация и декомпозиция сложных динамических процессов. - М.: ВЦ РАН, 1996. - С. 123-144.

3. Мунасыпов H.A. Игровая задача распределения ресурсов в системе распознавания //Деп. в ВИНИТИ от 31.10.96. J£ 3I8I-B96, - 12 с.