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

Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки цифровой инфор мации автоматизированных систем планирования и управления, а также дискретной автоматики, реализующих методы оптимизации параметров управления. Известно устройство для выделения экстремального значения функции, содерм жашее регистр экстремального значения функции и коммутатор, выход которого соединен с вторым входом схемы сравнения и входом регистра экстремального значения функции. Выход последнего соединен с первым входом коммутатора, вто рой вход которого подключен к выходу регистр текущего значения функции. Данное устройство обеспечивает вьщёление экстремального (максимального и минимального) значения функции одной ; переменной при задании исходной информации в виде приращений L 1J. Недсзстатком данного устройства является ограниченность класса решаемых задач, приводящая к невозможности отыскания экстремума недифференцнруемой функции двух переменных и, соответственно, определения координат точки экстре,мума заданной функции. Известно устройство для поиска максимума корреляционной функции, содеркашее блок управления, первый и второй аналого- цифровые преобразователи, входы которых являются первым и вторым входом устройства, а выходы подключен соответственно к блоку дискретной задержки и блоку задержки, выход которого подключен к первым входам блоков умножения, вторые входы которых соединены с соответствующими выходами блока дискретной задеркки, выходы блоков умножения через соответствующие цифровые интегри- торы соединены с блоком выделения экстремума. Данное устройство позволяет отыскать макстлум функции одной пер мённой при наличии аналитического выражения для оптимизируемой функции 12. Недостатком данного устройства явля ется ограниченность класса решаемых задач, приводящая к невозможности отыс кания минимума анализируемой функции к невозможности отыскания экстремума функ1 йи при отсутствии аналитического выражения для заданной функции, а также при задании функции набором из ряда вычисленных в заданных точках значений. Наиболее близким к предлагаемому .изобретению является устройство, которое содеркит память значений функции, предназначенную для хранения цифровых кодов дискретных опорных значений функции и память значений переменных соответствующих вычисленнь1м значениям функции, входы которых соединены со входом устройства адресный вычислитель ный блок, соединенный с памятью значений функции и памятью значений nejjeMeH ных, к выходу которого подключены интерполяционные вычислительные блоки. Адресный вычислительный блок предназначен для .определения двух адресов тех значений функции, которые окружают искомое значение функции и обеспечивает считывание по данным адресам из памяти значений функции кодов значений. Счи танные из памяти значений функции коды значений записываются в интерполяционные вычислительные блоки. Перед интерполяционными вычислительными блоками включены регистры для запоминания искомого значения функции или ее.опорных значений. Интерполяционные вычислитель ные блоки осуществляют линейные интер поляции между соответствующими двумя, считанными из памяти значений функции, значениями путем образования корректировочного значения. Корректировочное значение формируется в умножителе как произведение разности опорных значе-. НИИ функции .и пропорциональной составляющей. Полученное корректировочное значение суммируется в выходном сумматоре с одним из опорных значений функции. Коды числовых значений функции, вычисленные в интерполяционных бл ках, поступают на вь1ход устройства. Устройство обеспечивает числовое оп ределение значений функции на интерва- лах между известными опорными значениями и отыскание, в процессе анализа вычисленных значений, координаты точ963 ки экстремума унимодальной функции одной переменной 3 J. Недостатком рассматриваемого устройства является невозможность ртыска ния экстремального значения унимодальной функции двух переменных, заданной набором из вычисленных в заданных точках значений, а также определения значений координат точки экстремума заданной функции. Цель изобретения - расширение функциональных возможностей за счет обеспечения нахождения экстремального значения недифференцируемой унимодальной функции двух переменных, заданной набором из вычисленны; с в заданных точках значений. Поставленная цель .достигается тем, что в устройстро, содержащее блок уп. равления, блок формирования адреса, блок интерполяций, блок памяти значений функции и блок памяти значений переменных адресный вход и информационный выход . которого соединены соответственно с первым выходом и. первым входом блока формирования адреса, второй выход которого подключен к адресному входу блока памяти значений функции, информационный вход которого и информационный вход блока памяти значений переменных соединений с информационным входом устройства, управляющий вход которого соединен с первым входом блока управления, второй вход которого соединен с третьим выходом блока формирования адреса, первый выход блока управления подключен к второму входу блока формирования адреса, четвертый выход которого является выходом устройства, введены блок сравнения, блок суммирования и вычислительный блок, информационный и управляющий входы которого соединены соответственно с вторым и третьим выходами блока управления, а выход подключен к третьему входу блока формирования адреса,, четвертый и пятый входы которого соединены соответственно с выходом блока суммирования и с первым выходом блока сравнения, второй выход которого подключен к третьему входу блока управления, четвертый выход .которого соединен с первым входом блока суммирования, второй вход которого соединен с пятым выходом блока формирования адреса, первый и второй входы блока сравнения соединены соответственно с выходом блока памяти значений функции и с выходом блока интерполяции, вход которого подключей к третьему выходу блока сравнения. Кроме того, в устройстве блок формирования адреса содержит счетчики, г не ратор тактовых импульсов, регистры координат вершин, регистр адреса, регистр переменных, элементы И, группы элемен тов И, схемы сравнения, триггеры, групп элементов ИЛИ и коммутатор, входы которого являются сбответственно третьим четвертым и пятым входами блока, выход коммутатора подключен к входам первого, второго и третьего регистров коорди - нат вершин, выход первого из которых подключен к первым входам элементов И первой, второй и третьей групп, выход второго регистра координат ве1яиин подключен к первым входам элементов И четвертой, пятой и шестой групп, выход третьего регистра коорцинат вершин подключен к первым входам элементов И седьмой, восьмой и девятой групп, вторые входы элементов И первой, четвертой и седьмой групп соединены с выходом первого счетчика, вход которого и первый вход второго счетчика соединены с выходом генератора тактовых импульсов, выход второго счетчика является первым выходом блока, первый вход блока подключен к входам регистра адреса и регистра переменных, выход которого соединен с первыми входами первой, второй и третьей схем сравнения, вторые входы которых подключены соответственно к выходам элементов И первой, четвертой и седьмой групп, выходы схем ср1авнения соединены соответственно с первыми входами пержого, второго и третьего триггеров, вторые входы которых и первый вход генератора тактовых импульсов подключены к второму входу блока, выходы триггеров, соединены соответственно с первыми входами первого, второго и третьего элементов И и с первым, вторым и третьим входами четвертого элемента И, выход которого подключен к вторым входам генератора тактовых -импульсов, второго счетчика и к третьему выходу блока, вторые входы первого, второго и третьего элементов И подключены к вькоду регистра адреса, а выходы соединены с вторым выходом блока, вторые входы элементов И второ пятой и восьмой групп соединены с пятым входом блока, а выходы подключены соответственно к входам группы элементов ИЛИ, выходы которых соединены соответственно с первыми входами элементов И десятой группы и с пятым выхо93 дом блока, вторые входы элементов И десятой группы подключены к второму входу блока, а выходы соединены с четвертым выходом блока, вторые входы элементов И третьей, шестой и девятой групп соединены с четвертым входом блока, а выходы подключены к пятому выходу блока. Вычислительный блок в устройстве содержит группы элементов И, регистр кода ребра, регистр константы, регистру коо| динаты, сдвигатель, два сумматора, два вычитателя, два умножителя и регистры, -.- выходы которых соединены с выходом блока, входы регистра кода ребра, регистра. константы и элементов И перовой группы соединены с информационным входом блока, выход регистра коаа ребра подключен к jiepBbiM входам элементов И второй группы, выход регистра константы подключен к первым входам элементов И третьей группы, вторые входы элементов И второй и треть-ей групп подключены к управляющему входу блока, выходы элементов И первой группы подключены к входам первого и второго регистров координаты, выходы элементов И второй группы соединены с входом сдвигателя и с п€рвь1м входом первого умножителя, второй вход которого и первый вход второго умножителя соединены с выходами элементов И третьей группы, выход первого регистра координаты подключен к пертым входам первого сумматора и первого вычитателя и к входу первого регистра, выход второго регистра координаты соединен с первыми входами второго вычита- теля и второго сумматора, выход сдвигателя подключен к вторым входам первого сумматора, первого вычитателя и второго умножителя выходы первого и второго умножителей соединены соответственно с вторым входом второго сумматора и с вторым входом второго вычитателя, выход которого соединен с входами второго и третьего регистров, выходы первого и второго сумматоров и выход первого вычитателя соединены соответственно с входами четвертого, пятого и шестого регистров. Блок интерполяции в устройстве содержит сумматор, вычитатель, три группы элементов И, три регистра, входы которых и первые входы - элементов И трех групп соединены с входом блока, выходы первого, второго и третьего, регистров подключены к вторым входам элементов И соответственно первой, второй и третьей групп, выходы элементов И первой

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

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

