Устройство для оптимизации функций многих переменных

 

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

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

Социаяистичесяик

Ресяубяик (6I) Донолиительное к авт.сеид-ву (22) 3 " «о 14. 03. 80 (21)2925234/18-24 (51)М. Кл.

6 0 F 15/31 с ярнсоелииениещ заявки,йв(23) Приоритет

9кударетееввб канптет

CCCt пе делан «забретенкй и пткрыткб

Оиубликоваио 23 04.82. бюллетень М15

Дата оиубликоваиия оиисаник 23 04 82 (З) УДК е81.333 (088.8) (54) УСТРОЙСТВО ДЛЯ ОПТИМИЗАЦИИ ФУНКЦИЙ

МНОГИХ ПЕРЕМЕННЫХ, 3

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

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

Недостатком данного .устройства является то, что оно не работает при поступлении íà его вход единичных реализаций нестационарных случайных процессов. Наиболее близким к изобретению является устройство для оптимиза" ции функцией многих перемещений содержащее блоки формирования линей2 но независимых функций, кольцевой счетчик, регистры сдвига, оперативный регистр, блок скалярного произведения, блок масштаба приращений коэффициентов, ключи и генератор ,импульсов Р23.

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

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

Поставленная цель достигается тем, что для оптимизации функций многих

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

35 первыми входами всех блоков умножения второй группы, второй вход кажДого блока умножения второй группы подключен к выходу соответствующего ключа второй группы и выходу соответствующего ключа третьей группы, выход каждого блока умножения второй группы соединен с соответствующим входом группы входов первого счетчика, выход которого подключен к первому входу блока умножения, выход которого соединен с первым входом второго сумматора, второй вход которого подключен к выходу третьего регистра сдвига, каждый выход группы выходов которого соединен со -вторым входом соответствующего блока умножения первой группы, выход второго сумматора через второй счетчик подключен ко второму входу блока управления, управляющему входу первого ключа и входу третьего регистра, выход блока задания коэффициентов соединенысо вторым входом бло1 4 ка умножения, информационный вход первого ключа подключен к входу первого счетчика и выходу второго ключа, информационный вход ко;орого соединен с выходом генератора импульсов

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

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

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

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

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

15 и 16.

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

На вход блоков 1 и 7 в тактовые моменты времени поступают выборки случайных процессов x(j). Блок 7 . управления после прихода сигнала

x (j ) вырабатывает сигнал С1 „который открывает ключ 2, соединяющий генератор 4 импульсов со входом линии

5 задержки. На выходе линии задержки формируется сигнал "1" или "0".

Ключи 2, на которые поступает сигнал "1" открыты, а ключи 2, на которые поступает "0" - закрыты. Тогда в тактовые моменты времени на вход регистра сдвига 5 через ключи 2 последовательно поступят сигналы

Я Х 1)); Ч(Х(-1)) ... М (43-11)) .

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

13

3S

43

S0

Я регистра 5 сдвига поступят через ключи 2 на первые входы блоков

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

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

It входов накапливающего сумматора 9, где происходит формирование сигнала

С 1Ч Х(1)) . Сигнал, полученный

)а 1 на выходе накапливающего сумматора 9, поступает на вход первого сумматора

10, на второй вход которого поступа-, ет сигнал 3(j.) со входа устройства.

На выходе сумматора 10 формируется сигнал ta(3)-Q С Ч (х(j))) . Этот сигнал поступает на входы блоков 8 умножения второй группы, на вторые входы которых поступает сигнал, снимаемый с 1 выходов первого регистра сдвига 5. Сигналы с выходов блоков 8 умножения Поступают íà и входов пер" вого счетчика 11, в котором образуют ся сигналы, равные вектору градиента критерия качества

11

