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

 

(72) Автор изобретения

В. В. Савичев (7! ) Заявитель (54) УСТРОЙСТВО ДЛЯ ПОИСКА КООРДИНАТ

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

ПЕРЕМЕННЫХ

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

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

Данное устройство обеспечивает выделение экстремального (максимального и .

20 минимального) значения функции одной: переменной при задании исходной информации в виде прирашений 1), Недостатком данного устройства является ограниченность класса решаемых задач, приводяшая к невозможности отыс« кания экстремума недифференцируемой функции двух переменных и, соответствен- но, определения координат точки экстре,мума заданной функции.

Известно устройство для поиска максимума корреляционной функции, содеркашее блок управления, первый и второй аналого- цифровые преобразователи, входы которых являются первым и вторым вхо- дом устройства, а выходы подключен соответственно к блоку дискретной задеркки и блоку задержки, выход которого. подключен к первым входам блоков умножения, вторые входы которых соединены с соответствуюшими выходами блока дискретной задержки, выходы блоков умножения через соответствуюшие цифровые интеграторы соединены с блоком выделения экс,тремума. Данное устройство позволяет отыскать максимум функции одной пере3 966703 4 менной при наличии аналитического BbIpB» ки экстремума унимодаль жения для оптимизируемой функции t. 23 ной переменной t 3), Недостатком данного устройства явля- Недостатком рассматр ется ограниченность класса решаемых ройства является невозмо задач, приводяшая к невозможности отыс- 5 ния экстремального значе кания минимума анализируемой функции ной функции двух перемен и невозможности отыскания экстремума набором из вычисленных функцйи при отсутствии аналитического ках значений, а также on выражения для заданной функции, а так- ний координат точки экст же при задании функции набором иэ ря- щ функции. да вычисленных в заданных точках эна- Дель изобретения - pa чений. ь

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

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

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

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

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

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

40 импульсов подключены к второму входу блока, выходы триггеров соединены соответственно с первыми входами перво« го, второго и третьего элементов И и с первым, вторым и третьим входами четвертого элемента И, выход которого под4$ ключен к вторым входам генератора тактовых -импульсов, второго счетчика и к третьему выходу блока, вторые входы первого, второго и третьего элементов И подключены к выходу регистра адреса, а выходы соединены с вторым выходом блока, вторые входы элементов И второй пятой и восьмой групп соединены с пятым входом блока, а выходы подключены соо ветственно к входам группы элемен И тов ИЛИ, выходы которых соединены соответственно с первыми входами элементов И десятой группы и с пятым выхо03 6 дом блока, вторые входы элементов И де сятой группы подключены к второму входу блока, а выходы соединены с четвертым выходом блока. вторые входы элементов И третьей, шестой и девятой групп соединены с четвертым входом блока, а выходы подключены к пятому выходу блока.

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

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

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

И соответственно первой, второй и третьей групп, выходы элементов И первой

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

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

И подключен к первому входу второго триггера и через последовательно соединенные;первый элемент задержки и пер» вый усилитель - к второму входу первого триггера, к первому входу третьего триггера и к входу второго элемента задержки, выход которого через второй усилитель соединен с вторым входом третье-"

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

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

На фиг. 1 представлена блок-схема устройства; на фиг. 2 - схема блока формирования адреса; на фиг. 3 - схема вы« числительного блока; на фиг. 4 — схема блока. интерполяции; на фиг 5 - схема блока управления; на фиг. 6» схема блока сравнения; на фиг. 7 - схема блока суммирования; на фиг. 8 - схема узла управления.

На схемах показаны блок 1 памяти значений функции, блок 2 памяти значений переменных, блок 3 формирования anреса, вычислительный блок 4, блок 5 интерполяции, блок 6 управления, блок 7 сравнения, блок 8 суммирования, счетчик

9, счетчик 10, коммутатор 11, генератор 12 тактовых импульсов, регистры 13

14 и 15 координат вершин, регистр 16 адреса, регистр 17 переменных, группы элементов И 18, 19 и 20, схемы 21, 22 и 23 сравнения, элемент И 24, тригге. ры 25, 26 и 27, элементы H 28, 29 и 30, группы элементов И 31, 32 и 33, группа элементов ИЛИ 34, группа элементов.И 35-38, группа элементов И 39, регистр 40 кода ребра, регистр 41 конденсаты, группы элементов И 42 и 43; регистр 44 координаты, сдвигатель 45, регистр 46 координаты, сумматор 47, вычитатель 48, умножители 49 и 50, вычи татель 51, сумматор 52, регистр 53-58, регистры 59, 60 и 61, группы элементов И 62, 63 и 64, сумматор 65, вычитатель 66, элемент ИЛИ 67. элемент

