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

1

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

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

На фиг.1 приведена схема устройства; на фиг,2 - граф, по которому реализуется коммутатор направлений поиска; на фиг.З - схема переключателя; на фиг.4 - таблица программирования постоянного запоминаюш,его устройства.

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

Коммутатор 2 предназначен для формирования сигналов управления направлением поиска и реверсом движения в направлении S в зависимости от текущего значения сигнала изменения вспомогательной функции 6 . Коммутатор 2 выполнен по известньгм принципам и представляет собой автомат, описываемый графом, приведенным на фиг.2, где 6 ,1 - входные сигналы; i), р - команды, вырабатываемые автоматом в соответствуюиц х состояниях.

Узел 7 памяти выполнен в виде постоянного запоминающего устройства на К п-разрядных слов, представляющих направления поиска S(S ,... ) . На фиг. 4 показана таблица прог

раммирования постоянного запоминающего устройства для t п 8.

Триггер 8 предназначен для формирования сигнала R знака движения в заданном направлении и выполнен в виде счетного триггера.

Группа 9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ предназначена для умножения ком- вектора S на сигнал R знаюа

0

5

0

движения в заданном направлении, число элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соответствует числу компонент векто- ,ра S .

Триггер 12 цикла предназначен 5 для формирования сигнала завершения цикла перебора направлений и может быть вьшолнен в виде счетного триггера.

Регистр 17 сдвига предназначен для предотвращения случайного формирования сигнала признака минимума.

Переключатель 13 предназначен для распределения сигналов, постут1а ощих с генератора 1 тактовых сигналов на реверсивного счетчика 14 в зависимости от сигнала изменения вспо- нога.тельной функции & .

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

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

Процесс управления поиском состо- ит в поочередном формировании, инвертировании, при необходимости, и фиксировании на некоторое время на выходе 11 устройства п -компонентных двоичных векторных сигналов, задающих на.правления изменения искомых ременных решаемой задачи (минимизируемой функции), а также в формировании на выходе 18 сигнала uiJ при до.сти ;ении процессом поиска минимума (решения). Значение каждой из компо55 нент Xf ,,..., Xh задает скорость и знак изменения во времени соответствующей переменной, что в совокупности определяет скорость и направ45

3

ление движения в пространстве пере- ме.нньгх точки поиска, задаваемой тек щими значениями переменных (координат) .

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

поиска в этом направлении. I

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

В соответствии с целью поиска - минимизацией значения целевой функции коммутатор 2 удерживает направление S, дающее убывание значения функции, до прохождения минимума в этом направлении и появления сигнала 6 1. Затем по ближайшему сигналу t формируется команда v , и если в новом направлении S сигнал t 1 далее, то по последующему 1 формируется команда f . Поочередное генерирование команд ii и р продолжается до появления сигнала Г 0, т.е. до нахождения направления, дающего убывание значения функции. Обычно первое же новое направление при одном из знаков дает убьшание значения функции на некотором отрезке.

Работа коммутатора 2, представляющего собой дискретный автомат, описьшается графом (фиг.2). Состояние Исх соответствует удержанию направления. В него автомат возвращается из состояний Н и Р по условию &Г , т.е. при появлении сигнала & 0. По условию S t автомат переходит из состояния Исх в состояние Н, где формируется командаV , и далее, если Й 1 , поочередно по

44682 ,4

сигналам Т меняет состояния Н и р (команда р ) цо появления сигнала S 0 и возврата в состояние Исх

Команды поступают в блок 3 на 5 счетный вход счетчика 4. При этом счетчик циклически меняет выходной код, задающий номер формируемого устройством направления. Номер направления преобразуется дешифратором 5 в 10 позиционный сигнал С ( 1 ,. . . ,f К) , который поступает на соответствующий вход считывания узла 7 памяти в блоке 6 . В результате на входы элементов 9 из узла 7 памяти поступает дво15 ичный векторный сигнал, представляющий соответствующее направление поиска.

Команды р поступают в триггер 8, представляющий собой счетный триггер.

20 Каждая очередная команда вызывает изменение на противоположное значение выходного сигнала триггера 8.:-Послед- НИИ поступает на входы элементов 9 и задает прямое () либо инверсное

25 () прохождение на выход устройства 11 вектора S.

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

35 возрастание или убьшание соответствующей переменной с фиксированной скоростью.

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

Формирование сигнала J признака достижения процессом поиска минимума

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

Формирование сигнала сх) осуществляется путем подсчета на периоде перебора направлений поиска разности числа сигналов t на интервалах времени, когда сигнал 6 0 (1 °) и когда (t , до появления устойчивой величины оценки на нескольких

циклах перебора. Подсчет числа L

и о существляется с помощью реверсивного счетчика 14, устанавливаемого в нулевое состояние в начале каждого цикла. Переключатель 13 в зависимости от значения входного сигнала устройства & подключает тактовые сигналы к входу прямого (при ) или обратного (при 6 1) счет реверсивного счетчика 14. Емкость реверсивного счетчика выбирается исходя из максимального возможного продвижения в сторону минимума на цикле направлений поиска с учетом частоты сигналов и должна быть око(f - частота сигналов

ло /V,

V -скорость изменения переменной в относительных единицах), что со- ставЛяет 2-2

г

На входы элемента ИЛИ 15 подаются m старших разрядов счетчика. В результате при появлении единиц в этих разрядах, т.е. при достижении разностью l ° -Л определенной величины, на выходе элемента 15 воз- сигнал 1 . В конце каждого цикла значение выходного сигнала aj заносится в триггер 16, а информация с триггера 16 заносится в регистр 17. Одновременно сигнал с выхода триггера 16 поступает на вход

установки в нуль регистра 7 и в случае cJ 0 устанавливает его в нулевое состояние.

Прием и сдвиг информации в регистре 7 происходит по заднему фронту выходного сигнала триггера 12 цикла, этот же сигнал передним фронтом устанавливает в нуль реверсив- ный счетчик 14 и записывает значение сигнала cJ в триггер 16.

Формирование сигнала J на выходе 18 происходит при сдвиге через, все q разрядов регистра сигнала т.е.при устойчивом формировании сигнала на q на циклах перебора. Этим исключается возможность случайного возникновения сигнала cL) .Обычно достаточно взять q равным 3-4. На счетный вход триггера 12 поступает сигнал j) позиционного кода нанравх(ения S , выбранного для отсчета циклов перебора, совпадающий с задним .фронтом сигнала t (по моменту формирования команд ) и f ) , а на вход ус;тановки в нуль триггера 12 поступгиот сигналы t , передним фронтом сбрасывающие его в-нулевое состояние „ Формируемый на выходе триг- гера сигнал возникает в момент начала цикла перебора направлений, совпадающий с задним фронтом сигналов , и длится до прихода следующего L .

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

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

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

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

0ai-Z

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