Устройство для оптимизации функций многих переменных Советский патент 1982 года по МПК G06F17/10 

(5) УСТРОЙСТВО ДЛЯ ОПТИМИЗАЦИИ ФУНКЦИЙ многих ПЕРЕМЕННЫХ.

1

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

.Известно устройство для оптимизации функции многих переменных, содер жащее входной счетчик 2 п+ 1 множиг тельных устройств, накапливающий сум матор, сумматор на два входа и один выход, генератор импульсов, счетчик На п -( 1 вход и один выход, счетчик на два входов и один выход, блок фЬр мирования эталонного сигнала, блок памяти, pervicTp сдвига tl3.

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

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

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

15 шагов адаптации устройство не успевает отслеживать нестационарности случайных процессов.

Цель изобретения - расширение jg функциональных возможностей за счет учета нестационарности переменных оптимизируемой функции.

Поставленная цель достигается тем, что для оптимизации функций многих переменных, содержащее группу блоков формирования линейно независимых функций, регистры сдвига, три группы ключей, четыре ключа и генератор импульсов, дополнительно содержит блок управления, блок задания коэффициентов, линию задержки, кольцевой счетчик, две группы блоков умножения, блок умножения, два сумматора, накапливающий сумматор, два счетчика причем первый вход устройства соединен С- первым входом блока управления и через соответствующий блок формирования линейно-независимых функций группы с информационным входом СООТветствующего ключа первой группы, . выход каждого ключа первой группы подключен к первому входу первого регистра сдвига, каждый выход группы выходов которого соединен с информа.ционным входом соответствующего ключа второй группы, выход первого регистра сдвига подключен к первому входу втор го регистра сдвига, каждый выход груп пы выходов которого соединен с информационным входом соответствующего клю ча третьей группы, выход каждого ключа второй группы соединен с первым входом соответггвующего блока умножения первой группы, выход которого подключен к соответствующему входу накапливающего сумматора, выход которого соединен с первым входом первого сумматора, второй вход которого подключен ко второму входу устройства выход первого сумматора соединен с первыми входами всех блоков умножения второй группы, второй вход каждог блока умножения второй группы подключен к выходу соответствующего ключа второй группы и выходу соответствующего ключа третьей группы, выход каждого блока умножения второй группы соединен с соответствующим входом группы входов первого счетчика, выход которого подключен к первому входу блока умножения, выход которого соединен с первым входом второго сумматора, второй вход которого подключен к выходу третьего регистра сдвига, каждый вь1ход группы выходов .которого соединен со вторым входом соответству ющего блока умножения первой группы, выход второго сумматора через второй счетчик подключен ко второму входу блока управления, управляющему входу первого ключа и входу третьего регистра, выход блока задания коэффициентов соединены со вторым входом бло ка умножения, информационный вход первого ключа подключен к входу первого счетчика и выходу второго ключа, информационный вход когорого соединен с выходом генератора импульсов и информационными входами третьего и четвертого ключей, выход третьего ключа соединен с входом кольцевого счетчика, выход которого подключен ко второму входу второго регистра сдвига, все выходы группы входов сдвига, все выходы группы выходов кольцевого счетчика соединены со вторым входом первого регистра сдвига, третий вход блока управления подключен к выходу первого блока умножения второй группы, выход четвертого ключа соединен с входом линии задержки, выход которой по ключен к четвертому входу блока управления , каждый выход группы выходов ЛИНИИ задержки соединен с управля1гицим входом соответствующего ключа первой группы, первый выход блока управле ия подключен к управляющему входу четвертогр ключа, второй выход блока управления соединен с управляющими входами всех ключей второй группы,, третий выход блока управления подключен к управляющему входу второго ключа, четвертый выход блока управления соединен с управляющими входами третьего ключа и всех ключей третьей группы. Кроме того, блок управления содержит четыре блока памяти и два счетчика, причем первый вход первого блока памяти соединен с первым и вторым входами блока управления, первый выход первого .блока памяти подключе.н к первому выходу блока управления, второй выход первого блока памяти соединен с первым входом второго блока памяти, первый выход которого подключен ко второму выходу блока управления, второй вы- ход второго блока памяти соединен со вторым входом первого блока памяти, первый вход третьего блока памяти подключен к третьему и четвертому входам блока управления, первый выход третьего блока памяти соединен с третьим выходом блока управления, второй выход третьего блока памяти подключен к первому входу четвертого блока памяти, первый выход которого соединен с четвертым выходом блока управления и с первым

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

На фиг.1 представлена блок-схема устройства; на фиг.2 - схема блока 5 управления. . ,

Устройство содержит блоки 1 формирования линейно-независимых функций, ключи 2, линию 3 задержки, генератор i импульсов, регистры 5 сдви- 20 га, кольцевой счетчик 6, блок 7 управления, блоки 8 умножения, накапливающий сумматор 9, сумматоры 10, счетчик 11, блок 12 задания коэффициентов, счетчик 13. Блок управления 25 содержит блоки памяти и счетчики 15 и 16.

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

На вход блоков 1 и 7 в тактовые зо моменты времени поступают выборки случайных процессов х (j). Блок 7 управления после прихода сигнала X (j) вырабатывает сигнал С1, который открывает ключ 2, соединяющий jj генератор импульсов со входом линии 5 задержки. На выходе линии задержки формируется сигнал 1 или О. Ключи 2, на которые поступает сигнал 1 открыты, а ключи 2, на ко- ц торые поступает О - закрыты. Тогда в тактовые моменты времени на вход регистра сдвига 5 через ключи 2 последовательно поступят сигналы

ixij))-. ч(мr1))