И 68, вычптаюший счетчик 69, наборный коммутатор 70, схема 71 сравнения, регистр 72 координат исходной точки, элемент ИЛИ 73, триггер 74, группа элементов И 75, элемент задержки 76, усилитель 77, триггер 78, элемент задеркки 79, усилитель 80, триггер 81, элемент ИЛИ 82, элемент задержки 83, усилитель 84, триггер 85, элемент И 86, элемент. задержки 87, усилитель 88, триггер 89, элементы И 90-93, схема 94 сравнения, элемент HE 95, группы элементов И 96 и 97, коммутатор 98, ре-. гистры 99, 100 и 101 значений функ,ции, схема 102 сравнения, узел 103 уп9 9867 равления. коммутатор 104, дешифратор

105, сдвигатели 106 и 107, регистры

108-113, группы элементов И 114-121, сумматоры 1 22-1 2 5, вычислители 1 2 6 и

127, триггеры 128, 129 и 130, элемен- 5 ты И 131-136, элементы ИЛИ 137, 138 и 139, элементы задержки 140, 141 и

142; элементы НЕ 143 и 144.

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

Блок 2 памяти значений переменных 20 предназначен для приема,,хранения и выдачи в блок 3 цифровых кодов переменных, соответствующих вычисленным в заданных опорных точках значениям оптимизируемой функции, и представляет со- 25 бой функционально законченный блок оперативной памяти, выполненный, например, в виде оперативного запоминающего устройства на ферритовых сердечниках и интегральных микросхемах. В ячейке блока 5Е

