Устройство для управления решением многоэкстремальных оптимизационных задач Советский патент 1986 года по МПК G06F17/11 

«.1

Изобретение относится к вычислительной технике, в частности к устройствам гибридных вычислительных машин, управляющих процессом решения- отыскания минимумов или максимумов некоторой целевой функции, и может быть использовано в различных областях народного хозяйства, где применяется гибридная вычислительная техника для решения многоэкстремальных оптимизационш 1х :и других сводимьпс к ним инженар,нь№ задач, например, при управлении технолсугическими процессами или экcпёi имeнтaми.

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

На фиг.1 представлена схема пред- лагаемого устройства; на фиг,2- граф, описывающий работу блока задания направления поиска; на фиг.3 - таблица программирования узла памяти для К и 8; на фиг,4 - схема п.ёреклю- чателя; на фиг,5 - схема узла задержки; на фиг,6 - пример регшизации схемы сравнения, .

На фигурах приняты следующие обог значения: генератор 1 тактовых импульсов, блок 2 задания (коммутатор) направления поиска, блок 3 формирования признаков направлений, счетчик 4 адреса, дешифратор 5, блок 6 формирования направлений поиска, узел 7 памяти, триггер 8 реверса, группа 9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вход 10 и выход П устройства, элемент 12 ИС- КЛЮЧАЩЕЕ ИЛИ, переключатель 13, блок 14 переключателей, блок 15 задания цели поиска, элемент 16 ИСКЛЮЧАНМЦЕЕ ИЛИ, триггер 17, элемент 18 И-НЕ, узел 19 задержки, схема 20 сравнения элемент 21 ИСКЛЮЧАЩЕЕ ИЛИ, счетчик 22 циклов, элементы 23, 24 И, элемент 25 И-НЁ, элемент 26 НЕ, счетчик 27, переключатель 28, схема 29 сравнения элементы 30, 31 И-НЕ, триггер 32, элементы 33 ИСКЛЮЧАЮПЩЕ ШЩ, элементы 34, 35 И-НЕ,

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

В составе гибридной вычислитель- ной машины устройство осуществляет управление процессом отыскания значений переменных, которым -соответствуют минимальные или максимальные в некоторой окрестности (локальные) значения целевой или вспомогательной функции, к оптимизации которой сводится .решение исходной задачи, Опти011 мизируемая функция может иметь как унимрдальньМ (одноэкстремальный), так и мног.оэкстремальный характер. Реализуемый устройством процесс поиска состоит из двух уровней: уровня локального поиска, реализуемого блоками 2, 3 и 6 и обеспечивающего нахождение минимума (максимума) целевой функции, в. зоне притяжения которого находилась начальная точка поиска; уровня глобального поиска, реализуемого элементом 12, переключателем 13, блоками 15 и 14 и обеспечивающег исследование пространства переменных задачи указанными локальными поисками с целью отыскания всех локальных минимумов (максимумов). Процесс управления поиском на локальном уровне состоит в поочередном формиров ании, инвертировании при необходимости и фиксировании на некоторое время на выходе 11 устройства tt -компонентных

у

двоичных векторных сигналов S(x,,,, ,,,, X ), задающих направления изменения искомых переменных. Значение каждой из компонент задает скорость и знак изменения во времени соответствующей переменной, а в совокупност определяет скорость и направление движения в пространстве переменных точ&и поиска задаваемой текущими значениями цеременных (координат) , Формуемые устройством направления 1,,,, ,k принадлепоиска S

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

Однако в отличие от входного сигнала С) значение которого б О соответствует убыванию целевой функции а б I - возрастанию, соответствие между значенийми сигнала б и изменением целевой функции зависит от сиг нала цели поиска об , поступающего на вход элемента 12.При о6 , а при ei .(j , т.е. указанное соответствие становится обратными при возрастании функции б О, а пр убьюании (J 1..

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

После появления.сигнала б I по ближайшему сигналу с блок 2 переходи в состояние Н, где формируется команда ) и происходит переход на но- вое, следующее по циклу направление поиска S . Если в направлении сигнал б I, то блок 2 переходит в состояние Р, где формируется команда р и осуществляется реверс дви женин точки Т1§)иска в направлении S путем его инвертирования (S ). Дальнейшее сохранение d 1 приводит к чередующимся переходам по каждому между состояниями Н и Р и поочередному формированию команд И р до появления сигнала С; О и возврата блока 2 по условию б Г в состояние удержания направления ИСХ. Обычно каждое новое направ- дном из -знаков движения

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

Команды 9 поступают в блок 3 на счетный вход счетчика 4. При этом счетчик циклически меняет выходной код ,. задающий номер формируемого устройством направления S Номер направления преобразуется дешифратором 5 в позиционный сигнал, который поступает на вход считьгоания узла 7 памяти в блике 6. В результате на входы группы 9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ поступает двоичный век-

