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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 19) (11) 15/20 1511 4 С 06 3 ищак, Н.М.Ле.Л.Шихутский ЕОНации реш я и окращения до минодного локальрасширяются вмногоэкстремал ума длительно иска. Тем самым,можности р задач метод ых поис о ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(71) Институт проблем моделирования в энергетике АН УССР(56) Грездов Г.И., Гищак К.И. Гиб ные дифференциальные методы нахождения экстремумов. -Гибридные вычислительные системы и комплексы, вып.1. Киев: Наукова думка, 1979,Грездов Г.И. Теория и применение гибридных моделей. Киев, Наукова думка, 1975, с,18-51, рис.20(54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ РЕШ НИЕМ МНОГОЭКСТРЕМАЛЫЬБ ОПТИИИЗАЦИ НЫХ ЗАДАЧ(57) Устройство относится к области вычислительной техники, в частности к устройствам гибридных вычислительных машин, управляющих процессом решения - отыскания минимума некоторой целевой функции, и может быть использовано в различных областях народного хозяйства, где применяется гибрид ная вычислительная техника для решения многоэкстремальных оптимизационных задач, например, при управлении технологическими процессамийли экспериментами. Цель изобретения - повышение производительности.Устройство содержит генератор тактовых сигналов, коммутатор направления поиска, блок формирования признаков направлений, блок формирования направлений поиска, узел памяти, триггер реверса, группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, а также триггерцикла, переключатель,.реверсивныйсчетчик, элемент ИЛИ, регистр сдвига, и триггер признака. Введениеэтих элементов позволяет на дополнительном выходе устройства сформировать сигнал признака минимума -прихода процесса поиска в зону минимума вспомогательной функции, чтосоздает возможность полной автоматим многократньп локала также повышается изводительность в целом. 4 ил.Изобретение относится к вычислительной технике, в частности к устройствам,управляющим процес.сом ре - щения - отыскания минимума некоторой целевой функции, и может быть использовано в различных областях народного хозяйства, где применяется гибридная вычислительная техника для целей решения многоэкстремальных оптимизационных задач, например, при управлении технологическими процессами или экспериментами,Целью изобретения является повышение производительности и расширение функциональных возможностей при решении многоэкстремальных задач за счет точного определения момента достижения требуемого минимума.На фиг.1 приведена схема устройства; на фиг.2 - граф, по которому реализуется коммутатор направлений поиска; на фиг.3 - схема переключателя; на фиг.4 - таблица программирования постоянного запоминающего устройства.Устройство содержит генератортактовых сигналов, коммутатор 2 направлений поиска, блок 3 Формирования признаков направлений включающий счетчик 4 адреса и дешифратор 5,блок б формирования направлений поиска, узел памяти 7, триггер 8 реверса, группу 9 элементов ИСКЛЮЧАЮЩЕЕИЛИ, вход 10 устройства, выход 11устройства, триггер 12 цикла, переключатель 13, реверсивный счетчик 14,элемент ИЛИ 15, триггер 16 признака, регистр 17 сдвига, выход 18 устройства, элемент НЕ 19, элементыИ-НЕ 20 и 21,Коммутатор 2 предназначен для формирования сигналов управления направлением поиска и реверсом движения в направлении Б в зависимости от текущего значения сигнала изменения вспомогательной функции Ь , Коммутатор 2 выполнен по известным принципам и представляет собой автомат, описываемый графом, приведенным на фиг.2, где Б ,- входные сигналы; д,1 э - команды, вырабатываемые автома - том в соответствующих состояниях.Узел 7 памяти выполнен в виде постоянного запоминающего устройства на К и-разрядных слов, педставляющих направления поиска Б (Б Б ). На Фиг.4 показана таблица программирования постоянного запоминающего устройства для К = и = 8.Триггер 8 предназначен для формирования сигнала Н знака движения5 в заданном направлении и выполнен ввиде счетного триггера,Группа 9 элементов ИСКЛЮЧАЮЩЕЕИЛИ прецназначена для умножения компонент вектора Б на сигнал К знака10 движения в заданном направлении,число элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соответствует числу компонент векто.,ра Б,Триггер 12 цикла предназначен15 для формирования сигнала завершенияцикла перебора направлений и можетбыть выполнен в виде счетного триг -гера,Регистр 17 сдвига предназначенпля пре.дотвращения случайного формирования сигнала признака минимума.цереключатель 13 предназначен дляраспределения сигналов, поступающихс генератора 1 тактовых сигналов навходы реверсивного счетчика 14 в зависимости от сигнала изменения вспомогательной Функции ВУстройство работает следующим образсм.0 Е составе гибридной вычислительной машины устройство осуществляетуправление процессом отыскания значений переменных, которым соответствует минимальное значение некоторойЗ 5 целевой или вспомогательной Функции,к минимизации которой сводится решение исходной задачи. Реализуемыйустройством процесс минимизации функции имеет локальный характер, т.е,40 сходится к тому минимуму, в зонепритяжения которого находилась начальная точка поиска,Процесс управления гоиском состо-ит в поочередном формировании, ин-Чвертировании, принеобходимости, ификсировании на некоторое время навыходе 11 устройства ь -компонентныхдвоичных векторных сигналов, задающих направления изменения искомых переменных решаемой задачи (минимизируемой функции), а также в формиро -вании на выходе 18 сигнала О придостижении процес.сом поиска минимума(решения), Значение каждой из компо -нент )(, , )( задает скорость изнак изменения во времени соответствующей переменной, что в совокупности определяет скорость и направ3 1244 ление движения в пространстве переменных точки поиска, задаваемой текущими значениями переменных (координат).фомируемые устройством направления Я (1 = 1к) принадлежат некоторой заранее выбранной системе направлений поиска, записанной в узле 7 памяти. Оттуда они в параллельной форме поочередно выводятся и пря мо либо инвертируясь поступают на выход.11, Инвертирование направления (реверс) меняет знак движения точки поиска в этом направлении.Сохранение направлений, их изме 5 нение на следующее по циклу и инвертирование задаются коммутатором 2, который по сигналам генератора 1 тактовых сигналов формирует команды перехода на новое направление и .ре 20 верса направления р . Формирование команд 1 и р осуществляется в за - висимости от входного сигнала В устройства, принимающего значения О и25 1 и содержащего информацию об убывании (6=0) или возрастании (6 =1) во времени. значения минимизируемой функции при изменении переменных в заданном направлении.В соответствии с целью поиска - минимизацией значения целевой функции коммутатор 2 удерживает направление Я , дающее убывание значения функции, до прохождения минимума в этом направлении и появления сигнала 8 =1. Затем по ближайшему сигналу 7 формируется команда, и если в новом направлении Я сигнал=1 далее, то по последующемуформируется команда. Поочередное генерирование команди р продолжается до появления сигнала 7 =О, т.е. до нахождения направления, дающего убы-. вание значения функции. Обычно первое же новое направление при одном из знаков дает убывание значения функции на некотором отрезке.Работа коммутатора 2, представляющего собой дискретный автомат, описывается графом (фиг.2). Состоя 50 ние Исх соответствует удержанию направления, В него автомат возвращается из состояний "Н" и "Р" по условию ВГ , т.е. при появлении сигнала 6 =О. По условию 8автомат переходит из состояния "Исх" в состояние "Н", где формируется команда 1 и далее, если Ь =1, поочередно по 682 4сигналамменяет состояния "Н и"Р" (команда Р ) до появления сигнала Й =О и возврата в состояние "Исх"Команды поступают в блок 3 насчетный вход счетчика 4, При этомсчетчик циклически меняет выходнойкод, задающий номер формируемого уст.ройством направления, Номер направления преобразуется дешифратором 5 впозиционный сигнал 4 (, 1,. АО,который поступает на соответствующийвход считывания узла 7 памяти в блоке 6. В результате на входы элементов 9 из узла 7 памяти поступает двоичный векторный сигнал, представляющий соответствующее направление поиска,Команды р поступают в триггер 8,поедставляющий собой счетный триггер.Каждая очередная команда вызывает изменение на противоположное значениевыходного сигнала триггера 8. Последний поступает на входы элементов 9и задает прямое (К=О) либо инверсное(2=1) прохождение на выход устройства 11 вектора Я".В рассматриваемом случае система8-мерных направлений Я содержит минимальное число ( К =) направлений -8, в качестве которых используетсясистема функции Уолша-Адамара, обладающих свойством взаимной ортогональностиКаждая компонента вектОра Япринимает значения О или 1, задающиевозрастание или убывание соответствующей переменной с фиксированнойскоростью,Особенностью реализуемого устройством процесса поиска минимума является отсутствие нулевой скорости из-. менения переменных и продолжение процесса поиска после достижения зоны минимума. Нри этом если вдали от минимума траектория движения точки поиска состоит из более или менее .продолжительных продвижений в направлениях поиска, то в зоне минимума процесс поиска сводится к непрерывному перебору направлений и небольшим продвижениям в них, т.е. высокочастотным колебаниям переменных относительно точки минимума. Амплитуда колебаний определяется запаздыванием в контуре управления, числом переменных, скоростью их изменения, влиянием помех и др.Формирование сигнала с 3 признака достижения процессом поиска минимумав устройстве осуществляется на основе учета описанного характера процесса поиска в зоне минимума и вдали от него - путем оценки на одном цикле перебора направлений поиска соотношения времени, в течение которого минимизируемая функция возрастает Г (6 = 1) и убывает Т (6=0) В зоне минимума время возврата к тдчке минимума определяется предшествовавшим ему временем запаздывания в . переключении направления после появления сигнала Ь =1. Поэтому величина 1, - 1 близка к нулю на цикле перебора направлений, т,к.Т 1, Вдали от минимума, где по крайней мере часть направлений 8 дает значи 4тельное продвижение при Ь =О, величина , Гформирование сигнала м) осуществляется путем подсчета на периоде перебора направлений поиска разности числа сигналов . на интервалах времени, когда сигнал 8 =О (ф) и когода о =1 (, до появления устойчивой величины оценки на нескольких. (о) циклах перебора . Подсчет числа Х и " осуществляется спомощью реверсивного счетчика 14, устанавливаемо - го в нулевое состояние в начале каждого цикла. Переключатель 13 в зависимости от значения входного сигнала устройства б подключает тактовые сигналы к входу прямогс (при Я=О) или обратного (при Б =1) счета реверсивного счетчика 14, Емкость реверсивного счетчика выбирается исходя из максимального возможного продвижения в сторону минимума на цикле направлений поиска с учетом частоты сигналов и должна быть око - ло Г /Ч (1 - частота сигналов Ч -скорость изменения переменной в относительных единицах), что со 6ставляет 2 - 21На входы элемента ИЛИ 15 подаются ш старших разрядов счетчика. Врезультате при появлении единиц вэтих разрядах, т.е. при достижении(оразностью-определенной величины, на выходе элемента 15 воз -1никает сигнал=1. В конце каждо -го цикла значение выхсдного сигнала,У заносится в триггер 16, а информация с триггера 16 заносится в регистр 17. Одновременно сигнал с выхода триггера 16 поступает на вход установ.ки в нуль регистра 17 и вслучае=О устанавливает его внулевое состояние,Прием и сдвиг информации в регистре 1 1 происходит по заднему фронту выходного сигнала триггера 12цикла, этот же сигнал передним фронтом устанавливает в нуль реверсив -О ный счетчик 14 и записывает значение сигнала 3 в триггер 16.формирование сигналана выходе.8 происходит при сдвиге через все1Ч разрядов регистра сигналао-5 т.е.при устойчивом формировании сиг 1нала и 3 =1 на и на циклах перебора,Зтим исключается воэможность случайного возникновения сигнала й 3 . Обычно до -статочно взять я равным 3-4.На счетный вход триггера 12 поступает сигнал , позиционного коданаиравления Б , выбранного для отсчета циклов перебора, совпадающий сзадним .фронтом сигналами (по моменту25формирования команд 1 и Р ), а навход установки в нуль триггера 12поступают сигналы . , передним фронтом сбрасывающие его в нулевое состояние формируемый на выходе триг -гера сигнал возникает в момент начала цикла перебора направлений, совпадающий с задним фронтом сигналови длится до прихода следующего55 формула изобретенияУстройство для управления решением многоэкстремальных оптимизационных задач, содержащее генератор тактовых сигналов, коммутатор направлений поиска, блок формирования признаков направлений включающий счетчик адреса и дешифратор, блок формирования направлений поиска, включающийл памяти триггер рвра и группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы которых являются информационным выходом устройства, выход генератора тактовых сигналов соединен с информационным входом коммутатора направлений поиска, управляющий вход которого соединен с задающим входом устройства, а выходы подключены соответственно к счетным входам триггера реверса и счетчика адреса, выходы разрядов которого соединены соответственно " входами дешифратора, выходы которого с первого по к-й подклю244682чены соответственно к входам считывания узла памяти, выходы которого ивыход триггера реверса соединены соответственно с входами элементовИСКЛЮЧАЮЩЕЕ ИЛИ группы, о т л и ч аю щ е е с я тем, что, с целью повышения производительности за счет точного определения момента достижениятребуемого минимума, в него введенытриггер цикла, триггер признака, переключатель, реверсивный счетчик,элемент ИЛИ и регистр сдвига, выходкоторого является выходом сигналаокончания работы устройства, входсдвига соединен с выходом триггерацикла, а установочный вход - с выходом триггера признака, входы которого соединены соответственно с выходами триггера цикпа и элемента ИЛИ,входы которого подключены соответ -ственно к выходам разрядов реверсивного счетчика, суммирующий и вычитающий входь которого соединены соответственно с выходами переключателя,а установочный вход подключен к вы 10 ходу триггера цикла, счетный вход которого подключен к к - му выходу дешифратора, установочный вход триггера цикла и информационный входпереключателя соединены с выходом ге 15 нератора тактовых сигналов, разрешающий вход переключателя соединен с задающим входом устройства,1244682 оставитель А.Жеренов ехред Л.Олейник Корректор В.Бутяга тор М.Циткин 4/5 изводственно-полиграфическое предприятие,г.ужгород,ул.Проектная аказ 3920/53 Тираж ВНИИПИ Государственног по делам изобретений 113035, Москва, Ж, 671 Подписнокомитета СССРи открытийаушская наб., д