Вычислительное устройство для решения задачи выправки железнодорожного пути Советский патент 1981 года по МПК G06F17/00 

штрафной функции соединен с выходом второго элемента ИЛИ, нулевой выход триггера фиксации штрафной функции через последовательно соединенные третьи элементы И, ИЛИ соединен со вторым входом блока управления,выход которого соединен со вторым входом .триггера фиксации штрафной функции и со входами третьего элемента И и сче чика итераций, выходы которого соеди нены со входом третьего элемента ИЛИ и вторь входом регистра ограничения невязок и со вторым входом регистрамаски. На чертеже представлена блок-схем предлагаемого устройства. Устройство содержит арифметически блок 1, блок 2 памяти, блок 3 вводавывода, блок 4 управления, регистр 5 ограничения невязок, сдвиговый регистр 7 маски, группу элементов И 8, элементы ИЛИ 9-11, дополнительный блок 12 памяти, сдвигающий регистр 1 штрафов, Элементы И 14-16, тригге| л 17 и 18, триггер 19 фиксации штрафно функция, счетчик 20 итераций. Устройстгво работает следующим образом. В процессе ввода в ячейки блока 2 из блока 3 заносится информация об ограничениях на сдвиги в соответству ющих, точках деления пути и о свободных членах неравенств решаемой системы (вычисленных во время ввода как функции от значений стрел кривизны в соответствукядих точках деления пути В регистр 5 заносится код, равный абсолютной величине ограничения d. на невязки г , в регистр 7 заносится код, содержащий единицы во всех разрядау, кроме фиксированного числа младших разрядов,куда заносят нули. Число нулевых разрядов соответствует ближайшему к i числу d 2, причем Afoi.. Таким образом, регистр 7 маскирует нулями некоторое заданное множество разрядов арифметического блока 1. Если в процессе вычисления иевязки ее значение по абсолютной величине превышает установленное ограничение, .то по крайней мере в одном из незамасАированных старших разрядов арифметического блока 1 появляется единица, которая через элемент ИЛИ 9 переключает триггер 17 в единичное состояИие. При этом информация об абсолютн м значении невязки поступает в блок 2 из регистра 5. Информация о знаке невязки 1; поступает на вход знакового разряда регистра 5 непосредственно с выхода знакового разряда арифметического блока 1. Триггер 17 перед началом, вычисления очередной невязки предварительно устанавливается в состояние О управляющим сигналом на соответствующем выходе блока 4. Коды, записанные в регистры 5 и 7, уменьшаются, например, в 8 раз путем выполнения операции трехкратного сдвига в сторону младших разрядов. Таким образом, вначале ищется решение задачи при искусственно уменьшенных (по сравнению с заданными ограничениях на невязки. На это отводится, например, шестнадцать итераций. По завершении шестнадцатой итерации на выходе четвертого разряда счетчика 20 появляется управляющий сигнал, по которому происходит однократный сдвиг кодов в регистрах 5 и 7 в сторону старших разрядов. При этом ограничение на невязки cL возрастает в два раза. Если в последующие шестнадцать итераций решение не будет обнаруж но, то эта операция повторяется вновь (через каждые шестнадцать итераций на выходе четвертого разряда счетчика 20 появляется управляющий сигнал). Описанная операция сдвига кодов в регистрах 5 и 7 повторяется до трех раз, т.е. до тех пор, пока не будет получено решение либо не исчерпается минимум допустимого числа итераций (64). В последнем случае в счетчике 20 устанавливается код 64 и единичный сигнал с выхода старшего разряда этого счетчика проходит через элемент ИЛИ 11 на вход схемы останова устройства в блоке 4. По Э авершении ввода информации начинается процесс решения згудачи путем реализации обобщенного градиентного метода с использованием метода штрафных функций. При этом решается итерационная задача минимизации модулей .составляквдих вектора сдвига X за счет изменения в допустимых пределах управляющего вектора невязок Z . В процессе вычисления величин сдвигов Х; каждая из этих величин прибавляется к содержимому специальной ячейки блока 2 памяти, в которой накапливается сумма модулей сдвигов m ,.,,, проверяется на допустимость по заданным ограничениям сверху (( и снизу ((blj) , т.е. проверяется справедливость неравенств ,a, -i -(Ь) х.( Эта проверка осуществляется путем анализа знака разности ()(-|Ь)) , а затем (Х -|Ь,) . Если вычисленный сдвиг X | не удовлетворяет какому-либо из ограничений, то этот факт фиксируется путем записи штрафной функции (единичного сигнала) в соответствующий 1-ый разряд сдвигающего регистра 13. Одновременно сигнал с элемента ИЛИ 10 переключает в единичное соетояние триггер 19, обеспечивая этим запрет на прохождение (в конце итеpauHHJ управляющего сигнала на вход схемы останова устройства, поступает в блок 4, инициируя выполнение операции сложения содержимого специальной ячейки в блоке 2 с абсо лютным значением разности (Jl - 6) , либо (Х - й) , т.е. выполнение опера ций накопления следующей суммы: ,A.-.SjlX,.(.4,lX,.4;y при Х i при Х lf ГО при X,- 7/ при Xj (bl Полученная сумма А записывается снова в специальную ячейку блока 2, предназначенную для хранения текущего значения минимизируемой целевой функции А. (в дальнейшем для определенности будем называть зту ячейку регистром целевой функции А). Содержимое регистра целевой функции А используется при вычислении нового век тора невязок 2 , который обеспечивает на последующей итерации умень шение величины этой целевой функции В устройстве требуется, чтобы и сумма модулей всех сдвигов Х (как оштрафованных, так и неоштрафованных не превышала установленное для данно го микроплана ограничение S д . Эта сумма накапливается по мере вычисления величин сдвигов Х в специальной ячейке блока памяти, которую для оп ределенности назовем регистром суммы модулей сдвигов. Текущее значение накоплений суммы равно SrS..,-ix,i i 1,l,...,W Ни одно из текущих значений суммы м дулей сдвигов не должно превышать о раничение Sroa , величина которог хранится в одной из рабочих ячеек блока 2 i 5 .Srnax -, 1, - I 1 Если это требование выполняется до конца расчета всех сдвигов Xi, т.е. сумма 5„.(х,, iti ТО минимизация целевой .функции осуществляется только за счет тех составляющих Х вектора сдвигов, которые выходят за рамки своих локальны ограничений и для которых штрафы Ч; 1. Если же S S ,v(ay. то все последующие значения суммыЗ( JS;j+,. Sm) и подавно будут больше . В этом случае минимизация суммы сдв гов осуществляется за счёт всех составляющих вектора сдвигов, т.е. всем сдвигам Х приписывается штраф Ч, 1 (i 1,2,... ,fnj . Таким образом, минимизируемая целевая функция равна ..4.{lx,.Xj-B;M - S 1Х,1 Ч ГО при X( i ifc при Х- (,. Го при X,- / II |1 при X,- ft О при 5гг (5„a при 5 „ S „а„ Сравнение текущего значения модулей сдвигов со своим ограничением происходит путем анализа знака разности ( - S „дх ) Smaxi то этот факт фиксируется путем записи штрафной функции (единичного сигнала) во все разряды сдвигакядего регистра 13. Таким образом, будут оштрафованы все слагаемые X-, суммы 5,, & Хц| Одновременно сигнал с элемента ИЛИ 10 переключает в единичное состояние триггер 19, обеспечивая этим запрет на прохождение (в конце итерации управляющего сигнала из блока 4 на схему останова устройства через элементы И 16 и ИЛИ 11, поступает в блок 4, обеспечивая вычисление всех последующих сдвигов X , ..., X m без проверки их на допустимость по локальным ограничениям, что экономрт время решения. При этом выполняется только операция накопления суммы модулей всех сдвигов. По завершении вычисления всех сдвигов и накопления суммы S yii эта сумма переписывается в регистр целевой функции А и используется при вычислении нового вектора невязки Z Новые невязки вычисляются по основной формуле обобщенного градиентного метода .lll,. где К - номер итерации,- градиентный множитель, значение которого определяется выражением н Р i-Aazгде Р - значение минимизируемой целевой функции,записанной в .регистр целевой функции А ,., блока 2, , ол - - частные производные вектора i сдвигов i -ным приращениям вектора невязок 2 , которые вычисляются по формулам:i 0,1,2,.,,,111-1, где L; -m постоянных коэффициентов, которые хранятся в ячейках дополнительного блока 12, SJflfnXj- знаки ранее выч ислвнных величин сдвигов, которые хранятся в соответствующих раз рядах сдвигового регистра 6 (сдвиги этого регистра и сдвигающего регистра 13 осу ществляются синхронно в моменты вызова .ИЗ дополнитель ного блока 12 очередного ко эффициента; Ь Ч;- штрафные функции, значения которых хранятся в соответствующих разрядах сдвнганлйе го регистра 13, Штрафные функции принимают еди ничное значение в случаях, если соответствующий Х не удовлетворяет какому-либо из своих локальных огра ничений, сумма кК дулей сдвигов превы шает свое ограничение S ridx В этом случае все Vf 1, что обеспечиваетоя путем записи единичного сигна ла с элемента ШШ 10 во все разряды Сдвигающего регистра 13, Значения, штрафов Ч,} .подаются в ка честве разрешающих сигналов в моменты вызова и дополнительного блока 12 соответстВукяцих постоянных коэффйциэнтов Ьj приведенных формул, Зна чение в соотвеТйтвующем разряде сдвии-аюкего регистра 13 разрешает ( ) либо запрещает () считывание а выхода дополнительного блока 12 соответствующего постоянного коэф фициента Uj в момейт формирования каядЕ(ого члена суммы парных произведений при вычислении очередной частной производной. Полученные новые значения невязок Z записываются в подблок невязок блока 2 и используются при расчете на следующей итерации нового вектора сдвигов X, Вели все величины сдвигов X удовлетворяют заданным ограничениям и при этом сумма модулей сдвигов так же не превышает свое ограничение / то это Является признаком по лучения искомого решения, В этом слу чае- триггер 19, установленный вначале итерации в нулевое состояние сигналом из блока 4, сохраняет Это состояние до конца итерации. Нулевое состояние триггера 19 поддерживает единичный потенциал на элементе И 16, В конце итерации в блоке 4 вырабатывается управляющий сигнал, который поступает на счетный вход счетчика 20 и на элемент И 16, Этот сигнал через элемент И 16 и через элемент ИЛИ 11 поступает на вход схемы останова устройства в блоке 4, Процесс вычислений заканчивается, В сметчике 20 зафиксирован код числа итераций. Вели в течение 64 итераций решение не по лучено, то останов,устройства происходит по завершении 64-И итерации вычислител ьного процесса импульсом переполнения счетчика 20, Это импульс поступает непосредственно с выхода старшего разряда счетчика 20 на элемент ИЛИ 11 и затем на вход схемы останова устройства, Описанный процесс.Минимизации целевой функции предусматривает поиск решения в б.олее узких (по сравнению с первоначально заданными} границах изменения невязок ,что повышает скорость обработки,Этим осуществляётся оптимизация целевой функции качества пути (суммы невязок 2) Формула изобретения Вычислительное устройство для решения задачи выправки железнодорожного пути по авт,са, 802967, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия, в него дополнительно введены счетчик итераций, триггер фиксации штрафной функции, третий элемент И, третий элемент ИЛИ, причем первый вход триггера фиксации штрафной функции соединен с выходом второго элемента ИЛИ, нулевой выход триггера фиксации штрафной функции через последовательно соединенные третьи элементы И, ИЛИ соединен со втО1ялм входом блока управления, выход которого соединен со вторым входом триггера фиксации штрафной функции и со входами третье го элемента И и счетчика итераций, выходы которого соединены со входом третьего элемента ИЛИ и вторым входом регистра ограничения невязок и со вторым входом регистра-маски. Источники информации, принятые во внимание при экспертизе 1, Авторское свидетельство СССР 802967, кл, G 06 F 15/20, 1977 (прототип), .