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

 

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

СО1ОЭ СОВЕТСНИХ

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

РЕСПУБЛИН

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3814757 24-24 (22) 14. 11.84 (46) 15.07.86. Бюл. Р 26 (71) Институт проблем моделирования в энергетике АН УССР (72) Г.И.Грездов, К.И.Гищак, EI.М.Ле. щенко, О.В.Ткаченко и А.Л.Шихутский (53) 681.34(088.8) (56) Грездов Г.И., Гищак К.И. Гибридные дифференциальные методы нахождения экстремумов. -Гибридные вычислительные системы и комплексы, вып.1.

Киев: Наукова думка, 1979.

Грездов Г.И. Теория и применение гибридных моделей. Киев, Наукова думка, 1975, с.18-51, рис.20 ° (54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ РЕШЕНИЕМ МНОГОЭКСТРЕМАЛЫЬБ ОПТИМИЗАЦИОННЫХ ЗАДАЧ (57) Устройство относится к области вычислительной техники, в частности к устройствам гибридных вычислительных машин, управляющих процессом решения — отыскания минимума некоторой целевой функции, и может быть использовано в различных областях народного хозяйства, где применяется гибрид ная вычислительная техника для реше„„SU„, 244682 д 1 (1) 4 G 06 J 1/00, С 06 F 15/20 ния многоэкстремальных оптимизационных задач, например, при управлении технологическими процессами или экспериментами. Цель изобретения — повышение производительности.

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

1244682

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

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

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

Устройство содержит генератор тактовых сигналов, коммутатор 2 направлений поиска, блок 3 формирования признаков направлений„ включающий счетчик 4 адреса и дешифратор 5, блок б формирования направлений поиска, узел памяти 7, триггер 8 реверса, группу 9 элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ, вход 10 устройства, выход 11 устройства, триггер 12 цикла, переключатель 13, реверсивный счетчик 14, элемент ИЛИ 15, триггер 16 признака, регистр 17 сдвига, выход 18 устройства, элемент НЕ 19, элементы

И-НЕ 20 и 21.

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

Узел 7 памяти выполнен в виде постоянного запоминающего устройства на К п-разрядных слов, представ1 ляющих направления поиска S (S

S ) . На фиг. 4 показана таблица программиров ания по сто янного запоминающего устройства для K, = n = 8.

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

5 в заданном направлении и выполнен в виде счетного триггера.

Группа 9 элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ прецназначена для умножения компонент вектора S на сигнал R знака

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

Триггер 12 цикла предназначен

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

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

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

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

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

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

40 сходится к тому минимуму, в зоне притяжения которого находилась начальная точка поиска.

Процесс управления гоиском состо— ит в поочередном формировании, ин ю" вертировании, при необходимости, и фиксировании на некоторое время на выходе 11 устройства 1 -компонентных двоичных векторных сигналов, задающих направления изменения искомых переменных решаемой задачи (минимизируемой функции), а также в формиро— вании на выходе 18 сигнала 1) при достижении процес.сом поиска минимума (решения). Значение каждой из компо— нент )(i,,..., )(задает скорость и знак изменения во времени соответствующей переменной, что в совокупности определяет скорость и направ3 1244 ление движения в пространстве переменных точки поиска, задаваемой текущими значениями переменных (координат) .

Формируемые устройством направления S (4 = 1,...,К) принадлежат некоторой заранее выбранной системе направлений поиска, записанной в узле 7 памяти. Оттуда они в параллельной форме поочередно выводятся и пря- 10 мо либо инвертируясь поступают на выход.ll . Инвертирование направления (реверс) меняет знак движения точки поиска в этом направлении.

Сохранение направлений, их изме15 нение на следующее по циклу и инвертирование задаются коммутатором 2, который по сигналам генератора 1 тактовых сигналов формирует команды перехода на новое направление и .ре20 верса направления p . Формирование команд 4 и р осуществляется в за— висимости от входного сигнала 8 устройства, принимающего значения 0 и

1 и содержащего информацию об убы вании (6=0) или возрастании (6 =1)

I во времени. значения минимизируемой функции при изменении переменных в заданном направлении.

B соответствии с целью поиска— минимизацией значения целевой функции коммутатор 2 удерживает направление S дающее убывание значения функции, до прохождения минимума в этом направлении и появления сигнала B -=l. Затем по ближайшему сигналу 7 формируется команда I, и если в новом направлении S сигнал i =1 далее, то по последующему формируется команда p . Поочередное генерирование команд 1 и р продолжается до появления сигнала 7 =О, т.е. до нахождения направления, дающего убы-. вание значения функции. Обычно первое же новое направление при одном из знаков дает убывание значения функции на некотором отрезке. .Работа коммутатора 2, представляющего собой дискретный автомат, описывается графом (фиг.2). Состоя50 ние Исх соответствует удержанию направления. В него автомат возвращается из состояний "Н" и "Р" по условию 8i, т.е. при появлении сигнала 6 =0. По условию 8 автомат переходит из состояния "Исх" в состояние "Н", где формируется команда1 и далее, если Ь =1, поочередно по

682 4 сигналам меняет состояния "Н и

"P (команда P ) до появления сигнала 8 =0 и возврата в состояние "Исх"

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

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

Каждая очередная команда вызывает изменение на противоположное значение выходного сигнала триггера 8.:.Послед-. ний поступает на входы элементов 9 и задает прямое (R=Î) либо инверсное (R=1) прохождение на выход устройства 11 вектора S

B рассматриваемом случае система

8-мерных направлений S содержит минимальное число (К = ) направлений—

8, в качестве которых используется система функции Уолша-Адамара, обладающих свойством взаимной ортогональности..Каждая компонента вектбра Я принимает значения 0 или 1, задающие возрастание или убывание сооTHeTcT вующей переменной с фиксированной скоростью.

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

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

1244682 в устройстве осуществляется на основе учета описанного характера процесса поиска в зоне минимума и вдали от него — путем оценки на одном цикле перебора направлений поиска соотношения времени, в течение которого минимизируемая функция возрастает TÄ (6 = 1) и убывает Т (6=0)

В зоне минимума время возврата к тдчке минимума определяется предшествоBBBIIIHM ему временем запаздывания в . переключении направления после появ— ления сигнала S -=-1. Поэтому величина T, — l„ близка к нулю на цикле перебора направлений, т.к.T„ l

Вдали от минимума, где по крайней мере часть направлений Я дает значи4 тельное продвижение при Ь =О, величина T, >) Г„