первым входом пятого триггера и через последовательно соединенные четвертый элемент задержки и четвертый усилитель с вторым входом пятого триггера; выходы второго и третьего элементов И соединены с третьим выходом блока, первый и четвертый выходы которого подключены соответственно к выходам четверрегистр 72 координат исходной точки, элемент ИЛИ 73, триггер 74, группа элементов И 75, элемент задержки 76, усилитель 77, триггер 78, элемент задержки 79, усилитель 80, триггер 81, элемент ИЛИ 82, элемент задержки 83, усилитель 84, триггер 85, элемент И 86, элемент задержки 87, усилитель 88,триггер 89, элементы И 90-93, схема 94

сравнения, элемент НЕ 95, группы элементов И 96 и 97, коммутатор 98, регистры 99, 10О и 101 значений функции, схема 102 сравнения, узел 103 уптого и пятого элементов И. На фиг. 1 представлена блок-схема устройства; на фиг. 2 - схема блока формирования адреса; на фиг. 3 - схема вычислительного блока; на фиг. 4 - схема блока, интерполяции; на фиг 5 - схема блока управления; на фиг. 6 - схема блока сравнения; на фиг. 7 - схема блока суммирования; на фиг. 8 - схема узла управления. На схемах показаны блок 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 и 33, группа элементов ИЛИ 34, группа элементов И 35-38, группа элементов И 39, регистр 40 кода ребра, регистр 41 конденсаты, группы элементов И 42 и 43. регистр 44 координаты, сдвигатель 45, регистр 46 координаты, сумматор 47, вычитатель 48, умножители 49 и 5О, вычитатель 51, сумматор 52, регистр 53-58, регистры 59, 6О и 61, группы элементов И 62, 63 и 64, сумматор 65, вычитатель 66, элемент ИЛИ 67. элемент И 68, вычитающий счетчик 69, наборный коммутатор 70, схема 71 сравнения. 966 равления, коммутатор 1О4, дешифратор 105, сдвигатели 1О6 и 107, регистры 10&-113, группы элементов И 114-121 сумматоры 122-125, вычислители 126 и 127, триггеры 128, 129-и 130, элемен ты И 131-136, элементы ИЛИ 137, 13 и 139, элементы задержки 140, 141 и 142; элементы НЕ 143 и 144. Блок 1 памяти значений функции предназначен. для приема, хранения и выдачи в блок сравнения 7 цифровых кодов значений унимодальной функции двух перемен ных, измеренных в заданных опорных точ ках, и представляет собой функционально законченный блок- оперативной памяти, выполненный, например, в виде оперативного запоминающего устройства на фер- ритовых сердечниках и интегральных микросхемах. Блок 2 памяти значений переменных предназначен для приема, хранения и выдачи в блок 3 цифровых кодов переменных, соответствующих вычисленным в заданных опорных точках значениям оптимизируемой функции, и представляет собой функционально законченный блок оперативной памяти, выполненный, например, в виде оперативного запоминающего устройства на ферритовых сердечниках и интегральных микросхемах. В ячейке блока 2 памяти значений переменных записаны код адреса ячейки памяти значений функции, в которой записан код измеренного в точке с координатами , V-f } значения функции | j -1 F ( v ) « ° i у f V коодинаты у , являющейся первой переменной функции F(Xi,V- l координаты , являющейся второй, переменной функции (X i, ) Такщм образом, код операнда, записиваемого в ячейку блока 2 памяти значеНИИ переменных, может быть представлен выражением А,У,-Л Блок 3 предназначен для формирования цифровых кодов адресов ячеек б.юка 2памяти приема из вычислительного . блока 4 кодов координат верлин исходного симплекса приема из блока 2 кодов, операндов, сравнения кодов, считанных из блока 2 памяти с кодами, записанными в регистрах 13, 14 и 15, ивыдачи в блок 1 кодов адреса. С выхода блока 3выдаются коды координат, доставляющие экстремум заданной функции. Счетчик 9 блока 3 предназначен для формирования кода адреса ячейки блока 2 памяти значений переменных послёдо310вательным суммированием импульсов, поступающих с выхода генератора 12 тактоБЫх импульсов. Счетчик К) обеспечивает управлеиие процессом сравнения кодов координат вершин симплекса с текущими кодами координат путем последовательной выдачи разрешающих сигналов на элементы И 18, 19 и 20, обеспечивающих вьщачу кодов коор.динат в схемы 21,22 и 23 сравнения, и выполняется в виде пересчетной схемы на три с цепями обратной связи, запускаемой от генератора 12 тактовых импульсов. Коммутатор 11 обеспечивает управление обнулением и записью кодов координат вершин симплекса в регистры 13,14 и 15, поступающих аз вычислительного блока 4 и блока 8 суммирования, ипредставляет собой набор трех входовых элементов И, управляемых.блоком 7 сравнения. Генератор 12 тактовых импульсов предназначен для формирования последовательности импульсов, обеспечивающих синхронизацию функционирования элементов блока 3, и представляет собой за пускаемый одновибратор с цепями управления, выполненный, например на интегРольных микросхемах. Регистры 13, 14 и 15 предназначены для приема из вычислительного блока 4 или блока 8 и для хранения кодов координат вершин симплексу, а также выдачи данных кодов в соответствии с управляющими сигналами, поступающими из блока 7 сравнения. Регистр 16 адреса и регистр 17 кода переменных предназначены, соответствен- ° приема из блока 2 кодов адресов « переменных, хранения и выдачи в соответствии с управляющими сигналами даннЫх кодов в блок 1 памяти значений функции и схемы 21, 22 и 23 сравнения. Схемы 21, 22 и 23 обеспечивают сравнение кодов координат вершин симплекса с кодами параметров, хранящихся в регистре 17, и формирования сигнала совпадения кодов, и представляют собой комбинационные схемы сравнения. Триггеры 25, 26 и 27 формируют управляющие сигналы, обеспечивающие . выдачу через элементы И 28, 29 и 30 кодов адресов ячеек блока 1 памяти зна.чений функции; обнуление через элемент И 24 счетчика 9 и останов генератора тактовых импульсов 12. Группы элементов И 18-2О; 31-33; 35-38 служат для передачи кодов координат вершин симплек са на соответствующие входы блоков уст ройства в соответствии с управляющими сигналами. . Вычислительный блок 4 предназначен для формирования кодов координат вершин исходного симплекса X , , .,к для первого щага поиска и выдачи их в блок 3. Вычисление значений координат осуществляется в соответствии с выражениямио, , - М 4.i I О ./г ° 1 О 1. О I V l,- где XQ , Vo координаты исходной точки поиска; liQ - размер ребра симплекса. Регистры 44.и 46 координат исходной точки обеспечивают прием изблока 6 управления хранение и выдачу на узлы вычислительного блока координат исходной точки поиска. Регистры 4О и 41 предназначены, соответственно, для приема : из блока 6-управления, хранения и выдачи на узлы вычислительного блока кода размера ребра симплекса и кода константы О,57735 для случая равенстваЬо 13. Регистры 53-58 предназначены для приема, формирования и выдачи в блок 3 кодов координат вершин исходного .симплекса для первого шага.поиска. Группы элементов И 39, 42 и 43 обе печивают прием кодов в соответствующие регистры и элементы вычислительного блока 4 в соответствии с управляющими сигналами, поступающими из блока 6 управления и представляют собой наборы . двухвходовых элементов И. Сдвигатель 45 предназначен для формирования кода значения половины длины ребра симплекса посредством сдвига впра во на один разряд кода, поступающего на его вход, и представляет собой триггер- ный регистр с входными цепями сдвига. . Сумматоры 47 и 52 и-вычитатели.48 и 51 служат для поразрядного суммирования и вычитания кодов и представляют собой комбинационные узлы параллельного действия с одновременным переносом, вы полненные на элементах И, ИЛИ, НЕ. Умножители 49 и 50 обеспечивают формирование кодов произведения констан ты на значение длины и половины длины ребра симплекса соответственно, и представляет собой умножители с одновременным умножением на два разряда множителя и сдвигом множимого на два разряда влево. Блок 5 интерполяции осуществляет линейную интерполяцию между соответ ствующими тремя значениями функции путем образования корректировочного значения и последующего вычитанля экстремального из данных трех значений функций. Линейная интерполяция осуществляется в случае отсутствия в новой верщине симплекса значения функции в соответствии с выражением ...; . где Fug.j. - экстремальное значение функции; FU, Fy - значения функции для других вершин симплекса. Регистры 59, 60 и 61 служат для приема, хранения и выдачи в сумматор 65 и вычитатель 66 кодов значений функции, определенных и упорядоченных на предыдущем щаге оптимизации и являюц ихся исходными для определения иско-. мого значерия фyнкцииJ путем линейной интерполяции известных значений функции для предыдущего щага поиска. Группы элементов И 62, 63 и.64 обеспечивают передачу кодов значений функции на входы сумматора 65 и вычитателя 66 в соответствии с управляющим сигналом, поступающим из блока 7 сравнения. Сумматор 65 предназначен для формирования кода суммы слагаемых и об спечивает поразрядное суммирование кодов., значений функции, Вычитатель 66 для формирования разности кодов, поступающих на его вход . Блок 6 управления предназначен для формирования и подачи на логические ,элементы блоков уст{юйства тактовых синхронизирующих импульсов (СИ), обеспечивающих точное временное согласование функцпочирования всех блоков и узлов устройства в автоматическом режиме. Он представляет собой блок управления с жесткой логикой. Вход блока управления 6, на который подается сигнал Пуск, соединен с входом элемента ИЛИ 67. Элемент ИЛИ 67 служит для передачи сигнала Пуск или импульса +1 из .блока 3 на вход вычитающего счетчи ка 69. Элемент И 68 обеспечивает передачу :;нгнала Пуск на вход триггерной схе13.9667 мы формирования синхронизирующих импульсов при наличии разрещающего сигнала с выхода триггера 74. Вычитающий счетчик 69 предназначен для приема импульсов и формирования текущего кода числа щагов поиска и представляет собой двоичный реверсивный счетчик с цепями управления, выполненный на триггерах. Наборный коммутатор 70 обеспечивают 10 чения ручное формирование кодов координат исходной точки поиска, кода ребра симплекса и кода константы и выполнен на -тумблерах, на которые подается напряже ние питания. Тумблеры, формирующие коды координат исходной точки поиска, подают напряжение на триггеры регистра 72. Код ребра симплекса и константы подаются на входы триггеров регистра 40 и регис ра 41 вычислительного блока 4. . Число тумблеров равно сумме числа р азр5щов формируемых кодов. Схема 71 сравнения предназначена для фиксации нулевого состояния вычита ющего счетчика 69 и формирования упра ляющего сигнала, переводящего триггер 74 в нулевое состояние. Группа элементов И 75 обеспечивает дередачу кода координат исходной точ1ки поиска с выхода регистра 72 на вход вычислительного блока 4. Элементы задержки 76, 79, 83 и 87 обеспечивают формирование синхронизирующих импульсов необходимой длительУсилители 77, .80, 84 и 88 служат для формирования импульсов необходимой амплитуды после элементов задерж: ки. Триггеры 78, 81, 85 и 89 служат для формирования синхронизирующих импульсов необходимой длительности. Элементы И 90-93 служат для передачи синхрюнизирующих импульсов в узлы и блоки устройства. Блок 7 сравнения предназначен для последовательного приема из блока 1 па мяти значений функции или блока 5 интерполяции кодов значений функции, запи си кодов во входные регистры, их попарного сравнения с целью отыскания максимального (в случае отыскания координат, соответствующих минимуму заданной функции) или минимального (в случае отыскания координат, соответствующих максимуму) значения функции и .записи кодов значений в регистры в по- рядке убывания (возрастания). $ 314 Регистр, содержащий экстремальное значение функции, обнуляется, Группы элементов И 96 и 97 обеспечивают передачу кодов значений функции на вход коммутатора 98 в соответствии с управляющими сигналами, поступающими с выхода схемы 94 сравнения. Схема 94 сравнения предназначена лля фиксаций нулевого состояния хода зна- функции, поступающего иа вход бло- ка 7 сравнения, и формирования управляющих сигналов, поступающих на входы блока 5 интерполяции и элементов И 96 и 97. . Коммутатор 98 обеспечивает последовательный прием и запись в регистры . 99, 100 и 101 кодов значений функции, поступающих или из блока 1 памяти значений функции или из блока 5 интерполяции. Регистры 99, 1ОО и 101 обеспечивают прием, хранение и выдачу в схему 102 сравнения кодов значений функции с последующей переписью из регистра в регистр по управляющим сигналам, поступающим из узла 103 управления с последующим обнулением регистра 101. Схема 1О2 сравнения обеспечивает попарное сравнение кодов знач8:ний функции вычитанием их кодов с последующей выдачей в узел управления кода разности для формирования сигналов управления работой узлов блока сравнения и представляет собой комбинационный вычита- тель СОсхемой формирования знака. Узел управления 103 обеспечивает анализ результата вычитания сравнива - емых кодов значен,ий функции и формирования соответствующих сигналов управления. Коммутатор 1О4 обеспечивает последовательный прием и запись в регистры блока 5 интерполяции кодов значений функции, упорядоченных в блоке 7 сравнения. Дещифратор 1О5 обеспечивает преобразование двоичного позиционного кода номера регистра, хранящего код экстремального значения функции, в выходное напряжение возбуждения, обеспечивающего быдачу кодов координат экстремального значения функции из блока 3 в блок 8 и запуска блока 6 управления. Узел 103 предназначен для приема из схемы 102 ср)авненйя ,и анализа результатов сравнения кодов значений функции, а также формирования .сигналов, обеспечивающих управление работой коммутатора 104, выдающего упорядоченные коы значений функции в блок 5 инторполяции| формирование двоичного позиционного кода номера регистра, хранящего код экстремального значения функции, выдаваемого на дешифратор 105; форлирование управляющих сигналов, обеспечивающих j обнуление регистра, хранящего код экстремального значения функции, и перепись сосЛ-ветствующих кодов в регистрах 99, 100 и 101.

