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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ ( ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ )

На правах рукописи УДК 681.3,621.52

ТЕХНИЧЕСКИХ ИЗДЕЛИЙ

05.13.11 - математическое и программное обеспечение

вычислительных машин, комплексов , систем и сетей

АВТОРЕФЕРАТ

на соискание ученой степени кандидата физико-математических наук

Москва - 1996

... I

Работа выполнена в Московском государственном авиационном

институте ( техническом университете )

Научный руководитель: доктор физико-математических наук,

профессор А.Ю.Аржененко

Официальные оппоненты: доктор физико-математических наук,

профессор А.В.Пантелеев

Ведущая организация:

доктор технических наук, профессор И.П.Литиков

Серпуховское Высшее Военное Командное Инженерное Училище Ракетных Войск

-М- шал в

¿4?

часов на

Защита состоится заседании диссертационного Совета К 053.18.09 в Московском государственном авиационном институте.

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

Адрес института: 125871., Москва, А-80, Волоколамское шоссе, Автореферат разослан 199_£г.

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

М.В.Ротанина

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

Диссертационная работа Правоторовой E.H. посвящена проблеме построения оптимальных алгоритмов диагностирования вычислительных

комплексов, систем и сетей.

Актуальность работы. В области диагностики

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

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

Целью работы является:

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

для задач с детерминированными анкетами;

для задач с частично детерминированными анкетами;

для задач с неопределенными анкетами.

2) применение разработанных методов для создания пакета прикладных программ оптимизации условных алгоритмов диагностирования.

Методы исследования. При решении поставленных задач автор использовал математическое моделирование с применением теории бинарных отношений, теории графов и теории вопросников .

Научная новизна работы состоит в следующем:

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

• решена задача выбора корневого вопроса в нетранзитивных структурах, что позволило завершить разработку метода "корневого вопроса" в целом;

• поставлена и решена задача исследования частично заданных анкет;

• разработан метод сокращения для построения оптимального условного алгоритма по недетерминированный анкете;

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

• разработан принцип доопределения частично заданных анкет. Практическая значимость работы;

состоит в следующем. Разработанные математические методы оптимизации условных алгоритмов диагностирования были запрограммированы на алгоритмическом языке "Турбо-паскаль" и составили пакет прикладных программ. Использование разработанного комплекса программ для моделирования работы специализированного бортового вычислителя позволило повысить эффективность процесса его диагностирования. Затраты на поиск неисправного элемента в рассматриваемом специализированном бортовом вычислителе получились на 57% меньшими по сравнению с исходным алгоритмом. Сравнение проводилось с алгоритмом, построенным по методу сбалансированного дерева. Алгоритм, построенный с применением метода последовательного разбиения событий отличается от оптимального по стоимости на 7%.

С инженерной точки зрения, предложенные методы решения задай

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

Практическая ценность работы заключается в реализации и внедрении результатов диссертационной работы на предприятии МКБ "Компас", что подтверждается соответствующим актом внедрения.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на :

XXVII Вссесоюзной научно-технической конференции ВУЗов (Минск 1984г.) ;

Всесоюзной научно-технической конференции"Проблемы оптимизации конструкций и технологических процессов в машиностроении" (Пермь 1985г.);

Всероссийской научно-технической конференции " Автоматизация производственных процессов и управление качеством" (Москва 1986г.);

XI Научно-технической конференции СВВКИУРВ (Серпухов 1992г.);

семинарах кафедры ( Москва 1985,1986,1987гг.).

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

Структура и объем работы. Работа состоит из пяти глав и заключения. Общий объем работы 152 страницы, 103 рисунков, 89 библиографических названий.

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

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

ся замена исходного объекта исследования идеализированной математической моделью.

Анализ математической модели объекта относится к числу основных этапов процесса построения программ проверки технического состояния объекта. Целью анализа является либо получение таблицы функций неисправностей (Т.Ф.Н.), либо ее частей. Для построения Т.Ф.Н. (или анкеты ) рассматриваются все технические состояния объекта диагностирования и по его функциональной модели определяются исходы каждой проверки ( теста ) из заданного множества. Найденные результаты проверок заносятся в таблицу, столбцы которой соответствуют техническим состояниям объекта диагностики, а строки - диагностическим тестам.

В ряде работ Т.Ф.Н. или анкету рассматривают как некоторую достаточно абстрактную модель объектов диагностики, охватывающую ' практически все реальные технические системы.

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

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

