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

»' 'г О ■■) ,9 О

АКАДЕМИЯ НШ СССР

0РД5НА ЛЕБНА ИНСТИТУТ ПРСБЯЕ!/! УПРАВЛЕНИЯ (АВТОМАТИКИ И ТЕПШЕХАНИКИ)

На цравах рукописи ИСАЕВА Наталья Александровна

62-501.72

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

Специальности 05.13.13 и 05.13.II

- Вычислительные малины, комплексы, системы и сети

- Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ

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

Москва - 1990

Работа выполнена в Институте проблем управления

Научный руководитель - д.т.н., профессор Ю.М.5АТКИН Официальные оппонента:

доктор технических наук, профессор Э.А.ТРАШНГЕРЦ кандидат технических наук

В.Б.ВОРСККСВ

Ведущая организация: Всесоюзный научно-исследовательский институт системных исследований АН СССР

Зацита состоится чн - 1990 г. в ?О часов

на заседании Специализированного совета ДС02.68.01 Института проблем управления (117806, Москва, Профсоюзная ул., 65).

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

Ученый секретарь Специализированного совета д.т.н., профессор

В.В.ИГНАТУЩЕНКО

рТ.;;,;;^' '

I ;

I *

ОВЦАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Одним лз широко используемых современных подходов к оптимизации процессов решения сложных задач на ЭВМ - общим как для :слассичес.шх численных методов рзшения оптимизационных задач, так и для нетрадиционных, эвристических методов, - является настройка параметров используемте алгоритмов и реализующих их вычислительных процедур. Управление этими параметрами непосредственно в процессе счета задачи является одним из основных принципов гтрограммного обучения ЭВМ решению сложных оптимизационных задач,- принципов, разработанных и развивае;.ых в Институте проблем управления. Центральная идея такого подхода заключается в накоплении опыта решения задач данного класса и в использовании этого ошта для автоматического выбора или поиска решения аналогичных задач того же класса, с целью уменьшения объема вычислений, необходимых для получения решения текущей задачи или потока однотипных задач. Под потоком однотипных задач здесь понимается набор задач, имеющих идентичные математические модели одинаковой или близкой размерности и характеризующиеся некоторой системой признаков Р, удовлетворяющих следующему условии: из близости значений признаков Р следует близость оптимальных значений управляющих параметров VI

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

следовательно, времени счета оптимизационных задач обеспечивается здесь за счэт параметризации (динамической настрой»! параметров) гтр-.'.:.'.еняе:.ых матодов и алгоритмов решения этих задач на основе накопления и использования опыта их решений.

Существенным резервом для умень'ленля времени решения таких задач является параметризация процесса функционирования самого комплекса обучапгихся программ (т.е. параметризация алгоритмов КОП), - развеется, наряду с параметризацией алгоритмов решения самих задач.

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

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

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

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

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

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

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

Практическая реализация. Результаты, полученные в работе, использованы в едздупцих организациях:

- в Институте проблем управления при организации вышс-лительных процессов решения оптимизационных задач на стандартных ЭВМ и многопроцессорной вычислительной системе ПС— 2С00;

- в Институте хирургии им. А. 3.Вишневского АМН СССР для реяения задач элекгрокардиостимуляции;

- в ПКИИЗП гракдансельстроя для решения задач оптимальной компоновки архитектурных сооружений.

Практическое использование результатов диссертации под-тзерздено соответстьущими материалам о их внедрении.

Апробация работы. Основные результаты диссертации докладывались на X Всесоюзном совещании по проблемам управления, г.Алма-Ата, 1386 г., на XI Международном конгрессе фонетических наук, г.Таллин, 1967 г., на Ш Всесоюзном совещании "Высокопроизводительные вычислительные системы", г.Таллин, 1988 г., на XI Всесоюзном- совещании по проблемам управления, г.Ташкент, 1989 г.

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

Структура и объем работа. Диссертация состоит из введения, четырех глав, заключения, списка литературы (91 наименований), содерзшт стр. текста, П рисунков, 5 таблиц.

- о -

СОДЕРЖАНИЕ РАБОТЫ

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

Алгоритмическая и программная организация КОП-1 является ближайшим прототипом разрабатываемого в диссертации подхода к организации решения потоков оптимизационных задач. Общий алгоритм использования метода программного обучения ЭВМ и функционирования КОП-1 заключается в следующем.

