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

112871

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

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

10

На чертеже представлена функциональная схема устройства.

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

Устройство реализует метод наискорейшего спуска с оптимальным выбором

F;()F(.(r-:()F(2 ° )) -2F()Q,

0

80 2

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

Задача оптимизации задается в следующем виде: найти arg мин ) .d

-Iic,

при ограничении

1-1

F,(X) IZ

,

С,-Х -1 0, М,

(1)

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

показателя степени; X - аргумент функций; Т - значения верхних границ

суммирования; М - число ограничений; объем выборки.

М-

После преобразования Z 1пХ задача (1) принимает вид: найти

arg мин F, (Z) И Cie , при огра- 1 1

ничении

(Z)

UT +1

m-i

ае

ы,г

-1 О, М (2)

Итерационный поиск экспериментального значения состоит из двух этапов на первом этапе в текущей точке Z определяется градиент минимизируемой

функции:

Т,

со)

F, () Г: С-с. е

ciiZ

Со)

i 1

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

fT

мин А ,

iifntM

где допустимая величина шага для т-го ограничения (ш 2,М) или для целевой функции (), которая определяется:

, 1|

();

fO

31287

Очередная точка итерации определя-- ется по формуле , (Z -). Итерационный процесс продолжается до получения решения. Критерием останова является условие , где з - заданная точность вычислений.

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

С выходов значений весового коэффициента, коэффициента показателя степени и верхних границ суммирования блока 1 соответственно в первый, второй и третий блоки памяти заносятся значения С. , о . , Т . Сигнал с генератора 2 поступает через первый счетчик 8 на первый и второй блоки 3 и 4 памяти, первую и третью схемы 10 и 9 сравнения, на первый входы которых поступают значения верхних границ суммирования Т с выхода тре- 20 тьего блока 5 памяти и Т с выхода объема выборки блока 1 соответственно Г С выхода аргумента функции блока 1 через логарифмический преобразователь 6 и первый регистр заносит

15

25

ся начальная точка Z ° полученная путем логарифмического преобразования, -на выходе второго умножителя 15 формируется показатель Экспоненциальный преобразователь 14 вычис- О ляет функцию . В результате операции умножения на выходах первого, четвертого и третьего умножителей 1-6, 17 и 19 получаются выражения

1804

входах сброса с выхода первого элемента 18 задержки. Значение с выхода второго счетчика 11 адреса поступает на адресный вход третьего блока 5 памяти и четвертую схему 12 сравнения, при срабатывании которой открываются пятый и седьмой коммутаторы 27 и 41. Значение F (Z ° ) поступает на вход второго регистра 29, с выхода которого оно поступает на вход пятого, седьмого умножителей 39, 30 и через второй квадратор 34 на вход восьмого умножителя 33. Значение Q (F (Z )), .(z) , полученное на выходе последнего, поступает на блок 43 деления и вход шестого умножителя 28.. Значение F4z ° )F(Z ° ) , полученное на выходе седьмого умножителя 30, поступает на сумматор 36, через второй квадратор 34 на вход второго вычитателя 31 и при открытом седьмом коммутаторе 41 - на вход блока 43 деления, на выходе которого в этом случае формируется значение оптимального шага А, 1/Р (Z ). Значение 2-F(z ° ) (FJ ())2 F() с выхода шестого умножителя 28 поступает на второй вычитатель 31, на выходе которого формируется () V F (Z ° ))2 - 2F ().(F ():

F(Z ) , которое через блок 35 извлечения квадратного корня поступает на сумматор 36. Значение F () Fm.( ) +

С. , 35 |(F; () Г ()) -2F () (F, (°0 ) F ()

соответственно, первый накапливающий сумматор 22 накапливает сумму

с выхода последнего при открытом девя- : том коммутаторе 47 поступает на вход блока 43 деления, на выходе которого при- этом формируется значение оптимального шага т для т-го ограничения о Значе- . ние с выхода блока 43 деления поступает на первый вход пятой схемы 44 сравнения, на второй вход которой .с выхода третьего регистра 38 поступает максимально допустимое значение оптимального шага, полученное к данному моменту. При выполнении условия . пятая схема 44 сравнения вырабатывает разрешающий сигнал на шестой коммутатор 37 и значение Л поступает с выхода блока 43 деления на третий регистр 38. Таким образом на последнем формируется значение оптимального шага А минА. После

Т„

FJZ )

i-T«,,

сумматор 21 - F (Z

iVi

Ы,-7

CO)

)fe

; e

()

C. o,.

, a третий сумматор 20 bi-- . di.

Ci e - 1. После

.-

;-T -1-1

- m-,