Триггеры 128, 129 и 13О предназ- to начены для приема из схемы сравнения 1О2 сигналов разности сравниваемых кодов, запоминания их и выдачи на входы элементов И 131-136;

Триггер 128 фиксирует ре льтат срав-$ нения кодов, хранящихся в регистрах 99 И.1ОО, триггер 130- кодов, хранящихся в регистрах 99 и 101, триггер 13.1 кодов, хранящихся в регистрах 10О и 101,

Единичные состояния триггеров 128, jo 129 и 13О соответствуют результату сравнения Больше, а нулевое состояние соответствует результату сравнения Меньше или Равно, выдаваемым с выхода схемы сравнения 102.25

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

«Jr-PiVFia FiX . Di--FtiFi4 F,-2., Ue--F4% Fi-i li-a,

, 35

где ., F., F - коды значений функции, хранящиеся в регистрах 99, 10О и 101; U,,Uu,U5,U4,U5,U6 -управляющие сигналы.

Элементы И 131-136 служат дляформирования управляющих сигналов в соответствии с приведенной логикой, и представляют собой трехвходовые элементы И. Сформированные управляющие сигналы обеспечивают управление работой коммутатора 1О4.

Элементы ИЛИ 137, 138 и 139 слу-. жат для попарного объединения управляю- so щих сигналов и формирования сигналов

