автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Исследование принципов построения стохастических процессоров, реализующих адаптивные квазиградиентные методы статистической оптимизации

На правах рукописи

° СВИСТУНОВ

«о I..- -

' Сергеи Георгиевич

ИССЛЕДОВАНИЕ ПРИНЦИПОВ ПОСТРОЕНИЯ СТОХАСТИЧЕСКИХ ПРОЦЕССОРОВ, РЕАЛИЗУЮЩИХ АДАПТИВНЫЕ КВАЗИГРАДИЕНТНЫЕ МЕТОДЫ СТАТИСТИЧЕСКОЙ ОПТИМИЗАЦИИ

Специальность 05.13.05 — Элементы и устройства вычислительной техники и систем управления

Автореферат диссертации на соискание ученой степени кандидата технических наук

САНКТ-ПЕТЕРБУРГ 1996

- Работа выполнена в Петербургском государственном университете путей сообщения.

Научный руководитель —

доктор технических наук, профессор В. В. ЯКОВЛЕВ

Официальные оппоненты:

доктор технических наук, профессор И. В. ГЕРАСИМОВ;

кандидат технических наук, старший научный сотрудник Г. В. ДОБРИС

Ведущая организация — Информационно-вычислительный центр Октябрьской железной дороги.

Защита диссертации состоится « Я.?,1996 г. в Л!0.0, час на заседании диссертационного совета К 063.36.04 Санкт-Петербургского государственного электротехнического университета имени В. И. Ульянова (Ленина) по адресу. 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке Университета.

Автореферат разослан « . . . »....... 1996 г.

Ученый секретарь диссертационного совета Ю. В. ЮРКОВ

Подписано в печать 11.11.96 г. Формат 60Х84'/1б. Бумага для множ. апп. Печать офсетная. Объем 1 п. л. Зак. 1078. Тир. 100.

Типография ПГУПС. 190031, СПб, Московский пр., д. 9.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ. .

Актуальность темы. Проблема разработки теоретических методов проектирования специализированных процессоров является актуальной, поскольку широкое пришненпе спецпроцессоров характерно для с алых разнообразных систем обработки информации, начиная от микропроцессорных систем и включая высокопроизводительные кногопроцзссорннэ комплексы. Кроме того, в настоящее время спецпроцессора повсеместно применяются и в традиционных областях - системах управления, работающих в реальном насатабэ времени. Вопросы теории спецпроцессоров рассматривались в трудах В.Д. Байкова, В.Б. Сколоза, Д.В. Пузанкова и других авторов.

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

Наличие случайных-сигналов (покэх) пэ входе. спецпроцессора позволяет сделать продполопепиз, что можно отказаться от "традиционных" вычислительных устройств (ВУ). где информация представлена ?логоразряднш.ы двопчпикн числами, и перейти к использовании стохастичоскпх вичпслитехыггх устройств (СтВУ), где входная информация преобразуется в пипулъсн, вероятностные характеристики которых зависят от входного сигнала. В результате прзсбрезсЕзнкя код-вероятность (ПКВ) значительно упрощается аппаратура спецпроцессора и уменьаается вре?,*я выполнения отдельной итерации. Теория СтВУ развивалась в работах В.В. Яковлева, Р.Ф. СЗдорова, Г.В. Добриса и других авторов. Учитывая представленные факты, можно предположить, что одним из путей повышения эффективности репэния задач

статистической (стохастической) оптимизации является использование СтВУ. Исследование этой гипотезы и является одной из главных задач данной работы.

Целью работы является решение следующих задач: разработка и исследование структур стохастических оптимизаторов;

- разработка основ проектирования устройств стохастической оптимизации на СтВУ.

Основные направления выполненных исследований:

- разработка численного метода и алгоритма стохастической оптимизации для СтВУ, исследование сходимости вычислительного процесса;

- анализ и оценка производительности метода стохастической оптимизации, реализуемого на СтВУ;

- разработка структуры СтВУ;

- анализ быстродействия оптимизатора;

- разработка методов инженерного расчЗта структур СтВУ;

