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

 

Изобретение относится к вычислительной технике и может быть использовано для решения миогоэкстремальных, оптимизационных и других сводимЬ1Х к ним инженерных задач. . « 1 Целью изобретения являетсяповышение быстродействия и расширение функйиональных возможностей за счет обеспечения решения многоэкстремальньрс задач. Устройство содержит генератор I тактовых импульсов, блок 2 задания направления поиска, .блок 3 формирования признаков направлений, включающий счетчик 4 адреса и дешифратор 5, блок 6 формирования направлений поиска , включающий узел 7 памяти, триггер 8 реверса, группу 9 элементов ИСКЛЮЧАКНЦЕЁ ШШ, элемент 12 ИСКЛЮЧАЮЩЕЕ ИЛИ, переключатель 13, блок 14 / переключателей, блок 15 задания цели поиска , включающий элемент 16 ИСКЛЮЧАЮЩЕЕ ШШ, триггер 17, элемент 18 И-НЕ, узел 19 задержки, схему 20 Сравнения, элемент 21 ИСКЛЮЧАВДЕЕ ИЛИ, счетчик 22 циклов. Устройство обеспечивает автоматическое изменение цели поискаминимизации на максимизацию и наоборот в зависимости от хода поиска, а также комбинированное применение различных режимов управления. 6 ил. 8 СО

СООЭ СОВЕТСКИХ

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

