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

(59 4 Бюл,роблеУССР СТВО ДЛЯ УПРАВЛЕ КСТРЕИАЛЬНЫХ ОП тение относится ехнике и можетдля решения мно тимизационных и ним инженерных ОННЫХ ЗАДА (57) Иэобр лительной нользовано ,мальных, о сводимых к к вычис ыть ис- оэкстредругих адач,(21) 3814758/24-24(56) Грездов Г,И., Гнщак К.И,. Гибридные дйфференциальные методы нахождения экстремумов. Гибридные вычислительные системы н комплексы: Сборник. Вып.1, Киев: Наукова думка, 1979.Грездов Г,И. Теория и применение гибридных моделей, Киев: Наукова думка, 1975, с.48-.5.1, рис.20-23, (54) УСТРОЙ НИЯ РЕШЕНИЕМ МНОГОЭ ТИМИЗАЦИЦелью изобретения является повышение быстродействия и расширение функциональных возможностей за счет обеспечения решения многоэкстремальных задач. Устройство содержит генератортактовых импульсов, блок 2 задания направления поискаблок 3 формиро.вания признаков направлений, включа" ющнй счетчик 4 адреса и дешифратор 5, блок 6 формирования направлений поиска, включающий узел 7 памяти, триггер 8 реверса, группу 9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент 12 ИСКЛЮЧАЮЩЕЕ ИЛИ, переключатель 13, блок 14 переключателей, блок 15 задания цели по" иска, включающий элемент 16 ИСКЛЮЧА- Ж ЮЩЕЕ ИЛИ, триггер 7, элемент 18 И-НЕ, ру узел 19 задержки, схему 20 сравнения, элемент 21 ИСКЛЮЧАЮЩЕЕ ИЛИ, счетчик 22 циклов. Устройство обеспечивает автоматическое изменение цели поиска" ф минимизации на максимизацию и наоборот в зависимости от хода поиска, а также комбинированное применение различных режимов управления. 6 ил., Изобретение относится к вычислительной технике, в частности к устройствам гибридных вычислительных машин, управляющих процессом решения- отыскания минимумов или максимумов некоторой целевой функции, и может быть использовано в различных областях народного хозяйства, где применяется гибридная вычислительная техника для решения многоэкстремальных 10 оптимизационных;и других сводимых к ним инженерньщ задач, например, при управлении технологическими процессами или экспе 11 иментами.Цельизобретения - повышение быст родействия.На фиг,1 представлена схема предлагаемого устройства; на фиг.2 - граф, описывающий работу блока задания направления поиска; на фиг.3 - таблица .20 программирования узла памяти для К = и = 8; на фиг.4 - схема переключателя; на фиг.5 - схема узла задержки; на фиг.6 - пример реализации ,схемы сравнения.На фигурах приняты следующие обозначения: генератор 1 тактовых импульсов, блок 2 задания (коммутатор) направления поиска, блок 3 формирования признаков направлений, счетчик 4 .30 адреса, дешифратор 5, блок 6 формирования направлений поиска, узел 7 памяти, триггер 8 реверса, группа 9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вход 10 и выход 11 устройства, элемент 12 ИСКЛЮЧАЮЩЕЕ ИЛИ, переключатель 13, блок 14 переключателей, блок 15 задания цели поиска, элемент 16 ИСКЛЮЧАЮЩЕЕ ИЛИ, триггер 17, элемент 1.8 И-НЕ, узел 19 задержки, схема 20 сравнения, 40 элемент 21 ИСКЛЮЧАЮЩЕЕ ИЛИ, счетчик 22 . циклов, элементы 23, 24 И, элемент 25. И-НЕ, элемент 26 НЕ, счетчик 27, переключатель 28, схема 29 сравнения, элементы 30, 31 И-НЕ, триггер 32, элементы 33 ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы 34, 35 И-НЕ. 25 Устройство работает следующим образом.В составе гибридной вычислительной машины устройство осуществляет управление процессом отыскания зна- . чений переменных, которым соответствуют минимальные или максимальные в некоторой окрестности (локальные) значения целевой или вспомогательной функции, к оптимизации которой сводится .рещение исходной задачи. Опти 123810 2мизируемая функция может иметь как унимодальньй (одноэкстремальный), так и многоэкстремальный характер.Реализуемый устройством процесс поиска состоит из двух уровней: уровня локального поиска, реализуемого блоками 2, 3 и 6 и обеспечивающего на" хождение минимума (максимума) целевой функции, в. зоне притяжения которого находилась начальная точка поиска; уровня глобального поиска, реализуемого элементом 12, переключателем.13, блоками 15 и 14 и обеспечивающего исследование пространства переменных задачи указанными локальными поисками с целью отыскания всех локальных минимумов (максимумов), Процесс управления поиском на локальном уровне соСтоит в поочередном формировании, инвертировании при необходимости и фиксировании на некоторое время на выходе 11 устройства И -компонентных двоичных векторных сигналов Я=(хх ), задающих направления измеи фнения искомых переменных. Значение каждой из компонент задает скорость и знак изменения во времени соответствующей переменной, а всовокупности определяет скорость и направление движения в пространстве переменных точили поиска, задаваемой текущими значениями переменных координат) .Формумые устройством направленияпоиска Я , 1 = 11 с принадлежат некоторой заранее .выбранной системе направлений поиска, записанной в виде соответствующих векторов в узле 7 памяти. Оттуда они в параллельной форме поочередно выводятся прямо или инвертируясь. Инвертирование направления (реверс) меняет знак движения точки поиска в этом направлении. Сохранение направлений,их изменение на следующее по циклуинвертирование задается блоком 2, которыйпо сигналамгенератора 1 тактовых импульсов формирует команды перехода на новое направлениеи реверса направления 0Формирование командиосуществляется в зависимости от%50 входного сигнала блока б , принимающего как и входной сигнал устройства б, значения О и 1 и содержащего ин" формацию об убывании или возрастании во времени значения целевой функции при изменении переменных в заданном направлении.Однако в отличие от входного сиг-нала ( , значение которого бО ао. -50 3 , 1238 ответствует убыванию целевой функции, а б = 1 - возрастанию, соответствие между значениями сигнала б и иэмене кием целевой функции зависит от сигнала цели поиска с, поступающего на вход элеМента 12. При 0, = О б": б%У а при м = 1 б : б , т.е. указанное соответствие.сановится обратным. при возрастании функции б = О, а при убывании б = , 1 О Блок 2, работа которого описывается графом, приведенным на фиг.2, при бО (независимо от соответствия между сигналами б и б находитсяв исходном состоянии "ИСХ" и удерживает заданное направление изменения переменных 5 до появления сигнала ффб = 1, При ( ц это означает дви, жение в. направлении бдо прохождения в нем минимума целевой функции, а.) Фпри об - до прохождения максимума.После появления. сигнала б =по ближайшему сигналу с блок 2 переходит в состояние "Н", где формируется ко маида 1 и происходит переход на новое, следующее по циклу направление:и ф+1 поиска Я . Если в каправлении Я сигнал б = 1, то блок 2 переходит в состояние "Р", где формируется команда 0 и осуществляется реверс движения точки приска в направлении.+Я путем его инвертирования (Я ). Дальнейшее сохранение б = 1 приводит к чередующимся переходам по каждому Ф между состояниями "Н" и "Р" 35 и поочередному формированию командидо появления сигнала б = О и возврата блока 2 по условию б в состояние удержания направленияН ИИСХ . Обычно каждое новое направ ление при одном из знаков движения1+1 ТГГ(Яили Я . ) дает некоторое убывание значений функции, если процесс не находится в зоне минимума (макси- мума). 45Команды 9 поступают в блок 3 на счетный вход счетчика 4. При этом, счетчик циклически меняет выходноймгкод г, задающий номер 1 формируемого устройством направления .Я Номер направления преобразуется дешифратором 5 в позиционный сигнал, который поступает на вход считывания узла 7 памяти в блбке 6. В результате на входы группы 9 элементов ИСКЛ 0-55 ЧАЮЩЕЕ ИЛИ поступает двоичный век- . торный сигнал, представляющий соответствующее направление поиска Я 101 4Командыпоступают в триггер 8, и каждая очередная команда 0 вызывает изменение на противоположное значение его выходного сигнала. Последний поступает на управляющий вход группы 9 элементов и задает прямое или инверсное прохождение на выход 1 устройства вектора ЯНа фиг.З приведена таблица используемой в устройстве системы направлений поиска при= 8, записанная в узле 7 памяти. В данном случае система 8-мерных направлений Я содер жит минимальное число (1 =) направлений - 8, в качестве которых используется система функций Уолша-Адамара, обладающих свойством взаимнойфортогональности. Каждая компонента вектора Я принимает значения,О или 1, задающие возрастание или убывание соответствующей переменной с фиксированной скоростью.Указанный алгоритм управления изменением переменных обеспечивает быстрое отвскание минимума (максимума целевой функции, в зоне притяжения которого находилась начальная точка поиска, при условии, что функция имеет ограниченную скорость измене"+ния, причем при о = б идет процесс минимизации функции, а при б "б максимизации. Особенностью процесса поиска является отсутствие нулевой скорости изменения переменных и про" должение поиска и после достижения минимума (максимума), При этом, если вдали от минимума траектория движения точки поиска состоит из более или.менее продолжительных продвижений4в направлениях Я , то в зоне минимума процесс сводится к непрерывному перебору направлений и небольшим продвижением в них, т.е. высокочастотным колебаниям переменных относительно точки минимума х (максимуФФма х ), Амплитуда колебаний определяется запаздыванием в общем контуре управления, числом переменных, скоростью их изменения и др. Уровень глобального поиска, целью которого. является общее исследование пространства переменных и отыскание всех локальных решений (минимумов х ц ) в случае многоэкстремальной задачи реализуется в устройстве на основе указанного локального поиска путем чередования процессов миними. зации и максимизации. Управление че 23810редования осуществляется выходным сигналом К. блока 15. Сигнал Ы значением К = О ставит элемент:12 в режим повторения входного сигнала б , т.е,задает соответствие б = б и процесс минимизации целевой функции. Значение о = 1 задает режим инвертирования входного сигнала, т,е. соответствие Д" = Д и процесс максимиза- О ции.Включение поиска максимума при нахождении переменных в зоне минимума (результата предшествовавшегопоиска минимума)приводит к переходу значе ний переменных в зону одного из соседних максимумов или выходу на границу шкалы переменных. Попадание в тот или иной максимум зависит от положения точки поиска относительно точки дан ного минимума целевой функции в момент изменения цели поиска, а также от направления изменения переменных Б в этот момент. Точка минимума, как правило, лежит на границе зон д 5 притяжения соседних максимумов. Для используемого алгоритма локального поиска характерны значительные взаимные наложения зон притяжения локальных минимумов (максимумов), связанных с выбором конкретного направления начального изменения перемененных Такая же ситуация имеет место и при переходе на поиск минимума после нахождения точки максимума или выхода на границу шкалы.В устройстве предусмотрены три Р ежима управления изменением сигнала К: непосредственного ручного изменения автоматического изменения черезФзаданные интервалы времени; автоматического изменения с дополнительным4 условием по направлению поиска БНепосредственное ручное изменение сигнала А осуществляется иэмене 45кием состояния (нажатое ненажатое)соответствующего переключателя блока 14 и изменением значения сигналана входе элемента 16 ИСКЛЮЧАЮЩЕЕ ИЛИ.Режим автоматического изменения 50сигнала й через заданные интервалывремени включается нажатием соответствующего переключателя в блоке 14и снятием блокировки элемента 18И-НЕ и установки в нуль триггера 17.В этом режиме сигнал с третьего выхода блока 14 блокирует работу схемы20, устанавливая ее выходной сигнал в состоянйе, "1" (сигнал) и удерживает в нулевом состоянии счетчик22 циклов.Изменение сигнала О происходит припоступлении на счетныи вход триггера 17 сигнала 11 с выхода элемента18. Выходной сигнал Ф, триггера 17,представляющий предварительный сигнал цели поиска, прямо или, инвертируясь элементом 16, поступает навход элемента 12 как сигнал 0Сигнал р имеет значение О и совпа"дает с одним из сигналов , . Сигналформируется по условию б" ,юТреализуемому элементом18. Как видно из условия,фор-;мирование сигнала р (так как Яфпроисходит после прихода навход элемента 18 сигнала Т= 1 поближайшему условию б"С , по которомув блоке 2 формируется командат.е. после прохождения минимума(максимума) в текущем направлении Б,Поскольку после изменения целипоиска данное направление Б дает.нужное изменение целевой функции, вустройстве предусмотрена блокировкаформирования команды- сигнал 11блокирует прохождение сигналанаблок 2 через переключатель 13. С.этой целью для выравнивания моментов прихода на элемент 24 И (фиг,4)сигналов р и ь переключатель 3 содержит входной элемент 23 И, компен"сирующий задержку формирования сигнала (11, В следующий тактовый моменпосле изменения цели поиска (инвертирования сигнала б ) условие" не выполняется и движение в заданном направлении сохраняется.Сигнал р поступает также на входузла 19 задержки иустанавливает(задним фронтом) сигнал Тв значение О - блокировки формированиясигнала Ь,Узел 19 работает следующим образом.Тактовые сигналы Й поступают насчетный вход счетчика 27 через элемент 25 И-НЕ, Выходным сигналом счетчика являютсястарших разрядов,младший иэ которых соответствуеттребуемой дискретности задания задержки формирования сигнала задержки, Выходной код счетчика сравнивается в схеме 29 сравнения с выходнымкодом переключателя 28, который задается оператором. При достижениисчетчиком заданной величины выходной сигнал на инверсном выходе схемы 29 сравнения блокирует дальнейшее прохождение сигналовна вход счетчи- ка, а сигнал Г с выхода элемента 26 НЕ передним фронтом перезаписывает в триггер 32 сигнал на прямом выходе схемы 29 сравнения, Выходной сигнал . на прямом выходе триггера 32, форми- руемый по заднему фронту сигнала с1 и представляет сигнал Т д, Укаэанное заблокированное состояние узла 9 задержки сохраняется до прихода на вход установки в нуль счетчика 27сигнала ш , После сброса счетчика в нуль по переднему фронту сигнала ш (т.е.) по заднему фронту р (С) переводится в исходное состояние триггер, Введение задержки снятия сигнала 20 Т а связано с предупреждением укорочения сигнала р .Таким образом, в рассмотренном режиме устройство обеспечивает автоматическое изменение цели поиска - ми нимизации на максимизацию и наоборот вмоменты выполнения условия б"=1 с одновременной блокировкой формирования команды 1 . После каждого изменения цели поиска обеспечивается 30 блокировка на некоторый регулируемый интервал времени возможного изменения цели поиска,четности цикла задания кодаоСигналустанавливает прямое илиинверсное прохождение сигнала К через элемент 21, используемого далее в качестве контрольного сигнала ВТаким образом, в этом режиме изменение сигнала(формирование сигО нала р) также происходит после прихода сигнала Т ; = 1 по условию о Р,но не на любом направлении поискаа только при изменении переменных в2 2напрарлении. со знаком К = К,ь 2 05 Контрольный кодостается неизменоным на паре поисков минимизация -максимизация, тогда как сигнал Кизменяется в два раза чаще, причемфаза его изменения на четных и нечеть 2ных циклах задания кодапротиво 1 о,положная. В результате устройствообеспечивает переход, например, сминимизации на максимизацию последовательно на каждом из направленийБ и Я, и промежуточные переходыот максимизации к минимизации припротивоположном знаке движения КТакой алгоритм позволяет последовательно осуществлять выходы из точкиминимума в различных направлениях иобеспечивает высокую вероятность возврата в этот минимум из соседних максимумов. Этим облегчается детальноеисследование целевой функции в об ласти выбранного минимума. Изменениережима элемента 16 ручным сигналомуправления позволяет переключить алгоритм на аналогичное исследованиеточек максимумов.Комбинированное применение указанных трех режнмов управления измененияцели поиска, реализуемых устройством,обеспечивает высокую эффективностьпроцесса поиска в случае решения многоэкстремальных задач с большим чис"лом переменных. Устройство для управления решением многоэкстремальных оптимизационных задач, содержащее генератор тактовых импульсов, коммутатор направления поиска, блок формирования признаков направления, включающий счетчик адреса и дешифратор, блок формирования направления поиска, включающий узел памяти; триггер реверса и группу элеРежим автоматического изменения сигналас.дополнительным условием по направлению поиска включается одновременным формированием сигналов на втором и третьем выходах блока 14. Работа устройства в данном режиме отличается от рассмотренного режима работы включением в приведенное условие формирования. сигналадополнительного условия. Сигнал 1= 1 формируется схемой 20 сравнения при совпадении двоичного кода текущего 45 , направления изменения переменных и сигнала знака движения в заданном направлении К с контрольными значениями2 3 Р 2 кодаи сигнала К , Сигналформируется счетчиком 22 циклов. На 50 счетный вход счетчика 22 поступает выходной сигнал к триггера 17 и изменяет его состояние при каждом переходе из "1" в "0", т.е. по каждому второму сигналу , Первые Ф раэря ,дов счетчика циклов используются2как контрольный кодномера направления,. а разряд (ш+1) - как сигнал уо формула изобретенияментов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы кото-.рых являются информационным выходомустройства, информационные выходыкоммутатора направления поиска подключены соответственно к счетнымвходам триггера реверса и счетчикаадреса, выходы разрядов которого соединены соответственно .с входами дешифратора, выходы которого соединенысоответственно с входами считыванияузла памяти, выходы которого соединены соответственно с первыми входамиэлементов ИСКЛЮЧАЮЩЕЕ ИЛИ группы,вторые входы которых соединены с выходом триггера реверса, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия, в него введеныпереключатель, элемент ИСКЛЮЧАЮЩЕЕИЛИ, блок, переключателей и блок задания цели поиска, включающий первыйи второй элементы ИСКЛЮЧАЮЩЕЕ ИЛИ,элемент И-НЕ, триггер, узел задержки,счетчик циклов и схему сравнения, информационные входы которойсоединенысоответственно с выходами разрядовсчетчика адреса, с выходами П разрядов счетчика цикловс выходами триггера реверса и первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первые входы первогон второго элементов ИСКЛЮЧАЮЩЕЕ ИЛИблока задания цели поиска и счетныйвход счетчика циклов соединены с выходом триггера, выход (в+11-го разряда счетчика циклов соединен с вторым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый выход блока пере,лючателей соединен с вторым входом второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ блока. задания цели поиска, выход которогосоединен с первым входом элемента 10 ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого является информационным входомустройства, а выход подключен к информационному входу коммутатора направления приска и к первому входу 1 элемента ИНЕ, выход генератора так-.товых импульсов соединен с вторымвходом элемента И-НЕ и с информационными входами узла задержки и переключателявыход которого соединен 20 с управляющим входом коммутаторанаправления поиска, управляющие входы переключателя, узла задержки исчетный вход триггера соединены свыходом элемента И-НЕ, третий и 25 четвертый входы которого соединенысоответственно с выходами узла задержки и схемы сравнения, пятый, входэлемента И-НЕ и установочный входтриггера соединены с вторым выходом р блока переключателей, третий выходкоторого соединен с установочнымвходом счетчика циклов и управляющимвходом схемы сравнения,11238101 А. Жаренало. рректор А. Обручар Зака олиграфическое предприятие, г. Укгород, ул. Проектная,он 9 водстве Составитель едактор С. Лисина Техред Н .Во94/51 Тирам 671 ВНИИПИ Государственного по делам иэобретений 113035, Москва, Ж, Подписноекомитета СССРи открытийушская наб д.4/5