проведение сравнительного анализа оптимизаторов, реализуемых на основе СтВУ и на "традиционных" ВУ;

- разработка имитационной модели стохастического оптимизатора и статистическое моделирование его работы;

- статистическое моделирование алгоритмов-аналогов; -сравнительный анализ результатов статистического аксперимента.

Методы исследования. Включбнные в диссертацию результаты исследований базируются на теоретических результатах и результатах имитационного моделирования на универсальной ЭВМ. Математический аппарат включает в ' себя элементы теории вероятностей, математической статистики, функционального и математического анализа, математического программирования, теории рекуррентных методов стохастической оптимизации, статистического моделирования. Анализ работы предлагаемых устройств был проведЭн двумя путями, а именно математическим и имитационным моделированием. .

Научная новизна. Научная новизна работы заключается в том, что впервые .дляреализации адаптивных квазиградиентных методов статистической оптимизации предложены и исследованы численные

метода, реализуемые на СтВУ. Разработан алгоритм работы СтВУ и синтезирована структурная схема оптимизатора. Проведан анализ быстродействия и даны метода инженерного расчЗта стохастического оптимизатора на основе СтВУ. Проведено статистическое моделирование работа оптимизатора и дано сравнение результатов с алгоритмами-аналогами, реализуемыми на "традиционных" ВУ,.

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

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

Предлагаемые автором методы дают возможность сократить время решения задачи стохастической оптимизации по сравнению с "традиционными" ВУ.

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

Апробация работы. Основные результаты диссертации докладывались и обсуздались на кафедре "Электронные вычислительные машины" ПГУПС, в международной школе-семинаре "Перспективные системы управления на железнодорожном, промышленном и городском транспорте", Алушта, 1995 г.

Публикации. По теме диссертации опубликованы три работы.

Структура и объ8м работы. Диссертация состоит из введения, четырбх разделов, заключения, списка литературы, включающего 121 наименование, семи приложений. Основная часть работы изложена на 144 стр. машинного текста и содержит 66 рисунков,21 таблицу.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность исследования, дана краткая характеристика диссертационной работы, намечена цели и метода исследований, показано практическое значение работы.

В первом разделе дана общая характеристика стохастических методов оптимизации.

Под методом оптимизации обычно понимают способ, с помощью которого решается следующая задача: требуется найти х*-точку минимума (максимума) функции f(x) при условиях хс2ИКп. На практике, часто приходится учитывать влияние помех , которые накладываются на функцию Г(х). Помехи могут быть погрешностями вычислений, измерений и т.д. При наличии случайных воздействий (помех) известна не сама функция Г(х), а некоторая функция ср(х,ш) или е5 градиенты, где (О,й,Р)-вероятностное'пространство. В этом случае, в качестве Г(х) оСычно принимается детерминированная функция типа среднего риска :

1(х)=Нф(х,ш)= Г ф(х,ш)Р((Зш) , . окО.

где М - математическое ожидание.

Метода условной оптимизации используют когда х-некоторое подмножество R". Выбор того или иного метода условной минимизации зависит от способа . задания множества X. . Если Ж имеет простую структуру (например, гиперпараллелепипед) то удобно использовать проекцию точки на многество X:

ха+1^ив-рв£3), - ■ .

где ях(х) -проекция х на множество X; т.е. rcr(x)=ar^nln|x-s|, ,

где в - номер итерации, - стохастический квазиградаент (СКГ), т.е. случайный вектор, условное математическое ожидание которого совладает (или близко, в некотором смысле), с

градиентом (обобщённым градиентом f(х)) функции i(x).

Исследованиям стохастических квазиградаентннх алгоритмов посвящены многие работы Ермольева Ю.Н., Урясьева С.П. и других авторов. Если величина рэ адаптивно меняется, а да является детерминированной, то численный метод позволяет быстро достигнуть окрестности точют минимума х*. В 1990 г. оыл опубликован (Урясьев С.П.) метод адаптивной стохастической оптимизации:

Теорема I. Пусть i(х)-випуклая (возможно, негладкая) функция, заданная на выпуклом компактном подмножестве Функция i(x) удовлетворяет условию Липшица на Ж. Если выполняются условия: аа=а>1, з=0,1,... шах|х-у|=с1 и х,у«Х, |4ец^С2 п.H.,3=0,1 ,... И Ъа->0 п.н. при 8-та, р>0,

0^21ogatHsa^ 10<:) п.н. , з=0,1,..., тогда с вероятностью 1 все

предельные точки последовательности (Xs) (задаваемой

соотношениями:

„ - -<£э+1,Дха+1>-р

ха+1=тсл(ха-р8е8), pa+rnin(p,pea s) И

Mt53/Fs)=Iia|e€Si(xa)+bs, з=0,1.....

где о-алгебра IF определяется случайными величтами (x0,{°,...,xe"1.Ce"1,*e) и C4e-t«U"). где i (x"k«Ue).

JC X

Н Ja=i Us)+b3) принадлежат множеству ^={x*€X:i(x*)=mln Г (у)).

У€»

Здесь 01U)- субдаффэренциал функции Г(х), Мо - условное математическое охидание.

Метод данный в теореме I. позволяет "быстро" ( по экспоненте ) достигнуть окрестности s/янимума функции Их), но требует "трудоемких" вычислительных операций: возведониа в вещественную степень, определение скалярного произведения векторов в п-мэрлсгд пространство. Использование СтВУ позволяет устранить эти "трудсЭмкиэ" вычислительные операции и сохранить приомущэства адаптивной регулировки вага.

3 (СтВУ) входная информация преобразуется в

стохастическую последовательность импульсов и все дальнейшие операции осуществляются только над ниш . ПричЗм для представления исходных величин используется вероятность появления' импульса. Представление исходных величин стохастическими последовательностями осуществляется их преобразованием на специальных схемах: линейных и нелинейных преобразователях код-вероятность (ЛПКВ.ШШВ).

Таким образом на вход преобразователя код-вэроятность (ПКВ) поступают реализации стохастического квазиградиента (CICT) (х°) функции i(x), на изге итерации с номером в в точке х^еК". СКГ-является n-мерным случайным вектором, каждая