РЕСПУБЛИК (19) (1!1 (5D 4 G F !5/20 (21) 3814758/24-24 (22) 14.11.84 (46) 15.06.86. Бюл. h» 22 (71) Институт проблем моделирования в энергетике АН УССР (72) К.И. Гищак (53) 681.325.22(088.8) (56) Грездов Г,И., Гнщак К.И.. Гибридные дйфференциальные методы нахождения экстремумов. Гибридные вычислительные системы н комплексы: Сборник. Вып.l, Киев: Наукова думка, 1979.

Грездов Г.И. Теория и применение гибридных моделей. Киев: Наукова думка, 1975, с.48-.5.1, рис.20-23, (54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ РЕШЕНИЕМ МНОГОЭКСТРЕИАЛЬНЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ (57) Изобретение относится к вычис" лительной технике и может быть использовано для решения многоэкстре,мальных, оптимизационных и других сводимых к ним инженерных задач.

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

ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент 12 ИСКЛЮЧАЮЩЕЕ ИЛИ, переключатель 13, блок 14 переключателей, блок 15 задания цели по" иска, включающий элемент 16 ИСКЛЮЧАЮЩЕЕ ИЛИ, триггер 17, элемент 18 И-НЕ, узел 19 задержки, схему 20 сравнения, элемент 21 ИСКЛЮЧАЮЩЕЕ ИЛИ, счетчик

22 циклов. Устройство обеспечивает автоматическое изменение цели поиска" минимизации на максимизацию и наоборот в зависимости от хода поиска, а также комбинированное применение различных режимов управления. 6 ил.

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

Цель изобретения — повышение быстродействия.

На фиг.1 представлена схема предлагаемого устройства; на фиг. 2 - граф, описывающий работу блока задания направления поиска; на фиг.3 — таблица программирования узла памяти для

K = и = 8; на фиг.4 — схема переключателя; на фиг.5 — схема узла задержки; на фиг.6 — пример реализации ,схемы сравнения.

На фигурах приняты следующие обозначения: генератор 1 тактовых импульсов, блок 2 задания (коммутатор) направления поиска, блок 3 формирования признаков направлений, счетчик 4 адреса, дешифратор 5, блок 6 формирования направлений поиска, узел 7 памяти, триггер 8 реверса, группа 9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вход 10 и выход 11 устройства, элемент 12 ИСКЛЮЧАЮЩЕЕ ИЛИ, переключатель 13, блок

14 переключателей, блок 15 задания цели поиска, элемент 16 ИСКЛЮЧАЮЩЕЕ

ИЛИ, триггер 17, элемент 1.8 И-НЕ, узел 19 задержки, схема 20 сравнения, элемент 21 ИСКЛЮЧАЮЩЕЕ ИЛИ, счетчик 22 циклов, элементы 23, 24 И, элемент

25. И-НЕ, элемент 26 НЕ, счетчик 27, переключатель 28, схема 29 сравнения, элементы 30, 31 -HE, триггер 32, элементы 33 ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы 34, 35 И-HE.

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

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

Реализуемый устройством процесс поиска состоит из двух уровней: уровня локального поиска, реализуемого блоками 2, 3 и 6 и обеспечивающего на" хождение минимума (максимума) целевой функции, в. зоне притяжения которого находилась начальная точка поиска; уровня глобального поиска, реализуемого элементом 12, переключателем.

13, блоками 15 и 14 и обеспечивающего исследование пространства переменных задачи указанными локальными поисками с целью отыскания всех локальных минимумов (максимумов), Процесс управления поиском на локальном уровне соСтоит в поочередном формировании, 2О инвертировании при необходимости и фиксировании на некоторое время на выходе 11 устройства 11 -компонентных двоичных векторных сигналов Я=(х,,... х„), задающих направления изме25 нения йскомых переменных. Значение каждой из компонент задает скорость и знак изменения ао времени соответствующей переменной, à в совокупности определяет скорость и направление движения в пространстве переменных точили поиска, задаваемой текущими значениями переменных (координат) .

Формуемые устройством направления поиска $, 3 = 1,...,k принадлежат некоторой заранее .выбранной системе направлений поиска, записанной в виде соответствующих векторов в узле 7 памяти. Оттуда они в параллельной форме поочередно выводятся

40 пРямо или инвертируясь. Инвертирование направления (реверс) меняет знак движения точки поиска в этом направлении. Сохранение направлений,их изменение на следующее по циклу инвертирование задается блоком 2, который

45 по сигналам генератора 1 тактовых импульсов формирует команды перехода на новое направление 4 и реверса направления ) ° Формирование команд и Р осуществляется в зависимости от

% О входного сигнала блока б, принимающего как и входной сигнал устройства

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

Однако в отличие от входного сигнала (j значение которого б 0 ао.—

3 . )238 ответствует убыванию целевой функции, а 6 = 1 — возрастанию, соответствие между значени|!ми сигнала G и иэмене» кием целевой функции зависит от сигнала цели поиска ос, поступающего на вход элеМента 12. При < = О 6" = 6

7 а при е = 1 6 = 6, т.е. указанное соответствие.с !ановится обратным. при возрастании функции б = О, а при убывании 0 + = !, 1О

Блок 2, работа которого описывается графом, приведенным на фиг.2, при Q» О (независимо от соответствия между сигналами 6 и G находится

» в исходном состоянии "ИСХ" и удер 15 живает заданное направление изменения переменных B до появления сигнала % б = 1. При 5 о это означает дви», жение в. направлении 1 до прохождения

4. в нем минимума целевой функции, а .) Ф при о б — до прохождения максимума.

После появления. сигнала 6 = по ближайшему сигналу с блок 2 переходит в состояние "Н", где формируется ко. маида Э и происходит переход на новое, следующее по циклу направление з+| ф+1 поиска S .- Если в каправлении S

% сигнал б = 1, то блок 2 переходит в состояние "P" где формируется команда р и осуществляется реверс движения точки приска в направлении

=|+1

S путем его инвертирования (S ).

Дальнейшее сохранение б = приводит к чередующимся переходам по каждому между состояниями "Н" и "Р" 35 и поочередному формированию команд и до появления сигнала б» = О и возврата блока 2 по условию б в состояние удержания направления

Н И

ИСХ . Обычно каждое новое направ- 4о ление при одном из знаков движения +1 (S или S . ) дает некоторое убывание значений функции, если процесс не находится в зоне минимума (макси- мума). 45

Команды 9 поступают в блок 3 на счетный вход счетчика 4. При этом . счетчик циклически меняет выходной

| г код г, задающий номер формируемого устройством направления .S

Номер направления преобразуется дешифратором $ в позиционный сигнал, который поступает на вход считывания узла 7 памяти в бл4ке 6. В результате на входы группы 9 элементов ИСКЛ!0-55

ЧАЮЩЕЕ ИЛИ поступает двоичный век-торный сигнал, представляющий соответствующее направление поиска S

101 4

Команды Р поступают в триггер 8, и каждая очередная команда р вызывает изменение на противоположное значение его выходного сигнала. Последний поступает на управляющий вход группы 9 элементов и задает прямое или инверсное прохождение на выход ll устройства вектора S

На фиг.3 приведена таблица используемой в устройстве системы направлений поиска при |! = 8, записанная в узле 7 памяти. В данном случае система 8-мерных направлений S содер жит минимальное число (k = n) направлений — 8, в качестве которых используется система функций Уолша-Адамара, обладающих свойством взаимной ъ ортогональности. Каждая компонента

) вектора S принимает значения,О или

1, задающие возрастание или убывание соответствующей переменной с фиксированной скоростью.

Указанный алгоритм управления изменением переменных обеспечивает быстрое отв|скание минимума (максимума! целевой функции, в зоне притяжения которого находилась начальная точка поиска, при условии, что функция имеет ограниченную скорость измене"

2+ ния, причем при v = О идет процесс минимизации функции, а при 0 " б максимизации. Особенностью процесса поиска является отсутствие нулевой скорости изменения переменных и про" должение поиска и после достижения минимума (максимума). При этом, если вдали от минимума траектория движения точки поиска состоит из более или.менее продолжительных продвижений

4 в направлениях S,,то в зоне минимума процесс сводится к непрерывному перебору направлений и небольшим продвижением в них, т.е. высокочастотным колебаниям переменных относительно точки минимума х» (максиму)0 Ф ма х ). Амплитуда колебаний определяется запаздыванием в общем контуре управления, числом переменных, скоростью их изменения и др.

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

+ х „„„ ) в случае многоэкстремальной задачи реализуется в устройстве на основе указанного локального поиска путем чередования процессов минимизации и максимизации. Управление че1238101 редования осуществляется выходным сигналом . блока 15. Сигнал значением и = 0 ставит элемент:12 в режим повторения входного сигнала б, т.е, + задает соответствие б = б и процесс минимизации целевой функции. Значение о = 1 задает режим инвертирования входного сигнала, т.е. соответствие Д" = б и процесс максимиза- 10 ции.

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