Задача формулируется следующим образом.

Известно множество неисправностей технической системы yj ® * . з = (1|«> и их вероятности Задано множество

допустимых Э.П. \ е т , »• = (1,М), достаточное для идентификации любой неисправности Каждая Э.П. V е т характеризуется некоторой стоимостью С(\). Требуется определить условную

стратегию использования Э.П. из множества Т , так, чтобы средняя стоимость проведенных испытаний была минимальной.

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

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

Во второй главе введены понятия вариантного вопроса и смежного вариантному вопроса. Доказана теорема о необходимом условии существования контура в графе предпочтения. Таким условием является наличие среди трех попарно сравнимых вопросов вариантного вопроса. Было получено достаточное условие нетранзитивности:

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

нялись два условия :

1) цена вариантного вопроса должна быть меньше цен двух других вопросов;

2) функция предпочтения смежного вопроса должна быть больше функции предпочтения невариантного вопроса.

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

Проведенное исследование структуры нетранзитивности показало, что граф предпочтений нетранзитивного вопросника не может содержать простые циклы из " вопросов С " > 3 ). Для решения задачи выбора корневого вопроса в сложной нетранзитивной структуре, были изучены основные элементы такой конструкции, а именно треугольники. Эти исследования показали, что вариантный вопрос не может быть кошевым.

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

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

В начале необходимо провести упорядочение событий по невозрастанию их вероятностей. Для первых двух событий у, и у2 ,

имеющих максимальные вероятности выбирается вопрос , разде-

1

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

вероятностей оставшихся событий уэ» у4. у„. Исходом вопроса для этого события может быть 5 или 3 • Пусть уэс 1-э(*к>'

тогда вопросник Б4 будет разделять событие у2 и множество * V у2

Выберем вопрос с минимальной ценой из вопросов, разделяющих

события у4 и уэ. Пусть это будет вопрос . Построим вопросник

2

в2, который идентифицирует все события из множества Ц2=1у1'у2'уэ>-На каждом последующем шаге в множество включаем событие с максимальной вероятностью из множества неидентифицированных событий.

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

завершает цепочку из к вопросов , , • • •, , , тогда целесообразность перестановки вопроса с к+1 ранга на ранг (назовем такую перестановку р-перестановкой) определяется при помощи неравенства

V к

Си )£ р. < £ С(1.)Р<1. и ) I )

. , ^ 1 - -, V з т I.

1=к-р+1 I = к- р+ 1

выражение Р(1- >1 > обозначает вероятность событий,

V

входящих в подмножество 1т> - то есть 5-й исход вопроса на множестве событий ;

множество ^ - множество событий, для которого вопрос \ является корневым в вопроснике Иначе 1-1 можно определить следующим образом:

U = L \ {y.> j= l,i-l

исход s выбирается следующим образом: L (t ) I. с L (t.) I.

9 m L г >. IL.

1 i 1 г

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

Проведена оценка максимально возможной погрешности метода последовательного разбиения событий. Она составляет не более 10% от стоимости оптимального вопросника. Трудоемкость предлагаемого метода определяет полиномиальный характер рассмотренного алгоритма построения вопросника.

Четвертая глава посвящена исследованию неопределенных и частично заданных анкет.

Задача доопределения анкеты А имеет два аспекта :

1. Необходимо решить вопрос о возможности ее доопределения.

2. Если это возможно, то достроить анкету А ( то есть заменить все символы "тире" на 0 или 1 ) так, чтобы оптимальный вопросник для этой анкеты имел наименьшую стоимость среди оптимальных вопросников всех остальных тестовых систем.

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

Доказана теорема о возможности доопределения частично заданной анкеты, которая гласит:

если в расширенном вопроснике ы для анкеты А все группы событий можно разбить на непересекающиеся множества доопределения Мэ,

то анкета А может быть успешно доопределена.

На основании этой теоремы предложен алгоритм построения множеств доопределения.

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

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

1. анкеты, в которых никакой информации о тестах , кроме их стоимости не задано;

2. анкеты с несколькими определенными исходами тестов.

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

Согласно этому методу, сначала строится максимальное дерево вопросника по алгоритму безусловной идентификации, причем вопросы-задаются в порядке возрастания их цен. Число висячих вершин в таком вопроснике вычисляется по формуле: 5 = 2"

Но множество состоит из м элементов. Остальные

М0= 3 - N

концевых вершин будем считать событиями с нулевыми вероятностями. Удаляя одну из вершин у0 , получаем, что некоторое событие yj может быть идентифицировано уже на и - 1 ранге. Если в подвоп-роснике 21 - 1 концевых вершин имеют вероятности равные нулю и одна Р(ур, то сокращение вершины у0 позволяет удалить из под-вопросника все вершины - вопросы, лежащие на пути из в у г

Очевидно, что из стоимости вопросника при этом удаляется слагаемое

. т>+1

о. ,= р(у.)Е ctt )

и количество вершин с нулевыми вероятностями М„ сокращается на 21-! единицу.

Метод сокращения основан на последовательном вычитании из стоимости вопросника СС^) максимальных слагаемых С максимальные слагаемые определяются исходя из значений функции сокращения для каждого события ).