компонента этого вектора (k=T7n) в гаде щфрового кода или аналоговой величины поступает на вход ПКВ и преобразуется в случайную величину р®, принимающую .зпач&шш на множестве {-1,0,1). Вероятностные характеристики случайной воличшш (3®, долиш быть такими, чтобы обеспечивалась сходимость процесса с достаточной скоростью. Поскольку принимает значения {-1,0,15, то операция уиноаздсш на р® нэ является умпоеошшм игогорззрядаых чисел, а фактически -зто логическая операция. Данное обстоятельство позволяет строить весьш простые и быстродействующие схема вычислительных устройств.

На рис. I. показана структурная ozena наиболее распрастранбвного ПКВ.

sign £»

Рис. I.

Здесь аэ-тюхоторая числовая последовательность. На внходо ШШ ними злак (algn ç®> и '?, t>0

где u+(t)=-- функция ХегасаЯда •

[о, t«0

Если аа - равномерно распродолоаа от О до с=2г, то 7s=cß8 будот CItP (Jjinawji í(x), что п позволяет рэалпзоватъ адапишшю квасшрадакяшщо алгоритм! на СтВУ. Рассиатрпвшк'ся цскоторкэ прясладпно задачи, где жтаолызувтся

CTOXDCTÍI-ЮСКОЯ спивязшпп.

В раздела росскирдгаотся ряд стохастических транспорта!« задач, яогорнэ больпо соотвэтствуют реальннм ситуациям, чей доторгттаровппшз молол;! плшшровшгая пзуовооок, т.к. спрос на продукции и объем производства продукта в рэзличшх пактах подверши 'случаЯпк1 кояобашвэа. Затрата на оргашгсцж» перевозок такнэ завися? от ншгах ' непредсказуемых факторов.

Оптатзоцая паретотров зэхаолотзтсках процоссов показала па претро яспсш,80вшш СтЕУ для ваплапш стоило из шит. Том' описшзазтся' тсгшяра'шричосюа стсхастичоксш! оптпггзатор, яспсш>зускаЗ для овтомагачосксго управлопял процэесом. подготовка хрокаяисй пшгаы л процессом шоиавна стекла.

Псяалуй нокбэлоэ часто пэсбходакость оптпкЕзащщ возникает в связи с проблемна ядзнифшацил, т.е. при построит модола по шсяцпмся дашши об объекте .

Пртксрзш могут слугпть: задача статиотичоской оценки параеттрсв, задета рэгроссш, робсстпоэ оцепшзаппз, ' рекуррентное оцзяившшв, сналпз дшашх я т.д.

В рздпотезсЕЖО (радколошта, радненавагашш. радяоуцрозлзнан, систеяах связи, радиоастрономии, гадроакустк» ) пзмарэгом параметров сигналов производятся в условиях помог, (остоствзттгагх п йскусотЕсшшх). Обперукшшэ сигналов, измэрошм их пэрелонрев о условиях 'паках в раототалтоагак я nwjr -густоггот • шггеках прзазподится стотпстггеэсккмя иэтодеми, î!ç:i обработке радпотепшескях сигналов в роальпем

масштаба времени требования к быстродействию могут йыть очень высокие.

Для обнаруасения дефектов в рельсах на келезшх дорогах используются магнитные дафзктоскопы. Амплитуда сигнала , принимаемого дефектоскопом, имеет случайный характер н зависит от спорости движения вагона-дефектоскопа. Обнаружение неисправности осуществляется путём сравнения сглютгуды сигнала с порогом квантования 0*. Для решения этой задачи могут использоваться методы стохастической оптимизации.

Рассмотревшие в диссертации примеры показывают , что решение задач идентификации в системах реального времени кокет предъявить к стохастическим опткмизирую;дим вычислительным устройствам очень высокие тробования по быстродействию, надёжности и допустимому весу и габарита«; в этем случае целесообразно создавать специализированные стохастические оптимизатора. Кроме того, специализированные стохастические оптимизатор!! могут быть сопроцессорам! для универсальных ЭВМ.

На основании изложенного материала сделана постановка задачи и сформулированы цели исследования.

Во втором раздало рассматривается реализация стохастического оптимизатора на основе ЛПКВ. Дано математическое описание вычислительного процесса, реализуемого на СтВУ с ЛПКВ и доказана следующая теорема о его сходимости:

Теорема 2. Пусть £(х)- выпуклая (возмог,но, негладкая) функция, заданная на выпуклом компактном множестве Функция удовлетворяет условию Липшица на Если выполняется: яах5х-у|=с

(ф^г1 п.н. 1 а, к=1.....п

МвСв=Г(хв), где 1(хв)евГ(1в),

где )и+(1|-а3), к=1,...,п

ав€1К0,с], 0>0,

то с вероятностью 1 все предельные точки последовательности {хе> (задаваемые соотношениями:

ха+1 =1; (^_2шг(га)тВ) 3=0>1

где г 1>тШСа„,г -<73+1,Дхв+1>-а2епг(Га)},'

3+1 "О 3 *

Чо>0, Го=0, ЛХа*1=Х3+1-Х3) принадлежат множеству И*=<х*€Х: Г(х*)=ш1п Г (у))

Для оценки скорости сходимости вычислительного процесса доказана следующая теоре:,:з:

Теорема 3. Для последовательности Сх3) выполняются все условия теорекы 2. , функция Г(х) двазди непрерывно дафферэнцируека ка открытом множество , содержащая 'Д, И57а|г®о 3=0,1,2,... №):>Г(х*)+ВЕх*-х|г,

где В>0 и х* точка миЕмукэ 1(х) на К, тогда при ео=В/(1,251п2) имеем 156°° оГтхг! п.н.

На основании теоремы 2 определяется алгоритм работы СтВУ с ЛПК8 для решения задачи стохастической оптимизации. Как видно из теоремы 2 ', с увеличением размерности пространства п увеличивается количество операций, которые могут выполняться параллельно и используются только "короткие" операции: пересылки, сдвиг, алгебраическое сложение, сравпенио чисел, т.к. 71се{-21,0,21>, где 1-цолое, 2еп*(г) - два с целой степени.

При синтезе структурной схемы надо учесть, что в данном алгоритме отсутствует: операции умножения, деления, возведение в степень, обращение к таблицам ПЗУ, поэтому следует выбрать регистровую структуру СтВУ, которая синтезируется по алгоритму.

Будем считать, что 1 ,п, разрядность регистров ш, время сдвига на один разряд 1;сда, время суммирования время

пересылки 1;п, Б- общее число итераций, Ъскг- время вычисления СНГ заданы.

Общее время выполнения одной итерации для стохастического оптимизатора будет равно:

Общее время выполнения алгоритма будет определяться числом иагов итерации Б.

г0=5гкт=5£гокг+2гсдз+згпису,,(€пЬ(1о2гг1)+1)!

Если задана погрешность вычисления 0, то получим:

И § х341 -х* 1:> 56са"=е, т.к. Б»1, то клеем, что (Б+1)В2

3^1,56псо ГД0 0г _ даспорсдя помеха. *

Для последовательных оркфйэтгсю-лопиеских устройств »¿инимальное время счОта:

гт1п°1 '562°Я 1 ^Зи+Зт • еп'г (Го^п Ж, 6В

где х - длительность малинного такта.'

При использовании сумматоров . с групловым переносом

еШ (Ю^п) З'с

6В . ■

При реализации вычислительного процесса по теореме I на "традиционном" ВУ' последовательного действия минимальное время итерации , будет значительно больше гктт1п для СтВУ. При

этом обпей; внигршз ео времени рэвешш задачи оптимизации'может Сыть в б-Ю раз.

Рассмотрены, ьатодо расчЗта стохастических оптимизаторов с ЛШВ.,

Исходными данными для расчОуа являются : : п- размерность пространства, с=2г, гдо ]ф<с,к=Т7п п.н., гдэ ?в- стохастический квазяградазЕт;' . й- область задания аргументов Сушщсл Цх) {ак,Ьк), к=Т7п

- ",, ... В- параметр функция. }+В|х -х|*");

гскг~ ЕР°г-;л опредолзгыя вектора 5°; . .

о2- дисперсия компонента вектора С1СГ;

Н- количество шючгщях двоичных цифр в «омпонанто Еокторз С?:

Д- погрешность еычислэшй, 2""3=A=4L'(xk-x*),. k=TTñ, где х*- точка юпшмумз функция í(x); t - время решения задачи.

В результате расчёта определяется разрядность регистров СтВУ и требуемая длительность казкшого такта.

В третьем разделе рассматривается . реализация стохастического оптимизатора на основа 1ШКВ. Дня этого целесообразно рассмотреть пэллгейгоэ преобразование код-вероятность, например, где ав€ШО,В°] и Б3<с. Инеем но выходе IfflKB случайную величину slsn(íj®)|p®|=slgn(S®)u+(|E®|-a°) , где и+(х)- функция ХэБнсаЯда

