Содержание к диссертации
Введение
1. Задача идентификации состояния объекта
2. Построение алгоритмов полной кджгижации состояния объекта
3. Построение алгоритмов неполкой идентификации состояния объекта
4. Исследование применения метода. ветвей и границ и метода динамического программирования в задачах идентификации состояния объекта
5. Практическое использование разработанных алгоритмов идштификации
Выводы
Заключение
Литература
- Построение алгоритмов полной кджгижации состояния объекта
- Построение алгоритмов неполкой идентификации состояния объекта
- Исследование применения метода. ветвей и границ и метода динамического программирования в задачах идентификации состояния объекта
- Практическое использование разработанных алгоритмов идштификации
Введение к работе
С увеличением сложности технических систем непрерывно возрастает роль методов и средств поддержания их в работоспособном состоянии. В связи с этим актуальной является задача идентификации состояния объекта, от решения которой может в значительной степени зависеть стоимость эксплуатации технического объекта, а также трудоемкость и временные затраты на проведение регламентных работ. Для принятия решения о состоянии различных технических объектов часто используется множество измеряемых параметров, каждый из которых контролирует работоспособность определенной части технического объекта. Решение о состоянии выносится на основе проверки соответствия значений параметров номинальным. В реальных задачах часто проверки бывают весьма дорогостоящими вследствие сложности и трудоемкости, а также значительных энергетических затрат. При этом, используемые проверки являются зависимыми в том смысле, что результат какой-либо проверки может предопределять результат некоторых других проверок. Использование зависимости результатов проверок, как правило, позволяет существенно снизить затраты, связанные с определением технического состояния объекта.
В настоящее время начинается широкое внедрение автоматизированных обучающих систем, реализованных на базе дорогостоящих комплексов технических средств. В связи с этим возникает необходимость разработки методов эффективного использования технических средств для обучения, что не может быть выполнено без построения и исследования формализованных моделей сложных человеко-машинных комплексов. Одним из перспективных направлений является разработка моделей, учитывающих семантическую зависимость между заданиями (вопросами), поскольку на их основе удается решить ряд важных для практики задач при минимальных затора
Рассматриваемые в диссертационной работе задачи относятся к задачагл дискретной оптимизации и в общем случае столь же сложны, как и ряд других широко известных экстремальных комбинаторных задач. Представленные в разделах 2,3,4, результаты включают разработку и исследование строгих и приближенных методов построения минимаксных стратегий выполнения проверок, т.е. стратегий минимизирующих максимальное значение затрат. В том числе рассмотрены перечислительные и эвристические алгоритмы, приведены оценки их характеристик. Исследованы области предпочтительного использования различных алгоритмов построения минимаксных стратегий.
В разделе 5 рассмотрены вопросы использования полученных теоретических результатов в конкретных системах технического диагностирования, а также в автоматизированных обучающих системах. Рассмотрена задача диагностирования аппаратуры системы автоматического управления при наличии в ней кратных отказов (дефектов). Предложено формализованное описание процесса контроля знаний обучаемого, на основе которого разработана методика опроса, позволяющая сократить гарантированное время, затрачиваемое на контроль знаний обучаемого. Рассмотрена модификация основной формальной модели, которая может быть использована для построения стратегии диагностирования более широкого класса систем с аппаратурной избыточностью. Оценен технический эффект применения теоретических результатов в рассмотренных практических системах. В приложениях приведены материалы по программной реализации разработанных методов идентификации.
Построение алгоритмов полной кджгижации состояния объекта
Будем считать, что множество зависимых проверок представлено орграфом 0=(Х, Г) типа диаграммы Хассе [2/1,23], Определим множест во двоичных функций SCG), полагая, что se &Сб), если, s удовлет воряет условию ЗСэс) SC c J при ОС 6 I ос % где I O:\OCi множество вершин графа G достижимых из лз. Легко заметить, что С( 3 совпадает с множеством всех двоичных функций на X , если G есть множество несвязанных вершин, и необходимо провести iJ проверок, чтобы по их результатам определить состояние объекта. В общем случае 1 SfCfi) I - 5 t так как условие scx)is(»fjno3BOflHeT доопределить значение s по результату проверки X , полагая, что scoe o для вершин следующих за эс ( в случае soc!)-o) или scoc)-f для вершин, предшествующих ое в случае s с ас .
Теперь определим процесс идентификации состояния объекта путем последовательного осуществления проверок. Для этого введем в рассмотрение бинарное дерево ( R - граф ) , каждой вершине которого постав-лена в соответствие пара (ос5 G) где эс - вершина подграфа G графа G . Причем, для вершин ( ое, »х?)и С 2"» & :) » являющихся непосредственными потомками вершины (х,С ) в R - графе, 6 = tf%3cyG) получается из С? исключением вершины зе и следующих за ней вершин, а также инцидентных им дуг С что соответствует .отрица-тельному результату проверки, т.е. sc&) o) , a G? ъ С -з61) полу-чается из G исключением вершины х и предшествующих ей вершин, а также инцидентных им дут ( что соответствует успешной проверке, т.е.
Заметим, что между множеством концевых вершин R -графа и множеством состояний объекта может быть установлена взаимно однозначное соответствие, если полагать значения функции S равными нулю С еди-нице) для всех удаленных вершин при получении G ЗІ С 6« се ) из G Высота R -графа определяет число проверок, необходимое для идентификации состояния объекта в самом неблагоприятном случае. Очевидно, 15 что для исходного графа G может быть построено множество R -графов.
Это число может быть уменьшено, если учесть, что множество рассматриваемых подграфов с заданным числом вершин разбивается на подмножества изоморфных между собой подграфов, количество которых, ,как правило, существенно меньше. Однако требуемая при этом проверка изоморфизма двух графов имеет большую вычислительную сложность [7у}] . Отметим, что сформулированная задача по крайней мере столь же сложна, как и ряд других широко известных экстремальных комбинаторных задач.
Существующий опыт решения этих задач говорит о том, чти, несмотря на все ухищрения, практические алгоритмы оптимизации,, например алгоритмы ветвей и границ, имеют экспоненциальную трудоемкость. В связи с высокой трудоемкостью оптимизации в строгом смысле определенный интерес представляют методы приближенной оптимизации, в частности,- методы эвристического типа. Последние, как правило, имеют полиноминальную оценку трудоемкости, и основной интерес в их анализе представляет отыскание гарантированной величины погрешности. Далее приводится ряд результатов по построению приближенных алгоритмов с оценкой погрешности.
Из неравенства CSA) следует, что на классе деревьев без линейных участков верхняя и нижняя оценки совпадают и дают истинное значение LQ . Для деревьев с линейными участками верхняя и нижняя оценки различаются, поэтому представляет интерес исследование их точности для различных подклассов деревьев с линейными участками. Исчерпывающий анализ этого вопроса весьма затруднителен. Вместе с тем, отметим, что для линейного графа G верхняя оценка точнее нижней и отличается от UG всего на 2. Кроме того, нетрудно доказать, что класс деревьев, для которых нижняя граница точна, включает в себя деревья с линейными участками, удовлетворяющие следующему условию: для любого поддерева = ( Пс, Г) .
Построение алгоритмов неполкой идентификации состояния объекта
Одним из весьма распространенных способов неполной идентификации состояний объекта является пороговая бинарная классификация, при которой множество состояний объекта разделяются на два класса, в зависимости от того, превышает ли значение функционала от состояния некоторую величину или нет. С одной стороны определение функционала должно с наибольшей полнотой отражать содержание практических задач, а с другой, формализация должна быть достаточно "простой", чтобы можно было рассчитывать на успешное решение задачи. Этим, как правило, противоречивым требованиям отвечает следующая интерпретация пороговой, бинарной классификации состояний объекта по результатам зависимых проверок.
Предположим, что проверки независимый положительному результату проверки ос приписано некоторое положительное число и)с ос) , называемое в дальнейшем весом проверки. Весом состояния будем называть величину где #={хеХ : $ос)= ] и полагать se iS\ , если 4JCs) Н , в противном случае s&0 Аналогичный подход может быть использован и в случае зависимых проверок. Отличие заключается в том, что вес проверки может быть слагаемым в весе состояния, а сама проверка проведена не будет. Это происходит тогда, когда следующая за ней проверка в G уже проведена с положительным результатом.
В некоторых случаях, роль контроля может быть сведена к бинар- ной классификации состояний объекта. Ограничимся рассмотрением интегральной оценки уровня состояния объекта, проводимой в упрощенном варианте на основании количества проверок с положительным результатом. На множестве состояний $ (G) определим неотрицательную функцию LCS) = 5L 5С ) . Множество SLG) относительно заданного порога Н можно разбить на два непересекающихся подмножества So,Bi полагая, что se б± , если h,Cs) Н , иначе se Й0 . Каждой последовательной стратегии, классифицирующей состояния на 30jg}., , поставим в соответствие R „ -граф, который может быть получен в результате усечения R -графа. Обозначим через Сх #) и С еД ?г) вершины, непосредственно следующие в R -графе за вершиной ( сс ,6), причем в (peg Й) входит дуга s(x , G = ? , а в (xr Gr) входит дуга. sC jG )-"!
Отметим, что сформулированная задача может быть решена, например, методом динамического программирования. Наша цель заключается в разработке более простых и достаточно близких к оптимальным алгоритмов. Пусть G Q G t причем вместе с каждой вершиной osc X , подграф G содержит все вершины, предшествующие вершине ее в графе (л. Множество вершин X называется правильным подмножеством вершин графа G . Подграф, порожденный правильным подмножеством вершин, будем называть правильным подграфом. Лемм a :5,1. Пусть G правильный подграф графа G . Тогда справедливо соотношение До-ка.зательство проведем от противного. Допустим, что для оптимальных деревьев классификации справедливо неравенство и н . . L»„i , и убедимся в том, что это противоречит предположению ц -о минимальной высоте R .» -графа. Обозначим через хр вершину непосредственно предшествующую ХеХ в R -графе, а через х эсг вершины, непосредственно следующие за х , причем в Xg входит дуга $0 0= о , ,а в хг дуга Sae)=. "f .
При преобразованиях, связанных с удалением каждой вершины рсєХ высота дерева классификации не увеличивается. Таким образом Ья- LG t и поэтому L% UG . Теперь осталось показать, что R -граф классифицирует по порогу Н множество реализаций S(G ). Действительно, поскольку G правильный подграф графа G , то доопределив каж-дую реализацию se S CG ) , полагая scoc)=0 для всех xlX , получаем подмножество (6?) множества SC.G), причем, если s & () то соответствующая ей реализация (.G ) .
Исследование применения метода. ветвей и границ и метода динамического программирования в задачах идентификации состояния объекта
В общем случае класс алгоритмов ветвей и границ может быть описан с помощью девяти объектов ( Е , , Е , F , D , L , ТГ , BR , R6) , где В - правило ветвления, $ - правило выбора, F - характеристическая функция, 3) - отношение доминирования, U - функция нижней оценки, V - верхняя оценка стоимости, - правило исключения, BR - величина максимального относительного отклонения оптимальной стоимости от стоимости приемлемого решения, RB -предельное количество ресурсов 79] . Правило выбора S служит для выбора следующей вершины ветвления из текущего множества активных вершин (вершина называется текущей активной вершиной в том и только в том случае, когда она порождена, но еще не исключена и не подвергнута ветвлению).
Величина 6 R представляет собой допустимую величину максимального относительного отклонения оптимального решения от приемлемого решения. На каждом шаге алгоритма проверяется неравенство (U"-L)/XT 4 в » где IT - значение минимизируемой функции для наилучшего из полных решений, U - известная (на данном шаге)нижняя оценка функции. Если неравенство выполняется, то задача решена с приемлемой точностью. Предельное количество ресурсов R& представляет собой вектор, компонентами которого являются верхние границы времени, отведенного для расчетов, и объем памяти для хранения активных вершин и непосредственных потомков вершины ветвления. Совокупность остальных объектов, описывающих алгоритм ветвей и границ,определяют набор правил исключения вновь порожденных и текущих активных вершин из числа активных. Эффективность метода ветвей и границ при решении некоторого класса задач существенно зависит от качества процедуры определения оценок. Требования к используемым процедурам, как правило, противоречивы, так как должны быть достаточно точными и при этом легко вычислимыми. В разделе 3 был рассмотрен алгоритм построения нижней оценки Lr для величины LG , если G - дерево. В качестве оценки LG использовалась сумма длин несвязанных линейных участков графа G . Та же величина может быть использована для нижней оценки и в общем случае, когда G - диаграмма Хассе.
Нижнюю оценку Lr можно улучшить, если в качестве LQ ВЗЯТЬ сумму длин несвязанных линейных участков графа G . Как показано в разделе 2, когда Q - дерево, вычисление Lr может бьгюь выполне-но за 0(jvj операций. Рассмотрим подробнее задачу вычисления Li для общей диаграммы Хассе. Для этого перейдем к эквивалентной постановке задачи - нахождению в диаграмме Хассе антицепи максимального веса.
Под стягиванием будем подразумевать операцию удаления дуги Є и отождествление ее концевых вершин. Будем говорить, что вершины, инцидентные удаляемой дуге, стягиваются. Теперь определим преобразование графа G , заключающееся в последовательном выполнении операции стягивания некоторых его вершин. Две соседние вершины эсА , Х2 , эс2еГэе2. стягиваются, если выполняются следующие условия , 98 Иначе говоря, вершина ас?у и непосредственно следующая за ней вершина осг стягиваются, если вершина ас, имеет одну исходящую и не более одной входящей дуги, а вершина осг - одну входящую и не более одной исходящих. Таким образом, каждый линейный участок W графа G заменяется одной вершиной xw с весом СС с -УСо С -- - , где Уь - число стягиваемых вершин линейного участка VA/ . Вес вершины графа Q , не стягиваемой ни с одной другой вершиной,равен единице.
Доказательство. Обозначим через \Х множество антицепей в G , а через Q множество антицепей в Р . Каждой антицепи ttell поставим в соответствие антицепь а е О. , полагая, что XU- -Y во . Тогда вес вершин антицепи UGLT равен числу вершин ІОІ соответствующей антицепи oeQ . Остается показать, что в Р не существует антицепи, мощность которой превышает максимальный вес антицепи в G . Для доказательства последнего утверж-дения допустим противное, что существует такая антицепь Ц , что ІО сСи ) , где U - антицепь максимального веса в G . Покажем, что тогда в G существует антицепь и , вес которой ССи) с Си ) , что противоречит предположению о максимальном весе антицепи ц" єТГ .
Теперь рассмотрим алгоритм вычисления верхней оценки LG Следует отметить, что при использовании метода ветвей и границ не обязательно вычислять верхнюю оценку (при минимизации функционала) когда требуется найти точное решение задачи. Другое дело, если метод ветвей и границ используется в качестве приближенного алгоритма. Это связано, в первую очередь, с ограничением на объем используемой памяти и на время решения задачи. Тогда на момент останова, в связи с нарушением вводимых ограничений, необходимо оценить точность полученного решения, которая определяется нижней оценкой совместно с верхней.
Представляется важным и следующий факт, учитывающий особенность данной проблемы. Как уже отмечалось, часто на практике приходится отказываться от точного решения задачи идентификации не только из-за сложности решения данной комбинаторной задачи, но и из-за значительного объема памяти, требуемой для хранения решения задачи. В связи с этим возрастает роль тех эвристических конструкций, которые вместо оптимизации в целом выполняют последовательную оптимизацию (МВТ без возвратов). Основу таких алгоритмов составляет процедура вычисления по некоторому критерию корневой вершины программы идентификации ( R -графа ) . После того как определена корневая вершина ос и известно ее состояние ( т.е. известен результат проверки, соответствующей корневой вершине),строится подграф Q или эс (в зависимости от результата проверки ос. ) и вновь используется процедура определения корневой вершины по графу, в качестве которого используется &ЗС. или GJC .К таким алгоритмам относятся, в частности, алгоритмы, основанные на методе дихотомии числа состояний, рассмотренные в разделе 2.
Практическое использование разработанных алгоритмов идштификации
В ходе выполнения НИР-530С73 были рассмотрены и реализованы алгоритмы построения программ идентификации состояния объекта по результатам зависимых проверок. При этом предполагалось, что возможны любые комбинации отказавших элементов, при отсутствии достоверной информации о распределении вероятностей на множестве состояний объекта, что определило выбор минимаксного критерия при оптимизации программы диагностирования. Здесь рассматривается стратегия диагностирования фрагмента САУ при различных предположениях относительно числа одновременно отказавших элементов.
Построению программы предшествует этап описания объекта диагностирования в виде информационно-энергетического графа, который выполняется по его функциональной схеме. Этот этап подробно описан в специальной литературе [ 5"- 7] и поэтому здесь не рассматривается.
На рис. 5А изображен граф G-(X,r) , представленный заказчиком, соответствующий фрагменту САУ. Программа поиска R CG) одного отказавшего элемента приведена на рис. 5.2
Предположим, что число одновременно отказавших элементов р 2 . Для построения & &)(щс.5.Ъ ) был использован подоптималь-ный алгоритм, описанный в заключительном отчете по НИР-530 L 3 При этом каждая вершина в Rz(.G0 -графе выбирается таким образом, чтобы число концевых вершин обоих поддеревьев различались возможно меньше.
В работе [-13] было предложено формировать стратегию обучения и контроля знаний в АОС на основе зависимости вопросов (заданий) , предъявляемых обучаемому по инициативе системы. Первым шагом построения предлагаемой модели является описание зависимости вопросов, т.е. построение графа G . Ниже кратко излагается методика построения графа зависимости вопросов и, в качестве примера, рассматривается автоматизированный коллоквиум "Системы счисления и представления чисел в памяти ЭВМ М-600", используемый в учебном процессе на кафедре АСУ ЛИАП по курсу "Основы программирования".
Обозначим через Е множество, элементами которого являются определения, леммы, утверждения и т.д., т.е. тот разделенный на порции материал, знание .которого дает возможность правильно ответить на множество вопросов В .
Поставим в соответствие элементам множества В некоторое семейство подмножеств множества Е , полагая, что &&-« E(6)QE, если наличие знаний контролируемого материала, соответствующего Е(&) необходимо и достаточно для правильного ответа на вопрос &,
Опишем предметную область автоматизированного коллоквиума "Системы счисления и представления чисел в памяти ЭВМ М-600" по їм средством множества элементарных вопросов изоморфного множеству Е. е ) Сколько двоичных разрядов содержит ячейка памяти ЭВМ М-6000? е ) Сколько ячеек памяти отводится для представления целого числа? е ) Укажите значение знакового разряда ячейки, если в ней записано положительное число. ец") Какой код используется для представления отрицательного числа? е ) Сколько ячеек памяти требуется для представления вещественного числа? е Укажите количество двоичных разрядов (исключая знаковый разряд ) , используемых для представления мантиссы вещественного числа.
Теперь сформулируем вопросы, отличающиеся от вопросов множества Е тем, что требуют для правильного ответа некоторую совокупность знаний о предметной области. в ) Переведите десятичное вещественное число {с целой частью) в о -ичное (10 и о не связаны степенной зависимостью). B-2) Переведите вещественное О -ичное число (с целой частью ) в 10-ичное (о и 10 не связаны степенной зависимостью). в,4) Переведите вещественное р -ичное число (с целой частью) в р -ичное-в]\ Переведите вещественное р -ичное число ( с целой частью ) в Р -ичное. Bj) Переведите вещественное р -ичное число (с целой частью) в (и 4 10 ) в Переведите вещественное р -ичное число (с целой частью) в о -ичное ( р и а 10) . Дать ответ в нормализованном виде. в7) Переведите вещественное р -ичное число (с целой частью ) в р -ичное. Дать ответ в нормализованном виде. в ) Переведите вещественное р -ичное число (с целой частью) в р -ичное. Дать ответ в нормализованном виде. в о.) Напишите содержимое ячейки памяти М-6000, если в ней записано целое положительное двоичное число d. . в,и) Напишите содержимое ячейки памяти М-6000, если в ней записано отрицательное целое двоичное число а . ви) Укажите порядок вещественного числа, записанного в ячейках памяти М, Mfl. в )2) Укажите мантиссу вещественного числа, записанного в ячейках памяти М, M+I. вв} Укажите через запятую знак мантиссы и знак порядка вещественного положительного числа, записанного в ячейках памяти М, ШІ. ви) Перевести целое р -ичное число в о -ичное ( р Q , р И Cj не равны 10). BIS") Запишите в ячейку памяти целое 8-ичное число и дайте 2-ичное представление содержимого ячейки. в, Л Запишите в ячейку памяти целое (отрицательное) Ю-ичное число Результат дать в 2-ичной форме. в (7") Запишите вещественное Ю-ичное число (положительное) в ячейку М, M+I. Дать через запятую 2-ичное представление их содержимого, в Запишите в ячейку памяти М, M+I вещественное двоичное число(с целой и дробной частью) в нормализованной форме. в ") Запишите целое Ю-ичное число (отрицательное) в ячейку памяти. Дайте 8-ичное представление содержимого этой ячейки. в2о}Какое р -ичное целое число записано в ячейке памяти, если известно, что она содержит Q ( Q - 2-ичное отрицательное число, B.2j) Записать вещественное (отрицательное) 2-ичное число в ячейку памяти в нормализованной форме. Укажите 8-ичное представление содержимого этих ячеек. в2 ) Записать вещественное (положительное) Ю-ичное число в ячейку памяти в нормализованной форме. Укажите 8-ичное представление содержимого этих ячеек. в2 ) Записать вещественное (отрицательное) Ю-ичное число в ячейки памяти. Укажите 2-ичное представление содержимого ячеек. выдайте 2-ичное представление содержимого ячеек памяти М, M+I, если в них записано р -ичное (отрицательное) число в нормализованной форме вг )Какое нормализованное (отрицательное) р -ичное число ( р НО, р 2 ) содержится в ячейках памяти М, M+I, если их 8-ичное № содержимое есть число CL . вЯ(Г) Записать вещественное (положительное) р -ичное число в ячейки памяти в нормализованной форме. Указать 8-ичное представление содержимого ячеек. в Записать вещественное (отрицательное) 10-ичное число в ячейки памяти. Дать их 8-ичное представление. в2 )Записать вещественное (отрицательное) р -ичное число в нормализованной форме в ячейки памяти М, M+I. Дать представление их содержимого в 8-ичной форме вгд)Записать 8-ичное представление содержимого ячейки памяти, если в ней записано р-ичное целое отрицательное) число в3о)Записать 2-ичное представление содержимого ячейки памяти, если в ней записано р-ичное целое (положительное) число (р 2- Л в ) Записать 8-ичное представление содержимого ячейки памяти, если в ней записано р -ичное целое (положительное) число Ср 2 WfOj. Следующий шаг формализации заключается в установлении зависимости между элементами множества 6 и Е .