в третьем регистре 5 записаны значения весовых коэффициентов, полученные на предыдущем шаге адаптации. Последовательная выборка сигмалов осуществляется линией 3 заде)жки. По прошествии п импульсов на выходе линии 3 задержки формируется сигнал, поступающий на вход блока 7 управления. Блок 7 управления вира батывает сигнал управления С2 и одновременно прекращает действие сигнала С1. В результате этого и вы§ODOK входного сигнала с первого

регистра 5 сдвига поступят через ключи 2 на первые входы блоков 3 умножения первой группы, на вторые входы которых поступают сигналы с выходов третьего регистра 5 сдвига, в котором хранится старое значение вектора весовых коэффициентов. Сигналы с выходов блоков 8 умножения поступают но /1/входов накапливающего сумматора 9 где происходит формирование сигнала

С (.X(.j)) . Сигнал, полученный на выходе накапливающего сумматора 9 поступает на вход первого сумматора

10, на второй вход которого поступает сигнал :Kj) со входа устройства. На выходе сумматора 10 формируется

сигнал ) Зтот сигнал пост Т1ает на входы блоков 8 умножения второй группы, на вторые входы которых поступает сигнал, снимаемый с п выходов первого регистра сдвига 5. Сигналы с выходов блоков 8 умножения ррступают на п входов первого счетчика П, в котором образуют ся сигналы, равные вектору градиента критерия качества

)-fetj4txij))4ix(j)).

Сигнал с первого блока 8 умножения поступает на вход блока 7 управления Блок 7 управления вырабатывает сигнал СЗ и одновременно прекращает действие сигнала С2. Сигнал СЗ откроет ключ 2, соединяющий генератор k импульсов со счетмиком 11 и через первый ключ с третьим регистром 5 сдвига. Импульсы с генератора 4 импульсо вытесняют значения вектора градиента критерия качества из счетчика 11 и вектора весовых коэффициентов из третьего регистра 5 сдвига. Причем . импульсы на третий регистр сдвига идут через ключ 2, который открыт только в том случае, если на выходе второго сумматора 10 нет сигнала. Значения вектора градиента критерия качества последовательно умножаются в блоке Э умножения на величину шага адаптации, формируемую в блоке 12 задания коэффициентов. Эти сигналы затем последовател11но складывают в сумматоре 10 со старыми значениями вектора весовых коэффициентов, вытесненными из третьего

