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

 

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

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

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

РЕСПУБЛИК . (5D 4 G 06 F 15/36

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

Н A ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3875074/24-24 (22) 25.03,85 (46), 30.01.87. Бюл. ¹ 4 (72) С.М.Брейтман, Ю,Л.Литвин. и Ж.К.Иартинкевич . (53) 681.333(088.8) (56) Авторское свидетельство СССР № 1205156, кл. G 06 F 15/36, 17.01.85. (54) УСТРОЙСТВО ДЛЯ НАХОЖДЕНИЯ ЭКСТРЕМУМОВ (57) Изобретение относится к области вычислительной техники и может быть использовано при разработке специализированной аппаратуры и различных автоматизированных систем управления.

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

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

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

12871

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

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

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

5 памяти, логарифмический преобразователь 6, первую группу элементов

ИЛИ 7, первый счетчик 8 адреса, третью схему 9 сравнения, первую схему

10 сравнения, второй счетчик 11 адреса четвертую схему 12 сравнения, первый регистр 13., экспоненциальный 25

° йреобраэаватель 14, второй умножитель

15, первый умножитель 16, четвертый умножитель 17, первый элемент 18 задержки, третий умножитель 19, третий накапливающий сумматор 20, второй накапливающий сумматор 21, первый накапливающий сумматор 22, четвертый коммутатор 23, второй коммутатор 24, первый коммутатор 25, второй элемент

26 задержки, пятый коммутатор 27, шестой умножитель 28, второй регистр

29, седьмой умножитель 30, второй вычитатель 31, первый квадратор 32, восьмой умножитель 33, второй квадратор 34, блок 35 извлечения корня, сумматор 36, шестой коммутатор 37, третий регистр 38, пятый умножитель

39, первый вычитатель 40, седьмой коммутатор 41, вторую группу элементов ИЛИ 42, блок 43 деления, пятую .схему 44 сравнения, восьмой коммутатор 45, вторую схему 46 сравнения, девятый коммутатор 47, обратный логарифмический преобразователь 48, третий коммутатор 49, Устройство реализует метод наискорейшего спуска с оптимальным выбором

F(2 1F (2 )+

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

Задача оптимизации задается в следующе;< виде: найти arg мин F,.(Х) т, У С„Х, при ограничении т (4 .

F (Х)= „«» С Х -1 О, ш 2 М, 1 =Т,„,4 1 (1) где С. > 0 — значения весовых коэф1 фициентов;

e R — значения коэффициентов

14 показателя степени;

Х вЂ” аргумент функций;

Т вЂ” значения верхних границ суммирования;

М вЂ” число ограничений;

Т„- объем выборки.

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

arg мин F, (Z) = .С. С„: е, при orpaz

1=! ничении т

ы;л (2)= C е -1 с О, ш=2 И (2)

i=-Т +I

Ьъ-

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

Т, (a)

F (Z ) = Cd-; е

i=1

На втором этапе текущей итерации находится оптимальная величина шага вдоль направления антиградиента, для чего производится квадратичная аппроксимация функции F и левых частей ограйичений F (Z): мин )1„„, j c Я4 где 1 — допустимая величина шага для m-ro ограничения (m == 2, И) или для целевой функции (ш=i), которая определяется:

Р 1 F, (Z );, m=1,М;

1 1=T .1

1ш=1, М.

А„= где (= (F (Z ) т (Z )=2

) т, р" (z. ) .. 1

С.d,. е

3ъъ (о1 и (O) R I3;Z

F (Z )=,i Сd е

+1

1=T1

1287180 Т

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

;=т +»

Pn- ) С. dc

z (oo)

»е а третий сумматор 20

45 (о) Й,-Е

Г (Z ) = С;: е — 1. После

; =.т + »

tTI- f того, ка к первая схема 1 О сравнения выработает разрешающий сигнал для первого, второго и че т ве р т о г О коммутат ор а 2 5, 2 4 и 2 3, значения с третьего, второго и первого н ак апливающих сумматоров 2 0, 2 1 и 2 2 поступают на шестой, седьмой и восьмой умн ожи тели 2 8, 3 О и 3 3 с о от в е тс т в енн о, Затем накапливающие сумматоры устанавливаются в начальные состояния пр и появлении сигналов на их

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

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

С выходов значений весового коэффициента, коэффициента показателя степени и верхних границ суммирования блока 1 соответственно в первый, второй и третий блоки памяти заносятся значения С., Ы, Т . Сигнал с

»9 19 4Ъ генератора 2 поступает через первый ,счетчик 8 на первый и второй блоки

3 и 4 памяти, первую и третью схемы

1О и 9 сравнения, на первый входы которых поступают значения верхних границ суммирования Т с выхода тре- 20 тьего блока 5 памяти и Т с выхода объема выборки блока 1 соответственно. C выхода аргумента функции блока 1 через логарифмический преобразователь 6 и первый регистр заносит- 25 ся начальная точка Z 1, полученная путем логарифмического преобразования,. на выходе второго умножителя 15 (o) формируется показатель Ы; Z . Зкспоненциальный преобразователь 14 вычис-30 ляет функцию е . . И результате операции умножения на выходах перво-. го, четвертого и третьего умножителей 16, 17 и l9 получаются выражения

d. z со) .zсо) . р» z о) соответственйо, первый накапливающий сумматор 22 накапливает сумму (о

Т а ;z. (о

Р (Е )= С ol е, второй

i=T +1 40 входах сброса с выхода перного элемента 18 задержки. Значение с выхода второго счетчика 11 адреса поступает на адресный вход третьего блока 5 памяти и четвертую схему 12 сравнения, при срабатывании которой открываются пятый и седьмой коммутаторы

27 и 41. Значение F (Z ) поступает на вход второго регистра 29, с выхода которого оно поступает на вход пятого, седьмого умножителей 39, 30 и через второй квадратор 34 на вход восьмого умножителя 33. Значение (F, (Z + )) Р .(Е ), полученное на выходе последнего, поступает на блок 43 деления и вход шестого умножителя 28.. Значение F (Z )F (Z " ), полученное на выходе седьмого умножителя 30, поступает на сумматор 36, через второй квадратор 34 на вход второго вычитателя 31 и при открытом седьмом коммутаторе 41 — на вход блока 43 деления, на выходе которого в этом случае формируется значение оптимального шага Ь, = 1/F" (Z ) °

Значение 2 Р (Z ) . (F (Z )) F (2 ) с выхода шестого умножителя 28 поступает на второй вычитатель 31, на выходе которого формируется (Г (Z )» .» F (Z ))г 2F (Zo ) (F (Z(o!)) ., ц (Ol

» F (Z ),которое через блок 35 извлечения квадратного корня поступает на сумматор 36. Значение F (Z ) Fm(W + (Z"î)) (» (Z"î)) ) F (Z(î)) с выхода последнего при открытом девятом коммутаторе 47 поступает на вход блока 43 деления, на выходе которого приэтом формируется значение оптимального шага >m для m-ro ограничения. Значение с выхода блока 43 деления поступает на первый вход пятой схемы 44 сравнения, на второй вход которой,с выхода третьего регистра 38 поступает максимально допустимое значение 3 оптимального шага, полученное к данному моменту. При выполнении условия

< пятая схема 44 сравнения вырабатывает разрешающий сигнал на шестой коммутатор 37 и значение А, поступает с выхода блока 43 деления на третий регистр 38. Таким образом на последнем формируется значение оптимального шага = мин 1 . После »„».м того, как .третья схема 9 сравнения вырабатывает разрешающий сигнал, сбрасываются первый и второй счет12871 80 чики адреса 8 и 11, выста.вляется через второй элемент 26 задержки максимально допустимое значение шага на третьем регистре 38 и открывает я восьмой коммутатор 45, при этом значение оптимального шага 1 с выхода третьего регистра 38 поступает на второй вход второй схемы 46 сравнения и первый вход пятого умножителя

39, на выходе которого формируется 10 значение P - Г„(Z<о)), поступающее на вход первого вычитателя 40, на второй вход которого поступает значение Е с первого регистра 13. На (о) выходе первого вычитателя 40 формируется новая итерационная точка

Z = Z — Ь Г„ (Z ), которая поступает на вход первого регистра 13, на первый вход второй схемы 46 сравнения поступает значение A . При 20 выполнении условия аЕ вторая схема 46 сравнения вырабатывает разрешающий сигнал на третий коммутатор

49 и значение экстремума Z с пер(o) вого регистра 13 поступает через тре- 25 тий коммутатор 49 и обратный логарифмический преобразователь 48 на выход устройства.

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

Устройство для нахождения экстремумов, содержащее блок задания параметров функции, генератор тактовых импульсов, первый счетчик адреса, 35 первый и второй блоки памяти, первую и вторую схемы сравнения, первый вычитатель, первый регистр, логарифмический преобразователь, первую группу элементов ИЛИ, три коммутатора, 40 пять умножителей, два накапливающих сумматора, квадратор, эксноненциальный преобразователь, обратный логарифмический преобразователь, причем вход запуска генератора тактовых 45 импульсов является входом запуска устройства, выходы значений весового коэффициента, коэффициента показателя степени, объема выборки, точности вычислений и аргумента функции 50 блока задания параметров функции подключены к информационным входам первого и второго блоков памяти, к первому входу второй схемы сравнения и к входу логарифмического преобразователя соответственно, выход генератора тактовых импульсов подключен к счетному входу первого счетчика адре,са, выход которого подключен к адресным входам первого и второго блоков памяти и к первому входу первой схемы сравнения, выход Равнон которой подключен к управляющим входам первого и второго коммутаторов, выход первого блока памяти подключен к первому входу первого умножителя, второй вход которого подключен через экспоненциальный преобразователь к выходу второго умножителя, выход второго блока памяти подключен к первым входам второго, третьего и четвертого умножителей, вход третьего умножителя подключен к выходу четвертого умножителя, выход третьего умножителя через первый накапливающий сумматор подключен к информационному входу первого коммутатора, выход пятогс умножителя подключен к входу вычитаемого первого вычитателя, выход которого подключен к первым входам элементов ИЛИ первой группы, вторые входы которых подключены к выходам логарифмического преобразователя, выходы элементов ИЛИ первой группы подключены к информационным входам первого регистра, выход которого подключен к второму входу второго умножителя, к информационному входу третьего коммутатора и к входу уменьшаемого первого вычитателя, выход первого умножителя подключен к второму входу четвертого умножителя, выход четвертого умножителя подключен через второй накапливающий сумматор к информационному входу второго коммутатора, выход второй схемы сравнения подключен к управляющему входу третьего коммутатора, выход которого подключен к входу обратного логарифмического преобразователя, выход которого является выходом устройства, о т л и ч а ющ е е с я тем, что, с целью расширения области применения устройства путем обеспечения возможности нахождения экстремума функций с ограничениями на значения аргумента, в него введены второй счетчик адреса, третий блок памяти, третья, четвертая и пятая схемы сравнения, шестой, седьмой и восьмой умножителя, второй и третий регистры, вторая группа элементов ИЛИ, второй квадратор, сумматор, третий накапливающий сумматор, четвертый, пятый, шестой, седьмой, восьмой и девятый коммутаторы, второй вычитатель, два элемента задержки, блок извлечения квадратного кор1287180 ня, блок деления, причем выходы значений объема выборки и дополнительный выход значений верхних границ суммирования блока задания параметров подключены к первому входу третьей схемы, сравнения и к информационному входу третьего блока памяти соответственно, выход которого подключен к второму входу первой схемы сравнения, выход которой подключен 10 к входу первого элемента задержки, управляющему входу четвертого коммутатора и счетному входу второго счетчика адреса, выход которого подключен к адресному входу третьего блока памяти и к входу четвертой схемы срав!! I! нения, выход Равно которой подключен к управляющему входу девятого коммутатора и управляющим входам седьмого и пятого коммутаторов, 20 выход последнего подключен к информационному входу второго регистра, выход которого подключен к вторым входам пятого и седьмого умножителей и к входу второго квадратора, выход которого подключен к первому входу восьмого умножителя, второй вход которого подключен к.выходу первого коммутатора, а выход — к входу делителя блока деления и второму входу З0 шестого умножителя, выход которого подключен к входу вычитаемого второго вычитатетя, выход которого подключен к входу блока извлечения квадРатного корня, выход котоРОго под- 35 ключен к первому входу сумматора, выход которого подключен к информационному входу девятого коммутатора, выход которого подключен к второму входу элементов ИЛИ второй группы, 40 первый вход которых подключен к выходу седьмого коммутатора, а выход— к входам делимого блока деления, выход которого подключен к первому входу пятой схемы сравнения и к информационному входу шестого коммутатора, управляющий вход которого подключен к выходу Меньше пятой схемы сравнения, а выход — к информационным входам третьего регистра, управляющий вход которого подключен к выходу второго элемента задержки, а выход — к второму входу пятой схемы

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

1287180

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

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

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

Подписное

Тираж 694

Заказ 7719/53

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

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

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