ivviax и2.м1ах1 U,waXj

где,,. ..

4mo.K--Fi-i F-ixN4 Fi., 55 awtciji--F a Fi-,7 Р г 1г Р1ЧPi4,

ЧУЯС -- F 1 v ti-,

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

Элементы задержки 14О, 141 и 142 обеспечивают выдачу упорядоченных кодов через коммутатор 104 в блок 5 до обнуления соответствующего регистра.

Элементы НЕ 143 и 144 обеспечивают формирование сигналов переписи кодов из регистров в регистр.

Двоичный позиционный код, формируемый на выходах элементов ИЛИ 137, 138 и 139, может принимать значения 100, 01О, 001. При комбинации 100 обнуляется регистр 99 по сигналу, поступающему с выхода элемента задержки 14О, на выходах элементов НЕ 143 и 144 формируется управляющие сигналы, разрешающие перепись кодов из регистра 100 в регистр 99 и из регистра 101 в регистр ipo. При наличии сигнала на выходах элемента задержки (комбинация 010) обнуляется регистр 100 и производится перепись кода из регистра 101 в регистр 10О. При наличии сигнала на выходе элемента задержки 142 обнуляется регистр 101, перепись не производится.

Блок 8 предназначен для формирования и выдачи в блок 3 кодов координат вершины симплекса для;оче.реш1р.го шага поиска. Значения координат новой вершины симплекса для очередного шага поиска вычисляются в соответствии с выражениями