S в этот момент. Точка минимума, как правило, лежит на границе зон притяжения соседних максимумов.

Для используемого алгоритма локального поиска характерны значительные взаимные наложения зон притяжения локальных минимумов (максимумов), связанных с выбором конкретного направления начального изменения перемен енных Такая же ситуация имеет место и при переходе на поиск минимума после нахождения точки максимума или выхода на границу шкалы.

В устройстве предусмотрены три

P ежима управления изменением сигнала

К: непосредственного ручного изменения автоматического изменения через

Ф заданные интервалы времени; автоматического изменения с дополнительным

4 условием по направлению поиска S

Непосредственное ручное изменение сигнала А осуществляется иэмене45 кием состояния (нажатое ненажатое) соответствующего переключателя блока 14 и изменением значения сигнала на входе элемента 16 ИСКЛЮЧАЮЩЕЕ ИЛИ.

Режим автоматического изменения 50 сигнала и через заданные интервалы времени включается нажатием соответствующего переключателя в блоке 14 г и снятием блокировки элемента 18

И-НЕ и установки в нуль триггера 17.

В этом режиме сигнал с третьего выхода блока 14 блокирует работу схемы

20, устанавливая ее выходной сигнал в состоянйе; "1" (сигнал 9 ) и удерживает в нулевом состоянии счетчик

22 циклов.

Изменение сигнала О происходит при поступлении на счетныи вход триггера 17 сигнала 11 с выхода элемента