Процесс решения оптимизационной задачи характеризуется в КОП-1 набором числовых параметров, в который могут входить, например, численные значения параметров алгоритма вычислений, "нсленное значение начального приолижения, заданная точность получения решения, шаг интегрирования либо количество дискретизаций на интервале интегрирования и пр. Эффективность использования каждого такого конкретного набора параметров и их значении при решении данной задачи оценивается количественно по значениям внутреннего критерия эффективности Е, формируемого в процессе решения задачи и включающего как затраты вычислительных ресурсов ЭВМ (в частности - машинное время), так и значение функционала и оптимизационной задачи. Величина и характер изменения критерия эффективности Е, а также результаты анализа предыдущих решений являются основой для работы логических процедур, предназначенных для нахождения эффективных значений управляющих параметров VI , т.е. значений, при которых достигается экстремум упомянутого критерия Е. При этом экстремизация критерия Ь исходной задачи осуществляется не только путем непосредственного решения данной задачи, но и через оптимизацию параметров алгоритмов и вычислительных процедур счета задачи.

Полученный в процессе счета задачи оптимальный набор параметров VI и результаты ее решения вместе со значением критерия эффективности Е, составляют элемент опыта решения конкретной задачи данного класса. Эта информация запоминается в тер-

минах решенной задачи вместе с набором признаков, например, таких как размерность системы уравнений, значения граничных условий и др. Пои поступлении в ЭВМ очередной задачи того же , "класса она идентифицируется по некоторой мере близости своих признаков с признака?® уже решенных задач, в результате чего определяется задача, наиболее близкая к решаемой. Ее решение, а также соответствующий ему набор параметров \л/ используются в качестве начального приближения при решении текущей задачи.

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

Обобщенная структура КОП-1 обведена штриховой линией на рис. I. Процесс функционирования комплекса обучающихся программ на ЭВМ может быть представлен как последовательное включение ряда взаимозависимых функциональных блоков.

КОП-2

ЙСС^рси^Е-де пи£

РДы "Л

ПАМЯТИ

ьрскич 5«°«- Ъг

¿ы*. ИНТ

Логика

Яг

©

И

Запсми «А кие рпьпд щ

От !

1 Г"*** /

© а7

/