Р

Формирование сигнала м) осуществляется путем подсчета на периоде перебора направлений поиска разности числа сигналов ь на интервалах времени, когда сигнал & =0 (cü ) и когл да =1 (), до появления устойчивой величины оценки на нескольких . (0) циклах перебора. Подсчет числа Z и " осуществляется с помощью реверсивного счетчика 14, устанавливаемо— го в нулевое состояние в начале каждого цикла. Переключатель 13 в зависимости от значения входного сигнала устройства 6 подключает тактовые сигналы к входу прямогс (при о=0) или обратного (при б =1) счета реверсивного счетчика 14. Емкость реверсивного счетчика выбирается исходя из максимального возможного продвижения в сторону минимума на цикле направлений поиска с учетом частоты сигналов и должна быть око— ло f /Ч„ (f — частота сигналов

V -скорость изменения переменной

Yi в относительных единицах), что со16 ставляет 2 — 2

На входы элемента ИЛИ 15 подаются ш старших разрядов счетчика. В результате при появлении единиц в этих разрядах, т.е. при достижении (o) разностью 1 — определенной ве— личины, на выходе элемента !5 воз—

1 никает сигнал « =1. В конце каждо— го цикла значение выхсдного сигнала У заносится в триггер 16, а информация с триггера 16 заносится в регистр 17. Одновременно сигнал с выхода триггера 16 поступает на вход установ.ки в нуль регистра 17 и в случае =0 устанавливает его в нулевое состояние, Прием и сдвиг информации в регистре 17 происходит по заднему фронту выходного сигнала триггера 12 цикла, этот же сигнал передним фронтом устанавливает в нуль реверсив—

10 ный счетчик 14 и записывает значе-! ние сигнала «3 в триггер 16.

Формирование сигнала 1 на выходе. !

8 происходит при сдвиге через все

1 разрядов регистра сигнала < !

5 т.е.при устойчивом формировании сиг1 нала < =1 íà g на циклах перебора. Зтим исключается воэможность случайного возникновения сигнала й3.Обычно дав статочно взять q равным 3-4.

На счетный вход триггера 12 поступает сигнал,1 позиционного кода

J наиравления Б, выбранного для отсчета циклов перебора, совпадающий с задним .фронтам сигнала с (по моменту

25 формирования команд и P ), а на вход установки в нуль триггера 12 поступают сигналы, передним фронтом сбрасывающие его в нулевое состояние„ Формируемый на выходе триг— гера сигнал возникает в момент начала цикла перебора направлений, совпадающий с задним фронтом сигналов

Я, и длится до прихода следующего 5 Фо рмула и за бр е тения

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

11 чены соответственно к входам считывания узла памяти, выходы которого ивыход триггера реверса соединены соответственно с входами элементов

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

l го соединены соответственно с. выходами триггера цикпа и элемента ИЛИ, входы которого подключены соответ— ственно к выходам разрядов реверсивного счетчика, суммирующий и вычитающий входь которого соединены сооТветственно с выходами переключателя, а установочный вход подключен к вы10 ходу триггера цикла, счетный вход которого подключен к к — му выходу дешифратора, установочный вход триггера цикла и информационный вход переключателя соединены с выходом ге)5 нератора тактовых сигналов, разрешающий вход переключателя соединен с задающим входом устройства.

1244682

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

Редактор М.Циткина Техред Л.Олейник Корректор В.Бутяга

Заказ 3920/53 Тираж 671 Подписное

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

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

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