того, как первая схема 10 сравнения выработает разрешающий сигнал для первого, второго и четвертого комму татора 25, 24 и 23, значения с третьего, второго и первого накапливающих сумматоров 20, 21 и 22 поступают на шестой, седьмой и восьмой умножители 28, 30 и 33 соответствен- но. Затем накапливающие сумматоры устанавливаются в начальные состояния при появлении сигналов на их

fO

87

- з

2015

25

О

1804

входах сброса с выхода первого элемента 18 задержки. Значение с выхода второго счетчика 11 адреса поступает на адресный вход третьего блока 5 памяти и четвертую схему 12 сравнения, при срабатывании которой открываются пятый и седьмой коммутаторы 27 и 41. Значение F (Z ° ) поступает на вход второго регистра 29, с выхода которого оно поступает на вход пятого, седьмого умножителей 39, 30 и через второй квадратор 34 на вход восьмого умножителя 33. Значение Q (F (Z )), .(z) , полученное на выходе последнего, поступает на блок 43 деления и вход шестого умножителя 28.. Значение F4z ° )F(Z ° ) , полученное на выходе седьмого умножителя 30, поступает на сумматор 36, через второй квадратор 34 на вход второго вычитателя 31 и при открытом седьмом коммутаторе 41 - на вход блока 43 деления, на выходе которого в этом случае формируется значение оптимального шага А, 1/Р (Z ). Значение 2-F(z ° ) (FJ ())2 F() с выхода шестого умножителя 28 поступает на второй вычитатель 31, на выходе которого формируется () V F (Z ° ))2 - 2F ().(F ():

F(Z ) , которое через блок 35 извлечения квадратного корня поступает на сумматор 36. Значение F () Fm.( ) +

40

45

50

с выхода последнего при открытом девя- : том коммутаторе 47 поступает на вход блока 43 деления, на выходе которого при- этом формируется значение оптимального шага т для т-го ограничения о Значе- . ние с выхода блока 43 деления поступает на первый вход пятой схемы 44 сравнения, на второй вход которой .с выхода третьего регистра 38 поступает максимально допустимое значение оптимального шага, полученное к данному моменту. При выполнении условия . пятая схема 44 сравнения вырабатывает разрешающий сигнал на шестой коммутатор 37 и значение Л поступает с выхода блока 43 деления на третий регистр 38. Таким образом на последнем формируется значение оптимального шага А минА. После

- irniM

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

чики адреса 8 и 11, выставляется через второй элемент 26 задержки максимально допустимое значение шага на третьем регистре 38 и открывается восьмой коммутатор 45, при этом значение оптимального шага А с выхода третьег о регистра 38 поступает на второй вход второй схемы 46 сравнения и первый вход пятого умножителя 39, на выходе которого формируется значение Л ) , поступающее на вход первого вычитателя 40, на второй вход которого поступает значение Z с первого регистра 13.-На выходе первого вычитателя 40 формируется новая итерационная точка 2(1) (), которая посJO

тупает на вход первого регистра 13, на первый вход второй схемы 46 сравнения поступает значение А . При выполнении условия Д вторая схема 46 сравнения вырабатывает разрешающий сигнал на третий коммутатор 49 и значение экстремума Z ° с пер12871 80 6

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

вого регистра 13 поступает через тре- образователя, выходы элементов ИЛИ

тий коммутатор 49 и обратный логарифмический преобразователь 48 на выход устройства.

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

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

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

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

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

0

11

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

ходу.седьмого коммутатора, а выход - к входам делимого блока деления, выход которого подключен к первому входу пятой схемы сравнения и к информационному входу шестого коммутатора, управляющий вход которого подключен к выходу Меньше пятой схемы сравнения, а выход - к информационным входам третьего регистра, управляющий вход которого подключен к выходу второго элемента задержки, а выход - к второму входу пятой схемы сравнения и к информационному вход:у восьмого коммутатора, выход которого подключен к второму входу второй схемы сравнения и к первому входу пятого умножителя, выход первого счетчика адреса подключен к второму входу третьей схемы сравнения, выход Равно которой подключен к входу сброса первого и второго счетчиков адреса, управляющему входу восьмого кoм ryтa- тора и входу второго элемента задержки, выход первого элемента задержки подключен к входам сброса первого, второго и третьего накапливающих сумматоров , информационный вход последнего подключен к выходу первого умножителя, а выход - к информационном свходу четвертого коммутатора, выход которого подключен к первому входу шестого умножителя, выход второго коммутатора подключен к информационному входу пятого коммутатора, к первому входу седьмого умножителя, выхо которого подключен к второму входу сумматора, инфо14мационному входу седьмого коммутатора и входу квадратора, выход которого подключен к входу уменьшаемого второго вычита- теля.

Ф Выход

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

Редактор С. Лиснна

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

Техред А.Кравчук Корректор А. Обручар

Заказ 7719/53

Тираж 694

ВНИИПИ Государственного комитета СССР

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

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

Подписное