|| р 1—- ~—[_ ъ

йю. I

Диспетчерский блок выполняет управление другими блоками программы; в его функции входит вызов и размещение блоков в оперативной памяти, контроль и координация работы блоков логики, оптимизации, памяти и базовой модели. Елок логики яеля-ется центральны:.', в КОП-1, в нем осуществляется выбор наил', тших значений управляющих параметров '<-.' , вычисление величины внутреннего критерия качества функционирования Е, а такхе органнза-шя образки: к блоку памяти с целью поиска информации, близкой к вектору-запросу текущей решаемой задач;!. Ь олске памяти производится запоминание, хранение, поиск и воспроизведение информации. Поиск необходимой информации по своей сути является ассоциативным, а выполняемые б блоке Рп процедуры представляют собой ассоциативную обработку информации, реализованную алгоритмическими и программными средствами. Математическая модель объекта (задаваемая, например, системой дифференциальны: управлений), называемая в КОП-1 базовой моделью , реализуется в блоке базовых моделей , т.е. этот блок осуществляет моделирование функционирование объекта на заданном интервале времени (например, решение задачи Коши в случае задания в ¡и« системы дифференциальных уравнений). Адекватность базовой модели объекту оценивается по значению функционала L , являющегося критерием эффективности целенаправленности поведения объекта, который необходимо экстремизпровать. В оптимизирующем блоке 0„( производится формирование упрошенных оптимизационных моделей у, поиск оптимальных управлений в них, а также выработка прогноза решения в базовой модели. Упрощение модели и с может •достигаться за счет декомпозиции исходной задачи, исключения ^асти связей, агрегирования переменных, линеаризации правых частей дифференциальных уравнений к др. Рецепторный блок ^ предназначен для сравнения прогноза значений фазовых переменны:': модели с реализованным! их значениями в блоке и выдачи информации об их рассогласовании для блоков логики и памяти.

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

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

Применение известного КОП-1 к базовой модели м0 сводится в конечном итоге к решению оптимизационной задачи в самом КОП-1 с помощью некоторого оператора преобразования Ма . Поэтому КОП-1 вместе с исходной моделью Ы5 монно интерпретировать как зновь получаемую модель

Следовательно, к этой модели также можно применить оператор

lid :

двухъярусной организации комплекса обучающихся гтрогра.'лм (КСП-2): во внутреннем ярусе производится решение исходной задачи , а внещний ярус предназначен для настройки параметров внутреннего яруса с целью его адаптации к параметрам конкретной решаемой задачи и к особенностям реализующей ее ВС. Таким образом, во внутреннем ярусе осуществляется параметризация (динамическая "настройка параметров) алгоритмов селения задач, а во внешнем ярусе - параметризация алгоритмов функционирования самого комплекса, причем в этой иерархической структуре имеет место критериальное управление.

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

Обобщенная структура КОП-2 приведена на рис. I. Отметим, что одноярусный комплекс (КОП-1) образует внутренний ярус в КОП-2 и интерпретируется как базовая модель по отношению к энещнему ярусу. Как и в КОП-1, в контуре I КОП-2 осуществляется непосредственное решение задачи, в контуре 2 осуществля-

(I)

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

Полученный в результате работы внутреннего яруса вектор V* = (верхний индекс означает номер яруса, нижний

- номер итерации), состоящий из значений признаков, управляющих параметров и решений, запоминается в блоке внутреннего яруса, после чего происходит обращение во внешний ярус; в блоке этого яруса вычисляется функционал Ь" внешнего яруса (например, расходуемое внутренним ярусом машинное время),формируется критерий эффективности внешнего яруса Е" , по значению которого принимается решение о формировании очередного вектора управляющих параметров внешнего яруса \лУ;Лм , который в качестве управляющей информации снова передается во внутренний ярус.

Отметим, что различные параметры, входящие в вектор неравноценны, во-первых, по их влиянию на значение критерия Е*, а во-вторых - существенно различны по правилам и возможностям их настройки, в частности - в диалоговом режиме.

В отличие от КОП-1 в настоящей работе рассматривается возможность и оценивается целесообразность использования иерархии управляющих параметров 1л/1 ; при этом на верхнем уровне иерархии (т.е. на внешнем ярусе КОП-2) в качестве настраиваемых параметров используются наиболее важные из них, которые и образуют вектор управляющих параметров внешнего яруса У/"- . Следует, однако, отметить, что разделение управляющих параметров на "более" или "менее" важные может быть далеко не однозначным и в свою очередь являться процессом, оптимизируемых при функционировании КОП-2.

В качестве компонент могут выступать:

а) количество одновременно изменяющихся компонент вектора V/1 внутреннего яруса;

б) заданное количество подряд идущих неудачных попыток, после которых изменяется направление поиска экстремума. Фактически этот параметр задает количество обращений к блоку 6т (например, количество решений задачи Копи, в случае задания в

- II -

t«c системы дифференциальных уравнений);

в) значение порогов для распознавания различных конфигураций максимизируемой функции с* , весовые коэффициенты и т.д.;

г) параметры алгоритмов блока Р,, для организации классификационных и информационно-поисковых процедур;

Нахождение оптимального вектора управля-лих параметров

WЕнешнего яруса, по аналогии с нахождением W/)t в КОП-1, основано на эапомииавки получаемой в процессе функционирования КОП-2 информации и последующем использовании ее в логических процедурах поиска экстремума. И в конечном итоге сводится к задаче

