Устройство для вероятностного моделирования сложных систем

 

I б щ1Й9т64а МВА

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советскик

Социалистических

Республик (11)717776 (61) Дополнительное к авт. санд-ву (22) Заявлено 12.09.77 (21) 2524671/18-24 с присоединением заявки И (23) Приоритет (51)М. Кл.

G 06 F 15/20

Гвсударствеиньй кеиатет

СССР аа делам изобретений к аткритай

Опубликовано 25,02.80. Бюллетень М 7 (53) УДK 681.325 (088,8) Дата опубликования описания28 02.80

В. Н. Горбиков, Б, Я, Буянов, В, И. Финаев и A. B. Осипов

{72) Авторы изобретения

Таганрогский радиотехнический институт имени В. Д. Калмыкова

{71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ

СЛОЖНЫХ СИСТЕМ

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

Известно устройство для вероятностного моделирования, содержащее генератор равномерно распределенных случайных чисел, блок сравнения, блок памяти, регистр адреса, блок управлени (11.

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

Наиболее близким техническим решени ем к данному изобретению является устройство для вероятностного моделирования сложных систем, содержащее генератор равномерно pàñïôåäåëåííéõ случаиных чисел, выход которого соединен с первым входом блока сравнения, регистр адреса. выход которого соединен с первым входом первого блока памяти, второй вход которого является первым входом устройства, регистр числа, блок управления (2), Недостатком известного устройства для вероятностного моделирования является его использование только для моделирования стационарных цепей Маркова, то есть матрицы переходных вероятностей, которые не зависят от времени и, как следствие, возможность их использования в качестве генератора стационарных смешанных стратегий.

Однако в инженерной практике широко распространены объекты, математическими моделями которых являются нестационарные цепи Маркова. Их матрицы пере3 71777 ходных вероятностей существенно зависят от времени. К подобного рода моделям сводятся алгоритмы ада и йвйИ о управления и многие реальные производственные процессы. Эж обстоятельства су"щественно сужают область применения из в естного,устройства.

Ileum предлагаемого изобретения состоит в расширении функциональных воз можностей устройства.. 10

Для-достижения поставленной цели уст- ройство содержйт блок задания-вероятностей, сумматор, блок задания адреса, элемент И, второй блок памяти и блок согласования, выход которого является выхо- >> дом устройства, а вход блока согласования соединен с выходом второго блока памяти, первый вход второго блока помяти соединен с выходом элемента И, а выходы второго блока памяти соединены со- 10

- отввтЖФенно с пврвьМи входйи регистра адреса и блока задания вероятностей, вто Рйе "вхбйы Kîòoðé яМяа г*ся "третьйм и четвертым входами устройства сбответсч венно, третий вход и выход блока задания 25 вероятностей соединейй жом% гсгввйно: с-первым выходом и третьим входом первого блока памяти, второй выход "которо - т о совдннен с первым входом сумматора, Выход которого соединен со вторым вхо 30 дом блока срЖненйя, восход которого сое-" динен с первым входом элемента И, второй вМод "к отофбж" соед%ней" с "йервым вы. ходом блока задания адреСа," второй выход

" ""котщ бЖ Соединен с третьим входом ре гистра адреса, а вход блока з Мйя адре са обьеди нвн со входом гейвра гбра равно- мерно распределенных спучайййх чисел, co в горь@я входом сумматора и с третьим входом устройства.

Кроме того, блок задания вероятностей содержит первый и второй элементы И, элемент ИЛИ, элемент сравнейия, сумма- тор, делятель, регистры адреса, первый

Жид перво о из которых является выхо-! дом блока, второй выход и первый вход не його" регистра адреса соединены соот" = " ветственно с.нервам входом и выходом сумматора, второй Йход которого соединен с выходом элемента ИЛИ, входы котЗрож соедйнены с выходамй iiàðâîãî и второго алемейтов И ссоре ггЪ йзенно, пер "sbIB Ъходы которьк соедййвны с выходами . элемента сравнения соответственно, первый

"жод=которого является первым входом блоха, "а второй -жид элЖИИЖ cpiissemas

Соединен с йервьм выходом второго perierpa alipeca, второй вход которого сов

6 4 динен со вторым входом первого регистра адреса, третий вход которого является вторым входом блока, третий вход блока соединен со вторым входом первого эле мента И и через делитель со вторым входом второго элемента И.

Блок-схема устройства приведена на фиг. 1.

На фиг. 2 приведена схема блока зада ния вероятностей.

Элементы устройства взаимосвязаны следуккцим образом. Шины установки начальных состояний 1 и 2 соединены соответственно с первыми входами первого блока памяти 3 и второго блока памяти

4, шины входных воздействий 5 соединЬны с первыми входами регистра адреса

6; блок задания адреса 7, генератора 9 равномерно распределенных случайных чисел сумматора 9. Шина выходных сигналов 10.coeдинeнa с выходом блока согласования 1-1, вход которого соединен с и ервым выходом второго блока памяти 4, второй выход которого соединен со вторым входом регистра адреса 6, выход которого соединен со вторым входом первого блока памяти 3, первый-выход-котороro соединен со вторым входом сумматора

9, выход которого соединен с первым входом блока сравнения 12, второй вход которого соединен с выходом генератора 8 равномерно распределенных случайных чи сел, а выход - с первым входом элемента И 13, второй вход которого соединен с первйм выходом блока 7, второй выход которого соединен с третьим входом регистра адреса 6. Выход элемента И 13 соединен со вторым входом второго блока памяти 4, третий выход которого соединен с первым входом =блока задания вероятностей 14, второй вход и выход которо го соединены соответственно со вторым и третьим входом первого блока памяти

3, а третьи входы - с шинами реакции внешней среды 15.

В блоке задания вероятностей 14 первый вход 16 элемента сравнения 17 яв- ляется первым входом блока 14. Первый вход 18 реестра адреса 19 является вторым входом блока 14, а второй вход соедийвн-с первйм "выходом ретнстра адреса 20, второй выход которого соединен со втсфйм=входом элемента сравнения 17, первый и второй вйходы которого соответ стввнно соединены с первыми входами элементов И 21 и 22, вторые входы которых соединены с шиной реакции внешней среды 16, причем вход элемента И 22

5 71777 соединен через делитель 23, а выходы элементов И 21 и 22 соединены соответ- ственно с первым и вторым входом элемента ИЛИ 24, выход которого соединен с первым входом сумматора 25, выход и второй вход которого соответственно соединены с третьим входом и первым выходом регистра адреса 19, второй выход 26 которого является выходом блка 14. 10

Работа устройства происходит следующим образом.

По шине 1 в первый блек памяти 3 производится запись элементов матрицы переходных вероятностей. В случае раба- 15 ты устройствв в режиме обучения записывается начальная рввновероятная матрица.

По шине 2 во второй блок памяти 4 производится запись кода начальнога -внут» реннего состояния устройства. Начало цик 20 ла работы определяется временем поступ ления входного сигнале, представляющего собой К-элементный двоичный код, па шине входных воздействий 5.

Этим сигналом первоначальна npossso

25 днтся сброс сумматора 9 в исходное состояние, запускается блок 7 и генератор

8 равномерно распределенных случайных чисел.

Генератор 8 равномерно распрвделей» ных случайных чисел генерирует случай ное число, равномерно распределенное sa участке f ° )," гдв Щ точность

Г„, представлейия числа генератора.

Одновременно входной сигнал постуца. ! ет на первый вход регистра адреса 6, который представляет собой дешифратор.

Эжм сигналом обеспечивается выбор кон40 кратной матрицы переходов в первой блоке памяти 3, На второй вход регистра адреса ат второго блока памяти 4, поступает код, соот ввтствуюшего предыдущего внутреннего состояния устройства (или начальнога со45 стадия). Этим сигналом через дешифрв. тор регистра адреса 6 ив второго блока йамяти 3, выбирается строка матрицы переходных вероятностей.

Сигналы от блока задания номера стра-

; 50 ки поступают нв третий вход регйстрв ад- реса 6, в виде последовательности номе ров элементов 1, 2, ..., m, выраженных в двоичном коде, гдв m - число элемент

55 тов в строке.

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

6 6 этих импульсов, определяющий номер импульса. По сигналам, соответствующим номерам элементов строки матрицы пере ходных вероятностей, из блока 7, по третьему входу регистра адреса 6 производится выбор элементов строки из перво,го блока памяти 3 и их запись в ре-»; гистр 19, блока 14, а также элементы строки матрицы передаются в сумматор 9.

Сумматор 9 формирует последовательно суммы элементов строки матрицы пере ходных вероятностей

Z.q,,, где С1 ° ° - i -й элемент J -й строки мат-.

j3 рицы переходных вероятностей.

Суммы, получаемые в сумматоре 9, последовательно сравниваются блоком срав» пения 12 со случайным числом, посту паквцим в блок сравнения 12 от генерато ра равномерно распределенных случайных чисел 8.

Устройство сравнения срабатывает в случае, если сумма

Х. Я;;, При выпалив ии этого неравенства блок сравнения 12 вырабатывает сигнал, который открывает элемент И 13, и но» мер элемента, при котором сработал блок, записывается через элемент И 13 во вто рой блок памяти 4.

Сигнал со второго блока памяти 4 че рез блок 11, обеспечивающий преобраэо« ванне данного сигнала в сигнал выхода, поступает по шине 10 на объект ynpas л ения.

По шине реакции внешней среды 15 в блок 14 поступает сигнал приращения мат рицы b P.

Блок 14 выполняет следующие функции, К элементу строки матрип переходных вероятнос гей Q;g номер которого нахо дится so втором блоке памяти 4, прибав ляется величина АР с присушим ей знаком, Остальные элементы j -й строки уменьшаются или;увеличиваются в вази симости от знвкеЬР на величину „ g записываются в первый блок памятй3 па тому же адресу, в те же ячейки, где хра нилась непреобразованная строка.

Работает блок следующим образом.

Элементы строки матрипы записаны в двоичном коде в регистр 19 (см. фиг. 2), по сигналам блока 7.

По сигналам от регистра 20 элементы строки матрицы иэ регистра 19 подаются поочередно в сумматор 25.

7 717776

Величина по шине реакции внешней с среды в двоичном коде поступает на второй вход элемента И 21 и на делитель в

23, который преобразует величину hР в к величину — с сохранением знака ЬР, S лР

Величина — 4 поступает на второй вход элемента И 22. По Входу 16 на первый вход элемента сравнения 1 7 из второго блока памяти 4 поступает код, соответствующий

1О номеру выходного элемента устройства.

Номера элементов строки из регистра

20 последовательно поступают на второй вход элемента сравнения 17. Элемент сравнения 17 выдает сигнал по прямому !

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

Формул а изобретения

Инверсный сигнал элемента сравнения

17 открывает элемент И 22, и величина через элемент ИЛИ поступает в

ЬР сумматор 25 для образовании новых элементов, строки, которые после преобразОВания заносится ВКОВь B регистр апре» са. Прямой сигнал с элемента сравнении

17 открывает элемент И 22 и Величина

ДР через элемент И 22 и элемент ИЛИ

24 попадает в сумматор 25, в котором

3; элемент изменяется на величинуаР в зависимости От ее знака.

Преобразованная таким образом строка заносится В первый блок памяти 4.

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

1 ного сигнала.

Эффективность устройства определяет1 ся тем, что реализованное предлагаемое устройство дает значительну1О экономию

I 4Q машинного времени, так как функциониро вание аналогичных устройств реализова лось в основном в виде машинных алгс ритмов.

В результате использования подобных

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

s0 труда в

1. Устройство для вероятностного мо»

55 делирования сложных систем, содержащее, генератор равномерно распределенных слу чайных чисел, выход которого соединен

8 первым входом блока сравнения, регистр адреса, выход которого соединен с первым ходом первого блока памяти„второй вход оторого является первым входом устройства, о т л и ч а ю щ е е с я тем, что, целью расширения функциональных возожностей устройства за счет моделиро» ения нестационарных процессов, оно соержит блок задания вероятностей, сумматор, блок задания адреса, элемент И,вторОй блОк памяти и блОк сОГласования, Bbt» од которого является выходом устройста, а вход блока согласования соединен с

ыходом второго блока памяти, первый вход которого является вторым входом стройства, второй вход второго блока памяти соединен с выходом элемента И, а

ыходы второго блока памяти соединены соответственно с первыми входами регистра адреса и блока задания вероятностей, вторые входы которых являются третьим и четвертым входами устройства соответственно, третий вход и выход блока зада ния вероятностей соединены соответственно с первым выходом и третьим входом nepBoro блока памяти, второй выход которого соединен с первым входом сумматора, Выхо которого соединен со вторым входом блока сравнения, выход которого соединен с первым входом элемента И, второй вход которого соединен с первым

r выходом блока задания адреса, второй вы ход которого соединен с третьим входом регистра адреса, а вход блока задания ад» реса обьединен со входом генератора равномерно распределенных случайных чисел, со вторым входом сумматора и с третьим входом устройства.

2. Устройство для вероятностного мо» делировании сложных систем по и. 1, о т л.и ч .а ю щ е е с я тем, что блок задании вероятностей содержит первый и второй элементы И, элемент ИЛИ, элемент сравнениЯ, Сумматор, делитель, и регистры адреса, первый выход первого из которых явлиетси выходом блока, а второй выход и первый вход первого регистра адреса соединены соответственно с первым входом и выходом сумматора, второй вход которого соединен с выходом элемента

ИДИ, входы которого соединены с выходами первого и второго элементов И соот- ветственно, первые входы которых соединены с выходами элемента сравнения собт-. ветственно, первый вход которого является первым входом блока, а второй вхол эл емента сравнЕния соединен с первым выходоы

717776

lug. у

Составитель A. Kapacos

Редактор Э. Губнипкая Техред М.Келемеш Корректор Г. Решетник

Заказ 9849/67 Тираж 751 Подписное

БНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, ?К-35, Раушская наб., д» 4/8

Филиал ППП Патент, г. Ужгород, ул. Проектная, 4

9 второго perserpa адреса, второй выход которого соединен со вторым входом пер» ного регистра адреса, третий вход которого является вторым входом блока, третий вход блока соединен со вторым входом

1 первого элемента И и через делитель со вторым входом второго элемента И. 0

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР /

¹ 488212, кл. G 06 F 1/02, 1974.

2. Авторское свидетепьство СССР

: ¹ 451085, кл. G 06 Р 15/36, 1973 . (прототип).