Вычислительное устройство для решения задачи выправки железнодорожного пути

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТ©И:К©МУ СВ НВЛЬСТВУ

Союз Соввтсннд

Соцналнстнческнх

Республнн (61) Дополнительное к авт. санд-ву в 802967 (22) Заявлено 180178 (21) 2569054/18-24 ®)М. КЛ. с присоединением заявки Но4 06 f 15/20

Госудаоетаевкый аомнтет

СССР ло делам изобретений

s отармтиА (23) Приоритет(53) УДЫ 681.З25 (088. 8) Опубликовано 3011Я1. бюллетень И%44

Дата опубликования описания 303.1,81 (72) Авторы изобретения

Ю.В.Власенко и;Э.Ç.Трайнив (71) Заявитель

Ордена Ленина институт кибернети (54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

ЗАДАЧИ ВЫПРАВКИ ЖЕЛЕЗНОДОРОЖНОГО

ПУТИ

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

Задача определения оптимального микроплана железнодорожного пути является специфической задачей нелинейного программирования с двусторонними ограничениями на зависиввее 29 и на независимые переменные. Порядок задачи m =10-15 обусловлен количеством точек деления пути (через 10 м) в пределах расчетного микроплана пути длиной 100-150 и. Число точек 25 микроплана обеспечивает необходимую точность решения, что позволяет заменить громоздкий расчет микроплана пути длиной до 4 км расчетами множества мнкропланов длиной по 150 м. . 3g

По основному авт.св. 9 802967 Нз вестно вычислительное устройство дпя решения задачи выправки железнодорожного пути, содержшаее сдвигаквдий 9егистр штрафов, второй триггер, два элемента И, второй элемент ИЛИ, прячем вход второго триггера и первый вход сдвигакщего регистра штрафов соединены с выходом блока управления,, второй и третий выходы арифметического блока соединены с первыми sxo»» дами первого и второго элементов И, выходы которых через второй элемент

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

Однако известное устройство характеризуется недостаточным быстродействием.

Цель изобретения - повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство дополнительно введены счетчик итераций, триггер фиксации штрафной функции, третий элемент И, третий элемент ИЛИ, причем первый вход триггера фиксации

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

На чертеже представлена блок-схема предлагаемого устройства. устройство содержит арифметический 15 блок 1, блок 2 памяти, блок 3 ввода-. вывода, блок 4 управления, регистр 5 ограничения невязок, сдвиговый регистр 7 маски, группу элементов И 8, элементы ИЛИ 9-11, дополнительный 20 блок 1.2 памяти, сдвигающий регистр 13 штрафов, элементы И 14-16, триггеры *

17 и 18, триггер 19 фиксации штрафной функции„ счетчик 20 итераций. устройство работает следукщим об- 75 разом.

В процессе ввода в -ячейки блока 2 из блока 3 заносится информация об ограничениях на сдвиги в соответствующих.точках деления пути и о свободных членах неравенств решаемой системы (вычисленных во время ввода как функции от значений стрел кривизны в соответствующих точках деления пути) .

В регистр 5 заносится код, равный абсолютной величине ограничения. d. на невязки X . В регистр 7 заносится код, содержащий единицы во всех разрядаж, кроме фиксированного числа младших разрядов, куда заносят нули.

Число нулевых разрядов соответствует ближайшему к nL числу eL =2", причем (1

Таким образом, регистр 7 маскирует нулями некоторое заданное множест- у5 во разрядов арифметического блока 1.

Если в процессе вычисления иевяэки ее значение по абсолютной величине превышает установленное ограничение, то по крайнеЙ мере в одном из неэа- 50 маскированных старших разрядов арифметического блока 1 появляется единица, которая через элемент ИЛИ 9 переключает триггер 17 в единичное состояйие. При этом информация об абсолютн (м значении невязки поступает в блок 2 иэ регистра 5. Информация о знаке невяэки 2 поступает на вход знакового разряда регистра 5 непосредственно с выхода знакового разряда арифметического блока 1. Триггер 60

17 перед началом вычисления очередной невязки предварительно устанавливается в состояние "0" управлякщим сигналом на соответствующем выходе блока 4. 65

Коды, записанные в регистры 5 и 7, уменьшаются, например, в 8 раз путем выполнения операции трехкратного сдвига в сторону младших разрядов.

Таким образом, вначале ищется решение задачи при искусственно уменьшенных (по сравнению с заданными) ограничениях на невяэки. На это отводится, например, шестнадцать итераций.

По завершении шестнадцатой итерации на выходе четвертого разряда счетчика 20 появляется управляющий сигнал, по которому происходит однократный сдвиг кодов в регистрах 5 и 7 в сторону старших разрядов. При этом ограннчение на невяэки возрастает в два раза. Если в последующие шестнадцать итераций решение не будет обнаружено, то зта операция повторяется вновь . (через каждые шестнадцать итераций на выходе четвертого разряда счетчика 20 появляется управляющий сигнал) . Описанная операция сдвига кодов в регистрах 5 и 7 повторяется до трех раз, т.е. до тех пор, пока не будет получено решение либо не исчерпается минимум допустимого числа итераций (64) . В последнем случае в счетчике 20 устанавливается код 64 и единичный сигнал с выхода. старшего разряда этого счетчика проходит через элемент ИЛИ 11 на вход схемы останова устройства в блоке 4.

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

В процессе вычисления величин сдвигов Х; каждая из этих величин прибавляется к содержимому специальной ячейки блока 2 памяти, в которой накапливается сумма модулей сдвигов

tYl

5-"Ег )х;1, Тал проверяется на допустимость по заданным ограничениям сверху (ц) и

I снизу (ф„), т.е. проверяется справедливость неравенств

Эта проверка осуществляется путем анализа знака разности (х„ - ф(), а затем (X„-ь ;)

Если вычисленный сдвиг Х; не удовлетворяет какому-либо иэ ограничений, то этот факт Фиксируется путем записи штрафной функции (единичного сигнала) в соответствующий (-ый разряд сдвигающего регистра 13, Одновременно сигнал с элемента

ИЛИ 10 переключает в единичное сос886004 гов осуществляется за счет всех составляющих вектора сдвигов, т.е. всем сдвигам Х> приписывается штраф Ч; =

=1(j =1,2,...,1Т) .

Таким образом, минимизируемая целевая функция равна

-$ $ -$»», S»11

8=A +8 и 9 .C(Ix<-$„I Ч,.+ix,-S,IVД+ Ч . IX I

f0 npv X< 4 y„ 1 при Х ° >.

М = /О при Х; р . (1 при Х; <р

Ч= (0 при Х;=Р;

11 при X„. >р;

50 где Кн«Ф

S5 то минимизация целевой, функции осуществляется только эа счет тех составляющих Х„ вектора сдвигов, которые выходят за рамки своих локальных 60 ограничений и для которых штрафы f;=1. Если же S„> $ „„ «, то все последующие значения суммыЗ($;,,,В„,,..., Sw) и подавно будут больше S у, В этом случае минимизация суммы сдви- 65 где Pах а ".

1 тояние триггер 19, обеспечивая этим запрет на прохождение (в конце итерации) управляющего сигнала на вход схемы останова устройства, поступает в блок 4, инициируя выполнение операции сложения содержимого специальной ячейки в блоке 2 с абсолютным значением разности ()(< - ) либо (М; - l3 „), т.е. выполнение операций накопления следующей суммы:

l»1»» а=а-а,-д а,.= (I»,-ð<.», к, s,.i ») Ч = 0 при Х; i fb 1 при Х < P!.

Полученная сумма А записывается снова в специальную ячейку блока 2, предназначенную для хранения теку- ;ф щего значения минимизируемой целевой функции А. (В дальнейшем для определенности будем называть эту ячейку регистром целевой функции A) . Содержимое регистра целевой функции А ис- 5 пользуется при вычислении нового век«+» тора невязок Z „ который обеспечивает на последующей итерации уменьшение величины этой целевой функции.

В устройстве требуется, чтобы и ЗП сумма модулей всех сдвигов Х (как

1 оштрафованных, так и неоштрафованных) не превышала установленное для данного микроплана ограничение 5 „, » . Эта сумма накапливается по мере вйчисления величин сдвйгов Х; в специальной ячейке блока памяти, которую для определенности назовем регистром суммы модулей сдвигов.

Текущее значение накоплений суммы равно

S.--5. +!Х 1

1 1» 1

1=1,2,..., т

Ни одно из текущих значений суммы модулей сдвигов не должно превышать or- 45 раничение S a», величина которого хранится в одной из рабочих ячеек блока 2

5„=KIX

1 1

» = 1, rX,..., ò

Если это требование выполняется до конца расчета всех сдвигов Х;, т.е. сумма

»». »

0 при 5„„<$

1 прин >$

Сравнение текущего значения сумея модулей сдвигов со своим ограничением происходит путем анализа знака

Разности {9„ — S „ ) . Есди5; >S a»» то этот факт фиксируется путем зайиси штрафной функции (единичного сигнала) во все разряды сдвигающего регистра

13. Таким образом, будут оштрафованы все слагаемые Х; суммы $ В IX I

Одновременно сигнал с элемента ИЛИ

10 переключает в единичное состояние триггер 19, обеспечивая этим запрет на прохождение,в конце итерации) управляющего сигнала из блока 4 на схему останова устройства через элементы И 16 и ИЛИ 11, поступает в блок 4, обеспечивая вычисление всех последующих сдвигов Х;+1, ..., Х щ без проверки их на допустимость по локальным ограничениям, что экономит время решения. При этом выполняется только операция накопления суммы модулей всех сдвигов. По завершении вычисления всех сдвигов и накопления суммы S -"F,X„i зта сумма переписывается в регистр целевой функции А и используется при вычислении нового вектора невязки г

Новые невязки вычисляются по основной формуле обобщенного градиентного метода . кт1 ««+1 ак«

= Z1++H аг,. номер итерации; градиентный множитель, значение которого определяется выражением

К1 р

» (з 11 значение минимизируемой целевой функции, записанной в

;регистр целевой функции А

1блока 2, частные производные вектора сдвигов Х"по i -иым приращениям вектора невязок г«, ко886004 торые вычисляются по формулам:

3Х к M 4 64<(ьХ "Ч „-1

0,1,2...,,rn -1, где - m постоянных коэффициентов, 1 которые хранятся в ячейках дополнительного блока 12, з а ьХ - знаки ранее вычисленных величин сдвигов, которые хранятся в соответствующих разрядах сдвигового регистра 6. (сдвиги этого регистра и сдвигающвго регистра 13 осуществляются синхронно в моменты вызова .из дополнительного блока 12 очередного коэффициента t)), Ч вЂ” штрафные функции, значения

j которых хранятся в соответствующих разрядах сдвигающего. регистра 13.

Штрафныв функции принимают еди-. ничное значение в случаях, если соответствующий 2> . не удовлетворяет какому-либо из своих локальных ограничений, сумма модулей сдвигов превышает свое ограничение 6 err . В этом случае всв Ч 1., что обеспечивается путем зааисй единичного сигнала с элемента ИЛИ 10 so эсе разряды сдвигающего регистра 13.

Значения штрафов Ч .подаются в ка честве разрешающих сигналов в моменты вызова иэ дополнительного блока

12 соответствующих постоянных коэффициентов h> приведенным Формул. Значение Ч в соотвевтствующем разряде сдвигающего регистра 13 разрешает (Ч яЦ либо запрещает (Ц -О) считывание с выхода. дополнительного блока

i2 соответствующего постоянного коэфФициента 4 в момент формирования каждого члена суммы парных произведений при вычислении очередной частной производной. Полученные новые значения невязок Z „ записываются

t в подблок .невязок блока 2 и используются при расчете на следующей итерации нового вектора сдвигов Х.

Если все величины сдвигов Х; удовлетворяют заданным ограничениям и при этом сумма модулей сдвигов, также не превышает свое ограничение

Ф g, то это является признаком почения искомого решения. В этом случ -триггер 19, установленный вначале итерации в нулевое состояние сигналом из блока 4, сохраняет это состояние до конца итерации. Нулевое состояние триггера 19 поддерживает единичный потенциал на элементе И 16.

В конце итерации в блоке 4 вырабатывается управляющий сигнал, который поступает на счетный вход счетчика

20 и на элемент И 16. Этот сигнал через элемент И 16 и через элемент ИЛИ.

11 поступает на вход схемы останова устройства в блоке 4. Процесс вычислений заканчиваетсй. В счетчике 20 зафиксирован код числа итераций. Если в течение 64 итераций решение не получено, то останов, устройства происходит по завершении 64-й итерации вычислительного процесса импульсом

15 переполнения счетчика 20. Этот импульс поступает непосредственно с выхода старшего разряда счетчика 20 на элемент ИЛИ 11 и затем иа вход схемы останова устройства.

;ф Описанный процесс минимизации це левой функции предусматривает поиск решения в более узких (по сравнению с первоначально заданными) границах йзмвнения невязок,что повышает

25 скорость обработки. Этим осуществля-ется-оптимизация целевой -функции качества пути (суммы невязок 2;) Формула изобретения

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

ro элемента И и счетчика итераций, выходы которого соединены со входом третьего элемента ИЛИ и вторым входом регистра ограничения невязок и со вторым входом регистра-маски.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

Р 802967, кл. G 06 Р 15/20, 1977 прототип).

886004

Составитель Ю.Власенко

Редактор И.Михеева Техред И. Гайду

Корректор С Щомак

Заказ 10560/78 Тираж 748 Подписное

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

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

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4