4pt = mo ¿Иг Е " (w") ( .

' Jw£tiw г j Г)

Во внешнем ярусе опыт накапливается в виде векторовV^jP.V t i.

Суть предложенного метода формирования очередного вектора управляющих параметров для верхнего .яруса состоит з следующем. КЗ памяти вившего яруса (блок Ru,Pr, ) выбирается информация, состоящая из \i векторов v'^ =]р, W' Z"J-, близких к вектору-запросу ?' по совокупности признаков Р . Поступающая из памяти информация (блок внешнего яруса) используется оператором того же яруса, где из векторов v~ формируется матрица, элементами которой являются векторы W* я соответствующие им значения Е.

Напомним, что в КОП-I наряду с вектором управляющих параметров VJ" используется вектор критериев = . . . , ^ ^ > компонентам которого являются:

- функционал решаемой оптимизационной задачи;

- общее текущее машинное время решения задачи, отсчитываемое от начала решения;

tj'? - отношение приращения функционала к израсходованному на его получение машинному времени;

Ljl, - машинное время ЭВМ затрачиваемое на выполнение одной итерации.

Эти компоненты вектора критериев if используются во внутреннем ярусе при решении задачи различных классов, т.е. независимо от типа или вида модели ju0 .

- 12 -

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

1- '

Акалогичшм образе:/. :.;о:::ет бить сформирован и кг'/.терий эффективности внешнего яруса с" = ь'(м")иеРез вектор критериев г ■=■ ,. , .¡',;, компоненты которого, однако, «мечт иную содоркательнуэ трактовку с учетом специфики функций Еношнего яруса:

,Г, - функционал и внешнего яруса; как правило, это - время рспения задет/, во внутренне:.; ярусе;

- сС'шгз тс;-у.:; ее вр-кия ст начала функционирования КОП-С до те^уцего момента; ^ - приреш:ек;:е йунетксн-.лй мекду двумя обращениями к внутреннему ярусу;

•С ~ машинное время, расходуемое на одно обращение к внутреннему ярусу.

Указанные компоненты ■„," также могут использоваться вне зависимости от типа или вида базовой модели . Сднакс существует следу:о.ци/. путь для упрощения формирования и использования вектора критериев к, соответственно, критерия эффективности внешнего яруса £ - .

Заметим, что параметры ч - ^ ц , <-1 ц вектора | непосредственно зависят от заданно;'; точности решения оцг/.:.:пэицлоннэ-.'. задач;!. Таким образом, вопрос, точности ресения, как к само р-.-ше-ние оптимизационной задач/, обеспечиваются средства:.^ (алгоритмами V. программами) только внутреннего яруса КСП-1. Это создает лрннцип;:альну:-э ьэзмо;-шость исключить средства обеспечения точности решения задачи из блоков внешнего яруса КОП-2 и сэес-тн вектор ц*- и критерий эффективности внешнего яруса к скалярной величине с" = ^ - Ь'. В конечном счете это приводит к существенному упрощению формирования и истояьзсванля £" по отношению к работе с критерием внутреннего яруса ¿' .

В главе 3 рассматриваются особенности организации вычислительных процессов решения оптаиизашошвве задач при лег.ользоза-нии КОП-2.

В рамках КОП-1 параметры блока Ц , в котором реализован

- ГЗ -

прежний алгоритм поиска , задавались фиксированными и ос-

тавались нонзт.тет^п.и; в процессе ресэния оптимизационной задачи. Предлагается, для совершенствования процедур« поиска компонент вектора управляющих параметров внутреннего яруса , непо-

средственно использовать параметры блока и,- внутреннего яруса в качестве кс-мпои-:нт вектора управлякгд'.х параметров внешнего яруса -л* та:::::.; образом, осуцестзлять их настройку з процессе функционирования КОП-2.

Одной из областей эффективного использования КСП является решение задач лариметрической идентификации для сложных статических .' д::н.--:"р-:сс:-:;1х моделей объекта. Однако, применение КСП-1 : реа-тлзсваинкм ранее методом поиск.! управляющих параметров

.. .. для решения кздсбнкх задач приводит к медленно;! сходимости >:терац,:оннсгэ процесса и зачастую - к невозможности но-лека идентифицируемой функши с заданной точностью за приемлемее время. Заметим, что процедура поиска г в КОП-1 организована таким образом, что в блоке Рп запсганаются (накапливается) з»ктпгы V-. , при которых '/.мело место улучшение значе-нл;'- критерия эффективности * независимо от величины ггеира-ления, :т йгесгудк к итерации, -Т'/нкц:::нала релаемой задачидц.

Суть предлагаемо:«, модификации метода определения оптимальных значений управлявших параметров \dcjc заключается в следующем.

Процесс достижения требуемо;': точности с " вычислении разделяется на несколько этапов, на ка:;дом из которых уточняется оптимальные управления:

■ (4)

*

Отметим, что ;дс-я последовательного достижения требуемой гочности -¿егы&л оптимизационной задач; известна и хорошо себя зарекомендовала лри семени;:, например, некоторые задач поиска глобального экстремума. Особенность такой организации вычислений з кадем случае заключается в том, что в началэ каждого « -го этапа выделений ( -го "включения" внутреннего яруса) границы интервалов поиска оптимальных уравнений по каждому компоненту х". вектора расширяются до максимальных, а в качестве

начального вектора управлений используется последний, наилучший вектор V?ср-д-1 I предыдущего этапа. Поэтапное достижение заданной точности 6* позволяет уменьшить зависимость конечных результатов вычислений от ошибок в выборе начальных значений управлений V/, .

Предлагается также корректировать вычислительную процедуру поиска оптимальных значений управлений ;-с не только по золнчине внутреннего критерия Е, но и по величине приращения ¿ункшонала .1 ь резаемой задач;: от итер&фи к итерации в рамках каждого -гс этапа. С этой целью задается некоторое пороговое значение а^,-. для величины приращения функционала, с помощью которого кэдпфнцфуется процедура поиска очередного вектора V.1 . Если величина приращения функционала л Ь становится меньше заданного порогового значения (что, как правило, свидетельствует о приближении реаения задачи к локальному экстремуму), то по каждому оптимизируемому параметру цг,- гра-кнш его поиска, как и в предыдущем случае, расширяются до максимально возможных (допустимых), а в качестве начального вектора управлений используется наилучший (обеспечивающий наибольшее значение Е) вектор , достигнутый на предыдущих итерациях данного и предшествующих "включен:!/." внутреннего яруса.

Напомним, что оцнкой эффективности принятого управления в КОП-2 является значение критерия эффективности внешнего яруса с* . Так же, как и во внутреннем ярусе, значение £ * фор:.:и-руется после обращения к блоку базовых моделей В я» . Однако роль VI функции этого блока в КОП-2 выполняет блоки внутреннего яруса в пело;.; (су., рис. I). Таким образом, для оценки эффективности лишь одного управляющего воздействия необходимо полностью решить оптимизационную задачу во внутреннем ярусе, что требует принципиально больших затрат ма;шшного времени по сравнению с получением очередного значения Е"Д1\'[). Отсвда возникает задача уменьшения времени определения Ъм'Лс

Для сформулированного выше критерия эффективности и" внешнего яруса время формирования 'л' "^ мокет быть существенно уменьшено, особенно при решении потока однотипных оптимизационных задач, за счет прерывания процесса функциони-

рования внутреннего яруса, если время решения оптимизационной задачи во внутреннем ярусе с очередным значением 'vJf становится большим, чем было затрачено на получение предыдущего значения £ ( № ,).

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

В главе 4 диссертации оценивается эффективность КОП-2 при решении потоков сложных оптимизационных задач двух классов и приводятся параметры его технической реализации.

Формально оценить эффективность КОП-2 для потока однотипных задач по сравнению с КОП-1 монно следущей мерой выигрыша:

1 = 1с1ы + и > 1 (5) '

где -ь'с, - среднее малинное Бремя решения одной задачи данного класса при использован™ КОП-1; - время настройки параметров внешнего яруса для достижения требуемой точности решения задач заданного класса; ±с - среднее время решения одной задачи после настройки параметров самого комплекса; N - число решенных задач потоков. Значения 1'с. и N устанавливаются из статистики использования КОП-1 на данном классе задач. Из (5) очевидно, что величина г^ будет тем больше, чем меньше время настройки г= и среднее время решения одной задачи после настройки ±с •

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

Выбор указанных классов задач был обусловлен тем, что для их решения широко использовался одноярусный комплекс обучающихся программ (КОП-1), имелись обширные статистические данные и оценки затрат ресурсов ВС, в частности, машинного времени на ЭВМ 1СЬ 4-70, ЕС-1045.

- Id -

Содержательно задача гемодинамики сводится к задаче ком-плексирования (объединения) математических моделей, спискваю-щих функционирование двухкамерного сердца и всемью эластичными резервуарами

Постановка задачи в терминах и обозначения:'., принятых для КОП, имеет вид:

JU = I L - i. t i ) Oxt'i X - F(_x,C,i),

о ( x,C, о , t tic.t^ , (G)

где bfl^Ct)- система из Iô-и обыкновенных дифференцналь-ных уравнений, х. - j v| , l - I, 13. Вектор С » | С, j ( =1,3-) постоянных коэффициентов образуется из коэффициентов -омпле:-'-сируемых моделей. Отметим, -тс поскольку ставилась задача имитации С7а;у,онарн1:х режимов крсЕообраденкя (при отсутствии внешних воздействии), тс задача (С) решалась на интервале времени, равно:.: времени одного пульеезого удара Т'0 , т.о. t, - Г- .

Система ограничений ' формировалась следующим обра-

зом:

С - а , £ X , ; j ) l = 1, К ,

