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

Актуальность темы

и предмет исследования.

Переход на инновационный путь развития связан с необходимостью создания технических устройств и систем, обладающих необходимыми характеристиками качества и надёжности. Отечественный и зарубежный опыт проектирования и эксплуатации систем различного назначения показывает, что значительную часть отказов составляют постепенные (параметрические) отказы, а задача учёта отклонений параметров от расчётных значений и обеспечение требуемого качества допуска при наличии таких отклонений является одной из наиболее сложных и трудоёмких задач проектирования. При этом по мере усложнения технических объектов, повышения требований к их надёжности и увеличения ответственности выполняемых ими функций необходимость и важность решения этой задачи постоянно возрастает [27, 77].

Задача обеспечения надёжности сложных систем весьма многогранна, и существуют различные направления исследований в данной области [1, 46, 60, 77, 108, 113]. Эффективное решение проблемы обеспечения надёжности в определённой мере зависит от правильного понимания состояния и тенденции развития теории надёжности, в которой можно выделить три методологически различных направления [1]:

• вероятностно-статистическое (математическое) главным образом основывается на применении аппарата теории вероятностей и математической статистики на основе апостериорной информации о статистике отказов и булевой модели состояния системы только в режиме полной работоспособности или только в режиме полного отказа;

• физико-статистическое (причинно-следственное) основывается на исследовании и моделировании внутренних физико-химических процесс-сов (причин) в составных элементах системы, чувствительность выходных характеристик к изменениям в этих элементах и построении модели отказов, основанной на изученных взаимосвязях;

• направление, связанное с анализом и обеспечением надёжности по постепенным (параметрическим) отказам.

Классическим математическим аппаратом исследований в теории надёжности являются вероятностные методы [17, 19, 27, 34, 46, 49, 52, 108, 113, 116], использующие статистические характеристики, такие как среднее время наработки до отказа, средняя наработка между отказами, средняя частота отказов и др. [26, 46]. При этом во многих работах также уделяется внимание детерминированным методам, связанным с исследованием области допустимой вариации параметров, которая определяется топологией исследуемой системы и требованиями к выходным характеристикам [1−8, 11, 12, 15−17, 19, 24, 25, 31−37, 39−43, 52−62, 69, 79−82, 84−90, 96, 98, 108, 112−116, 118]. Целью исследования этой области является оптимизация значений параметров с учётом их дрейфа.

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

Далее в работе область допустимой совместной вариации параметров сложного технического объекта (системы) будет называться областью работоспособности (ОР) и в главе 1 будет дано строгое её определение.

Задача построения и анализа ОР занимает важное место в процессе создания технических устройств и систем и часто рассматривается как отдельная задача [40, 52]. Её разновидностью является задача построения областей устойчивости и областей качества [25, 33], широко распространённая в теории автоматического управления. Особую важность эта задача приобретает при решении проблемы оптимального проектирования технических систем с учётом изменений параметров и требований надёжности. Решение этой задачи позволяет оценить запас работоспособности при выбранной структуре системы и сравнивать потенциальные возможности различных структур, осуществлять назначение допусков и выбор номинальных значений параметров элементов проектируемых систем.

В ряде работ, посвященных выбору номинальных значений параметров и допусков, используются различные методы исследования области допустимой вариации параметров. Один из подходов связан с зондированием пространства параметров. Примером такого подхода являются сеточные методы поиска в работах Батищева Д. И. [15, 16], различные методы поиска в работе Беккера П. и Йенсена Ф. [17], построение многомерных сеток с помощью ЛПТпоследовательностей в работе Соболя И. М. и Статникова Р. Б. [72], реализация метода Монте-Карло [71] в работах ряда отечественных и зарубежных авторов [1, 17, 39 41, 60, 85, 116], использование генетических алгоритмов в работе коллектива авторов Dhanwada N.R., Nunez-Aldana A., Vemuri R. [90] и эволюционных методов в публикации авторов Р. Jantos, J. Rutkowski [96]. Другой подход связан с построением геометрической аппроксимации ОР фигурами известной конфигурации. Наиболее распространённой для этой цели фигурой является гиперпараллелепипед. В работах Абрамова O.B. [1, 2, 4, 5, 7], Антушева Г. С. [11, 12], Здора В. В. [24, 35, 36], Маслова АЛ. [52, 53], Bandler J.W., Abdel-Malek H.L. [84], Spence R., Soin R.S. [113], Taylor N.H. [118] и других авторов [33, 39, 69] рассматривается задача построения вписанных и описанных гиперпараллелепипедов (брусов). Помимо представления ОР с помощью гиперпараллелепипедов в некоторых работах для этой цели используются эллипсоиды, например в работе Горячева JI.B. и Здора В. В. [25], Диго Г. Б. и Диго Н. Б. [31], Дзенскевич Е. А. [32], Sapatnekar S.S. [112] а также в работах [98, 114]. Для описания ОР также применяют методы обхода её контура [37, 87] и построения более сложных фигур, например многоугольников[89]. Недостатком большинства методов, в частности обхода границы ОР, является отсутствие информации о внутрен-ности этой области. Для получения информации о внутренности ОР исполь-зуются методы сканирования области поиска.