В работе доказано, что задача построения оптимального вопросника для недетерминированной анкеты является NP - трудной задачей. Это означает, что она не может быть решена ни одним полиномиальным алгоритмом.

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

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

Проведена оценка трудоемкости предлагаемого алгоритма, которая показывает его полиномиальный характер относительно размерности анкеты. Это позволяет рекомендовать его для широкого использования.

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

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

В приложении 1 приводятся исследования всех типов анкет для простейших композиций нетранзитивных структур С дополнение к главе 2 ). Приложение 2 содержит тексты программ и результаты их работы для исследуемого бортового вычислителя.

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

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

В работе получены следующие основные результаты:

1. Исследованы сложные нетранзитивные структуры в графе предпочтения. Предложен алгоритм выбора кошевого вопроса в таких структурах, завершающий построение метода "корневого вопроса".

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

2.1 Доказана теорема об оптимальных р - перестановках в цепи сравнимых тестов.

2.2. Исследован вопрос о целесообразности перестановок несравнимых тестов.

2.3. Получена оценка верхней границы погрешности предлагаемого метода.

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

3. Исследованы неопределенные и частично определенные анкеты.

3.1. Получены необходимые и достаточные условия для успешного доопределения анкет.

3.2. Для построения оптимальных вопросников по анкетам, в которых никакой информации о тестах, кроме их стоимости, не задано, разработан метод сокращения.

3.3. Проведена оценка трудоемкости метода сокращения.

3.4. Предложен алгоритм доопределения частично заданных анкет.

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

5. Проведен сравнительный анализ разработанных алгоритмов с уже известными методами.

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

1. Аржененко A.D. ,Катасонова E.H. Анализ нетранзитивных вопросников. -М.: ВИНИТИ № 5548-1984 деп.

2. Казакова О.Г., Правоторова E.H. Адаптивный алгоритм оптимального поиска неисправностей радиотехнических изделий. //В кн. Автоматизация производственных процессов и управление качеством. -М.: МИЭМ, 1986. -с.46.

3. Катасонова E.H. Анализ нетранзитивных вопросников. // В кн. Тезисы докладов УУУ11 студенческой научно-технической конференции ВУЗов. -Минск. БПИ. 1984 -с.49.

4. Правоторова E.H. Метод последовательного разбиения событий для оптимизации бинарных вопросников. -М.: 1988. -Деп. в ВИНИТИ. N4485 - В88.-21с.

5. Правоторова E.H.»Казакова О.Г. Выбор корневого вопроса для оптимального контроля технических изделий. // В кн. Проблемы оптимизации конструкций и технологических процессов в машиностроении. -Пермь, Пермский политехнический институт, 1986. -с.З.

6. Правоторова E.H. Метод сокращения для построения оптимальной системы бинарных тестов. -М.1989.-Деп.в ВИНИТИ № 2179- В89. -13с.

7. Правоторова E.H. Доопределение частично заданных анкет.-М. 1989. - Деп.в ВИНИТИ № 2180 - В89.-12с.

8. Правоторова E.H. Об одном методе оптимизации условных алгоритмов диагностирования. ' В кн. Тезисы докладов XI научно-технической конференции СВВКИУРВ. - Серпухов. - СВВКИУРВ,1992. -с 12.

9. Правоторова E.H. Оптимизация вопросников по неопределенным и частично определенным анкетам. -М.: Изд-во Р0У,1995 -15с.

10. Правоторова E.H. Алгоритм оптимизации нетранзитивных вопросников. -М.: Изд-во Р0У,1995 -37с.

11. Правоторова E.H. Р-перестановки в цепи сравнимых вопросов. -М.: Изд-во РОУ,1995 -23с.