Устройство для нахождения экстремума функции Советский патент 1987 года по МПК G06F17/18 

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

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

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

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

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

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

N и

arg мин F(X) 7 С, П

i i J--1

где С. О - значение весовых коэффициентов; е R - значение коэффициентов

показателя CTeneHjij X - аргумент функции; N - объем выборки; М - размерность аргумента.

X.-iiJ

(1

После преобразования Z.

j 1, М задача (1) дующий вид. Найти

1пХ.,

принимает слеarg мин F(Z)

Р, С. е

(2)

(01

Итерационный процесс поиска экстремального значения аргумента состоит в следующем. Пусть {z, ,. .., I - текущая точка. На К-ом шаге (К 1, М) каждой итерации в качестве оптимизируемой выбирается К-ая координата аргумента, а остальные координаты фиксируются. Для получения очередного приближения К-ой координаты Z решается следующая

одномерная оптимизационная Найти

задача:

arg мин F(Z,)

С. е

1-1

,(3)

где

С.

1

5

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

. ° / - ... :

F. (Z,

к

) 11

Ь1 .

С|.

30

и величина шага вдоль направления тиградиента, равная:

ан5

h 1/

1-1

С. oL.

1 IX.

е

(О)

ZK

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

Z к

(О)

h

к

(Л.

Итерационный поиск получения оптимального решения заканчивается при выполнении условия: м

izl-z l-f

где

- заданная точность вычислений.

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

В начальном состоянии первый и второй счетчики 9, lO установлены в О, третий счетчик 22 - в 1, четвертый блок 6 памяти содержит нулевые значения. С выходов значений весового коэффициента, коэффициента показателя степени и аргумента функции блока 1 задания параметров функции в первый, второй и третий блоки 3-5 памяти соответственно заносятся

Ci, ,U 2

Сигнал с выхода

мируются веса

значения

и

генератора 2 поступает на счетный вход первого счетчика 9, увеличивая его значение на 1, которое поступает на адресные входы первого, четвертого и второго блоков 3, 6 и 4 памяти. На второй адресный вход посг леднего поступает значение с третьего счетчика 22, которое одновременно поступает на управляющий вход третьего блока 5 памяти. На выходе второго умножителя 31 формируется произведение Zj-, пока значение второго счетчика 10 меньше М, на выходе пятого элемента 1-5 сравнения значение О, следовательно, закрыт ключ 16 и открыт ключ 20 с инверсным управляющим входом, через который произведение otjj Zj поступает на вторые входы элементов ИЛИ 8 второй группы, значение с выходов которых поступает на второй вход сумматора 23, суммируясь с предьщущим значе- .нием, поступающим с выхода четвертого блока 6 памяти, на котором фор, . С вы- ,

J-T хода объема выборки блока 1 значение

N поступает на первый вход элемента 11. сравнения, который срабатывает при дости5кении на счетчике-9 значения N, после чего на блоке 6 памяти формируется последнее значение А N, сбрасывается счетчик 9 и увеличивается на 1 значение счетчика 10, при достижении на котором значения М - 2 устройство 1 бтово к итерационному поиску экстремума, которьш заключается в следующем.

При значении счетчика 10 М-1 на выходе сумматора 23 формируются значения М заносятся в

й,-с:

блок 6 памяти. С выхода размерности аргумента блока 1 значение М поступает на первые входы элементов 13, 15 сравнения, на вторые входы которых поступает значение с выхода счетчика 10, при достижении на котором значения М, срабатывает элемент 15 сравнения, закрывая тем самым ключ 20 и открывая ключ 16, через который произведение d Z поступает на вход пятого умножителя. На выходе

..

5

0

0

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

г.;.

J--7JiK

Сигнал с выхода элемента 15 сравнения через первый элемент 24 задерж- ки поступает на управляющий вход ключа 18, через который накопленное в блоке 6 памяти значение иi поступает на вход экспоненциального преобразователя 26, значение с выхода которого, равное , поступает на вход операнда первого умножителя 30. На вход дру1 О1 о операнда поступает значение- Cj с выхода блока 3 памяти. На выходе умножителя 30 формируется значение , которое поступает на вход операнда четвертого умножителя 33, на вход другого операнда которого поступает значение (Х с выхода блока 4 памяти, которое поступает также на вход операнда 5 третьего умножителя 32, на вход другого операнда которого поступает

с выхода умножите- выходов умножителей 33 и 32 поступают на информаци- сонные входы накапливающих сумматоров

28 и 27, на выходах которых формиру- N

i

значение С.о(,(

f К

ля 33. Значения с

ются значения

и

..

N

5

i-1 соответственно.

ко0

5

0

5

L.c,,;e 1 1

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

счетчика 22 и управляющий вход ключа 17, через который с выхода накапливающего сумматора 29 значение

м .

т11 :-2к1

К;1

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

м

При невьшолнении условия

К 1

на одном выходе элемента 12 сравнения появляется сигнал, который поступает на вход сброса накапливающего сумматора. 29, и итерационный процесс повторяется. При выполнении

м Iусловия Л I 2 -Z UE сигнал появ

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

5

20

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

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

переменных, в него введены третий и

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

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

35

40

45

50

55

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

5

0

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

5

0

5

0

5

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

Пуск

Стоп

JO

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

20

25

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

Заказ 7719/53 Тираж 694 Подписное ВНИКЛИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие,г.Ужгород,ул.Проектная,4

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