Файл: Васильев, В. В. Гибридные модели задач оптимизации.pdf

Г л а в а 7

РЕШЕНИЕ НЕКОТОРЫХ ЗАДАЧ ОПТИМИЗАЦИИ НА ЦИФРОВЫХ АНАЛОГАХ

7.1. РЕШЕНИЕ МАТРИЧНЫХ ИГР НА ЦИФРОВОЙ МОДЕЛИ ПУТЕМ РЕАЛИЗАЦИИ ИТЕРАТИВНОГО МЕТОДА БРАУНА

Известно [74, 184], что матричные игры можно свести к эквивалентным задачам линейного программирования. На этой основе могут быть построены специализированные электронные мо­ дели матричных игр.

Интересным с точки зрения моделирования представляется итеративный метод решения матричных игр, известный под назва­ нием метода Брауна или метода фиктивной игры. Суть этого метода в следующем. Игра с матрицей А — || a£J- ||т ,„ многократно повторя­ ется. В каждой партии каждый из игроков выбирает чистую стра­ тегию, наилучшую против смешанной стратегии противника, ком­ поненты которой непрерывно корректируются от партии к партии на основе частот использованных чистых стратегий. Доказано [184], что при достаточно большом числе партий выигрыш в методе фик­ тивной игры стабилизируется и стремится к цене игры, а частоты использования чистых стратегий игроков определяют компоненты векторов оптимальных смешанных стратегий.

Математически этот метод сводится к следующему. Пусть после S-й партии первый игрок обнаружил, что его противник выбрал /-ю чистую стратегию 5 /раз (J = 1,2, ..., п). На этом основании пер­ вый игрок предполагает, что его противник придерживается сме­ шанной стратегии:

W(S) = (SJS, S 2/S .......... SJS).

При этом допущении первый игрок выбирает в S + 1 партии is-ю чистую стратегию, обеспечивающую максимальный средний выиг­ рыш против W(S>. Величина определяется как номер максималь­ ной компоненты вектора A W (S>*.

Аналогично второй игрок после t партий предполагает, что сме­

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

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

Величины элементов матрицы выигрышей ас) хранятся в регист­ рах Рп , ..., Р22. В схеме модели используются также счетчики Ux и 112 по числу чистых стратегий первого игрока, счетчики Wxu W2 по числу стратегий второго игрока, накапливающие сумматорыиндикаторы экстремального сигнала «ЭКСТР-1» и «ЭКСТР-2», схемы И, ИЛИ и логические элементы, управляющие работой модели, куда входят триггеры 7\ и Т2, счетчик числа партий IV формировате­ ли импульсов Фи Ф2, Ф3 и схема # 9.

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

До начала работы счетчики 1)г, U2, Wi, W2, N и триггеры 7\ и Т2 находятся в нулевом положении. Предварительно на одном из выходов «ЭКСТР-1» устанавливается сигнал логической единицы. Для определенности пусть это будет выход № 1. Сигнал пуска, поступивший на единичный вход триггера Т2, установит его в еди­ ничное положение и откроет схему Я9 на счетный вход триггера Тх. Первый импульс установит его в единичное состояние. Этот сигнал, сформированный Ф2, пройдет через открытую схему # 3 и запишет единицу в счетчике Ux, что будет соответствовать выбору первым игроком в первой партии первой чистой стратегии. Второй импульс установит триггер Тг в нулевое состояние. Сигнал нулевого выхода 7\ поступит на входы схем Ихи И2, но пройдет на выход только схемы Иъ открытой по второму входу единичным сигналом первого выхода «ЭКСТР-1». Выходной сигнал Иг используется в качестве управляю­ щего для выдачи в сумматор-индикатор «ЭКСТР-2» содержимого первой строчки регистров РХ1 и Р12. «ЭКСТР-2» выбирает номер ка­ нала с минимальным содержимым (пусть это будет канал № 2).

стратегии, наилучшей против первой чистой стратегии первого иг­ рока. Импульс Ф3 запишет единицу в счетчике N числа пар­ тии.

180

Очередной импульс тактового генератора приведет к записи содержимого регистров второго столбца Р12 и Р22 в «ЭКСТР-1», выделению в последнем номера канала с максимальным содержи­ мым, записи в соответствующем счетчике единицы и т. д. с той раз­

ницей, что на каждом последующем шаге содержимое группы ре­ гистров будет суммироваться с накопленными ранее числами в сумматорах-индикаторах экстремальных сигналов «ЭКСТР-1» и «ЭКСТР-2». Работа модели будет остановлена по сигналу перепол­ нения счетчика N.