.. - Vui .- иъ u ex-br,

где Хук , VUK - координаты вершины

симплекса, К 1, 2, 3; Xue,,.,Vyg .у- координаты вершины

симплшсса, для которой значение функции имеет экстремум.

Сдвигатели 1О6 и 107 предназначены для формирования кодов, соответствующих удвоенному значению координат вершины симплекса, доставляющем экстремум значению функции, посредством сдвига поступающего кода влево на один разряд, и представляют собой регистры с входными цепями сдвига. Регистры 108-113 предназначены дл приема из блока 3, хранения и выдачи, в соответствии с управляющими сигналами, поступающими из блока 6 управлени в сумматоры 122-125 кодов координат вершин симплекса. Сумматоры 122, 123, 124 и 125 предназначены, соответственно, для формирования кодов сумм и выдачи кодов сумм в вычитатели 126 и 127 и представляют собой поразрядные комбинационные сумматоры. Вычитатели 126 и 127 обеспечивают формирование кодов -координат верщины симплекса посредством вычитания из кодов сумм кодов удвоенных значений координат, доставляющих экстремум функ ции. Устройство реализует симплексный метод поиска экстремума унимодальной функции переменных, заданной набором измеренных в опорных точках значений, основанный на последовательном отражении вегниин симплекса в пространстве не зависимых переменных, не требующей сложных вычислений при полной формализации операций поиска, В исходном состоянии на блоки устройства подано питание, регистры блока 3, блока 5 интерполяции, блока 7 сравнения, блока 8 суммирования обнулены, в соответствующих ячейках блока 1 памя ти значений функции записаны коды значений оптимизируемой функции; в ячейках блока 2 памяти значений переменных за писаны коды адресов соответствующих значений функции и коды координат точе в которых произведено вычисление значе ний оптимизируемой функции; с помощью тумблеров блока 6 управления сформированы коды координат исходной точки . поиска, ребра симплекса и константы С (С 0,57735). Работа устройства для поиска координат точки экстремума функции двух переменных может осуществляться в цъух, режимах: автоматическом режиме и режиме диалога. В автоматическом режиме осуществля ется поиск координат точки экстремума унимодальной функции, обеспечивающей принятие предпочтительного решения ,по результатам анализа функции. -Размер симплекса в автоматическом режиме уст навливается равным минимальному расстоянию между точками, в которых вычислены значения функции, и в процессе работы не изменяется. Работа устройства в автоматическом режиме начинается по сигналу Пуск поступающему на вход блока 6 управления. По этому сигналу, при условии нахождения в нулевом состоянии триггера 74, через элемент И 68 переводятся в единичное состояние триггер 78, формируюший сигнал СИ 1 и триггер 74, разрешающий выдачу синхронизирующих через элемент ИЛИ 67; устанавливается в исходное состояние вычитающий счетчик 69 и выдаются в вычиcлитeльн Iй блок коды координат ис ходной точки поиска. Длительность сигнала СИ 1 определяется временем -распространения сигнала в элементе задержки 76 и должна обеспечивать устойчивое срабатывание триггеров 4О, 41, 44 и 46 и вычислительного блока 4. Одновременно с обнулением триггера 78 в единичное состояние переводится триггер 81, формирующий сигнал СИ 2, поступающий в вычислительный блок 4 н обеспечивающий формирование кодов коороинат вершин исходного симплекса. Сформированные коды коор1ина- вершин симплекса записываются через коммутатор 11 блока 3 в регистры 13, 14 и 15. Через время, определяемое элементом задеркки 79, триггер 81 обнуляется и в единичное состояние переводится триггер 85, формирующий сигнал СИ 3 и вьщаваемый в блок 3, запускающий генератор 12 тактовых импульсов с одновременным обнулением триггеров 25, 26 и 27 Оиновремейно по СИ 3 в блок 8 выдаются сформированные коды координат симплекса. Генератор 12 тактовых импульсов формирует последовательность импульсов, -обеспечивеющих рюботу блока 3. Счетчик 9 последовательным суммированием импульсов формирует коды адресов ячеек блока 2 памяти значений переменных, по KOTOfft-iM осуществляется их считывание н запись в регистры ,16 и 17. В регистр 16 записывается код адреса ячейки блока 1 памяти значения функции, а в регистр 17 записываются считанные коды координат значений. Счетчик 10 формирует .последовательность из трех импульсов, обеспечивающих последовательную вьщачу из регистров 13, 14 и 15 кодов координат симплекса на вхОды схем сравнения 21, 22 и 23, обеспечивающих сравнение кодов координат вершин исходного симплекса и кодов координат, хранящихся в регистре 17. В случае совпадения сравниваемых кодов на выходе соответствующей схемы формируется сигнал совпадения, переводящий один из триггеров 25, 26 и 27 Б единичное состояние. Триггер, переведенный в единичное состояние разрешает выдачу кода, хранящегося в регистре 16, в блок 1 памяти значений функции, обеспечивая считывание кода значения функции из ячейки памяти по данному адрзесу. При отыскании всех кодов координат вершин симплекса триг геры 25,26 и 27 переводятся в единичное состояние и на выходе элемента И 2 сформируется высокий потенциал,, останавливающий генератор 12 тактовых импульсов, обнуляющий счетчик 9 и изменяющий состояние вычитающего счетчика 69, уменьщая его содержимое на единицу Считанные в соответствии с адресами на ячейках блока 1 памяти значений функции значения поступают на вход блока 7 срав нения с целью отыскания экстремального значения функции для рассматриваемых координат. Код значения функции поступает на вход схемы 94 сравнения, .осуществляющей проверку равенства нулю кода значения функции и управление выдачей кодов на вход коммутатора 98. В случае равенства кода значения функции нулю, с выхода схемы сравнения в блок 5 интерполяции и поступает управ ляющий сигнал, по которому формируется код интерполированного значения функции и через группу элементов И 97 и комму татор 98 записывается в обнуленный регистр 1OI. Коды значений функции, записанные в регистрах 99, 10О и lOlj последовательно сравниваются в схеме 1О2 сравнения с последующим анализом в узле 103 управления кода разности. Упорядоченные коды значений функции через коммутатор 104 переписываются в регистры 59, 60 и 61 блока 5 интерполяции. С выхода дешифратора 1О5 управляющие с-игналы поступают на группы элементов И 31, 32 и 33, разрешая вы дачу кодов координат ввуаиины, для которой значения функции приняло экстремум в блок 8, и на выход коммутатора 11, обнуляя регистр, хранящий коды, и на вход элемента И 86 через элемент 73 блока 6 управления, разрешая формирование сигнала СИ 4, обеспечцвающего формирование кодов координат новой верщины симплекса в блоке 8. По сиг;налу СИ 4 в блоке 8 на входы сумматоров 122-125 и вычитателей 126 и 127 вы даются коды координат вершины симплек са, по которым.формируются коды, посту пающие на вход коммутатора 11 и записываемые в обнуленный регистр коордиаты вершины симплекса блока 3. По окончании сигнала СИ 4 триггер 89 переводится в нулевое состояние, разрешая ормирование сигнала СИ 3 и запуская генератор 12 тактовых импульсов. Цикл работы устройства повторяется. Счетчик 69 обнуляется через заданное число шагов поиска и на выходе схемы сравнения формируется сигнал, переводящий триггер 74 в нулевое состояние, формируя на выходе блока 6 управления сигнал СИ 5. По сигналу СИ 5, поступающему в блок 3, на группу элементов И 38, на выход устройства вьщаются коды координат точки экстремума функции двух переменных. Работа устройства в режиме диалога может использоваться при исследовании характера функции, выявления глобальных и локальных экстремумов и отыскания координат точек экстремумов. В этом режиме размер ребра симплекса может устанавливаться кратным расстоянию Между точками, в которых вычислены значения функции с последовательным уменьшением размера ребра до глинимального и переносом координат исходной точки в интересующую область переменных. Работа устройства в рзежиме диалога не отличается от работы в автоматическом режиме и полностью соответствует работе, описанной выше. Формула изобретения 1. Устройство для поиска координат точки экстремума функции двух переменных, содержащее блок управления, блок формирования адреса, блок интерполяций, блок памяти значений, функции и блок памяти значений переменных, адресный вход и информационный выход которого соединены соответственно с первым выходом и первым входом блока формирования адреса, второй выход которого подключен к адресному входу блока памяти значений функции, информационный вход которого и информационный вход блока памяти значений переменных соединены с информационным входом устройства, управляющий вход которого соединен с первым входом блока управления, второй вход которого соединен с третьим выходом блока формирования адреса, первый выход блока , управления подключен к второму входу бло-. 1ка формирования адреса, четвертый выход

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

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

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