ление при о ( или S

торный сигнал, представляющий соответствующее направление поиска S

, - . и 10

- яf5 я я 20 .

т . 3540

45

50 55

30

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

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

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

ния,

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

Уровень глобального поиска, целью которого является общее исследование пространства переменных и отыскание всех локальных решений (минимумов X ) в случае многоэкстремальной задачи реализуется в устройстве на основе указанного локального поиска-- путем чередования процессов минимизации и максимизации. Управление чередования осуществляется выходным сигналом Л. блока 15. Сигналов значением Л О ставит элемент 12 в режим повторения входного сигнала d , т.е, задает соответствие б С5 и процесс минимизации целевой функции. Значение oi 1 задает режим инвёртирова- НИН входного сигнала, т.е. соответствие ( 0 и процесс максимиза- ции.

Вк чение поиска максимума при нахождении переменных в зоне минимума (результата предшествовавшего прис ка минимума) приводит к переходу значе- НИИ переменных в зону одного из соседни максимумов или выходу на границу шкалы переменных. Попадание в тот или иной максимум зависит от положения точки поиска относительно точки дан ного минимума целевой функции в мо- мент изменения цели поиск;а, а также от направления изменения переменных S в этот момент. Точка минимума, как правило, лежит на границе зон притяжения соседних максимумов. Для используемого алгоритма локального поиска характерны значительные взаимные наложения зон притяжения локальных минимумов (MaKCHHyMOB)j, связанных с выбором конкретного направления начального изменения переменных. Такая же ситуация имеет место и при переходе на поиск минимума после нахождения точки максимума или выхода на границу шкалы.

В устройстве предусмотрены три режима управления изменением сигнала ot; непосредственного ручного изменения; автоматического изменения через заданные интервалы времени; автоматического изменения с дополнительным условием по направлению поиска S .

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

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

с

5 0 5 0 ,

в состояние : 1 (сигнал;) и удерживает в нулевом состоянии счетчик 22 циклов.

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

Сигнал имеет значение О и совпадает с одним из сигналов J . Сигнал |U формируется по условию 6 « Тч. реализуемому элементом

5

0

5

50.

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

Поскольку после изменения цели поиска данное направление S дает нужное изменение целевой функции, в устройстве предусмотрена блокировка формирования команды ) - сигнал (U блокирует прохождение сигнала 1 на блок 2 через переключатель 13. С

.этой целью для выравнивания моментов прихода на элеме нт 24 И (фиг.4) сигналов (а и t переключатель 13 содержит входной элемент 23 И, компенсирующий задержку формирования сиг нала (И , В следукиций тактовый момен;

it после изменения цели поиска ( вертирования сигнала б) условне 0. t He выполняется и движение в заданном направлении сохра яяется,

Сигнал ju поступает также на вход узла 19 задержки и устанавливает (задним фронтом) сигнал в значение О - блокировки формирования снгнаяа (U . ,

Узел 19 работает следунщим обра- .

зом.

Тактовые сигналы Z поступают на

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

счетчиком заданной величины выходной сигнал на инверсном выходе схемы 29 сравнения блокирует дальнейшее прохождение сигналов 7 на вход счетчи- j ка, а сигнал с выхода элемента 26 НЕ передним фронтом перезаписьшает в триггер 32 сигнал на прямом выходе схемы 29 сравнения. Выходной сигнал на прямом выходе триггера 32, форми- ю руемый по заднему фронту сигнала , и представляет сигнал . Указанное заблокированное состояние узла 19 задержки сохраняется до прихода на вход установки в нуль счетчика-27- js сигнала Ц , После сброса счетчика в нуль по переднему фронту сигнала lu (т.е. S ) по заднему фронту (Г) пе-. реводится в исходное состояние триггер. Введение задержки снятия сигнала 20 связано с предупреждением укорочения сигнала |u .

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

Режм автоматического изменения сигнала ( с .дополнительным условием 35 по направлению поиска включается одновременным формированием сигналов на втором и третьем выходах блока 14. Работа устройства в данном режиме отличается от рассмотренного режима работы включением в приведенное условие формирования. сигнала fj дополнительного условия. Сигнал I формируется схемой 20 сравнения при , совпадении двоичного кода текущего

направления изменения переменных иЪиг- нала знака движения в заданном направлении R с контрольными значениями

Z у

кода f и сигнала R. Сигнал у формируется счетчиком 22 циклов, Ка 0 счетный вход счетчика 22 поступает выходной сигнал л триггера 17 и изменяет его состояние при каждом переходе из 1 в О, т.е. по каждому второму сигналу fu , Первые m разря- 55

дов счетчика циклов используются как контрольный код f номера направг ления, а разряд (m+l) - как сигналу

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

Таким образом, в этом режиме изменение сигнала ti (формирование сигнала IU) также происходит после прихода сигнала 1 по условию d но не на любом направлении поиска а только при изменении переменных в направлении j со знаком R R Контрольный код о остается неизмен 0

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

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

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

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

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

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

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

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

6Ч

gjuff.Z

tpU9.y

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

фие.

фиг:В

- - . о .

дуиеб

Составитель А. Жаренов Редактор С. Лкскяа Техред Н.Вояк ало; Корректор А. Обручар

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий И3035, Москва, Ж-35, Раушская наб., д.4/5

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