Если взять величину D3 пз условия, что .,|),

то очевидно, что при тисом нэлшойнил преобразовании свойства

СНГ сохраняются.-Величину Da гязкно определить как Ds=2 s, где 1 иеиианыаая целая степень nprs icotopca выполняется перзвенство Как к ранее, рассматриваем случайнко события шгя, где (П.Г.Р)- вероятностное пространство.

Пусть • ГПСЧ генерируот равномерно рзспроделЭшше случайте числа Xa в диапазоне СО.сЗ. Над величинами t0 производится нелинейное прзобразовашгэ вида:

Мокно показать, что 7¿=Ds3igi(££)u+(|^|-<*s) будет компонентой

скг. .

Дано математическое сшиеаякэ. вычислительного процесса, реализуемого на СтВУ с ШКВ я доказана его сходимость:

■ Теорема 4. Пусть f(x)- вазуклзя (возмсето, негладкая) функция, заданная на выпуклой клашастнеа мяагествэ ^".Функция удовлетворяет условию Липшица па Ж. Если выполняется:

x.ylx 1

п.и. в=0,1,... (k=T7ñ>

МеСа=Г(ха>,

где 1(хв)е0Г(ха), Св=7в-1(хе),

где 7£=В°а1да(фи+(|ф-ав). к=ТТп и ав=гв-1)эепг(гэ/ва), гвешо.сз

21в=Бвйпах{К®|.....| )

в>0,

то с вероятностью 1 все предельные точки последовательности

(Xе) (задаваемые соотношениями:

по.« епКг )

3 Г), 8=0,1,...

гдо ге+1=П11п{яо,гв-<7в+1,Дхв+1>-02 ° ),

Яо>0, го-0, Лхе+1=хв+1-хв)

