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

(51)5 6 06 Р 15/31 ПИСАНИЕ ИЗОБРЕТЕН К АВТОРСКОМУ С ЕТЕЛЬСТВУМа ЪГ ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМРИ ГКНТ СССР(56) Авторское свидетел ьство СССРМ 1287180, кл, 6 06 Р 15/36, 1985,Авторское свидетельство СССРК. 1322318, кл. 6 06 Р 15/36, 1986,Авторское свидетельство СССРМ 922761, кл. 0 06 Р 15/31, 1980,(54) УСТРОЙСТВО ДЛЯ НАХОЖДЕНИЯЭКСТРЕМУМА АДДИТИВНОЙ ФУНКЦИИМНОГИХ ПЕРЕМЕННЫХ(57) Изобретение относится к области вычислительной техники и может быть использовано и ри разработкеспециализированной аппаратуры для нахождения экстремума аддитивных функций,Изобретение относится к вычислитель нои технике и может быть использовано для нахождения экстремума (минимума) аддитивной функции многих переменных.Известно устройство для нахождения экстремумов, содержащее блок задания параметров функции, генератор тактовых импульсов, два счетчика адреса, три блока памяти, пять схем сравнения, восемь умножителей, три регистра, две группы элементов ИЛИ, два квадратора, сумматор, три накапливающих сумматора, девять коммутаторов, два элемента задержки, два вычитателя, блок деления, блок извлечения квадратного корня 1, Устройство предназначено для нахождения экстремумов функций и реализует метод оптимизации второго порядка, что влечет за собой ос овной недоЦель изобретения - расширение функциональных возможностей за счет учета ограничений на сумму аргументов целевой функции. Сущность изобретения состоит в том, что в устройстве содержится три группы ключей, ключ, линия задержки, три регистра, первая группа блоков вычисления значения функции, группа блоков умножения, накапливающий сумматор, блок задания коэффициентов, кольцевой счетчик. Новым в изобретении является введение триггера, четвертой группы ключей, двух групп сумматоров, второй группы блоков вычисления значения функции, двух групп вычитателей, вычитателя, блока задания приращения аргументов, блока задания ограничения, блока деления, блока задания количества аргументов с соответствующими связЯми 1 ил статок - необходимость вычисления на каждом шаге итерационного процесса решения а не только значения целевой функции, но и ее производных первого и второго порядка. О,Кроме того, известно устройство для на- (Л хождения экстремумов, содержащее блок задания параметров функции, генератор тактовых импульсов, шесть элементов сравнения; три блока памяти, логарифмический преобразователь, два счетчика адреса, группу элементов ИЛИ, семь умножителей, четыре регистра, одиннадцать блоков эле ментов И, два экспоненциальных преобразователя, пять накапливающих сумматоров, три элемента задержки, три вычитателя, пять блоков деления, блок вычисления обратной величины, два блока возведения в степень, обратный логарифмический преобразователь 2), Устройство предназначено для нахождения экстремумов функций при произвольных начальных точках; недостатком его является то, что в нем решается задача геометрического программирования, но безучета ограничений на аргументы.Известно устройство для оптимизации функций многих переменных - прототип, содержащее группу блоков формирования линейно-независимых функций, регистры, три группы ключей, четыре ключа, генератор импульсов, блок управления, блок задания коэффициентов, линию задержки, кольцевой счетчик, две группы блоков умножения, блок умножения, два сумматора, накапливающий сумматор и два счетчика 3),Устройство позволяет отыскивать минимум функции многих переменных в случае, когда на вход устройства поступают единичные реализации нестационарных случайных процессов.Недостатком данного устройства является то, что оно не обеспечивает решение экстремальной задачи выпуклого программирования с ограничениямии Г(Х) = Г(х 1, х 2., хп) =, 1(х) - эфп)и (1) при их М, (2)= 1 Целью изобретения является расширение функциональных возможностей устройства за счет учета ограничений на сумму аргументов целевой функции.Предлагаемое устройство реализует рекуррентную процедуру минимизации с использованием метода проекции градиента (4). В основе метода проекции градиента лежит релаксационный процесс построения последовательных векторов )ешения Х", где в - номер шага в = 1, М, таких, что каждый последующий вектор принадлежит области ограничений (2) и каждое последующее значение целевой функции не превышает предыдущего. Очередной шаг оптимизации включает; 1, Нахождение направления движения из точки Х к минимуму целевой функции, то есть вычисление значения градиента функции в данной точке7 Р Р(Х) = дгабЕ(Х(Нахождение частных производных целевой функции предлагается методом разделенных разностейИ(хРд) + Ь ;) - (х(д) )В качестве начального приближения решения на так называемом "нулевом" шаге 10 15 20 25 30 35 40 45 50 55 можно принять любые значения пеменныхв том числе и нулевые, то есть х= О, 1= 1,п), удовлетворяющие ограничениям (2),2. Нах)жжение последующего вектора решения Х без учета ограничений (шаг в-("-4направлении антиградиента)х ю = хи - ф-ц т(4)где Я - коэффициент, определяющий длину шага в выбранном направлении.3, Учет ограничений на переменные путем проектирования вектора Х ) на область ограничений по формуле(5)х =х;+где М - ограничение на сумму аргументовПрсцесс решения прекращается после заданного количества шагов М,Таким образом, предлагаемое устройство позволяет оптимизировать распределение однородных ресурсов, суммарное количество которых ограничено, а эффект от их использования описывается гладкой унимодальной функцией(1),Поставленная цель достигается тем, что в известное устройство, содержащее три группы ключей, ключ, линию задержки, вход которой соединен с выходом ключа, генератор импульсов, выход которого подключен к информационному входу ключа, три регистра, группу блоков вычисления значения функции, группу блоков умножения, накапливающий сумматор, блок задания коэффициентов, кольцевой счетчик, введены триггер, вход установки в единичное состояние которого подключен к входу сброса кольцевого счетчика, к управляющим входам первой группы ключей и является входом внешнего запуска устройства, вход сброса которого подключен к выходу кольцевого счетчика, счетный вход которого соединен с четвертым выходом линии задержки, выход триггера соединен суправляющим входом ключа, четвертая группа ключей, управляющие входы которых подключены к третьему выходу линии задержки, выходы которых соединены с соответствующими выходами первой группы ключей и входами первого регистра, информационные входы первой группы ключей являются входами начальных значений вектора решения устройства, выходы первого регистра являются выходами оптимальных значений вектора решения устройства, подключены к соответствующим входам первой группы блоков вычисления значения функции и к информационным входам второй группы ключей, управляю5 10 15 20 25 30 35 40 45 50 55,щие входы которых подключены к первому выходу линии задержки, а выходы соединены ссоответствующими входами второго регистра, первая группа сумматоров, входы первого слагаемого которых подключены к выходам второго регистра, блок задания приращения аргументов, выход которого подключен к входам второго слагаемого сумматоров первой группы, вторая группа блоков вычисления значения функции, входы которых подключены к соответствующим выходам первой группы сумматоров, первая группа сумматоров-вычитателей, входы вычитаемого которых соединены с соответствующими выходами первой группы блоков вычисления значения функции, входы уменьшаемого подключены к выходам второй группы блоков вычисления значения функции, а выходы соединены с соответствующими входами вторых сомножителей группы блоков умножения, входы первых сомножителей которых подключены к выходу блока задания коэффициентов, вторая группа сумматоров-вычитателей, входы вычитаемого которых подключены к выходам группы блоков умножения, входы уменьшаемого которых соединены с соответствующими выходами второго регистра, а выходы подключены к информационным входам третьей группы ключей, управляющие входы которых соединены со вторым выходом линии задержки, а выходы подключены к соответствующим входам третьего регистра, выходы которого соединены с входами накапливающего сумматора, сумматор-вычитатель, вход вычитаемого которого соединен с выходом накапливающего сумматора, блок задания ограничения, выход которого подключен к входу уменьшаемого сумматора-вычитателя, блок деления, вход делимого которого соединен с выходом сумматоравычитателя, блок задания количества аргументов, выход которого подключен к входу делителя блока деления, вторая группа сумматоров, входы первых слагаемых которых соединены с соответствующими выходами третьего регистра, входы вторых слагаемых подключены к выходу блока деления, а выходы соединены с соответствующими информационными входами четвертой группы ключей.Сопоставительный анализ с прототипом показывает, что заявляемое устройство отличается наличием новых блоков; триггер, группа ключей, две группы сумматоров, две группы блоков вычисления значения функции, группа сумматоров-вычитателей, сумматор-вычитатель, блок задания приращения аргументов, блок задания ограничения, блок деления, блок задания количества аргументов и их связи с остальными элементами схемы.Таким образом, заявляемое устройство соответствует критерию изобретения "новизна".Сравнение заявляемого решения с другими техническими решениями показывает, что данные блоки известны 1,2,3.Однако при их введении в указанной связи с остальными элементами схемы в заявляемое устройство для нахождения экстремума аддитивной функции многих переменных с ограничениями на сумму аргументов оно проявляет новые свойства, что обеспечивает решение экстремальной задачи выпуклого программирования с ограничениями, Это позволяет сделать вывод о соответствии технического решения критерию "существенные отличия".На чертеже представлена блок-схема устройства.Устройство содержит триггер 1, ключи 2, линию задержки 3, генератор импульсов 4, регистры 5, блок 6 задания приращения аргументов, группы блоков 7 вычисления значения функции, группу блоков умножения 8, накапливающий сумматор 9, группы сумматоров 10, вычитатели 11, блок 12 задания коэффициентов, кольцевой счетчик 13, блок 14 задания ограничения, блок 15 задания количества аргументов, блок деления 16.Конструкция и редлагаемого устройства основана на использовании известных элементов и технических трудностей для реализации не представляет,Устройство работает следующим образом,Работа устройства начинается по сигналу "Пуск". Данный сигнал взводит триггер 1,который разрешает прохождение сигналов генератора импульсов 4 через ключ 2 на вход линии задержки 3, приводит в исходное состояние (сбрасывает) кольцевой счетчик 13, а также обеспечивает занесение в первый регистр 5 начальных значений вектора аргументов (х)ь= 1,п) через первую группу ключей 2.Триггер 1, ключ 2, линия задержки 3, генератор импульсов 4, кольцевой счетчик 13 М итераций представляют собой устройство управления, которое обеспечивает осуществление М шагов итерационного процесса оптимизации решения.Каждый шаг итерационного процесса осуществляется следующим образом. Исходные значения вектора аргументов х ь= 1,п с первого регистра 5 поступают(п),на входы первой группы блоков вычисленияфункции т(х(", г = 1,п, поступают на входы вычитаемого первой группы вычитателей 11,Сигналом С 1 с первого выхода линии задержки 3, поступающим на управляющие входы второй группы ключей 2, значения вектора аргументов хг, г = 1,п с первого регистра 5 переписываются на второй регистр 5. С выходов второго регистра 5 значения х(гп поступают на входы первого слагаемого первой группы сумматоров 10, на входы второго слагаемого которых поступают единичные приращения с выхода блока задания приращения аргументов 6, С выходов первой группы сумматоров 10 значения аргументов, получивших приращение х);+1, Лх = 1,1= 1,п поступают на входы второй группы блоков вычисления значений функции 7, с выходов которых значения т(х(")+1) поступают на входы умен ьшаемого первой группы вычитателей 11. С выходов первой группы вычитателей 11 приращения функции1в качестве значений вектора градиентафункциих =хподаются на входы вторых сомножителей группы блоков умножения 8, где перем ножа ются на величину шага 3,поступающего с блока задания коэффициента 12, и поступают на входы вычитаемоговторой группы вычитателей 11. На входыуменьшаемого второй группы вычитателей11 поступают значения вектора аргументовх, = 1,п с выходов второго регистра 5. Кмоменту поступления сигнала С 2 со второговыхода линии задержки 3 на информационных выходах третьей группы ключей 2 присутствуют последующие значения векторааргументов х +" ь = 1,п без учета ограничений, По сигналу С 2, поступающему на управляющие входы третьей группы ключей 2,значения х гппереписываются в третийрегистр 5.С выхода третьего регистра 5 значения"ф(гп+1)вектора аргументов х гппоступают на входы накапливающего сумматора 9, с выходаи г( 1)которого величинах гп г поступает на=1вход вычитаемого сумматора-вычитателя11, на вход уменьшаемого которого поступает сигнал с блока 14 задания ограничения й, С выхода вычитателя 11ивеличина К - хпоступает на вход(гп+ 1),1 делимого блока деления 16, на вход делителя которого поступает сигнал с блока 15задания количества аргументов и.. ;с+вВеличина с выхода блоика деления 16 подается на входы второгослагаемого второй группы сумматоров 10,10 на входы первого слагаемого которых поступают значения вектора аргументов"(гп+1)х гг, г =1,п, К моменту поступления сигнала СЗ с третьего выхода линии задержки 3на информационных входах четвертой группы ключей 2 присутствуют значения векторааргументов на очередном шаге-(гп+ 1)(гп+1), " (гп+1)= 1х =х г+и20 По сигналу СЗ, поступающему на управляющие входы четвертой группы ключей 2,вычисленные значения вектора аргументовзаносятся в первый регистр 5.На этом очередной шаг приближения25 заканчивается с четвертого выхода линиизадержки добавляется единица в кольцевойсчетчик 13, генератор импульсов 4 вырабатывает следующий импульс и очередной шагповторяется.30 При осуществлении М шагов сигналомс кольцевого счетчика 13 триггер 1 сбрасывается и решение заканчивается. С этогомомента времени первый регистр 5 содержит оптимальное значение вектора аргу 35 ментов, то есть решение задачи,Таким образом, предлагаемое устройство позволяет находить экстремум аддитивной функции многих переменных сограничением на сумму аргументов,40 Формула изобретенияУстройство для нахождения экстремумааддитивной функции многих переменных,содержащее три группы ключей, ключ, линию задержки, вход которой соединен с вы 45 ходом ключа, генератор импульсов, выходкоторого подключен к информационномувходу ключа, три регистра, первую группублоков вычисления значения функции, группу блоков умножения, накапливающий сум 50 матор; блок задания коэффициентов,кольцевой счетчик, о т л и ч а ю щ е е с я тем,что, с целью расширения функциональныхвозможностей устройства путем учета ограничений на сумму аргументов целевой фун 55 кции, оно содержит четвертую группуключей, группы сумматоров, блок заданияприращения аргумента, вторую группу блоков вычисления значения функции, группывычитателей, вычитатель, блок задания ограничения, блок деления, блок задания количества аргументов и триггер, вход установки в единичное состояние которого подключен к входу сброса кольцевого счетчика, к управляющим входам ключей первой группы и является входом внешнего запуска устройства, вход сброса триггера подключен к выходу кольцевого счетчика, счетный вход которого соединен с четвертым выходом линии задержки, выход триггера соединен с управляющим входом ключа, управляющие входы ключей четвертой группы подключены к третьему выходу линии задержки, а выходы соединены с соответствующими выходами ключей первой группы и входами первого регистра, информационные входы ключей первой группы являются входами начальных значений вектора решения устройства, выходы первого регистра являются выходами оптимальных значений вектора решения устройства и подключены к соответствующим входам блоков вычисления значений функции первой группы и к информационным входам ключей второй группы, управляющие входы которых подключены к первому выходу линии задержки, а выходы соединены с соответствующими входами второго регистра, входы первого слагаемого.сумматоров первой группы подключены к выходам второго регистра, выход блока задания приращения аргумента подключен к входам второго слагаемого сумматоров первой группы, входы блоков вычисления значения функции второй группы подключены к выходам соответствующих сумматоров первой группы, входы вычитаемого вычитателей первой группы соединены с выходами соответствующих блоков вычисления значения функции первой группы, входы уменьшаемого подключе ны к выходам блоков вычисления значенияфункции второй группы, а выходы соединены с входами первых сомножителей соответствующих блоков умножения группы, входы вторых сомножителей которых под ключены к выходу блока задания коэффициентов, входы вычитаемого вычитателей второй группы подключены к выходам соответствующих блоков умножения группы, входы уменьшаемого которых соединены с 15 соответствующими выходами второго регистра, а выходы подключены к информационным входам ключей третьей группы, управляющие входы которых соединены с вторым выходом линии задержки, а выходы 20 подключены к соответствующим входамтретьего регистра, выходы которого соединены с входами накапливающего сумматора, вход вычитаемого вычитателя соединен с выходом накапливающего сумматора, вы ход блока задания ограничения подключенк входу уменьшаемого вычитателя, вход делимого блока деления соединен с выходом вычитателя, выход блока задания количества аргументов подключен к входу делителя 30 блока деления, входы первых слагаемыхсумматоров второй группы соединены с соответствующими выходами третьего регистра, входы вторых слагаемых подключены к выходу блока деления, а выходы соединены 35 с информационными входами соответствующих ключей четвертой группы.1765830 оставитель Н,Зубовехред М.Моргентал Корректор И.Шул Редактор Т,Орло а город, ул,Гаг Производственно-издательский комбинат "Патент аказ 3386 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб 4/5