УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ Российский патент 1994 года по МПК G06F15/20 

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

Известно устройство для решения задач нелинейного программирования, содержащее блок интеграторов, входы которого подключены к выходам блока сумматоров, а выходы соединены с входами блока градиента оптимизируемой функции и блока ограничения, подключенных соответственно к входам блока усилителей и блока коэффициентов, выходы которого соединены с первой группой входов блока сумматоров, блок ортогонализации, входы которого подключены к выходам блока усилителей и блока коэффициентов, а выходы соединены с вторыми входами блока сумматоров [1] .

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

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

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

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

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

При решении задач НСП вид оптимизируемой функции опредекляется свойствами и особенностями оптимизируемой системы. На практике часто приходится исследовать системы, которые имеют квадратичную зависимость критерия от параметров (например, стоимость - эффективность, стоимость - готовность и др. ). Поэтому в качестве прикладной задачи целесообразно рассмотреть вопрос определения вектора оптимальных параметров х₁(N)х₂(N) системы, имеющей критериальную функцию следующего вида:
ϕ(х₁(N), х₂(N) = C₁₁х₁²(N) + (C₁₂ +
+C₂₁)[х₁(N)х₂(N)] ² + c₂₂˙х₂²(N), (1) где N - номер шага поиска;
С₁₁, С₁₂, С₂₁, С₂₂ - постоянные коэффициенты.

В процессе решения оптимизационной задачи считается, что экстремальным значением функции (1) является ее минимальное значение,
Процедура НСП в общем виде задается рекурентным уравнением, где априорная f_N(Х) и апостериорная f_N+1(Х) плотности распределения вектора параметров связаны байесовским оператором, который в отличие от прототипа аппроксимируется следующим образом: f_N+1(X)= _если
(2) где I_N( θ ) - индикатор события θ , определяемый по формуле I_N(θ) =
(3)
а_N, h - параметры сдвига и сжатия f_N(Х);
ТХ - матрица вращения вектора Х.

В процессе поиска изменение функции f_N(х₁, х₂) в соответствии с изменением f_N+1(х₁, х₂) осуществляется аналогично прототипу: x₁(N+1)= m(N+1)+Г₁₁(N+1)x x S₁ + Г₂₁ ( N + 1 ) S₂ ;
х₂(N+1) = m(N+1) + Г₂₂(N+1) ˙S₂, (5) где m(N+1), m(N+1) - математическое ожидание параметров х₁, х₂ на (N+1)-м шаге поиска (на начальном шаге поиска (N= 0, m(N+1) = m, m(N+1) = m);
Г₁₁(N+1), Г₁₂(N+1), Г₂₂(N+1) - неслучайные величины;
S₁, S₂ - реализации датчиков равномерно распределенных случайных чисел.

Значения Г₁₁(N+1), Г₁₂(N+1), Г₂₂ (N+1) вычисляются следующим образом. На начальном шаге поиска (N= 0) Г₁₁(N+1) = Г₁₁, Г₁₂(N+1) = 0, Г₂₂(N+1) = Г₂₂. На следующих шагах
Г_n(N+1)= ; (6)
Г₂₁(N+1)= [K₂₁(N+1)] /[; (7)
Г₂₂(N+1)= , , (8) где K₁₁(N+1), K₂₁(N+1), K₂₂(N+1) - значения ковариационной матрицы искомых параметров х₁ и х₂ (на начальном шаге поиска (N = 0) K₁₁(N+1) = K₁₁, K₂₁ = 0, K₂₂(N+1) = K₂₂.

Процедура (2) организуется следующим образом. При успешном результате поиска (I_n( θ) = 1) центр распределения f_N(х₁(^N), х₂^(N)) cдвигается в точку Х (х₁, х₂), а вектор ln = (х₁ - m, х₂ - m) разворачивается в направлении вектора, характеризующего в среднем направление успешного поиска. Выражения для моментных характеристик, используемых в формулах (3), (4) и (5), в этом случае следующие.

Если I_N(θ) = 0, то m(N+1) = m(N); m(N+1) = m(N);
K₁₁(N+1) = K₁₁(N); K₂₁(N+1) = K₂₁(N); K₂₂(N+1) = K₂₂(N).

Если I_n(θ ) = 1 (на первом шаге поиска (N = 1) I_N(θ) всегда равен 1), то m(N+1) = х₁(N); m(N+1) = х₂(N);
K₁₁(N+1) = h II K_хII l₁²(N); (9)
K₂₁(N+1) = h II K_х II l₁(N) ˙l₂(N); (10)
K₂₂(N+1) = h II K_х II l₂²(N); (11)
l21

(N)= (1/n²); (12)
l₁(N)l₂(N)= (1/n²) ; (13)
l22(N)= (1/n²) , (14) где l₁(N), l₂(N) -координаты вектора/ характеризующего в среднем
направление успешного поиска;
n= I_k(θ) - число успешных проб за N шагов поиска (на начальном шаге
поиска I_N(θ)= 0); K= - норма начальной ковариационной матрицы.

Основа процесса поиска осуществляется при заданной точности ζ определения экстремума функции ϕ(x₁(N), x₂(N)) согласно следующему неравенству: Iϕ(х₁(N+1), х₂(N+1) - ϕ(х₁(N), х₂(N)≅ε. (15)
Цель изобретения достигается тем, что в устройство для решения задач нелинейного стохастического программирования, содержащее первый сумматор, первый блок умножения, первый датчик случайных чисел, выход которого подключен к первому входу первого блока умножения, выход произведения которого соединен с первым входом первого сумматора, введены три блока входных регистров, девять блоков элементов ИЛИ, узел установки нуля, триггер, с второго по восьмой сумматоры, генератор тактовых импульсов, девятнадцать элементов задержки, два блока сравнения, восемь элементов ИЛИ, пять коммутаторов, семь элементов И, тринадцать регистров, с второго по двенадцатый блоки умножения, второй датчик случайных чисел, шесть квадраторов, три блока вычитания, блок вычитания по модулю, три блока извлечения квадратного корня, восемь блоков деления, элемент НЕ, счетчик, три накопительных сумматора, два блока индикации и распределитель импульсов, тактовый вход которого соединен с выходом первого элемента И, а с первого по тридцать пятый выходы подключены соответственно к входам записи первого, второго и третьего блоков входных регистров, к первому входу считывания первого блока входных регистров, к управляющим входам первого и второго датчиков случайных чисел, к второму входу считывания первого блока входных регистров, к входам записи первого и второго регистров, к первым входам первого и второго элементов ИЛИ и к входам считывания третьего и четвертого регистров, к первым управляющим входам первого и второго коммутаторов, к первому и второму входам считывания второго блока входных регистров, к управляющему входу третьего коммутатора, к входу записи пятого регистра, к первым входам третьего и четвертого элементов ИЛИ, к первому и второму входам считывания третьего блока входных регистров, к тактовым входам первого, второго и третьего накопительных сумматоров, к входу записи шестого регистра, к первому входу пятого элемента ИЛИ, к тактовому входу счетчика, к входам записи седьмого, восьмого и девятого регистров, к первым входам шестого, седьмого и восьмого элементов ИЛИ и к входам считывания третьего и четвертого регистров, к входам записи десятого, одиннадцатого и двенадцатого регистров, к входам считывания этих же регистров, к входу записи тринадцатого регистра, к входам считывания пятого и тринадцатого регистров, к управляющему входу четвертого коммутатора, к первому управляющему входу пятого коммутатора, к третьему входу считывания третьего блока входных регистров, к второму управляющему входу пятого коммутатора, при этом с первого по четвертый информационные входы первого блока входных регистров являются входом задания начальных значений устройства, первый выход этого блока подключен к первому входу первого блока, элементов ИЛИ и через первый элемент задержки к первому входу второго блока элементов ИЛИ, второй выход блока входных регистров соединен с первым входом третьего блока элементов ИЛИ, а также через второй элемент задержки с первым входом четвертого блока элементов ИЛИ, третий и четвертый выходы первого блока входных регистров подключены к первым входам соответственно пятого и шестого блоков элементов ИЛИ, вторые входы которых соединены с выходами соответственно десятого и двенадцатого регистров, а выходы - соответственно с вторым входом первого блока умножения и первым входом второго блока умножения, второй вход которого подключен к выходу второго датчика случайных чисел, а выход произведения - к первому входу второго сумматора, второй вход которого соединен с выходом третьего блока элементов ИЛИ, а выход суммы - с информационным входом первого регистра, вход считывания которого подключен к выходу первого элемента ИЛИ, а выход - к информационному входу первого коммутатора, второй управляющий вход которого соединен с выходом четвертого элемента ИЛИ, первый выход - с первым входом седьмого блока элементов ИЛИ, а также через третий элемент задержки с вторым входом третьего блока элементов ИЛИ второй выход первого коммутатора соединен с вторым входом третьего блока, элементов ИЛИ, а третий выход - с входом первого квадрата, через четвертый элемент задержки с первым входом второго элемента И, с информационным входом третьего регистра, выход которого подключен через пятый элемент задержки к первому входу третьего элемента И, а также через шестой элемент задержки к первому входу четвертого элемента И, выход которого соединен с третьим входом третьего блока элементов ИЛИ, второй и третий входы первого блока элементов ИЛИ подключены к выходам соответственно седьмого элемента задержки и пятого элемента И, а выход - к второму входу первого сумматора, выход суммы которого соединен с первым входом третьего сумматора, второй вход которого через восьмой элемент задержки подключен к выходу произведения третьего блока умножения, а выход суммы - к информационному входу второго регистра, вход считывания которого соединен с выходом второго элемента ИЛИ, а выход - с информационным входом второго коммутатора, второй управляющий вход которого подключен к выходу третьего элемента ИЛИ, первый выход - к первому входу восьмого блока, элементов ИЛИ, второй выход - к входу седьмого элемента задержки и к второму входу восьмого блока элементов ИЛИ, а третий выход - к входу девятого элемента задержки, второго квадратора и информационному входу четвертого регистра, выход которого соединен через десятый элемент задержки с первым входом пятого элемента И, а также через одиннадцатый элемент задержки с первым входом шестого элемента И, выход которого подключен к второму входу второго блока элементов ИЛИ, выход которого соединен с входом вычитаемого первого блока вычитания, вход уменьшаемого которого подключен к выходу восьмого блока элементов ИЛИ, а выход разности - к первому входу четвертого блока умножения и входу третьего квадратора, выход которого соединен с первым входом четвертого сумматора и через двенадцатый элемент задержки с входом делимого первого блока деления, с первого по четвертый информационные входы второго блока входных регистров являются входом задания постоянных коэффициентов устройства, первый и второй выходы этого блока подключены к первым входам соответственно пятого и шестого блоков умножения, третий и четвертый выходы второго блока входных регистров соединены соответственно с первым и вторым входами пятого сумматора, выход суммы которого подключен к первому входу седьмого блока умножения, второй вход которого соединен с выходом произведения восьмого блока умножения, а выход - с первым входом шестого сумматора, выход суммы которого подключен к информационному входу третьего коммутатора, а второй вход через тринадцатый элемент задержки - к выходу суммы седьмого сумматора, первый и второй входы которого соединены с выходами произведения соответственно пятого и шестого блоков умножения, выход второго квадратора подключен к второму входу пятого блока умножения и к первому входу восьмого блока умножения, а выход первого квадратора соединен с вторыми входами шестого и восьмого блоков умножения, первый и второй информационные входы третьего блока входных регистров являются входом задания точности и параметра сжатия устройства, третий и четвертый входы этого блока являются входом задания начальных значений ковариационной матрицы устройства первый выход третьего блока входных регистров подключен к первому входу первого блока сравнения, второй выход - к первому входу девятого блока умножения, а третий и четвертый выходы - соответственно к первому и второму входам восьмого сумматора, выход суммы которого через первый блок извлечения квадратного корня соединен с вторым входом девятого блока умножения, выход произведения которого подключен к информационному входу шестого регистра, вход считывания которого соединен с выходом пятого элемента ИЛИ, а выход - с первыми входами десятого, одиннадцатого и двенадцатого блоков умножения, выходы произведения которых подключены к информационным входам соответственно седьмого, восьмого и девятого регистров, а вторые входы - к выходам частного соответственно второго, третьего и четвертого блоков деления, входы делителя которых соединены с выходами четвертого квадратора, а входы делимого - с выходами суммы соответственно первого, второго и третьего накопительных сумматоров, информационные входы которых подключены к выходам соответственно первого и шестого блоков деления, входы делителя которых соединены с выходами суммы четвертого сумматора, а выходы делимого пятого и шестого блоков деления подключены соответственно к выходу четырнадцатого элемента задержки и выходу произведения четвертого блока умножения, первый выход третьего коммутатора соединен с информационным входом тринадцатого регистра, а второй выход - с первым входом девятого блока элементов ИЛИ, второй вход которого подключен к первому выходу пятого коммутатора, а выход - к информационному входу пятого регистра, выходы пятого и тринадцатого регистров соединены с информационными входами соответственно четвертого и пятого коммутаторов, первый выход четвертого и второй выход пятого коммутаторов подключены соответственно к первому и второму входам второго блока сравнения, а второй и третий выходы четвертого и пятогo коммутаторов - к первому и второму входам блока вычитания по модулю, выход которого соединен с вторым входом первого блока сравнения, выход "меньше или ровно" которого подключен к первому входу седьмого и к второму входу второго элементов И, а также к сбросовому входу триггера, установочный вход которого соединен с выходом узла установки нуля, а прямой выход - с первым входом первого элемента И, второй вход которого подключен к выходу генератора тактовых импульсов, выход счетчика соединен с входом четвертого квадратора, а вход - с выходом "меньше" второго блока сравнения, который этим же выходом соединен через пятнадцатый элемент задержки с вторым входом пятого элемента ИЛИ, а также непосредственно с вторыми входами третьего и шестого элементов И, первого, второго и третьего элементов ИЛИ, с входом элемента НЕ, выход которого через шестнадцатый элемент задержки подключен к вторым входам четвертого и пятого элементов И, а также непосредственно к вторым входам шестого, седьмого и восьмого элементов ИЛИ, выходы которых соединены с информационными входами соответственно седьмого, восьмого и девятого регистров, выход седьмого регистра подключен к входам второго блока извлечения квадратного корня и семнадцатого элемента задержки, выход которого соединен с входом делителя седьмого блока деления, вход делимого которого подключен к выходу пятого квадратора, а выход частного - к входу вычитаемого второго блока вычитания, вход уменьшаемого которого соединен через восемнадцатый элемент задержки с выходом восьмого регистра, а выход частного через третий блок извлечения квадратного корня - с информационным входом двенадцатого регистра, выход девятого регистра подключен к входам пятого квадратора и девятнадцатого элемента задержки, выход которого соединен с входом делимого восьмого блока деления, выход частного которого подключен к информационному входу одиннадцатого регистра, выход которого соединен с первым входом третьего блока умножения, второй вход которого подключен к выходу второго датчика случайных чисел, выход второго блока извлечения квадратного корня подключен к входу делителя восьмого блока деления и к информационному входу десятого регистра, выход третьего элемента И соединен с вторым входом четвертого блока элементов ИЛИ, выход которого подключен к входу вычитаемого третьего блока вычитания, вход уменьшаемого которого соединен с выходом седьмого блока, элементов ИЛИ, а выход разности - с вторым входом четвертого блока умножения и с входом шестого квадратора, выход которого подключен к входу четырнадцатого элемента задержки и к второму входу четвертого сумматора, выход девятого элемента задержки соединен с вторым входом седьмого элемента И, выход которого подключен к входу первого блока индикации, а выход второго элемента И соединен с входом второго блока индикации.

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

Заявленное техническое решение соответствует критерию "новизна", так как отличается от прототипа наличием новых элементов и связей.

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

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

Устройство для решения задач нелинейного стохастического программирования содержит первый 1, второй 2 и третий 3 блоки входных регистров, распределитель 4 импульсов, девять блоков 5-13 элементов ИЛИ, узел 14 установки нуля, триггер 15, восемь сумматоров 16-23, генератор 24 тактовых импульсов, девятнадцать элементов 25-43 задержки, первый 44 и второй 45 блоки сравнения, восемь элементов ИЛИ 46-53, пять коммутаторов 54-58, семь элементов И 59-65, тринадцать регистров 66-78, двенадцать блоков 79-90 умножения, первый 91 и второй 92 датчики случайных чисел, шесть квадраторов 93-98, первый 99, второй 100 и третий 101 блоки вычитания, блок 102 вычитания по модулю, первый 103, второй 104 и третий 105 блоки извлечения квадратного корня, восемь блоков 106-113 деления, элемент НЕ 114, счетчик 115, первый 116, второй 117 и третий 118 накопительные сумматоры, первый 119 и второй 120 блоки индикации.

Устройство для решения задач нелинейного стохастического программирования работает следующим образом.

На первый и второй информационные входы первого блока 1 входных регистров с входа устройства подаются сигналы, соответствующие величинам m и m - начальным значениям математического ожидания параметров х₁ и х₂. На третий и четвертый информационные входы блока 1 с входа устройства подаются сигналы, соответствующие величинам Г₁₁ и Г₂₂ - начальным значениям неслучайных величин. Управляющий сигнал на запись подается на вход записи первого блока 1 входных регистров с первого выхода распределителя 4 импульсов, который работает следующим образом.

С выхода узла 14 установки нуля на установочный вход триггера 15 поступает нулевой сигнал, который приводит к появлению сигнала на его прямом выходе, что позволяет открыть первый элемент И 59, и тактовые импульсы с выхода генератора 24 тактовых импульсов через элемент И 59 поступают на тактовый вход распределителя 4 импульсов, он начинает работать.

На четыре информационных входа второго блока 2 входных регистров с входа устройства подаются сигналы, соответствующие величинам c₁₁, с₁₂, с₂₁ и с₂₂ - постоянным коэффициентам. Управляющий сигнал на запись подается на вход записи блока 2 с второго выхода распределителя 4 импульсов.

На первый и второй информационные входы третьего блока 3 входных регистров с входа устройства подаются сигналы, соответствующие величинам ε- точности и h - параметра сжатия. На третий и четвертый входы блока 3 с входа устройства подаются сигналы, соответствующие величинам К₁₁ и К₂₂ - начальным значениям ковариационной матрицы. Управляющий сигнал на запись подается на вход записи третьего блока 3 входных регистров с третьего выхода распределителя 4 импульсов.

По сигналу с четвертого выхода распределителя 4 импульсов на первый вход считывания первого блока 1 входных регистров с его третьего и четвертого выходов сигналы, соответствующие величинам Г₁₁ и Г₂₂, поступают соответственно через пятый блок 9 элементов ИЛИ на второй вход первого блока 79 умножения и через шестой блок 10 элементов ИЛИ на первый вход второго блока 80 умножения. На другие входы блоков 79 и 80 по сигналу с пятого выхода распределителя 4 импульсов с выходов первого 91 и второго 92 датчиков случайных чисел поступают сигналы, соответствующие случайным числам S₁ и S₂. С выходов произведения блоков 79 и 80 сигналы, соответствующие величинам Г₁₁S₁ и Г₂₂S₂, поступают на первые входы соответственно первого 16 и второго 17 сумматоров. На другие входы этих сумматоров соответственно через первый 5 и третий 7 блоки элементов ИЛИ по сигналу с шестого выхода распределителя 4 импульсов поступают с первого и второго выходов первого блока 1 входных регистров сигналы, соответствующие величинам m и m. Таким образом, на информационные входы первого 66 и второго 67 регистров поступают сигналы, соответствующие значениям параметров на начальном шаге - х₁(1) и х₂(1), определяемым по формулам (4) и (5). Управляющие сигналы для записи на эти регистры подаются соответственно с седьмого и восьмого выходов распределителя 4 импульсов.

По сигналу с девятого выхода распределителя 4 импульсов с выходов первого 66 и второго 67 регистров сигналы, соответствующие величинам х₂(1) и х₁(1), поступают соответственно через первый 54 и второй 55 коммутаторы (управляющие сигналы подаются на их первые управляющие входы с десятого выхода распределителя 4 импульсов) на информационные входы третьего 68 и четвертого 69 регистров, на входы первого 93 и второго 94 квадраторов, на входы четвертого 28 и девятого 33 элементов задержки. С выходов первого 93 и второго 94 квадраторов сигналы, соответствующие величинам х₂²(1) и х₁²(1), подаются х₂²(1) на вторые входы шестого 84 и восьмого 86 блоков умножения х₁²(1) на второй вход пятого 83 и первый вход восьмого 86 блоков умножения. На другие входы пятого 83 и шестого 84 блоков умножения подаются по сигналу с одиннадцатого выхода распределителя 4 импульсов сигналы, соответствующие величинам С₁₁ и С₂₂, с выходов второго блока 2 входных регистров. С выходов произведения блоков 83 и 84 сигналы, соответствующие величинам С₁₁х₁² (1) и с₂₂х₂² (1), поступают на первый и второй входы седьмого сумматора 22. С выхода суммы сумматора 22 сигнал, соответствующий величине С₁₁х₁² (1) + c₂₂х₂² (1), подается на вход тринадцатого элемента 37 задержки.

По сигналу с двенадцатого выхода распределителя 4 импульсов с выходов второго блока 2 входных регистров сигналы, соответствующие величинам С₁₂ и С₂₂, поступают на входы пятого сумматора 20. С выхода суммы сумматора 20 сигнал, соответствующий величине С₁₂+C₂₁, подается на первый вход седьмого блока 85 умножения. На другой вход блока 85 с выхода восьмого блока 86 умножения поступает сигнал, соответствующий величине х₂² (1) х₁² (1). С выхода произведения блока 85 на первый вход шестого сумматора 21 подается сигнал, соответствующий величине (С₁₂ + C₂₁) [х₁ (1) х₂ (1)] ². На другой вход сумматора 21 поступает с выхода тринадцатого элемента 37 задержки сигнал, соответствующий величине С₁₁х₁²(1)+ + C₂₂х₂²(1). С выхода суммы сумматора 21 сигнал, соответствующий величине ϕ(х₁(1), х₂(1)), определяемой по формуле (1), поступает через третий коммутатор 56 (управляющий сигнал на его вход подается с тринадцатого выхода распределителя 4 импульсов) и девятый блок 13 элементов ИЛИ на информационный вход пятого регистра 70. Управляющий сигнал на запись подается при этом с четырнадцатого выхода распределителя 4 импульсов.

По сигналу с семнадцатого выхода распределителя 4 импульсов на первый вход считывания третьего блока 3 входных регистров с его третьего и четвертого выходов сигналы, соответствующие величинам К₁₁ и К₂₂, поступают на первый и второй входы восьмого сумматора 23. С выхода суммы сумматора 23 сигнал, соответствующий величине К₁₁ + К₂₂, подается на вход первого блока 103 извлечения квадратного корня, с выхода которого сигнал, соответствующий величине II К_х II- норме начальной ковариационной матрицы, направляется на второй вход девятого блока 87 умножения. На другой вход блока 87 с второго выхода третьего блока 3 входных регистров по сигналу с восемнадцатого выхода распределителя 4 импульсов поступает сигнал, соответству- ющий величине h. С выхода произведения блока 87 сигнал, соответствующий величине h II K_х II подается на информационный вход шестого регистра 71. Управляющий сигнал на запись направляется при этом с двадцатого выхода распределителя 4 импульсов.

Параллельно с этой процедурой осуществляется вычисление величин l₁²(N), l₁(N)l₂(N) и l₂²(N) по формулам (12), (13) и (14). Здесь используются следующие блоки: распределитель 4 импульсов, счетчик 115, первый 66 и второй 67 регистры, первый 54 и второй 55 коммутаторы, первый 25, второй 26, двенадцатый 36 и четырнадцатый 38 элементы задержки, четвертый сумматор 19, четвертый блок 82 умножения, второй 6, четвертый 8, седьмой 11 и восьмой 12 блоки элементов ИЛИ, первый 99 и третий 101 блоки вычитания, третий 95, четвертый 96 и шестой 98 квадраторы, первый 116, второй 117 и третий 118 накопительные сумматоры, первый 106, второй 107, третий 108, четвертый 109, пятый 110 и шестой 111 блоки деления. С выходов частного блоков 107, 108 и 109 сигналы, соответствующие величинам l₁²(N), l₂²(N) и l₁(N) l₂(N), поступают на вторые входы соответственно десятого 88, одиннадцатого 89 и двенадцатого 90 блоков умножения. На другие входы блоков 88, 89 и 90 по сигналу с двадцать первого выхода распределителя 4 импульсов с выхода шестого регистра 71 подается сигнал, соответствующий величине h II K_х II . Таким образом, с выходов произведения блоков 88, 89 и 90 на информационные входы седьмого 72, восьмого 73 и девятого 74 регистров поступают сигналы, соответствующие величинам К₁₁(N+1), К₂₂(N+1)и К₂₁(N+1), которые определяются по формулам (9), (11) и (10). Управляющие сигналы на запись направляются в данном случае с двадцать третьего выхода распределителя 4 импульсов.

В дальнейшем осуществляется вычисление неслучайных величин Г₁₁(N+1), Г₂₁(N+1) и Г₂₂(N+1) по формулам (6), (7) и (8). По сигналам с двадцать четвертого выхода распределителя 4 импульсов с выходов седьмого 72, восьмого 73 и девятого 74 регистров величины К₁₁(1), К₂₂(1) и К₂₁(1) распределяются следующим образом: К₁₁(1) на выходы второго блока 104 извлечения квадратного корня и семнадцатого элемента 41 задержки; К₂₂(1) через восемнадцатый элемент 42 задержки на вход уменьшаемого второго блока 100 вычитания, К₂₁(1) на входы пятого квадратора 97 и девятнадцатого элемента 43 задержки. С выходов блоков 104 и 43 сигналы, соответствующие величинам и К₂₁(1), поступают на входы делителя и делимого блока 113 деления. Кроме того, величина которая соответствует значению Г₁₁(1), подается на информационный вход десятого регистра 75. Управляющий сигнал на запись направляется при этом с двадцать пятого выхода распределителя 4 импульсов. С выхода частного блока 113 сигнал, соответствующий значению Г₂₁(1), поступает на информационный вход одиннадцатого регистра 76. Управляющий сигнал на запись подается в данном случае с двадцать шестого выхода распределителя 4 импульсов. С выходов пятого квадратора 97 и семнадцатого элемента 41 задержки сигналы, соответствующие величинам К₂₁²(1) и К₁₁(1), поступают на входы делимого и делителя седьмого блока 112 деления. С выхода частного блока 112 сигнал, соответствующий величине К₂₁²(1)/К₁₁(1), подается на вход вычитаемого второго блока 100 вычитания. С выхода разности блока 100 сигнал, соответствующий величине К₂₂(1) - К₂₁(1)/К₁₁(1), поступает на вход третьего блока 105 извлечения квадратного корня. С выхода блока 105 сигнал, соответствующий величине Г₂₂(1), подается на информационный вход двенадцатого регистра 77. Управляющий сигнал на запись при этом подается с двадцать седьмого выхода распределителя 4 импульсов.

По сигналу с двадцать восьмого выхода распределителя 4 импульсов на входы считывания десятого 75, одиннадцатого 76 и двенадцатого 77 регистров с их выходов величины Г₁₁(1), Г₂₁(1) и Г₂₂(1) поступают соответственно через пятый блок 9 элементов ИЛИ на второй вход первого блока 79 умножения, на первый вход третьего блока 81 умножения и через шестой блок 10 элементов ИЛИ на первый вход второго блока 80 умножения. На другие входы блоков 79, 80 и 81 по сигналу с пятого выхода распределителя 4 импульсов с выходов первого 91 и второго 92 датчиков случайных чисел подаются случайные величины S₁ и S₂. С выходов произведения блоков 79, 80 и 81 сигналы, соответствующие величинам Г₁₁(1) S₁, Г₂₂(1) S₂ и Г₂₁(1) S₂, поступают соответственно на первые входы первого 16 и второго 17 сумматоров и через восьмой элемент 32 задержки на второй вход третьего сумматора 18. По сигналу с девятого выхода распределителя 4 импульсов на входы считывания первого 66 и второго 67 регистров величины х₂(1) и х₁(1) поступают соответственно через первый коммутатор 54, третий элемент 27 задержки и третий блок 7 элементов ИЛИ на второй вход второго сумматора 17, через второй коммутатор 55, седьмой элемент 31 задержки и первый блок 5 элементов ИЛИ на второй вход первого сумматора 16. С выхода суммы второго сумматора 17 сигнал, соответствующий величине х₂(2), поступает на информационный вход первого регистра 66. Управляющий сигнал на запись подается с седьмого выхода распределителя 4 импульсов.

С выхода суммы первого сумматора 16 сигнал, соответствующий величине х₁(1) + +Г₁₁(1), подается на первый вход третьего сумматора 18, с выхода суммы которого сигнал, соответствующий величине х₁(2), поступает на информационный вход второго регистра 67. Управляющий сигнал на запись подается с восьмого выхода распределителя 4 импульсов.

Далее осуществляется вычисление критериальной функции ϕ(х₁(2), х₂(2)) по формуле (1) так же, как и в предыдущем цикле. Единственное отличие заключается в том, что это значение функции через третий коммутатор 56 (управляющий сигнал при этом на него не подается) поступает на информационный вход тринадцатого регистра 78. Управляющий сигнал на запись подается с двадцать девятого выхода распределителя 4 импульсов.

Проверка неравенства (15) осуществляется следующим образом. По сигналу с тридцатого выхода распределителя 4 импульсов на вход считывания пятого регистра 70 с его выхода через четвертый коммутатор 57 (управляющий сигнал на его вход подается с тридцать второго выхода распределителя 4 импульсов) сигнал, соответствующий величине ϕ(х₁(1), х₁(1)), поступает на первый вход блока 102 вычитания по модулю. По сигналу с тридцать первого выхода распределителя 4 импульсов на вход считывания тринадцатого регистра 78 с его выхода через пятый коммутатор 58 (управляющий сигнал на его первый вход подается с тридцать третьего выхода распределителя 4 импульсов) сигнал, соответствующий величине ϕ(х₁(2), х₂(2)), поступают на второй вход блока 102 вычитания по модулю. С выхода блока 102 сигнал, соответствующий модулю разности между ϕ(х₁(2), х₂(2)) и ϕ(х₁(1), х₂(1)), поступает на второй вход первого блока 44 сравнения, на другой вход которого по сигналу с тридцать четвертого выхода распределителя 4 импульсов с первого выхода третьего блока 3 входных регистров подается точность ε. Если неравенство (15) выполняется, то на выходе блока 44 появляется сигнал, который поступает на сбросовый вход триггера 15, что приводит на его прямом выходе к появлению сигнала нулевого уровня, который приводит к закрытию первого элемента И 59, тактовые сигналы с выхода генератора 24 тактовых импульсов на вход распределителя 4 импульсов не поступают и устройство прекращает работать.

Кроме того, сигналы с выхода первого блока 44 сравнения поступают на входы второго 60 и седьмого 65 элементов И, что позволяет прохождению через них с выходов четвертого 28 и девятого 33 элементов задержки на входы соответственно второго 120 и первого 119 блоков индикации сигналов, соответствующих величинам х₂(2) и х₁(2), т. е. значениям, обеспечивающим оптимум критериальной функции.

В случае невыполнения неравенства (15) сигнал на выходе первого блока 44 сравнения отсутствует, поэтому информация в блоки 119 и 120 индикации не поступает, на тактовый вход распределителя 4 импульсов сигналы поступают и устройство продолжает работу.

По сигналам с тридцатого и тридцать первого выходов распределителя 4 импульсов с выходов пятого 70 и тринадцатого 78 регистров величины ϕ(х₁(1), х₁(1)) и ϕ(х₂(2), х₂(2)) поступают соответственно через четвертый 57 и пятый 58 коммутаторы на первый и второй входы второго блока 45 сравнения. Если неравенство в формуле (3) выполняется, то на выходе блока 45 появляется сигнал I_N(θ) = 1, который поступает на вход счетчика 115, где подсчитывается число успешных проб. Кроме того, этот сигнал поступает на входы пятнадцатого элемента 39 задержки, третьего 61 и шестого 64 элементов И, первого 46, второго 47, третьего 48 и четвертого 49 элементов ИЛИ, что позволяет производить вычисления по формулам (12), (13), (14), (9), (10), (11), (6), (7) и (8) для определения величин математических ожиданий m (N+1) и m (N+1) по уже описанному порядку для следующего цикла.

В случае невыполнения неравенства (3) на выходе второго блока 45 сравнения сигнал не появляется (I_N(θ) = 0), следовательно, на выходе элемента НЕ 114 появляется сигнал, который поступает на входы шестого 51, седьмого 52 и восьмого 53 элементов ИЛИ и шестнадцатого элемента 40 задержки. Это обеспечивает оценку математических ожиданий и значений ковариационных матриц через их значения в предыдущем цикле.

В заключение цикла осуществляется пересылка последующего значения критериальной функции ϕ(х₁(2), х₂(2)) в регистр, где было записано ее предыдущее значение ϕ(х₁(1), х₂(1)). Для этого по сигналу с тридцать первого выхода распределителя 4 импульсов значение ϕ(х₁(2), х₂(2)) с выхода тринадцатого регистра 78 через пятый коммутатор 58 (управляющие сигналы на его выходы подаются с тридцать третьего и тридцать пятого выходов распределителя 4 импульсов) и девятый блок 13 элементов ИЛИ поступает на информационный вход пятого регистра 70. Управляющий сигнал на запись направляется с четырнадцатого выхода распределителя 4 импульсов.

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

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

Быстродействие может быть охарактеризовано количеством вычислительный процедур при осуществлении случайного поиска. Моделирование работы устройства на ЭВМ показывает, что этот поиск при использовании предлагаемого устройства ускоряется в 2-3 раза, т. е. в 2-3 раза уменьшается количество вычислительных процедур.

Точность выражается разностью между точным значением экстремума критериальной функции и полученным в процессе поиска. Расчеты, проведенные с помощью ЭВМ, показывают, что использование предлагаемого устройства позволяет уменьшить эту разность в 1,5-2 раза.

Экономический эффект от внедрения изобретения может быть оценен суммой ущерба который предотвращается путем повышения быстродействия и точности определения параметров оптимизируемой системы. (56) 1. Авторское свидетельство СССР N 480090, кл. G 06 G 7/38, 1974.

2. Казаков И. Е. , Гладков Д. И. Методы оптимизации стохастических систем. М. : Наука, 1987, с. 264, рис. 11, 13.

Изобретение относится к автоматике и вычислительной технике и может быть использовано при решении широкого круга задач стохастического программирования. Цель изобретения - повысить быстродействие и точность определения параметров оптимизируемой системы. Устройство содержит три блока входных регистров, девять блоков элементов ИЛИ, узел установки нуля, триггер, восемь сумматоров, генератор тактовых импульсов, девятнадцать элементов задержки, два блока сравнения, восемь элементов ИЛИ, пять коммутаторов, семь элементов И, тринадцать регистров, двенадцать блоков умножения, два датчика случайных чисел, шесть квадраторов, три блока вычитания, блок вычитания по модулю, три блока извлечения квадратного корня, восемь блоков деления, элемент НЕ, счетчик, три накопительных сумматора, два блока индикации и распределитель импульсов. 5 ил.

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ, содержащее первый сумматор, первый блок умножения, первый датчик случайных чисел, выход которого подключен к первому входу первого блока умножения, выход произведения которого соединен с первым входом первого сумматора, отличающееся тем, что, с целью повышения быстродействия и точности определения параметров оптимизируемой системы, в него введены три блока входных регистров, девять блоков элементов ИЛИ, узел установки нуля, триггер, с второго по восьмой сумматоры, генератор тактовых импульсов, девятнадцать элементов задержки, два блока сравнения, восемь элементов ИЛИ, пять коммутаторов, семь элементов И, тринадцать регистров, с второго по двенадцатый блоки умножения, второй датчик случайных чисел, шесть квадраторов, три блока вычитания, блок вычитания по модулю, три блока извлечения квадратного корня, восемь блоков деления, элемент НЕ, счетчик, три накопительных сумматора, два блока индикации и распределитель импульсов, тактовый вход которого соединен с выходом первого элемента И, а с первого по тридцать пятый выходы подключены соответственно к входам записи первого, второго и третьего блоков входных регистров, к первому входу считывания первого блока входных регистров, к управляющим входам первого и второго датчиков случайных чисел, к второму входу считывания первого блока входных регистров, к входам записи первого и второго регистров, к первым входам первого и второго элементов ИЛИ и к входам считывания третьего и четвертого регистров, к первым управляющим входам первого и второго коммутаторов, к первому и второму входам считывания второго блока входных регистров, к управляющему входу третьего коммутатора, к входу записи пятого регистра, к первым входам третьего и четвертого элементов ИЛИ, к первому и второму входам считывания третьего блока входных регистров, к тактовым входам первого, второго и третьего накопительных сумматоров, к входу записи шестого регистра, к первому входу пятого элемента ИЛИ, к тактовому входу счетчика, к входам записи седьмого, восьмого и девятого регистров, к первым входам шестого, седьмого и восьмого элементов ИЛИ и к входам считывания третьего и четвертого регистров, к входам записи десятого, одиннадцатого и двенадцатого регистров, к входам считывания этих же регистров, к входу записи тринадцатого регистра, к входам считывания пятого и тринадцатого регистров, к управляющему входу четвертого коммутатора, к первому управляющему входу пятого коммутатора, к третьему входу считывания третьего блока входных регистров, к второму управляющему входу пятого коммутатора, с первого по четвертый информационные входы первого блока входных регистров являются входом задания начальных значений устройства, первый выход этого блока подключен к первому входу первого блока элементов ИЛИ и через первый элемент задержки к первому входу второго блока элементов ИЛИ, второй выход блока входных регистров соединен с первым входом третьего блока элементов ИЛИ, а также через второй элемент задержки с первым входом четвертого блока элементов ИЛИ, третий и четвертый выходы первого блока входных регистров подключены к первым входам соответственно пятого и шестого блоков элементов ИЛИ, вторые входы которых соединены с выходами соответственно десятого и двенадцатого регистров, а выходы соответственно с вторым входом первого блока умножения и первым входом второго блока умножения, второй вход которого подключен к выходу второго датчика случайных чисел, а выход произведения - к первому входу второго сумматора, второй вход которого соединен с выходом третьего блока элементов ИЛИ, а выход суммы - с информационным входом первого регистра, вход считывания которого подключен к выходу первого элемента ИЛИ, а выход - к информационному входу первого коммутатора, второй управляющий вход которого соединен с выходом четвертого элемента ИЛИ, первый выход - с первым входом седьмого блока элементов ИЛИ, а также через третий элемент задержки - с вторым входом третьего блока элементов ИЛИ, второй выход первого коммутатора соединен с вторым входом седьмого блока элементов ИЛИ, а третий выход - с первым входом первого квадратора, через четвертый элемент задержки с первым входом второго элемента И, с информационным входом третьего регистра, выход которого подключен через пятый элемент задержки к первому входу третьего элемента И, а также через шестой элемент задержки - к первому входу четвертого элемента И, выход которого соединен с третьим входом третьего блока элементов ИЛИ, второй и третий входы первого блока элементов ИЛИ подключены к выходам соответственно седьмого элемента задержки и пятого элемента И, а выход - к второму входу первого сумматора, выход суммы которого соединен с первым входом третьего сумматора, второй вход которого через восьмой элемент задержки подключен к выходу произведения третьего блока умножения, а выход суммы - к информационному входу второго регистра, вход считывания которого соединен с выходом второго элемента ИЛИ, а выход - с информационным входом второго коммутатора, второй управляющий вход которого подключен к выходу третьего элемента ИЛИ, первый выход - к первому входу восьмого блока элементов ИЛИ, второй выход - к входу седьмого элемента задержки и к второму входу восьмого блока элементов ИЛИ, а третий выход - к входам девятого элемента задержки, выход второго квадратора - к информационному входу четвертого регистра, выход которого соединен через десятый элемент задержки с первым входом пятого элемента И и через одиннадцатый элемент задержки с первым входом шестого элемента И, выход которого подключен к второму входу второго блока элементов ИЛИ, выход которого соединен с входом вычитаемого первого блока вычитания, вход уменьшаемого которого подключен к выходу восьмого блока элементов ИЛИ, а выход разности к первому входу четвертого блока умножения и выходу третьего квадратора, выход которого соединен с первым входом четвертого сумматора и через двенадцатый элемент задержки с входом делимого первого блока деления, с первого по четвертый информационные входы второго блока входных регистров являются входом задания постоянных коэффициентов устройства, первый и второй выходы второго блока входных регистров подключены к первым входам соответственно пятого и шестого блоков умножения, третий и четвертый выходы второго блока входных регистров соединены соответственно с первым и вторым входами пятого сумматора, выход суммы которого подключен к первому входу седьмого блока умножения, второй вход которого соединен с выходом произведения восьмого блока умножения, а выход - с первым входом шестого сумматора, выход суммы которого подключен к информационному входу третьего коммутатора, а второй вход через тринадцатый элемент задержки - к выходу суммы седьмого сумматора, первый и второй входы которого соединены с входами произведения соответственно пятого и шестого блоков умножения, выход второго квадратора подключен к второму входу пятого блока умножения и к первому входу восьмого блока умножения, а выход первого квадратора соединен с вторыми выходами шестого и восьмого блоков умножения, первый и второй информационные входы третьего блока входных регистров являются входом задания точности и параметра сжатия устройства, третий и четвертый входы третьего блока входных регистров - входом задания начальных значений ковариационной матрицы устройства, первый выход третьего блока входных регистров подключен к первому входу первого блока сравнения, второй выход - к первому входу девятого блока умножения, а третий и четвертый выходы - соответственно к первому и второму входам восьмого сумматора, выход суммы которого через первый блок извлечения квадратного корня соединен с вторым входом девятого блока умножения, выход произведения которого подключен к информационному входу шестого регистра, вход считывания которого соединен с выходом пятого элемента ИЛИ, а выход - с первыми входами десятого, одиннадцатого и двенадцатого блоков умножения, выходы произведения которых подключены к информационным входам соответственно седьмого, восьмого и девятого регистров, а вторые входы - к выходам частного соответственно второго, третьего и четвертого блоков деления, входы делителя которых соединены с выходом четвертого квадратора, а входы делимого - с выходами суммы соответственно первого, второго и третьего накопительных сумматоров, информационные входы которых подключены к выходам частного соответственно первого, пятого и шестого блоков деления, входы делителя которых соединены с выходом суммы четвертого сумматора, а выходы делимого пятого и шестого блоков деления подключены соответственно к выходу четырнадцатого элемента задержки и выходу произведения четвертого блока умножения, первый выход третьего коммутатора соединен с информационным входом тринадцатого регистра, а второй выход - с первым входом девятого блока элементов ИЛИ, второй вход которого подключен к первому выходу пятого коммутатора, а выход - к информационному входу пятого регистра, выходы пятого и тринадцатого регистров соединены с информационными входами соответственно четвертого и пятого коммутаторов, первый выход четвертого и второй выход пятого коммутаторов подключены соответственно к первому и второму входам второго блока сравнения, а второй и третий выходы четвертого и пятого коммутаторов - к первому и второму входам блока вычитания по модулю, выход которого соединен с вторым входом первого блока сравнения, выход "Меньше или равно" которого подключен к первому входу седьмого и к второму входу второго элементов И, а также к сбросовому входу триггера, установочный вход которого соединен с выходом установки нуля, а прямой выход - с первым входом первого элемента И, второй вход которого подключен к выходу генератора тактовых импульсов, выход счетчика соединен с выходом четвертого квадратора, а счетный вход - с выходом "Меньше" второго блока сравнения, соединенным через пятнадцатый элемент задержки с вторым входом пятого элемента ИЛИ, выход "Меньше" второго блока сравнения соединен с вторыми входами третьего и шестого элементов И, первого, второго и третьего элементов ИЛИ, с входом элемента НЕ, выход которого через шестнадцатый элемент задержки подключен к вторым входам четвертого и пятого элементов И, выход элемента НЕ подключен к вторым входам шестого, седьмого и восьмого элементов ИЛИ, выходы которых соединены с информационными входами соответственно седьмого, восьмого и девятого регистров, выход седьмого регистра подключен к входам второго блока извлечения квадратного корня и семнадцатого элемента задержки, выход которого соединен с входом делителя седьмого блока деления, вход делимого которого подключен к выходу пятого квадратора, а выход частного - к выходу вычитаемого второго блока вычитания, вход уменьшаемого которого соединен через восемнадцатый элемент задержки с выходом восьмого регистра, а выход частного через третий блок извлечения квадратного корня - с информационным входом двенадцатого регистра, выход девятого регистра подключен к входам пятого квадратора и девятнадцатого элемента задержки, выход которого соединен с входом делимого восьмого блока деления, выход частного которого подключен к информационному входу одиннадцатого регистра, выход которого соединен с первым входом третьего блока умножения, второй вход которого подключен к выходу второго датчика случайных чисел, выход второго блока извлечения квадратного корня подключен к входу делителя восьмого блока деления и к информационному входу десятого регистра, выход третьего элемента И соединен с вторым входом четвертого блока элементов ИЛИ, выход которого подключен к входу вычитаемого третьего блока вычитания, вход уменьшаемого которого соединен с выходом седьмого блока элементов ИЛИ, а выход разности - с вторым входом четвертого блока умножения и с входом шестого квадратора, выход которого подключен к входу четырнадцатого элемента задержки и к второму входу четвертого сумматора, выход девятого элемента задержки соединен с вторым входом седьмого элемента И, выход которого подключен к входу первого блока индикации, а выход второго элемента И соединен с входом второго блока индикации.