с' ; С i С" . ,

где xl , С* с" - константы.

5 отлкчиё от КОП-1, где все управляющие г;арг,:.:"тръ! формировались в едином информационно:.: массиве, соотьотствуошему вектору w* , а параметры блока логики задавались фпкег.рован-hljî-ги , в К0П-£ эти параметры были разделены на язе -г.сти: ли группу из 35 ЕзалмонезаЕпсн.'ъгх параметров ре-темс.'. задачи (коэффициентов базовой модели ), образуя!-:;« вектор , и на группу из 5 управляющих параметров самого комплекса, образующих вектор ; элемента.!;! последнего являли.сь количество одновременно изменяющихся компонент ве!:тора v. ' внутреннего яруса; количество подряд идуших неудачных попыток, после которых изменяется направление поиска экстремума, и др.

В целом, при решении потока задач гемодинамики с помощью КОП-2 использовались следующие из предложенных методов, алгоритмов и процедур;

- 17 -

- иерархическая организация управления процессом решения задачи; параметризация процессов управления как во внутреннем, так и во внешьзм ярусе КОП-2;

- упрощенный критерий эффективности Е^и/1 для внешнего яруса;

- модифицированный метод и алгоритм поиска значений управ-лякзшнх параметров, включающий процедуры предварительной настрой-■•и управляющих параметров внешнего яруса V/* , управление решением задачи не только по ь" , но и по величине прирашения функционала ы' с изменением направления поиска экстремума и расширением диапазона поиска и; до максимально возможного;

- процедура динамического управления вычислительным процессом в КОП-2, которая позволила сократить время настройки параметров внешнего яруса в 2,7 раза.

Использование указанных методов и средств в КОП-2 обеспе-тилз ускорение времени решения задачи гемодинамики в 5+8 раз.

Далее рассматривается одна из сложных задач речеобразова-ния - задача определения функции плошали речевого тракта. Известил акустическая модель, которая позволяет синтезировать речь :-:а основе решения прямой задачи речесбразозания: речевой тракт <• акустика. При этом качество синтезируемой речи в значительной степени зависит от точности аппроксимации функции площади речевого тракта. Описание значений этой функции является основой решения как прямой, так и обратной задачи речеобразования: для решения обратной задачи (акустика —речевой тракт) используется алгоритм решения прямой задачи, Еключенный в замкнутую систему совместно с КОП-2.

3 отличие от задачи гемодинамики, с взаимозависимыми управляющими параметрами (коэффициентами модели), рассматриваемая здесь задача имеет дело с девятнадцатью взаимозависимыми параметрами базовой модели, образующими вэктор л"1 . Поэтому в число настраиваемых управляющих параметров внешнего яруса не входит параметр, соответствующий количеству одновременно изменяющихся компонент Еектора ; в силу специфики решаемой задачи (взаимозависимость параметров), он задается константой. Это обстоятельство приводит к тому, что "розыгрыш" очередного вектора управлений V»/* в блоке внутреннего яруса должен осуществляться одновременно по всем компонентам , в то

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

Особенность этой процедуры заключается в том, что коррекция решения задачи во внутреннем ярусе КОП-2 осуществляется не только по критерию и величине прирацения функционала д L*, но и по величине £,_ - точности, заданной на g -м этапе вычислений (а -и "включении" внутреннего яруса). Кроме этой процедуры при решении задача речевой акустики применялись те же предложенные методы, алгоритмы и процедуры, что и при решении задачи гемодинамики .

Использовагае указанных методов и средств в КОП-2 обеспечило следующий суммарный эффект: если среднее время решения задач речевой акустики (по фенемам) в КОП-1 составляло -169,5 сек, и изменялось от 92,6 сек до 375 сек, то в КОП-2 достигнуто ускорение счета от 2,5 до 30 раз. При этом по фонемам время решения задач составляет 84 сек и изменяется от 4,5 до 148 сек.

КОП-2 представляет собой пакет программ на языке iOPTPAH-4, требующий для своей работы около 100К оперативной памяти и около 150К внешней памяти. Предусмотрена сегментация пакета, допускающая его размещение на ЗВМ с оперативной памятью 32 К и внешней памятью около 200 R . Вывод информации может производиться на дисплей, АЦШ/ и графопостроитель. Комплекс программ реализован на ЭВМ типа ЕС, мини ЭВМ ДБК-ЗМ, персональной ЭВМ IBM PC/XT,' многопроцессорной ВС ПС-2000.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

I. Разработаны принципы организации КОП-2: - двухуровневая иерархия построения комплекса и управления процессами решения потоков оптимизационных задач,-

- параметризация (динамическая настройка параметров) алгоритмов функционирования самого комплекса (внешний ярус), наряду с параметризацией алгоритмов решения задач (внутренний ярус);

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

2. Определены принципы формирования вектора управляющих параметров внешнего яруса.

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

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

по значениям критерия эффективности решения но и по величине приращения функционала решаемой задачи от итерации к итерации.

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

5. Проведена оценка эффективности КОП-2 на потоках сложных оптимизационных задач двух классов:

- задачи гемодинамики, математически описываемой системой обыкновенных дифференциальных уравнений с разрывами в правых частях с взаимонезависимыми параметрами (коэффициентами) базовой модели; время решения этой задачи с помощью обученного КОП-2 уменьшилось в 5+8 раз, а при учете затрат времени на настройку управляющих параметров внешнего яруса имеет место выигрыш г| = 2,2;

- задачи речевой акустики, математически описываемой системой дифференциальных уравнений в частных производных, с взаимозависимыми параметрами базовой модели; зремя решения этой задачи с помощью КОП-2 по различным фонемам уменьшилось в

2,5+30 раз.

- 20 -

Основное содержание диссертации изложено в следующих опубликованных работах:

1. Широколава B.C., Исаева H.A. Двухъярусный комплекс обучающихся программ. Б кн. : Модели управления сложной программой. -

:Инстптут проблем управления, 1965.

2. Широколава B.C., Исаева H.A. Построение двухъярусного комплекса обучающихся программ: Тез.докл. на Всесоюзной научно-технической конференции "Огит разработки и внедрения технических и программных средств С.! 3BU и АСВТ-ПС.-Северодонец::. НПО "импульс",

3. Щироколава B.C., Исаева H.A., Луказов В.З., Киридас Л.Ю. Реализация двухъярусного комплекса обуча^хся программ на ¡.этого процессорном Eii ПС-2СС0. Тез.докл. на Всесоюзной научно-технической конференции "Опыт разработки и внедрения технических и программных средств СИ SKÜ и АСВТ-ПС". Северодонецк: НПО "Импульс"*, 1985.

4. Алещенко Г.М., Бесшапов Е.П., Гусев В.Б., Исаева H.A. и др. Обучающаяся вычислительная система на базе ассоциативной ЭШ с перестраиваемой структурой. Тгз.докл. на X Всесоюзном совещаний по проблемам управления.- Алма-Ата, 19Б6.

5. Исаева H.A., Широколава B.C. Расширение возможностей комплекса обучающихся программ на многопроцессорных вычислительных системах. Тез.докл. на 7-й Всесоюзной школе-семинар* "Параллельное программирование и высокопроизводительные системы".- Киев: Институт кибернетики АН СССР, ISSö.

t>. Vlasov Y., Isaeva Я. The method for solving inverse problem oi apeeeh production ana articulatory portray o£ а зреакег. Proceedings 7.1 th ICPhS - Tallin: V. 5, 1987.

7. Исаева H.A. Оптимизация вычислительного процесса при проблемной ориентации двухъярусного комплекса обучающихся программ. Теэ.до:сл. на Ш Всесоюзном совещании "Высокопроизводительные вычислительные системы".-Таллин, 1968.

S. Исаева H.A. Исследование эффективности двухъярусного комплекса обучающихся программ. В кн.: Проблемная ориентация комплексов программ.- М.:Институт проблем управления, 1969.

9. Исаева H.A. Решение сложных опта мизацлонгах задач управления на основе двухъярусного комплекса обучающихся программ.

Тез.докл. на XI Всесоюзном совепании по проблемам управления.» Талкент, 1989.

Личный зклад. Все результаты, составляющие основное содержание длсосртапии получены диссертантом самостоятельно.

По работам, опубликозанным в соавторстве (см. список опубликованных работ), личный вклад состоит в следующем: в

[1-2] предложен алгоритм построения и функционирования двухъярусного КОП; в 13] предложена структура КОП-2, ориентированная на 133С ПС-2000; з ^4-5] предложена и разработана вычислительная процедура динамического управления вычислительным процессом в К0П-2, ориентированная на параллельную обработку; в ¡б] разработан модифицированный метод и алгоритм поиска оптимальных значений управляющих параметров для решения потока оптимизационных задач с взаимозависимыми параметрами.

1-01480,лодп.к печ.25/Ш-Э0г. Зак..\з 227,тир. 100.ОРТЕ УГТ