принадлежат множеству Х*=1х*(Х: 1 (х*)=ш1п1(у)}

уеЯ

Для оценки скорости сходимости вычислительного процесса доказана следующая теорема:

Теорем 5. ■ Для последовательности {х°) выполняются все условия теоремы 4 , функция 1<х) дваады непрерывно дифференцируема на открытом множестве, содержащим Ж и 1(х)?Х(х*)+В|х*-х|г, где В>0 и х* точка минимума функции

I(х) на X, М|7°|е<Од в=0,1,..., тогда при ^"П^Гй? ИМ90М Вг(1+е)

В качества о^ моино взять значение тах1вН(1У®)). Исследован вопрос . об устойчивости вычислительного процесса.

На основании теорема 4 определяется алгоритм работы СтВУ. Из алгоритма можно сделать следущие выводы: - с увеличением размерности пространства п увеличивается количество параллельно выполняемых операций;

используются . только. "короткие" арифметико-логические операции; пересылки, сдвиг, сложение, вычитание, сравнение

чисел.

Выбирается регистровая структура СгВУ т.к. в алгоритме отсутствуют операции умножения,деления, возведения в степень, обращения к таблицам в ПЗУ.

Операция НПКВ. осуществляется с помощью ГПСЧ, комбинационных схем и операции сравнения чисел.

Общее время выполнения одной итерации для стохастического оптимизатора с НПКВ будет равно:

^Т^сдв^п+Ч*161* (1°3гп)+1 нгскг

Общее время выполнения алгоритма будет определяться числом иагов итерации Б.

^^^"скг+^сдв^ Ьисум(епг(108гп>+1>1

Если задана погрешность вычисления 6, то из формулы получим:

Ц|Х3+,-Х*|24^4=9, т.К. З»1, ТО