; ключей к первым входам элементов И

седьмой, восьмой и девятой групп, вторы

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

3, Устройство по п, 1, о т л и ч а - ю ш е е с я тем, что вычислительный блок содержит группы элементов И, регистр кода ребра, регистр константы, ре1гистры координаты, сдвигатель, два сумматора, два вычитателя, два улшожитвля и регистры, выходы которых соединены с выходом блока, входы регистра кода ребра, регистра константы и элементов И первой группы соединены с информационным входом блока, выход регистра кода ребре подключен к первым входам элементов И второй группы, выход регистра константы подключен к первым входам элементов И третьей группы, вторые входы элементов И второй и третьей групп подключены к управляющему входу блока, выходы элементов И первой группы подключены к входам первого и второго регистров коороинаты, выходы элементов И второй группы соединены с входом сдвигателя и с первым входом пер вого умножителя, второй вход которого и первый вход второго умножителя соепинены с выходами элементов И третьей группы, выход первого регистра координаты подключен к первым входам первого сумматора и первого вычитателя и к входу первого регистра, выход второго регистра координаты соединен с -первыми входами второго вычитателя и второго сумматора, выход сдвигателя подключен к вторым входам первого сумматора, первого вычитателя и второго умножителя, выходы первого и второго умножителей соединены соответственно с вторым входом второго сумматора и с вторым входом второго вычитателя. выход которого соединен с входами второго и трет его регистров, Выходы первого и второг сумматоров и выход первого вычитателя соединены соответственно с входами четвертого,- пятого и шестого регистров. 4. Устройство по п. 1, отличающееся тем, что блок интерполяции содержит сумматор, вычитатель, три группы элементов И, три регистра, вход которых и первые входы элементов И трех групп соединены с входом блока, выходы первого, второго и третьего регистров подключены к вторым входам эл ментов И соответственно первой, второй и третьей групп, выходы элементов И n вой группы соединены с первым входом сумматора, выходы элементов И второй группы соединены с вторым входом сум матора, выход которого подключен к пер вому входу вычитателя, второй вход которого соединен с выходами элементов И третьей группы, выход вычитателя является выходом блока. . 5. Устройство по п. 1, отличают е е с я тем, что блок управления содержит элементы И, ИЛИ, триггеры, элементы задержки, усилители, вычитающий счетчик, схему сравнения, наборный коммутатор, группу элементов И, регистр координат исходной точки, вход которого соединен с выходом наборного коммутатора, а выход подключен к первым входам группы элементов И, вторые входы которых и первые входы первых элементов И, ИЛИ и первого триггера соединены с первым входом блока, второй вход которого соединен с вторым входом первого элемента ИЛИ, выход ко торого подключен к входу вычитающего счетчика, выход которого соединен с входом схемы сравнения, выход которой соединен с вторым входом первого триггера, первый выход которого соединен с вторым входом первого элемента И и с первым выходом блока, выходы наборного коммутатора и группы элементов И соединены с вторым выходом блока, второй выход первого триггера подключен к первым входам второго,третьего, четвертого и пятого элементов И, вторые входы которых соединены соответственно с выходами второго и третьего триггеров и с первыми выходами четвертого и пятого триггеров, выход первого элемента И подключен к первому входу второго триг- гера и через последовательно соединенные первый элемент задержки и первый усилитель - к второму входу первого триггера, к первому входу третьего триггера и к входу второго элемента задержки, выход которого через второй усилитель соединен с вторым входом третьеготриггера и с первым входом второго элемента ИЛИ, второй вход которого соеди нен с вторым выходом пятого триггера, выход второго элемента ИЛИ подключен к первому входу четвертого триггера и через последовательно соединенные третий элемент задержки ц третий усилитель - к второму.входу четвертого триггера, второй выход которого соединен с первым входом шестого элемента И, второй вход которого соединен с выходом третьего элемента ИЛИ, входы которого соединены с третьим, входом блока, выход шестого элемента И соединен с первым входом. пятого триггера и через последовательно соединенные четвертый элемент задержки и четвертый усилитель - с вторым входом пятого триг- гера выходы второго и третьего элементов И соединены с третьим выходом блока, первый и четвертый выходы которого подключены соответственно к выходам четвертого и пятого элементов И. Источники информации, принятые во внимание при экспертизе 1.Авторское сввдетельство СССР № 4020О1, кл, G06 F 15/36, 1971. 2.Авторское свидетельство СССР № 696479, кл. G06F 15/34, 1977. 3; Заявка ФРГ № 2421330, кл. GO6F 7/37, 1977 (прототип).

1

7 П k

(

Фиг.

6 г

б г

/3

14

S

а

/

РР

ill

/5

/

Н

I П

I 22

в

Ч

2

I

i

ш

8 Ч

L- L-/Л.5

Фие.

I r

Ir

ФигЛ

Фиг. 5

. 7 Г

I fflf| /.y| //g( I I //J

iTTT iiii тт

Pf/.f,y

r%

пгт

л7