Для данной работы особый интерес представляют методы построения ОР по результатам сканирования, основанном на переборе комбинаций значений параметров на некоторой сетке с вычислением выходных характеристик, т. е. многовариантном анализе [19, 60, 54, 70]. Аналогичной задачей является построение поверхности отклика для выбора оптимальных значений параметров [17, 49]. Примером реализации такого метода является модуль оптимизации в программном комплексе «Универсальный механизм» [66] для исследования поведения сложных механических систем при различных режимах их функционирования и выбора их оптимальных параметров.

Геометрическая аппроксимация ОР дискретным множеством параллелепипедов на основе результатов зондирования пространства параметров рассматривается в работах [86, 98], причём в последней используется дополнительно рекуррентное разбиение граничных параллелепипедов. Стоит отметить, что в этих работах не описываются используемые структуры данных и алгоритмы, реализующие эти методы, а также возникающие при этом трудности.

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

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

В основу алгоритмов построения ОР в данной работе положен метод матричных испытаний (ММИ)[19, 54, 70], суть которого состоит в переборе вариантов значений параметров системы на регулярной сетке, и метод аппроксимации ОР множеством непересекающихся гиперпараллелепипедов.

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

Основная идея и принцип построения ОР (метод матричных испытаний), которые легли в основу данной работы, изначально были ориентированы на физическое моделирование процессов дрейфа параметров элементов радиоэлектронной аппаратуры. Привлечение вычислительной техники для реализации этого метода не получило широкого распространения из-за высоких требований к ресурсам вычислительных машин. Интенсивное развитие технологий параллельных и распределённых вычислений за последние 10−20 лет, а также стремительный рост мощности вычислительной техники и вместительности устройств хранения данных в настоящее время позволяют решать такие задачи за приемлемое время. Для реализации этих методов необходима разработка эффективных алгоритмов и структур данных.

Описанные в работе методы и алгоритмы ориентированы, в первую очередь, на решение задачи параметрического синтеза первого уровня (ПС-1) [1], когда информация о закономерностях изменения значений параметров элементов полностью отсутствует, а модель системы задана в алгоритмическом виде и представляет собой «чёрный ящик», что не позволяет применять аналитические методы исследования. Стоит также отметить возможность применения предложенных в работе методов построения и анализа ОР к моделям объектов, не имеющих отношения к техническим, но которые достаточно сложны для аналитического описания и анализа.

Цель работы.

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

Задачи исследования.

Для достижения поставленной цели работы были решены следующие задачи:

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

2. Разработка и программная реализация алгоритмов декомпозиции задачи построения ОР для её параллельной реализации с учётом балансировки вычислительной нагрузки между узлами несимметричной параллельной вычислительной системы.

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

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

5. Разработка и программная реализация алгоритмов выбора оптимальных значений номиналов параметров по критерию запаса работоспособности.

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

Научная новизна.

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

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

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

На защиту выносятся.

1. Описание структур данных и использующие их алгоритмы построения ОР с помощью регулярных и нерегулярных детализированных сеток, а также алгоритмы уменьшения объёмов данных сеточного представления ОР.

2. Алгоритм декомпозиции задачи построения ОР с учётом балансировки вычислительной нагрузки при её параллельной реализации на несимметричной распределённой вычислительной системе.

3. Алгоритмы анализа OP, состоящие из алгоритма проверки связности сеточного представления области и визуализации сечений.

4. Алгоритмы вычисления оптимальных значений параметров с использованием детерминированного критерия максимального запаса работоспособности.

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

Практическая ценность работы.

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

Научные результаты работы использованы в ФГУП «Центральный научно-исследовательский институт автоматики и гидравлики» (ФГУП «ЦНИИАГ») для получения характеристик областей работоспособности, назначения допусков и номинальных значений параметров при разработке технических устройств и систем специального назначения.

Апробация результатов работы.

Полученные результаты обсуждались на международных симпозиумах «Надежность и качество» (Пенза, 2005 — 2010) — Азиатской международной конференции по проблемам управления (ASCC) (Бали, 2006) — Международной конференции по проблемам оптимизации и оптимального управления (СООС) (Улан-Батор, 2007) — Российской конференции «Дискретная оптимизация и исследование операций» (DOOR) (Владивосток, 2007) — международной конференции по промышленным технологиям и управлению (IEEM) (Сингапур, 2007) — Дальневосточной математической школе-семинаре им. академика Е.В.

