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

 

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

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

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

РЕСПУБЛИК (51)5 G 06 F 15/31

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4908089/24 (22) 29,12.90 (46) 30,09.92. Бюл. ¹ 36 (72) Н,Н.Зубов, B.Н,Зимин и Ю.Г.Шарашкин (56) Авторское свидетел ьство СССР

¹ 1287180, кл, G 06 F 15/36, 1985, Авторское свидетельство СССР № 1322318, кл. G 06 F 15/36, 1986.

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

¹ 922761, кл. G 06 F 15/31, 1980, (54) УСТРОЙСТВО ДЛЯ НАХОЖДЕНИЯ

ЭКСТРЕМУМА АДДИТИВНОЙ ФУНКЦИИ

МНОГИХ ПЕРЕМЕННЫХ (57) Изобретение относится к области вычислительной техники и может быть использовано при разработке специализированной аппаратуры для нахождения экстремума аддитивных функций.

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

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

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

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

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

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

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

F(X) = F(X1, Хг, ..., Хп) =, !, f(X;) min (1)

i =1. при и

xi N, (2)

i = 1

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

Предлагаемое устройство реализует рекуррентную процедуру минимизации с использованием метода проекции градиента (4). В основе метода проекции градиента лежит релаксационный процесс построения последовательных векторов оешения Х("), где m — номер шага m = 1, М, таких, что каждый последующий вектор принадлежит области ограничений (2) и каждое последующее значение целевой функции не превышает предыдущего.

Очередной шаг оптимизации включает;

1. Нахождение направления движения из точки Х((п) к минимуму целевой функции, то есть вычисление значения градиента функции в данной точке

VF F(X ) = gradF(X())

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

ar (хР") + Ь ;) - (х(") )

В качестве начального приближения решения на так называемом "нулевом" шаге

55 можно принять любые значения пер(,менных(в том числе и нулевые, то есть х i = О, i 1,п), удовлетворяющие ограничениям (2), 2. Нахождение последующего вектора решения Х без учета ограничений (шаг в

-М направлении антиградиента) = «(— p — I =„(m) (4) ( где,Р— коэффициент, определяющий длину шага в выбранном направлении.

3. Учет ограничений на переменные путем проектирования вектора X(m+1) на область ограничений по формуле

„„y {т+ 1) (m+1) ((и+1). + i = 1 (5) х i=x (+ где N — ограничение на сумму аргументов.

Прсцесс решения прекращается после заданного количества шагов М, Таким образом, предлагаемое устройство позволяет оптимизировать распределение однородных ресурсов, суммарное количество которых ограничено, а эффект от их использования описывается гладкой унимодальной функцией (1), Поставленная цель достигается тем, что в известное устройство, содержащее три группы ключей, ключ, линию задержки, вход которой соединен с выходом ключа, генератор импульсов, выход которого подключен к информационному входу ключа, три регистра, группу блоков вычисления значения функции, группу блоков умножения, накапливающий сумматор, блок задания коэффициентов, кольцевой счетчик, введены триггер, вход установки в единичное состояние которого подключен к входу сброса кольцевого счетчика, к управляющим входам первой группы ключей и является входом внешнего запуска устройства, вход сброса которого подключен к выходу кольцевого счетчика, счетный вход которого соединен с четвертым выходом линии задержки, выход триггера соединен суправляющим входом ключа, четвертая группа ключей, управляющие входы которых подключены к третьему выходу линии задержки, выходы которых соединены с соответствующими выходами первой группы ключей и входами первого регистра, информационные входы первой группы ключей являются входами начальных значений вектора решения устройства, выходы первого регистра являются выходами оптимальных значений вектора решения устройства, подключены к соответствующим входам первой группы блоков вычисления значения функции и к информационным входам второй группы ключей, управляю1765830 щие входы которых подключены к первому выходу линии задержки, а выходы соединены с соответствующими входами второго регистра, первая группа сумматоров, входы первого слагаемого которых подключены к выходам второго регистра, блок задания приращения аргументов, выход которого подключен к входам второго слагаемого сумматоров первой группы, вторая группа блоков вычисления значения функции, входы которых подключены к соответствующим выходам первой группы сумматоров, первая группа сумматоров-вычитателей, входы вычитаемого которых соединены с соответствующими выходами первой группы блоков вычисления значения функции, входы уменьшаемого подключены к выходам второй группы блоков вычисления значения функции, а выходы соединены с соответствующими входами вторых сомножителей группы блоков умножения, входы первых сомножителей которых подключены к выходу блока задания коэффициентов, вторая группа сумматоров-вычитателей, входы вычитаемого которых подключены к выходам группы блоков умножения, входы уменьшаемого которых соединены с соответствующими выходами второго регистра, а выходы подключены к информационным входам третьей группы ключей, управляющие входы которых соединены со вторым выходом линии задержки, а выходы подключены к соответствующим входам третьего регистра, выходы которого соединены с входами накапливающего сумматора, сумматор-вычитатель, вход вычитаемого которого соединен с выходом накапливающего сумматора, блок задания ограничения, выход которого подключен к входу уменьшаемого сумматора-вычитателя, блок деления, вход делимого которого соединен с выходом сумматоравычитателя, блок задания количества аргументов, выход которого подключен к входу делителя блока деления, вторая группа сумматоров, входы первых слагаемых которых соединены с соответствующими выходами третьего регистра, входы вторых слагаемых подключены к выходу блока деления, а выходы соединены с соответствующими информационными входами четвертой группы ключей.

Сопоставительный анализ с прототипом показывает, что заявляемое устройство отличается наличием новых блоков; триггер, группа ключей, две группы сумматоров, две группы блоков вычисления значения функции, группа сумматоров-вычитателей, сумматор-вычитатель, блок задания приращения аргументов, блок задания ограничения, блок деления, блок задания ко5

15 личества аргументов и их связи с остальными элементами схемы.

Таким образом, заявляемое устройство соответствует критерию изобретения "новизна".

Сравнение заявляемого решения с другими техническими решениями показывает, что данные блоки известны (1,2,3).

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

20 На чертеже представлена блок-схема устройства. Устройство содержит триггер 1, ключи

2, линию задержки 3, генератор импульсов

4, регистры 5, блок 6 задания приращения

25 аргументов, группы блоков 7 вычисления значения функции, группу блоков умножения 8, накапливающий сумматор 9, группы сумматоров 10, вычитатели 11, блок 12 задания коэффициентов, кольцевой счетчик 13, 30 блок 14 задания ограничения, блок 15 задания количества аргументов, блок деления

16.

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

Устройство работает следующим образом, Работа устройства начинается по сигна40 лу "Пуск". Данный сигнал взводит триггер 1, который разрешает прохождение сигналов генератора импульсов 4 через ключ 2 на вход линии задержки 3, приводит в исходное состояние (сбрасывает) кольцевой счет45 чик 13, а также обеспечивает занесение в первый регистр 5 начальных значений вектора аргументов (х )j, i = 1,rj) через первую группу ключей 2.

Триггер 1, ключ 2, линия задержки 3, 50 генератор импульсов 4, кольцевой счетчик

13 М итераций представляют собой устройство управления, которое обеспечивает осуществление M шагов итерационного

55 процесса оптимизации решения.

Каждый шаг итерационного процесса осуществляется следующим образом.

Исходные значения вектора аргументов (m), x j, i = 1,п с первого регистра 5 поступают на входы первой группы блоков вычисления значения функции 7, вычисленные значения

1765830 функции f(x()), i = 1,п, поступают на входы вычитаемого первой группы вычитателей

11.

Сигналом С1 с первого выхода линии задержки 3, поступающим на управляющие входы второй группы ключей 2, значения вектора аргументов х(m, i = 1,п с первого регистра 5 переписываются на второй регистр 5. С выходов второго регистра 5 значения x(m поступают на входы первого слагаемого первой группы сумматоров 10, на входы второго слагаемого которых поступают единичные приращения с выхода блока задания приращения аргументов 6, С выходов первой группы сумматоров 10 значения аргументов, получивших приращение х ) +1, Лxi = 1, i = 1,п поступают на входы второй группы блоков вычисления значений функции 7, с выходов которых значения

f(x(") +1) поступают на входы уменьшаемого первой группы вычитателей 11. С выходов первой группы вычитателей 11 приращения функции

1 в качестве значений вектора градиента функции

„(m) I подаются на входы вторых сомножителей группы блоков умножения 8, где перем ножа ются на величину шага j3, поступающего с блока задания коэффициента 12, и поступают на входы вычитаемого второй группы вычитателей 11. На входы уменьшаемого второй группы вычитателей

11 поступают значения вектора аргументов

x(m), i = 1,п с выходов второго регистра 5. К моменту поступления сигнала С2 со второго выхода линии задержки 3 на информационных выходах третьей группы ключей 2 присутствуют после„дующие значения вектора аргументов х +" ь i = 1,п без учета ограничений. По сигналу С2, поступающему íà управляющие входы третьей группы ключей 2, "(в+1) значения х переписываются в третий регистр 5.

С выхода третьего регистра 5 значения

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

i=1 вход вычитаемого сумматора-вычитателя

11, на вход уменьшаемого которого поступает сигнал с блока 14 задания ограничения N, С выхода вычитателя 11 и величина N — х поступает на вход (п1+1), 1 делимого блока деления 16, на вход делителя которого поступает сигнал с блока 15 задания количества аргументов и. ;(mm+ ) (=1

Величина с выхода блои ка деления 16 подается на входы второго слагаемого второй группы сумматоров 10, 10 на входы первого слагаемого которых поступают значения вектора аргументов (m+1) х, i = 1,п, К моменту поступления сигнала СЗ с третьего выхода линии задержки 3 на информационных входах четвертой группы ключей 2 присутствуют значения вектора аргументов на очередном шаге

y „-(m+ 1) (m+1) (m+1) i = 1 х i=x + и

20 По сигналу СЗ, поступающему на управляющие входы четвертой группы ключей 2, вычисленные значения вектора аргументов заносятся в первый регистр 5.

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

30 При осуществлении М шагов сигналом с кольцевого счетчика 13 триггер 1 сбрасывается и решение заканчивается. С этого момента времени первый регистр 5 содержит оптимальное значение вектора аргументов, то есть решение задачи.

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

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

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

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

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

20 подключены к соответствующим входам третьего регистра, выходы которого соединены с входами накапливающего сумматора, вход вычитаемого вычитателя соединен с выходом накапливающего сумматора, вы25 ход блока задания ограничения подключен к входу уменьшаемого вычитателя, вход делимого блока деления соединен с выходом вычитателя, выход блока задания количества аргументов подключен к входу делителя

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

35 с информационными входами соответствующих ключей четвертой группы.

1765830

Составитель Н,Зубов

Техред M.Ìîðãåíòàë Корректор И улла

Редактор Т,Орловская

Заказ 3386 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101