(Э+ПВ2

имеем

о .1,56пог 6Вг

Для последовательного арифметико-логического устройства получим:

^чгУ'55"0 II 4+Зям-ап'еп1 (1о^п) 1т 9В

При использовании сумматоров с групповым переносом:

гт1п=1,д|г [ 14+2 У5н-2Уш • епг (Ю^п) ] т

Исходники данными для расчета ОСтВУ с КПКВ является : п- размерность пространства, с=2х, где |?°|<с,к»Т7п п.н., где Iе- стохастический квазиградиент; Ж- область задания аргументов функции 1(2) (а^,^), к»ТТп а^х^;

В- параметр функции (1(х)>1(х*)+В1х*-х|г);

Нг?М(0о)г, где Ба-21а?яш:{|Е»|.....в-0,1,...;

гскг- время определения вектора 5я;

Л- количество значащих двоичных цифр в компонззте векторе 5®;

Л- погрешность вычислений, 2~;,=Л=4К(хк-х*)г-1 к=Пп, где х*- точка минимума функции Пх); г0- время роиения задачи.

Расчёт стохастического оптимизатора включает определение следущих величин: разрядности всех регистров в форме с фиксированной запятой, количества итераций Б,длительности такта т. В рэсчбт входит синтез ГПСЧ.

В четвертом разделе рассматриваются вопросы имитационного моделирования СтЕУ с ЛЛКВ , НПКВ и алгоритмов аналогов. В качестве типов исследуемых функций рассматриваются: квадратичные, "овражные" и негладкие. Проведено 16 различных вариантов статистического моделирования для СтВУ с ЛП1Ш и 16 вариантов для СтВУ с НПКВ. Результаты статистического моделирования подтвердили правильность асимптотической оценки сверху для погрешности вычислений.

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

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

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

Асимптотические свойства алгоритма проявляются при больших значениях номера шага итерации а. На рис. 2. приведено значение 1$1|ха-х*{г для случая квадрвткческой функции (п=3, о=0,3 ) в зависимости от относительного времени Х/ч. При этом СтВУ сделает 30000 итераций, а за это время адаптивный алгоритм на БУ сделает сделает только 1300 итераций.

1£М|хв-х"|г

0-4 0.8 1.2 1г6 2г0_

0

-1

-2|--3

-4 ■

-5

-6 .

Рис.2. Результаты стохастической оптимизации (квадратичная функция п=3, о=0.3 ): 1-адаптивный алгоритм; 2-алгоритм СтВУ с НПКЗ.

Использование СтВУ с НПКВ обеспечит за одинаковое время в асимптотическом рекяае работы точность на порядок выше чем адаптивный алгоритм , реализованный на "традиционном" ВУ. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЕ РАБОТЫ

1. Дано математическое описание вычислительного процесса для СтВУ с ЛПКВ и НПКВ, доказана его сходимость при весьма общих предположениях: требуется только выпуклость функции на выпуклом компактном множестве.

2. В стохастических оптимизаторах на осноез СтВУ исключаются '"медленные" операции: умнозяниэ, деление, возведение в вещественную степень, остаются "быстрые": сдвиг, сложение, вычитание, сравнение чисел.

3. Дана оценка производительности работа СтВУ в зависимости от числа итерацяй для дважды непрерывно дифференцируемых функций.

4. Предложен алгоритм работы СтВУ с учбтом параллельности выполнения операций над вектора*® в К".

б. В качество структуры вычислительного устройства выбрана регистровая структура, как наиболее отвэчащая алгоритму работы СтВУ.

в. Разработана структура вычислительного устройства и отдельных его элементов.

Проведан анализ времени выполнения задачи стохастической оптимизации на СтВУ при использований последовательного арифметико-логического устройства для различных разрядностей используемых регистров и различных размерностей пространства переменных исходной задачи.

8. Проведён анализ времени выполнения задачи стохастической оптимизации на СтВУ при использовании сумматоров с групповым переносом для различных разрядностей используемых регистров и различных размерностей пространства переменных исходной задачи.

9. Разработана методика расчёта стохастических оптимизаторов с ЛПКВ и НПКВ.

10. Предложен НПКВ, позволяющая увеличить быстродействие СтВУ по сравнении с ЛПКВ а 2-3 раза.

11. Путбм статистического моделирования исследована скорость сходимости вычислительного процесса в СтВУ и обоснованность теоретических оценок , данных в диссертации.

12. По результам статистического эксперимента для различных алгоритмов-аналогов можно сделать вывод, что СтВУ превосходят по точности вычислений всо другие исследованные алгоритмы при одинаковом времени счОта.

1. Свистунов С.Г. Случайно-импульсное микропроцессорное устройство для ресэная задач линейного стохастического программирования// Сборник научных трудов "Микропроцессорные система на железнодорожном транспорте", ЛШЕГ,1931,-0.39-1

2. Свистунов С.Г. Принципы аппаратной реализации стохастического оптимизатора// Труда мекд. школы семинара "Перспективные система управления на кэлезнодорожном, промышленном и городском транспорто", Алушта, 199-5.-19с.

3. Свистунов С.Г. Компьютерный регистратор сигналов для магнитных вагонов-дефектоскопов //Информационный листок N99-96, серия P55.4I.37, 1935-20.

ПУБЛИКАЦИИ ПО ТЕ.Е ДИССЕРТАЦИИ