18. Выходной сигнал c(триггера 17, представляющий предварительный сигнал цели поиска, прямо или, инвертируясь элементом 16, поступает на вход элемента 12 как сигнал IL

Сигнал р имеет значение 0 и совпа" дает с одним из сигналов, . Сигнал формируется по условию б» с х хТ 3 реализуемому элементом заЬ

18. Как видно из условия, фор-; мирование сигнала pt (так как Яф происходит после прихода на вход элемента 18 сигнала Т = 1 по ближайшему условию б"С, по которому в блоке 2 формируется команда т.е. после прохождения минимума (максимума) в текущем направлении S, Поскольку после изменения цели

1 поиска данное направление S дает. нужное изменение целевой функции, в устройстве предусмотрена блокировка формирования команды — сигнал у блокирует прохождение сигнала на блок 2 через переключатель 13. С .этой целью для выравнивания моментов прихода на элемент 24 И (фиг,4} сигналов р и ь переключатель 13 содержит входной элемент 23 И, компенсирующий задержку формирования сигнала (0, В следующий тактовый момен после изменения цели поиска (инвертирования сигнала 5 ) условие ,Ф

g"., не выполняется и движение в заданном направлении сохраняется.

Сигнал р поступает также на вход узла 19 задержки и устанавливает (задним фронтом) сигнал Т „ в значение 0 — блокировки формирования сигнала (Ь, Узел 19 работает следующим образом.

Тактовые сигналы и поступают на счетный вход счетчика 27 через элемент 25- И-НЕ, Выходным сигналом счетчика являются старших разрядов, младший иэ которых соответствует требуемой дискретности задания задержки формирования сигнала задержки. Выходной код счетчика сравнивается в схеме 29 сравнения с выходным кодом переключателя 28, который задается оператором. При достижении

1238101 счетчиком заданной величины выходной сигнал на инверсном выходе схемы 29 сравнения блокирует дальнейшее прохождение сигналов на вход счетчи- ка, а сигнал Г с выхода элемента 26

НЕ передним фронтом перезаписывает в триггер 32 сигнал на прямом выходе схемы 29 сравнения. Выходной сигнал . на прямом выходе триггера 32, форми- руемый по заднему фронту сигнала с

1 и представляет сигнал Т д . Укаэанное заблокированное состояние узла 19 задержки сохраняется до прихода на вход установки в нуль счетчика 27 . сигнала ш . После сброса счетчика в нуль по переднему фронту сигнала ш (т.е. b ) по заднему фронту !!1 (С) переводится в исходное состояние триггер, Введение задержки снятия сигнала 20

Т ц связано с предупреждением укорочения сигнала ш .

Таким образом, в рассмотренном режиме устройство обеспечивает автоматическое изменение цели поиска — ми- 25 нимизации на максимизацию и наоборот в моменты выполнения условия б" =1 с одновременной блокировкой формирования команды 1 . После каждого изменения цели поиска обеспечивается 30 блокировка на некоторый регулируемый интервал времени возможного изменения цели поиска, четности цикла задания кода о

Сигнал устанавливает прямое или инверсное прохождение сигнала К через элемент 21, используемого далее в качестве контрольного сигнала В

Таким образом, в этом режиме изменение сигнала (формирование сиг0 нала р) также происходит после прихода сигнала .Т ; = 1 по условию о Р, Р но не на любом направлении поиска а только при изменении переменных в

2 напрарлении (со знаком R = R .

Контрольный код остается неизмено ным на паре поисков минимизация— максимизация, тогда как сигнал R изменяется в два раза чаще, причем фаза его изменения на четных и нечетьt ных циклах задания кода противо o„ положная. В результате устройство обеспечивает переход, например, с минимизации на максимизацию последовательно на каждом из направлений

S и S . .и промежуточные переходы от максимизации к минимизации при противоположном знаке движения R

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

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

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

Работа устройства в данном режиме отличается от рассмотренного режима работы включением в приведенное условие формирования. сигнала р дополнительного условия. Сигнал 1 » = 1 формируется схемой 20 сравнения при совпадении двоичного кода текущего 45 . направления изменения переменных и сигнала знака движения в заданном направлении R с контрольными значениями

2 3 2 кода (и сигнала R, Сигнал у формируется счетчиком 22 циклов. Ffa счетный вход счетчика 22 поступает выходной сигнал триггера 17 и изменяет его состояние при каждом переходе из "1" в "0", т.е. по каждому второму сигналу !!! . Первые е разря,дов счетчика циклов используются

2 как контрольный код (номера направления,. а разряд (ш+1) — как сигнал 1" о

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

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

ИЛИ, блок, переключателей и блок задания цели поиска, включающий первый и второй элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент И-НЕ, триггер, узел задержки, счетчик циклов и схему сравнения, информационные входы которой соединены соответственно с выходами разрядов счетчика адреса, с выходами П1 разрядов счетчика циклов,,с выходами триггера реверса и первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первые входы первого н второго элементов ИСКЛЮЧАЮЩЕЕ ИЛИ блока задания цели поиска и счетный вход счетчика циклов соединены с выходом триггера, выход (m+1 l-ãî разряда счетчика циклов соединен с вторым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый выход блока пере;лючателей соединен с вторым входом второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ блока . задания цели поиска, выход которого соединен с первым входом элемента

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

20 с управляющим входом коммутатора направления поиска, управляющие входы переключателя, узла задержки и счетный вход триггера соединены с выходом элемента И-НЕ, третий и 5 .четвертый входы которого соединены соответственно с выходами узла задержки и-схемы сравнения, пятый, вход элемента И-НЕ и установочный вход триггера соединены с вторым выходом р блока переключателей, третий выход которого соединен с установочным входом счетчика циклов и управляющим входом схемы сравнения.

123810.1 авив 3

1238101

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

Редактор С. Лисина Техред.H.3оикало.. Корректор А. Обручар

Заказ 3294/51 Тирам 671, Подписное

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

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

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

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

 

Похожие патенты:

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

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

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

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

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

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

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

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

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