Устройство для нахождения экстремума функции

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (gg 4 G 06 F 15/36

ОПИСАНИЕ ИЗОБРЕТЕНИЯ!

°

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTPM

К АВТОРСКОМУ(СВИДЕТЕЛЬСТВУ (21) 3923114/24-24 (22) 27.06.85 (46) 30.01.87. Бюл. У 4 (72) С.M. Брейтман, Ю.Л. Литвин и Ж.К. Иартинкевич (53) 681.32(088.8) (56) Авторское свидетельство СССР

У 1205156, кл. С 06 F 15/36, 1984. (54) УСТРОЙСТВО ДЛЯ НАХОЖДЕНИЯ ЭКСТРЕИУИА ФУНКЦИИ (57) Изобретение относится к вычислительной технике и может быть ис-пользовано в автоматизированных системах управления. Цель изобретения— расширение класса решаемых задач за счет нахождения экстремумов функций

„„SU„„ I 287182 A 1 многих переменных, имеющих вид сумм произведений степенных функций.Уст- ройство содержит блок задания параметров. функции, генератор тактовых импульсов, три счетчика адреса, че- . тыре блока памяти, пять элементов сравнения, вычитатель, две группы элементов ИЛИ, шесть ключей, пять умножителей, три накапливающих сумматора, экспоненциальный преобразователь, сумматор, два элемента за держки, блок деления, блок выдачи результата с соответствующими функциональными связями. Устройство реализует метод покоординатного спус- Я ка. 1 ил.

1287182 (2) м 1Ol

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

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

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

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

f5 блок 5 памяти, четвертый блок 6 памяти, первую группу элементов ИЛИ 7,. вторую группу элементов ИЛИ 8, первый счетчик 9 адреса, второй счетчик 10 адреса, первый элемент 11 сравнения, второй элемент 12 сравне. ния, третий элемент 13 сравнения, четвертый элемент 14 сравнения, пяTbIH 3JIeMeHT 15 сравнения второй, первый и третий ключи 16, 17, 18 соответственно, четвертый, шестой и пятый ключи 19, 20, 21 соответственно, третий счетчик 22 адреса, сумматор 23, первый и второй элементы 24 и 25 задержки, экспоненциальный преобразователь 26, второй, первый и третий накапливающие сумматоры 27, 28 29, с первого по пятый умножители 30 — 34, блок 35 деления, вычитатель 36, блок 37 регистрации;

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

Задача оптимизации задается в следующем виде:

N М

arg мин Р(Х)= С, Г) 2 — 11 1

О1 с(У

arg мин F(Z) =, С. е "

1=1

Итерационный процесс поиска экстремального значения аргумента состо(о) Г (о) ит в следующем. Пусть Z = Z,,..., Е (— текущая точка. На К-ом шаге

1o) 1 (К = 1, М) каждой итерации в качестве оптимизируемой выбирается К-ая координата аргумента, а остальные его координаты фиксируются. Для получения очередного приближения К-ой координаты Z решается следующая к одномерная оптимизационная задача:

Найти

arg мин F (Z )= 2 С. е к,(3) 1=1

И

У < ° 2 где С. = С е,=1+к 1Ч

Для нахождения решения задачи (3) 1 определяется градиент функции F (Е„) (о). к в точке Z

К (.

N (о) F„(Z ) = 1 С с е

1=1 и величина шага вдоль направления антиградиента, равная: (о) h* = 1/(С К, е." к 1 1к

1=1

Тогда новое значение .К-ой координаты аргумента вычисляется по формуле (о) (о)

Z*=Z — g*F(Z) °

Итерационный поиск получения оптимального решения заканчивается при выполнении условия: (о) о1 где — заданная точность вычислегде С.> 0 — значение весовых.коэффициентов; ;„ < R — значение коэффициентов показателя степени

Х - аргумент функции;

N — объем выборки;

M — размерность аргумента.

После преобразования Z . .= 1nXÄ, — i, M задача (1) принймает следующий вид. Найти нни, Устройство работает следующим образом.

В начальном состоянии первый и второй счетчики 9, 10 установлены в

"0", третий счетчик 22 — в "1", четвертый блок Ь памяти содержит нулевые значения. С выходов значений весового коэффициента, коэффициента показателя степени и аргумента функ1267182 ции блока 1 задания параметров функции в первый,:второй и третий блоки

3-5 памяти соответственно заносятся значения С d " Z Сигнал с выхода

1j генератора 2 поступает на счетный вход первого счетчика 9, увеличивая

его значение на 1, которое поступает на адресные входы первого, четвертого и второго блоков 3, 6 и 4 памяти. На второй адресный вход пос леднего поступает значение с третьего счетчика 22, которое одновременно поступает на управляющий вход третьего блока 5 памяти. На выходе второго умножителя 31 формируется произ- 15 ведение Ы „ Z пока значение второго счетчика 10 меньше M на выходе пятого элемента 15 сравнения значение "0", следовательно, закрыт ключ 16 и открыт ключ 20 с инверсным управляющим вхоцом, через который произведение с ;, Z; поступает на вторые входы элементов ИЛИ 8 второй группы, значение с выходов которых поступает на второй вход сумматора

23, суммируясь с предыдущим значе,нием, поступающим с выхода четвертого блока 6 памяти, на котором формируются веса С выM-1

j= 1 хода объема выборки блока 1 значение

N поступает на первый вход элемента 11 сравнения, который срабатывает при достижении на счетчике 9 значения N после чего на блоке 6 памяти формируется последнее значение Ь И, сбрасывается счетчик 9 и увеличивается на 1 значение счетчика 10, при достижении на котором значения М = 2

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

При значении счетчика 10 M-1 на выходе сумматора 23 формируются зна45 чения и заносятся в д = d" 2.

3=1 блок 6 памяти. С выхода размерности аргумента блока 1 значение M поступает на первые входы элементов 13, 15 сравнения, на вторые входы которых поступает значение с выхода счетчика 10, при достижении на котором значения M срабатывает элемент 15 сравнения, закрывая тем самым ключ

20 и открывая ключ 16, через который произведение < Z поступает на к к вход пятого умножителя ° На выходе последнего формируется значение 4. Z поступающее на второй вход сумма— тора 23, на выходе которого формируется значение

:,а, =,„Z;. =1 1 к

Сигнал с выхода элемента 15 сравнения через первый элемент 24 задержки поступает на управляющий вход ключа 18, через который накопленное в блоке 6 памяти значение д, поступает на вход экспоненциального преобразователя 26, значение с выхода которого, равное е, поступает на вход операнда первого умножителя 30.

На вход другого операнда поступает значение С; с выхода блока 3 памяти. На выходе умножителя 30 формируется значение С е, которое постуЛ пает на вход операнда четвертого умножителя 33, на вход другого операнда которого поступает значение

d.,K с выхода блока 4 памяти, которое поступает также на вход операнда третьего умножителя 32, на вход другого операнда которого поступает значение С o(е с выхода умножитеД

1К ля 33. Значения с выходов умножителей 33 и 32 поступают на информаци"-онные входы накапливающих сумматоров

28 и 27, на выходах которых формиру— ются значения и

i -=1 соответственно, которые поступают на входы делимого и делителя блока,35 деления. При достижении N на счетчике 9 срабатывает элемент 11 сравнения, который открывает ключ 21 и чере-i второй элемент задержки 25 сбрасывает в ноль накапли-. вающие сумматоры 27 и 28. Значение с блока 35 деления через ключ 21 поступает на вход вычитаемого вычитателя 36 и информационный вход накапливающего сумматора 29. На вход уменьшаемого вычитателя 36 поступает значение Z, с блока 5 памяти, которое одновременно поступает на вход блока 37 регистрации. Новое значение координаты Z+ с выхода вычитателя

36 поступает через первую группу элементов ИЛИ 7 на вход блока 6 памяти.

Как только значение счетчика 22 становится больше М, срабатывает элемент 14 сравнения, сигнал с выхода которого поступает на вход сброса

1287182 сигнал появформула изобретения

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

17, через который с выхода накапливающего сумматора 29 значение м I z„ - z,l

К=1 поступает на один вход элемента 12 сравнения, на другой вход которого с выхода задания точности вы-, числений блока 1 поступает значение

При невыполнении условия

К=1 — Z (< Е на одном выходе элемента 12

М сравнения появляется сигнал, который поступает на вход сброса накапливающего сумматора 29, и итерационный процесс повторяется. При выполнении м ,Условия 7 7 — g ) c g

К=1 ляется на выходе "Меньше" второго . элемента 12 сравнения, который поступает на вход останова генератора

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

5 первого операнда четвертого умножителя, выход второго блока памяти подключен к входам первого операнда второго умножителя и второго операн10 да четвертого умножителя, выход которого подключен к информационному входу первого накапливающего сумматора, выход третьего умножителя подключен к информационному входу второго накапливающего сумматора, выход первого ключа подключен к второму входу второго элемента сравнения, выход вычитателя подключен к первым входам элементов ИЛИ первой группы, о T л и ч B ю щ р- е с я тем что с целью расширения класса решаемых задач путем обеспечения возможности нахождения экстремумов функций многих переменных, в него введены третий и

25 четвертый блоки памяти, вторая группа элементов ИЛИ, второй и третий счетчики адреса, третий, четвертый и пятый элементы сравнения, четвертый, пятый и шестой ключи, сумматор, третий накапливающий сумматор, первый и второй элементы задержки, блок деления и блок регистрации, причем выход аргумента функции блока задания параметров функции подключен к вторым входам элементов ИЛИ первой группы, а выход размерности аргумента блока задания параметров функции подключен к первым входам третьего, четвертого и пятого элементов сравнения, выход первого счетчика адреса подключен к адресному входу четвертого блока памяти, информационный вход которого соединен с выходом сумматора, а выход с первым входом сумматора и информационным входом третьего ключа, выход которого соединен с входом экспоненциального преобразователя, выход "Равнон первого элемента срав50 нения подключен к входу сброса первого счетчика адреса, управляющим входам четвертого и пятого ключей, входу второго элемента задержки и счетному входу второго счетчика ад55 реса, выход которого подключен к вторым входам третьего и пятого элементов сравнения, выход пятого элемента сравнения подключен к управляющим входам второго, шестого клю1287182

Составитель В. Орлов

Редактор С. Лисина Техред А.Кравчук Корректор М. Демчик

Заказ 7719/53 Тираж 694 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5

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

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

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

1 сброса первого и второго накапливающих сумматоров, выход первого накапливающего сумматора подключен к входу делимого блока деления, вход делителя которого, подключен к выходу второго накапливающего сумматора, а выход — к информационному входу пятого ключа, выход которого подключен к информационному входу третьего накапливающего сумматора и входу вычитаемого вычитателя, выход "Больше — Равно" второго элемента сравнения подключен к входу сброса третьего накапливающего сумматора, выход которого подключен к информационному входу первого ключа, выход Меньше второго элемента сравнения подключен к входу останова генератора импульсов.