,Я= чщ-рс.ч(кщ))ц(кцц.

1"-1

Сигнал с первого блока о умножения поступает на вход блока 7 управления.

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

7 922 с помощью сигналов, поступающих на вход регистра 5 сдвига с сумматора 10. При этом ключ 2 закрывается и прекращает доступ сигналов с генератора 4 импульсов на третий регистр 5 сдвига. Сигнал ,с выхода сумматора 10 поступает на вход счетчика 13. Сигнал с выхода счетчика 13 через и тактов поступит на вход блока 7 управления. Блок

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

С4, поступают на входы блоков 8 умно жения, первой и второй групп. Происходит уточнен е вектора весовых коэффициентов. После прихода сигна- 5в ла С3 с блока управления сигнал С4 прекращает действие. После выполнения всех операций и --й импульс с выхода счетчика. 13 формирует в блоке

7 управления сигнал С4,происходит проталкивание сигналов, записанных в первом регистре 5 сдвига на один щаг Процесс уточнения повторяется jjo тех пор, пока во второй регистр 5 сдвига не будут переписаны все значения входного сигнала..После этого -ый сигнал с выхода кольцевого счетчика 6 сбросит кольцевой счетчик 6 . и второй регистр 5 сдвига, и процесс уточнения повторится. Уточненные значения вектора весовых коэффици ентов получаются на выходе третьего регистра 5 сдвига, с выхода регистра они поступают на вход блока 7 управления. блок 7 управления формирует команду на прекращение уточне5О ния. Эта команда формируется с помощью счетчика, считывающего количество циклов уточнения вектора весовых коэффициентов.

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

1(()=Ч,. ((1)) (X(Ä)) .

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

5 устройства единичных реализаций нестационарных случайных процессов.

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

1ф поступают единичные реализации нестационарных случайных процессов.

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

15 переменных р =@(а с„,с „.c )) м где 1 (c) - функционал качества, зависящий от переменных коэффициентов; .И вЂ” операция определения

1 математического ожидания функции Q

Устройство реализует рекуррентную процедуру минимизации с использованием метода Ньютона-Рафсона. В этом случае для квадратичного критерия имеем а(с,...с„)фй-сс;« и >) >

r«« где Q(c) - функция, подлежащая минимизации;

V (i) - эталонный сигнал, поступающий с выхода устройства, весовые коэффициенты которого минимизируются;

C e;q„.(õÖ)) - выходной сигнал реального устройства; (;; - весовые коэффициенты устройства;

1(()) - входной сигнал устройства; 1() линейно незавиСимые функции. .Градиент этого функционала имеет вид

- Я

5,Е . М- - 11«((4 ;(»- () 1((».®

Ы

Алгоритм минимизации имеет вид

5(3tq)=C(j3 KH 909 (1((3+В С(3Ц4) где к - величина щага адаптации выбирается экспериментально;

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

Для случая единичных реализаций случайных процессов, она имеет вид

92276) 9

Следовательно, обратной матрицы для такой матрицы не существует.

Поэтому используется псевдообратная матрица, имеющая вид

" (3)=H(91Ú í(3È % где. 1 + 1 — операция псевдообращения

«H(3}=8; (х (j)) ч; (х())) (b)

Подставляя (5) и (6) в (4), получим рекуррентную формулу для опре деления оптимального значения

С (3н)=С(3)+ КЕ{3) Чф (»)t lt H{j) I. (1)

Таким образом, применение метода

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

Ньютона-Рафсона позволяет повысить быстродействие устройства, Формула изобретения

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

-,возможностей за счет учета нестационарности переменных оптимизируемой функции, оно дополнительно содержит блок управления, блок задания коэффициентов; линию задержки, кольцевой счетчик, две группы блоков умножения, блок умножения, два сумматора, накапливающий сумматор, два счетчика, причем первый вход устройства соединен с первым входом блока управления и через соответствующий блок формирования линейно независимых функций группы с информационным входом соответствующего ключа ïåðвой группы, выход каждого ключа первой группы подключен к первому входу первого регистра сдвига, каждый выход группы выходов которого соеди" нен с информационным входом соответствующего ключа второй группы, выход первого регистра сдвига подключен к первому входу второго регистра сдвига, каждый выход группы выходов ко" торого соединен с информационным входом соответствующего ключа третьей группы, выход каждого ключа вто)О рой группы соединен с первым входом соответствующего блока умножения пер" вой группы, выход которого подключен к соответствующему входу накапливающе.

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

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

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

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

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

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

1.Уидроу Б. и др. Стационарные и нестационарные характеристики обучения адаптивных фильтров, использующих критерий минимума СКО, ТИИЭР, т.64, 1976, М 8, с. 39.

2$

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

8 249773, кл. G 06 F 15/34, 1970 (прототип), 922761

Составитель Л. Терехов

Редактор Н.Пуаненкова Техред И.Гайду Корректор И.Демчик

Заказ 2583/65 Тираж 732 Подписное

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

1l3035, Иосква, N-35, Рауаская:наб., д. 4/5

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