2 памяти значений переменных записаны код адреса ) А„3 ячейки памяти значений функции, в которой записан код измеренного в точке с координатами („, „) значения функции I „J 1(4(1 g .) ) 1 код 35 (коодинаты „-, являющейся первой переменной функции (Х„q. (; код jg„$ координаты 3., являющейся второй переменной функции 7(X< у„).

Таким образом, код операнда, записы- ваемого в ячейку блока 2 памяти значе ний переменных, может быть представлен выражением (AÄ,Х „, „ .

Блок 3 предназначен для формирования цифровых кодов адресов ячеек блока

2 памяти приема из вычислительного блока 4 кодов координат вершин исходного симплекса приема из блока 2 кодов операндов, сравнения кодов, считанных из блока 2 памяти с кодами, записанными в регистрах 13, 14 и 15, и выдачи в блок 1 кодов адреса. С выхода блока

3 выдаются коды координат, доставляющие экстремум заданной функции.

Счетчик 9 блока 3 предназначен для формирования кода адреса ячейки блока

2 памяти значений переменных последо03 10 вательным суммированием импульсов, поступающих с выхода генератора 12 тактовых импульсов.

Счетчик 10 обеспечивает управление процессом сравнения кодов координат вершин симплекса с текущими кодами координат путем последовательной выдачи раз решающих сигналов на элементы И 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-20; 31-33; 35-38 служат для ями

11 9667 передачи кодов координат вершин симплекса на соответствуюшие входы блоков устройства в соответствии с управляюшими сигналами.

Вычислительный блок 4 предназначен для формирования кодов координат вершин исходного симплекса Х „,, „, для первого шага поиска и выдачи их в блок

3. Вычисление значений координат осушествляется в соответствии с выражени- 0

Х = — 1

+ Хо - о, И . 0 2 0>

2 Ъ

Х, =Хо о, "0, "О

ХъЪ

Х ъ=Хо - g " .,= o (-д о

rge Хо, у — координаты исходной точки поиска; о - размер ребра симплекса. 20

Регистры 44 и 46 координат исходной точки обеспечивают прием из блока 6 управления хранение и выдачу на узлы вычислительного блока координат исходной точки поиска. Регистры 40 и .41 предназначень:, соответственно, для приема из блока б,управления, хранения и выда- чи на узлы вычислительного блока кода размера ребра симплекса и кода константы 0,57735 для случая равенстваЬo 5Е

=1 3. Регистры 53-58 предназначены для приема, формирования и выдачи в блок 3 кодов координат вершин исходного симплекса для первого шага поиска.

Группы элементов И 39, 42 и 43 обес печивают прием кодов в соответствуюшие регистры и элементы вычислительного блока 4 в соответствии с управлявшими сигналами, поступающими из блока 6 управления и представляют собой наборы

49 двухвходовых элементов И.

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

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

Умножители 49 и 50 обеспечивают формирование кодов произведения константы на значение длины и половины длины 35 ребра симплекса соответственно, и представляет собой умножители с одновременным умножением на два разряда множи03 12 теля и сдвигом множимого на два разря- да влево.

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

Fku-- F к " Г к+4 Р

uextr где Г е„ „- экстремальное значение функции; к-+ К4 4

- значения функции для других вершин симплекса.

Регистры 59, 60 и 61 служат для приема, хранения и выдачи в сумматор

65 и вычитатель 66 кодов эначенийфункции, определенных и упорядоченных на предыдущем шаге оптимизации и являюц,ихся исходными для определения иско-. мого значения функции> путем линейной интерполяции известных значений функции для предыдушего шага поиска. . Группы элементов И 62, 63 и 64 обеспечивают передачу кодов значений функции на входы сумматора 65 и вычитателя 66 в соответствии с управляюшим сигналом, поступаюшим из блока 7 сравнения.

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

Вычитатель 66 слугит для формирования разности кодов, поступающих на его вход.

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

Вход блока управления 6, на который подается сигнал Пуск", соединен с входом элемента ИЛИ 67.

Элемент ИЛИ 67 служит для передачи сигнала "Пуск или импульса "+1" из ,блока 3 на вход вычитаюшего счетчи— ка 69.

Элемент И 68 обеспечивает передачу

=игнала Пуск" на вход триггерной схе03 14

Регистр, содержащий экстремальное значение функции, обнуляется.

Группы элементов И 96 и 97 обеспечивают передачу кодов значений функции на вход коммутатора 98 в соответствии с управляющими сигналами, поступающими с выхода схемы 94 сравнения.

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

5 интерполяции и элементов И 96 и 97.

Коммутатор 98 обеспечивает последовательный прием и запись в регистры

99, 100 и 101 кодов значений функции, поступающих или из блока 1 памяти значений функции или из блока 5 интерполяции.

Регистры 99, 100 и 101 обеспечивают прием, хранение и выдачу в схему 102 сравнения кодов значений функции с последующей переписью из регистра в регистр по управляющим сигналам, поступающим из узла 103 управления с последующим обнулением регистра 101.

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

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

Коммутатор 104 обеспечивает последовательный прием и запись в регистры блока 5 интерполяции кодов значений функции, упорядоченных в блоке 7 сравнения. дешифратор 105 обеспечивает преобразование двоичного позиционного кода номера регистра,хранящего код экстремального значения функции, в выходное напряжение возбуждения, обеспечивающего выдачу кодов координат экстремального значения функции из блока 3 в блок 8 и запуска блока 6 управления.

Узел 103 предназначен для приема из схемы 102 сравнения и анализа результатов сравнения кодов значений функции, а также формирования, сигналов, обеспечивающих управление работой коммутатора 104, выдающего упорядоченные коды значений функции в блок 5 интерполя3S

13 9667 мы формирования синхронизируюших импульсов при наличии разрешающего сигнала с выхода триггера 74.

Вычитающий счетчик 69 предназначен для приема импульсов и формирования

S текущего кода числа шагов поиска и представляет собой двоичный реверсивный счетчик с цепями управления, выполненный на триггерах.

Наборный коммутатор 70 обеспечивают 10 ручное формирование кодов координат исходной точки поиска, кода ребра симплекса и кода константы и выполнен на тумблерах, на которые подается напряжение питания. IS

Тумблеры, .формирующие коды координат исходной точки поиска, подают напряжение на триггеры регистра 72. Коды ребра симплекса и константы подаются на входы триггеров регистра 40 и регист-.р0 ра 41 вычислительного блока 4. Число тумблеров равно сумме числа разрядов формируемых кодов.

Схема 71 сравнения предназначена для фиксации нулевого состояния вычита- у юшего счетчика 69 и формирования управляющего сигнала, переводящего триггер

74 в нулевое состояние.

Группа элементов И 75 обеспечивает передачу кода координат исходной точки поиска с выхода регистра 72 на вход .вычислительного блока 4.

Элементы задержки 76, 79,. 83 и 87 обеспечивают формирование синхронизируюших импульсов необходимой длительности.

Усилители 77, 80, 84 и 88 служат для формирования импульсов необходимой амплитуды после элементов задержки.

Триггеры 78, 81, 85 и 89 служат для формирования синхронизируюших импульсов необходимой длительности.

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

Блок 7 сравнения предназначен для последовательного приема из блока 1 па» мяти значений функции или блока 5 интерполяции кодов значений функции, запи50 си кодов во входные регистры, их попарного сравнения с целью отыскания максимального (в случае отыскания координат, соответствующих минимуму заданной функции) или минимального (в случае отыскания координат, соответствующих максимуму) значения функции и ,записи кодов значений в регистры в порядке убывания (возрастания).

15 96670 ции; формирование двоичного позиционного кода номера регистра, хранящего код экстремального значения функции, выдаваемого на дешифратор 105; формирование управляющих сигналов, обеспечивающих обнуление регистра, хранящего код экстремального значения функции, и перепись ( соответствующих кодов в регистрах 99, 100 и 101, Триггеры 128, 129 и 130 предназ- уй начены для приема из схемы сравнения

102 сигналов разности сравниваемых кодов, запоминания их и выдачи на входы элементов И 131-136;

Триггер 128 фиксирует результат срав-5 нения кодов, хранящихся в регистрах 99 и.100, триггер 130- кодов, хранящихся в регистрах 99 и 101, триггер 131 - кодов, хранящихся в регистрах 100 и 101.

Единичные состояния триггеров 128, 129 и 130 соответствуют результату сравнения "Больше", а нулевое состояние соответствует результату сравнения

Меньше" или "Равно", выдаваемым с выхода схемы сравнения 102. 2S

Для случая отыскания координат точки минимума анализируемой функции логика формирования управляющих сигналов представляется следующими выражениями: 5й, 1 . " - "t1 1, 6 = F13

ОЪ=F1%77,Л Е1Ъ, ОЬ = Е1Ъ7Fn Л11, где Г -, р., — коды значений функ11 j2 1Ъ ции, хранящиеся в регистрах 99, 100 и 101;

Ьяя 03 ц4,0,0$ управляющие сигналы»

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

Сформированные управляющие сигналы обеспечивают управление работой. комму- татора 104.

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

"1м.ох Ugvnax ц3иеох. где

1пиОх 11 F1ú 1 Ъ 11 1ъ 11 55

ОО,= F„%7Г„11 Г„ЪV Г1Х Г Ъъ F1.1, NeCia = F 1+ 117 Г1 Ч 1Ъ " < 11

3 16

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

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

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

Двоичный позиционный код, формируемый на выходах элементов ИЛИ 137, 138 и 139, может принимать значения

100, 010, 001. При комбинации 100 обнуляется регистр 99 по сигналу, поступающему с выхода элемента задеркки 140, на выходах элементов HE 143 и 144 формируется управляющие сигналы, разрешаюшие перепись кодов из регистра 100 в регистр 99 и из регистра

101 в регистр 100. При наличии сигна» ла на выходах элемента задеркки (комбинация 010) обнуляется регистр 100 и производится перепись кода из регистра

101 в регистр 100. При наличии сигнала на выходе элемента задержки 142 обнуляется регистр 101, перепись не производится.

Блок 8 предназначен для формирования и выдачи в блок 3 кодов координат вершины. симплекса для:, очереднрго .«Ф »» 4« шага поиска.. Значения координат новой вершины симплекса для очередного шага поиска вычисляются в соответствии с выражениями

Х ц+1 -Х ц1+ Х ц1+ Хц -ЙХ,ХЬГ

Ъ > ЧК+ М < ЦЕХ -, rge Хцк, щ - координаты вершины симплекса, К = 1, 2, 3;

Х Ч - координаты вершины

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

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

966703

Регистры 108-113 предназначены для приема из блока 3, хранения и выдачи, в соответствии с управляюшими сигналами, поступающими из блока 6 управления, .в сумматоры 122-125 кодов координат вершин симплекса.

Сумматоры 122, 123, 124 и 125 предназначены, соответственно, для формирования кодов сумм и выдачи кодов сумм в вычитатели 126 и 127 и пред- 1Ф ставляют собой поразрядные комбинационные сумматоры.

Вычитатели 126 и 127 обеспечивают формирование кодов . координат вершины симплекса посредством вычитания 1% из кодов сумм кодов удвоенных значений координат, доставляюших экстремум функции.

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

3, блока 5 интерполяции, блока 7 срав- 3ф нения, блока 8 суммирования обнулены, в соответствуюших ячейках блока 1 памяти значений функции записаны коды значений оптимизируемой функции; в ячейках блока 2 памяти значений переменных за- jg писаны коды адресов соответствуюших значений функции и коды координат точек, в которых произведено вычисление значений оптимизируемой функции; с помошью тумблеров блока 6 управления сформированы коды координат исходной, точки поиска, ребра симплекса и константы С (С = 0,57735).

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

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

Работа устройства в автоматическом режиме начинается по сигналу Пуск", поступаюшему на вход блока 6 управления. По этому сигналу, при условии нахождения в нулевом состоянии тригге» ра 74, через элемент И 68 переводятся в единичное состояние триггер 78, формируюший сигнал СИ 1 и триггер 74, разрешаюший выдачу синхронизируюших импульсов через элемент ИЛИ 67; устанавливается в исходное состояние вычитаюший счетчик 69 а выдаются в вычислительный блок коды координат ис ходной точки поиска. Длительность сигнала СИ 1 определяется временем распространения сигнала в элементе задержки 76 и должна обеспечивать устойчивое срабатывание триггеров 40, 41, 44 и 46 и вычислительного блока 4.

Одновременно с обнулением триггера

78 в единичное состояние переводится триггер 81, формируюший сигнал СИ 2, поступаюший в вычислительный блок 4 и обеспечиваюший формирование кодов координат вершин исходного симплекса. Сформированные коды координат вершин симплекса записываются через коммутатор 11 блока 3 s регистры 13, 14 и 15. Через время, определяемое элементом задеркки 79, триггер 81 обнуляется и в единичное состояние переводится триггер 85, формируюший сигнал СИЗ и выдаваемый в блок 3, запускаюший генератор 12 тактовых имйульсов с одновременным обнулением триггеров 25, 26 и 27 Одновременно по СИЗ в блок 8 выдаются сформированные коды координат симплекса, Генератор 12 тактовых импульсов формирует последовательность импульсов, . обеспечиваюших работу. блока 3. Счетчик 9 пос-. ледовательным суммированием импульсов формирует коды адресов ячеек блока 2 памяти значений переменных, по которым осушествляется их считывание и запись в регистры 16 и 17. В регистр 16 записывается код адреса ячейки блока 1 па мяти значения функции, а в регистр 17 записываются считанные коды координат значений. Счетчик 10 формирует последовательность из трех импульсов, обеспечиваюших последовательную выдачу из регистров 13, 14 и 15 кодов координат симплекса на входы схем сравнения 21, 22 и 23, обеспечиваюших сравнение кодов координат вершин исходного симплекса и кодов координат, храняшихся в регистре 17. В случае совпадения сравниваемых кодов на выходе соответствуюшей схемы формируется сигнал совпадеОЗ

19 9667 ния, переводяший один из триггеров 25, 26 и 27 в единичное состояние. Триггер, переведенный в единичное состояние. разрешает выдачу кода, храняшегося в регистре 16, в блок 1 памяти значений S функции, обеспечивая считывание кода значения функции из ячейки памяти по данному адресу. При отыскании всех кодов координат вершин симплекса триг геры 25, 26 и 27 переводятся в единич- 10 ное состояние и на выходе элемента И 24 сформируется высокий потенциал, останавливаюший генератор 12 тактовых импульсов, обнуляюший счетчик 9 и изменяюший состояние вычитаюшего счетчика 1$

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

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

B случае равенства кода значения функции нулю, с выхода схемы сравнения в блок 5 интерполяции и поступает управ- З0 ляюший сигнал, по которому формируется код интерполированного значения функции и через группу элементов И 97 и коммутатор 98 записывается в обнуленныйрегистр 101. Коды значений функции. записанные в регистрах 99, 100 и 101 последовательно сравниваютСя в схеме

102 сравнения с последуюшим анализом в узле 103 управления кода разно сти.

Упорядоченные коды значений функции через коммутатор 104. переписываются в регистры 59, 60 и 61 блока 5 интерполяции. С выхода дешифратора 105 управляюшие сигналы поступают на группы элементов И 31, 32 и 33, разрешая выдачу кодов координат вершины, для которой значения функции приняло экстремум, в блок 8, и на выход коммутатора 11, обнуляя регистр, храняший коды, и на

50 вход элемента И 86 через элемент 73 блока 6 управления, разрешая формирование сигнала СИ 4, обеспечиваю пего формирование кодов координат новой вершины снмнлекса в блоке 8. По сигналу

SS

СИ 4 в блоке 8 на входы сумматоров

122-125 и вычитателей 126 и 127 выдаются коды координат вершины симплекса, по которым. формируются коды, поступаюшие на вход коммутатора 11 и записываемые в обнуленный регистр координаты вершины симплекса блока 3. По окончании сигнала СИ 4 триггер 89 переводится в нулевое состояние, разрешая формирование сигнала СИ 3 и запуская генератор 12 тактовых импульсов, цикл работы устройства повторяется. Счетчик

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

74 в нулевое состояние, формируя на выходе блока 6 управления сигнал СИ 5. По сигналу СИ 5, поступаюшему в блок 3, на группу элементов И 38, на выход устройства выдаются коды координат точки экстремума функции двух переменных.

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

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

Работа устройства в режиме диалога не отличается от работы в автоматичес« ком режиме и полностью соответствует работе, описанной выше.

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

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

966703

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

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

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

50 седьмой групп соединены с выходом первого счетчика, вход которого и первый вход второго счетчика соединены с выходом генератора тактовых импульсов, выход второго счетчика является первым выходом блока, первый вход блока подключен к входам регистра адреса и регистра переменных, выход которого соединен с первыми входами первой„второй и третьей схем сравнения, вторые входы которых подключены соответственно к выходам элементов И первой, четвертой и седьмой групп, выходы схем сравнения соединены соответственно с первыми вхо дами первого, второго и третьего триггеров, вторые входы которых и первый вход генератора тактовых импульсов подключены к второму входу блока, выходы триггеров соединены соответственно с первыми входами первого, второго и третьего элементов И и с первым, вторым и треть им входами четвертого элемента И, выход последнего подключен к вторым входам генератора тактовых импульсов, второго счетчика и к третьему выходу блока, вторые входы первого, второго и третьего элементов И подключены к выходу регист» ра адреса, а выходы соединены с вторым выходом блока, вторые входы элементов

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

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

И первой группы соединены с информационным входом блока, выход регистра кода ребра подключен к первым входам элементов И второй группы, выход регистра константы подключен к первым входам элементов И третьей группы, вторые входы элементов И второй и третьей . групп подключены к управляюшему входу блока, выходы элементов И первой группы подключены к входам первого и второго регистров координаты, выходы элементов И второй группы соединены с входом сдвигателя и с первым входом первого умножителя, второй вход которого и первый вход второго умножителя соеди23 9667 иены с выходами элементов И третьей группы. выход первого регистра координаты подключен к первым входам первого сумматора и первого вычитателя и к входу первого регистра, выход второго регистра координаты соединен с -первыми входами второго вычитателя и второго сумматора, выход сдвигателя подключен к вторым входам первого сумматора, первого вычитателя и второго умножите- 30 ля, выходы первого и второго умножителей соединены соответственно с вторым входом второго сумматора и с вторым входом второго вычитателя. выход кото» рого соединен с входами второго и треть-!5 его регистров, выходы первого и второго сумматоров и выход первого вычитателя соединены соответственно с входами четвертого,. пятого и шестого регистров. 20

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

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

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

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

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

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР № 402001, кл, 606 F 15/36, 1971.

2. Авторское свидетельство СССР № 696479, кл. G06 F 15/34, 1977.

3. Заявка ФРГ ¹ 2421330, кл. 6 06F 7/37, 1977 (прототип).

066703

Составитель А. Жаренов

Редактор Л. Авраменко ТехредМ. Гергепь Корректор С. Шекмар

Заказ 7 8 46/67 Тираж 731 Подписное

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

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

Филиал ППП "Патент, г. Ужгород, ул. Проектная, 4