Золотова (Владивосток, Хабаровск, 2005 — 2010) — Международной конференции студентов, аспирантов и молодых ученых «Интеллектуальный потенциал вузов — на развитие Дальневосточного региона России и стран АТР» (Владивосток, 2006 — 2009) — а также научных семинарах Института автоматики и процессов управления ДВО РАН.

Публикации.

По теме диссертации опубликовано 27 работ, среди которых 3 из списка изданий, рекомендованных ВАК.

Научные программы.

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

1. Проект РФФИ 05−08−1 398-а: «Оптимальное проектирование технических систем с учетом вариаций параметров и требований надежности»;

2. 06−1-ЭММПУ-054 Программа № 15 отделения ЭММПУ РАН: «Разработка методов, алгоритмов и программных средств параметрического синтеза стохастических систем»;

3. Проекты ДВО РАН:

• 06-III-A-03−070: «Разработка комплекса алгоритмов и программ параметрического синтеза по критерию надежности»;

• 09-III-B-03−082: «Разработка программного комплекса построения и анализа областей работоспособности аналоговых технических систем на основе технологии распределенных вычислений»;

• 10-III-B-03−035: «Разработка алгоритмических и программных средств оптимального выбора номиналов параметров в условиях неопределённости».

Структура диссертации.

Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и шести приложений. Основной объём диссертации составляет 150 страниц, в который входят: библиографический список из 119 наименований, 38 рисунков и 6 таблиц.

5.5 Выводы по главе.

В главе рассмотрен подход к построению ОР с помощью параллельных вычислений. Рассмотрены методы декомпозиции задачи построения ОР, которые предлагается выполнять путём разбиения цикла инициализации элементов МС. Разбиение цикла инициализации достигается разбиением самого МС на непересекающиеся блоки. Удобство такой декомпозиции задачи объясняется сравнительной простотой и гибкостью разбиения одномерного массива по сравнению с разбиением и-мерной сетки на произвольное количество блоков (разумеется, не более, чем количество элементов массива) различной длины, что даёт возможность обеспечить максимально полную и «равномерную» загрузку вычислительных узлов параллельной вычислительной системы.

Для балансировки вычислительных нагрузок предлагается два метода: балансировка по вычислительным мощностям узлов и автобалансировка, основанная на декомпозиции задачи на достаточно большое количество небольших по объёму подзадач и организации их раздачи в режиме FCFS / FIFO, когда каждый вычислительный узел по мере завершения работы с текущей подзадачей и отправки результатов главному процессу получает следующее задание из очереди. В результате такой декомпозиции вычислительные узлы, имеющие наибольшую вычислительную мощность, обработают большее количество заданий, а узлы с более низкими вычислительными показателями — меньшее. Кроме этого, при автобалансировке достигается асинхронность обмена данными между управляющим узлом и различными вычислительными узлами, что исключает пиковую нагрузку на коммуникационную среду. Балансировка вычислительных нагрузок по мощностям узлов заключается в предварительном получении сведений о вычислительных возможностях узлов путём измерения времени, потраченного на выполнение тестового задания каждым из них.

Реализация рассмотренных методов параллельного построения ОР рассматривается на РВС, узлами которой являются рабочие станции, объединённые в локальную компьютерную сеть. Топология РВС, состоящей из узлов двух типов: одного управляющего и нескольких (количество теоретически не ограничено) вычислительных, имеет централизованный тип «звезда», а взаимодействие узлов в рамках этой топологии имеет характер клиент-серверного, при котором управляющий узел находится в состоянии ожидания запросов от вычислительных узлов, а жизненный цикл приложения на вычислительном узле состоит из периодических запросов к управляющему узлу (наиболее частым и основным является запрос задания для обработки).

На примере решения задачи построения ОР с использованием РВС из рабочих станций локальной компьютерной сети типа Ethernet / Fast Ethernet показано, что балансировка вычислительных нагрузок на узлы РВС достигается с одинаковой эффективностью для обоих рассмотренных алгоритмов декомпозиции с учётом балансировки в указанных пределах, программная реализация рассмотренных алгоритмов позволяет создать «самодостаточные» программные модули РВС, работающие с функциями операционной системы, что позволяет использовать для расчётов практически любую сеть пользовательских компьютеров и рабочих станций, поддерживающую протокол ТСРЛР, без установки дополнительного программного обеспечения и привлечения дополнительного оборудования.

ЗАКЛЮЧЕНИЕ

.

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

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

В связи с вышесказанным, результатами данной работы является решение поставленных задач:

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

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

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

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