181

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

При этом содержимое счетчиков и { и Wj соответствует частотам использования чистых стратегий игроков от начала игры, содержи­ мое индикаторов «ЭКСТР-1» и «ЭКСТР-2» — числу проведенных партий. Если емкость счетчика N выбрать достаточно большой (ІО4 — ІО6 единиц), то указанные выше частоты будут стремиться к величинам компонент оптимальных смешанных стратегий игро­ ков, средние выигрыш и проигрыш — к цене игры, увеличенным в число партий раз.

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

Схема модели на основе счетчиковых систем с ручным вводом информации приведена на рис. 111. Информация о величинах эле­ ментов матрицы А вводится путем коммутации входов схем — И8 с выходами дешифратора датчика временных интервалов, общего для всей модели (на рис. 111 не показан). В качестве такого датчика в данном случае может быть использован десятичный счетчик. Роль сумматоров-индикаторов экстремального сигнала выполняют счет­ чики Счи Сч2, Сч3, триггеры Тг, Т2, Т5, Тв, Т9\ схемы совпадений

И9, И10, # 18; схемы разделения ИЛИ&, ИЛИ3, ИЛИ9, ИЛИ10 (для модели первого игрока). Аналогично для второго игрока.

Счетчики Счг и Сч2 начинают подсчет импульсов тактовой часто­ ты одновременно с датчиком временных интервалов. Счетчик Счх будет остановлен при поступлении сигнала на единичный вход 7\, а счетчик Сч2 — при поступлении сигнала на единичный вход Т2. Это будет соответствовать сложению в прямом коде содержимого счетчиков с элементами одного из столбцов матрицы. В режиме выделения максимального сигнала счетчики объединяются счет­ ными входами с помощью схем ИЛИ5, ИЛИв и опрашиваются им­ пульсами генератора тактовой частоты, подключенного ко входу R. Сигнал переполнения счетчика с максимальным содержимым уста­ новит триггер Тъ или Тв в единичное состояние и запретит поступле­ ние импульсов через схему И1а. Таким образом, в счетчике регенера­ ции Сч3 будет зафиксировано число импульсов, дополняющее мак­ симальный сигнал по емкости счетчика. Аналогичным образом работает сумматор-индикатор минимального сигнала (для модели второго игрока). Выделение минимального сигнала обеспечивается тем, что в счетчиках Сч4 и Счъ информация содержится в дополни­ тельном коде. Счетчики начинают считать после поступления сиг­ налов с выхода триггеров Т3 и Г4. Этим обеспечивается инвертиро­ вание кодов и переход к операции минимизации. Поясним назначение управляющих сигналов схемы: a, b — сигналы ходов отдельных

182

äfiwi I-----

игроков; с, d — сигналы выбора чистых стратегий; е, /, g, h — им­ пульсы тактовой частоты; k, I, т, п — сигналы ручного выбора стратегий игроков; р, q — сигналы сброса.

На рис. 111 ряд управляющих и сбросовых цепей не показан.

Востальном работа схемы рис. 111 аналогична работе схемы рис. 110.

Кнедостаткам цифровой модели на счетчиковых системах в опи­ санном варианте относится сравнительно низкое ее быстродействие.

Время, необходимое для проведения N партий, приблизительно равно

2 N (N + 10) 10m J - ,

/Т

где т число десятичных разрядов для кодирования элементов матрицы А; /т — частота тактового генератора.

Применение индикаторов экстремального сигнала с поразряд­ ным сравнением величин позволяет сократить это время до значения

21V[I0m+ (logW + m ) 1 0 ] 4 - .

/ Т

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

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

Описанные модели могут быть также использованы в режиме имитаторов, когда выбор стратегии одного из игроков определяется

с применением какого-либо вероятностного механизма, а вторым игроком является оператор.

7.2. ТОЧЕЧНЫЕ ИНТЕГРАТОРЫ НА ОСНОВЕ СЧЕТЧИКОВЫХ СИСТЕМ

Под точечными интеграторами, как известно, понимают устройства [1461, которые по значениям ординат некоторой функции в ряде точек по одной из формул численного интегрирования опре­ деляют значения интеграла в тех же точках.

Так, при использовании формулы трапеций будем иметь:

Точечные интеграторы на' основе счетчиковых систем могут быть построены по последовательной или параллельной схеме. В после-

184