регистра 5 сдвига сначала с помощью импульса,полученного с генератора импульсов, а затем поступающих С помощью сигналов, на вход регистра 5 сдвига с сумматора 10. При этом ключ закрывается и прекращает доступ сигналов с генератора t импульсов на третий регистр 5 сдвига. Сигнал ,с выхода сумматора 10 поступает на вход счетчика 13. Сигнал с выхода счетчика 13 через п тактов поступит на вход блока 7 управления. Блок 7 управления фррмирует сигнал С и одновременно прекращает действие си нала СЗ. Сигнал С4 подключает через ключ 2 к генератору 4 импульсов кольцевой счетчик 6, сигналы с ко-. торого поступают на вход первого регистра 5 сдвига, вытесняя сигналы записанные в этом регистре сдвига во второй регистр сдвига 5. Величина задержки между сигналами, снимае мыми с кольцевого счетчика 6, соотв ствует циклу определения нового уто ненного значения вектора весовых коэффициентов.Сигналы с выхода втор го регистра 5 сдвига через ключи 2 открывающиеся после прихода сигнала С , поступают на входы блоков 8 умн жения, первой и второй групп. Происходит уточнен е вектора весовых коэффициентов. После прихода сигнала СЗ с блока управления сигнал С прекращает действие. После выполнения всех операций п-и импульс с выхода счетчика 13 формирует в блок 7 управления сигнал С,происходит проталкивание сигналов, записанных в первом регистре 5 сдвига на один ujar.Процесс уточнения повторяется Д тех пор, пока во второй регистр 5 сдвига не будут переписаны все значения входного сигнала. .После этого f -ый сигнал с выхода кольцевого сч чика 6 сбросит кольцевой счетчик 6 и второй регистр 5 сдвига, и процес уточнения повторится. Уточненные значения вектора весовых коэффициентов получаются на выходе третьего регистра 5 сдвига, с выхода регистра они поступают на вход блока управления Блок 7 управления форми рует команду на прекращение уточнения. Эта команда формируется с помощью счетчика, считывающего количество циклов уточнения вектора весовых коэффициентов. Устройство мбжет работать как при постоянном значении величины ша га адаптации, в зтом случае блок задания коэффициентов представляет блок памяти, хранящий постоянную величину, так и при переменном значении, причем второй вариант предпочтительнее при поступлении на вход устройства единичных реализаций нестационарных случайных процессов. Устройство дает возможность искать минимум функции многих переменных в случае, когда на вход устройства поступают единичные реализации нестационарных случайных процессов. Устройство предназначено для того, чтобы определять минимум математического ожидания функции многих переменных Oio)W{QtC-,,c,i...) Д) где О (с) - функционал качества, зависящий от переменный коэффициентов ; М - операция определения математического ожидания функции Q . Устройство реализует рекуррентную процедуру минимизации с использованием метода Ньютона-Рафсона. В этом случае для квадратичного критерия имеем %-4),U(i)f.(a) где Q(c) функция, подлежащая минимизации;эталонный сигнал, поступающий с выхода устройства, весовые коэффициенты котоW рого минимизируются; )) - выходной сигнал реального устройства; С - весовые коэффициенты устройства; - входной сигнал устройства; Чч(зГ линейно независимые функции. Градиент этого функционала имеет вид S(3) .t«j}9 l 4i)} S(J)4(XU)(J) Алгоритм минимизации имеет вид OlHsCQHKHScSWi+DiCU), (4) где к - величина шага адаптации выбирается экспериментально; hf -обратная матрица вторых производных функционала качества. Для случая единичных реализаций случайных процессов, она имеет вид )-.4(x(i))4;uij)). 99 Следовательно, обратной матрицы для такой матрицы не сущ,ествует. Поэтому используется псевдообратная матрица, имеющая вид H4i)Hl3)lHrH(i)i, (S) где 1 -. I - операция псевдообращения ,ЬWU)-- IiUi)) (Ь) Подставляя (Si и (6) в , получим рекуррентную формулу для опре деления оптимального значения С ti4Mscii)+ne(i)4,{x (i))/itt-H(j)i Л1) Таким образом, применение метода Ньютона-Рафсона позволяет распростра НИТЬ область применения устройства на системы одноразового применения, т.е. системы, выходные сигналы которых заданы единичными реализациями. Кроме того, применение метода Ньютона-Рафсона позволяет повысить быстродействие устройства. Формула изобретения 1. Устройство дня оптимизации функций многих переменных, содержащее группу блоков формирования линейно независимых функций, регистры сдвига, три группы.ключей, четыре ключа и генератор импульсов, отличающееся тем, что, с целью расширения функциональных -.возможностей за счет учета нест ционарности переменных оптимизируё мой функции, оно дополнительно-содержит блок управления, блок задания коэффициентов, линию задержки, кольцевой счетчик, две группы блоко умножения, блок умножения, два сумматора, накапливающий сумматор, два счетчика, причем первый вход устрой ства соединен с первым входом блока управления и через соответствующий блок формирования линейно независи мых функций группы с информационным входом соответствующего ключа первой группы, выход каждого ключа пе вой группы подключен к первому вход первого регистра сдйига, каждый выход группы выходов которого соеди нен с информационным входом соответствующего ключа второй группы, выход первого регистра сдвига подключ к первому входу второго регистра сдвига, каждый выход группы выходов которого соединен с информационным входом соответствующего ключа треть ей группы, выход каждого ключа второй группы соединен с первым входом соответствующего блока умножения первой группы, выход которого подключен к соответствующему входу накапливающего сумматора, выход которого соединен с первым входом первого сумматора, второй вход которого подключен ко второму входу устройства, выход первого сумматора соединен с первыми входами всех блоков умножения второй группы, второй вход каждого блока умножения второй группы подключен к выходу соответствующего ключа второй группы и выходу соответствующего ключа третьей группы, выход каждого блока умножения второй группы соединен с соответствующим входом группы входов первого счетчика, выход которого подключен к первому входу блока умножения, выход которого соединен с первым входом второго сумматора, второй вход которого подключен к выходу третьего регистра сдвига, каждый выход группы выходов которого соединен со вторым входом ссютветствующего блока умножения первой группы, выход второго сумматора через второй счетчик подключен ко второму входу блока управления, управляющему входу первого ключа и входу третьего регистра, выход блока задания коэффициентов соединен со вторым входом блока умножения, информационный вход первого ключа подключен к входу первого счетчика и выходу второго ключа, информационный вход которого соединен с выходок генератора импульсов и информационными входами третьего и четвертого ключей, выход третьего ключа соединен С входом кольцевого счетчика, выход которого подключен ко второму входу второго регистра сдвига,все выходы группы выходов кольцевого счетчика соединены со вторым входом первого регистра сдвига, третий вход блока управления подключен к выходу первого блока умножения второй группы, выход четвертого ключа соединен с входом линии задержки, выход которой подключен к четвертому входу блока управления, каждый выход группы выходов линии задержки соединен с управляющим входом соответствующего ключа первой группы, первый выход блока управления подключен к управлякзщему входу четвертого кл-оча, второй выход блока управления соединен / с управляющими входами всех ключей .

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

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

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

.входу третьего блока памяти.

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

Фиг. I