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

ВВЕДЕНИЕ.А

1. ЗАДАЧА ИДЕНТИФИКАЦИИ СОСТОЯНИЯ ОБЪЕКТА.-А—

1.1. Модель объекта диагностирования.Л

1.2. Методы оптимизации алгоритмов диагностирования . 4О

1.3. Задача идентификации состояния объекта по результатам зависимых проверок

Выводы.

2. ПОСТРОЕНИЕ АЛГОРИТМОВ ПОЛКОЙ КдЕНТИФШШЩ СОСТОЯНИЯ ОБЪЕКТА.

2.1. Идентификация состояния объекта, представляемого древовидной структурой, алгоритмом ранжирования

2.2. Алгоритмы, использующие процедуру балансировки

2.3. Последовательная реализация алгоритма балансировки . ^

2.4. Идентификация состояния объекта, представляемого графом типа диаграммы Хассе

Выводы.

3. ПОСТРОЕНИЕ АЛГОРИТМОВ НЕПОЛНОЙ ИДЕНТИФИКАЦИИ СОСТОЯНИЯ ОБЪЕКТА.

3.1. Уровневый алгоритм пороговой классификации состояний.

3.2. Многопороговая бинарная классификация состояний

3.3. Приближенный алгоритм многопороговой бинарной классификации

Выводы.

4. ИССЛЕДОВАНИЕ ПРИМЕНЕНИЯ МЕТОДА. ВЕТВЕЙ И ГРАНИЦ И МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ЗАДАЧАХ ИДЖГИФИКАЦИИ СОСТОЯНИЯ ОБЪЕКТА.-И

4.1. Алгоритм ветвей и границ .Л£

4.2. Алгоритм динамического программирования .123

Выводы.

5. ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ РАЗРАБОТАННЫХ

АЛГОРИТМОВ ИДЕНТИФИКАЦИИ. М.

5.1. Диагностирование аппаратуры системы автоматического управления при кратных отказах

5.2. Построение системы контроля знаний.

5.3. Диагностирование объекта с аппаратурной избыточностью. ЛИ.

Выводы. -1М.

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

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

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

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

Выводы

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

2. Использование разработанных алгоритмов для идентификации состояния аппаратуры автоматического управления показало возможность сокращения максимального количества проверок на 10-30$.

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

ЗАКЛКЯЕ11ИЕ

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

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

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

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

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

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

5. Предложена методика построения графа, описывающего множество вопросов (проверок) в автоматизированной системе контроля знаний обучаемого.

6. Практическое использование алгоритмов полной идентификации состояния объекта по результатам зависимых проверок, описываемых графом типа дерева, позволило на 10-30% сократить максимальное время поиска отказавших элементов в рассмотренной системе.

Практическое использование алгоритмов бинарной пороговой классификации состояний объекта по результатам зависимых проверок, описываемых диаграммой Хассе, в системах автоматизированного контроля знаний, позволило для ряда учебных курсов сократить максимальное время, затрачиваемое на опрос студента, в среднем на 20-30%.

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

1. Автоматизация проектирования сложных логических структур. (Под редакцией В.А.Горбатова). - М.: Энергия, 1978

2. Айгнер М. Комбинаторная теория. М.: Мир, 1982.

3. Алексеев О.Г., Володось И.Ф. О комплексном применении метода динамического программирования и метода ветвей и границ в задачах дискретного программирования. Автоматика и телемеханика, 1976, В 4, с. 92-100.

4. Альсведе Р., Вегенер И. Задачи поиска. М.: Мир, 1982.

5. Анишев П.А., Ачасов С.М. Методы параллельного микропрограммирования. Новосибирск: Наука, 1981.

6. Аржененко А.Ю., Чугаев Б.Н. Оптимизация компактных вопросников. Электронное моделирование, 1984, № 4, с. 59-64.

7. Аткинсон Р., Бауер Г., Кротерс Э. Введение в математическую теорию обучения. М.: Мир, 1969.

8. Аткинсон Р. Человеческая память и процесс обучения. М.: Прогресс, 1980.

9. Аттель У. Обучающая вычислительная машина: моделирование в реальном масштабе времени обучающего диалога. В кн.: Кибернетика и проблемы обучения. - М., Наука, 1970.

10. Аузинь П.К., Осис Л.Я. Минимизация числа точек съема диагностической информации, основанная на алгебраическом анализе граф-модели сложного объекта. В кн.: Кибернетика и диагностика. Вып. 3. Рига: Зинатые, 1969, с. 33-43.

11. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

12. Бабкин В.Ф. Применение метода нумерации в задачах кодирования. В кн*: Информационный обмен в вычислительных сетях.

13. M.: Наука, 1980, с. 237-248.

14. Бобков А.И., Евсеев Г.С. Структурный подход к построению диалога. В кн.: Тезисы докладов Всесоюзной конференции „Диалог „Человек-ЭВМ"". - Л.: МАЛ, 1982. Ч. I, с. 80-82.

15. Бобков А.И., Евсеев Г.С. Об информационной избыточности множества зависимых проверок. В кн.: Тезисы докладов Всесоюзного симпозиума по проблеме избыточности в информационных системах. - Л., 1983, Ч. 2, с. 140-142.

16. Бобков А.И. Управление процессом контроля знаний. В кн.: Применение ЭВМ в учебном процессе. Межвузовский сборник. ЛИАП, 1983, вып. 165, с. 16-21.

17. Бобков А.И. Алгоритм пороговой классификации уровня знаний на частично упорядоченном множестве вопросов. В кн.: Применение ЭВМ в учебном процессе. Межвузовский сборник. ЛИАП, 1983, вып. 165, с. 21-26.

18. Бобков А.И., Макаренко В.Н. Идентификация состояния объекта с аппаратурной избыточностью. В кн.: Системы обработки и передачи информации. Межвузовский сборник. - Л.: ЛИАП, 1984, вып. 172, с. I08-II3.

19. Бобков А.И. Многопороговая классификация состояний диаграммы Хассе. В кн.: Систнмы обработки и передачи информации. Межвузовский сборник. - Л.: ЛИАП, 1984, вып. 172, с. 100-107.

20. Бобков А.И., Тюрликова O.A. Стратегия выбора вопросов прибинарной классификации уровня знаний. В кн.: Тезисы докладов научно-методической конференции »Применение АОС в учебном процессе". - Минск: ЕГУ, 1984, с. 70.

21. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. -М.: Высшая школа, 1976.

22. Беляев Ю.К., Ушаков И.Л. Математические модели для задач обнаружения и локализации неисправностей. В кн.: Кибернетику на службу коммунизму. - М.: Энергия, 1964, с. 24-33.

23. Берж К. Теория графов и ее применение. М.: ИЛ, 1962.

24. Богомолов A.M., Грунский И.О., Сперанский Д.В. Контроль и преобразование дискретных автоматов. Киев: Наукова думка, 1975.

25. Брегман В.И. Графы в задачах управления производством. -М.: Статистика, 1974.

26. Брюле Д.Д., Джонсон P.A., Клетский Е.Д. Отыскание неисправностей в технических устройствах. Зарубежная радиоэлектроника, 1961, Ш 7, с.

27. Бурлаков Е.А., Катханов М.И., Сафронов В.В. Оптимизация систем автоматического контроля по минимаксному критерию. -Автоматика и телемеханика, 1980, №-3, с. 170-179.

28. Вайнштейн Е.Д. Метод дихотомии в некоторых минимаксных задачах на графах. Автоматика и телемеханика, 1980, № 8,с.85-92.

29. Введение в техническую диагностику / Г.Ф.Верзаков, Н.В. Киншт, В.И.Рабинович и др.; Под ред. К.Б.Карандеева. М.: Энергия, 1968.

30. Винтер Б. Оптимальные диагностические процедуры. В кн.: Оптимальные задачи надежности. Пер. с англ. / Под ред. И.А.Ушакова. - М.: Изд-во стандартов, 1968.w

31. Гобземш А.Ю., Кизуб В.А. О построении сетевых диагностических моделей. Автоматика и вычислительная техника, 1983, № 3, с. 73-78.

32. Григоришин И.А. О возможности усложнения вопросов в системах автоматизированного обучения. Управляющие системы и машины, 1980, № 4, с. 65-71.

33. Гуляев В.А. Организация живучих вычислительных структур. -Киев: Наукова думка, 1982.

34. Гэри М.Р., Джонсон Д,С. Вычислительные машины и труднорешае-мые задачи. М.: Мир, 1982.

35. Данилов В.В., Тяжев В.Т. Тест поиска дефектов в конечном синхронном автомате. Автоматика и телемеханика, 1982, В 7, с.

36. Данилов В.В., Тяжев В.Т. Тест поиска дефектов в комбинационной схеме. Автоматика и телемеханика, 1981, № 8, с.

37. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.

38. Емеличев В.А., Комяик В.И. Метод последовательности планов для решения задач дискретной оптимизации. М.: Наука,1981.

39. Иванин В.М., Кукса А.И. Вычисление математического ожидания числа правильных подмножеств в ациклическом ориентированном графе со случайными дугами. В кн.: Теория оптимальных решений. - Киев: Ж АН УССР, 1977, с. 41-45.

40. Карибский В.В., Пархоменко П.П., Согомонян Е.С. Техническая диагностика объектов контроля. М.: Энергия, 1967.

41. Карп P.M. Сводимость комбинаторных задач. Кибернетический сборник. Вып. 18. М.: Мир, 1981.

42. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. М.: Мир, 1978.

43. Конвей P.B., Максвелл В.А. Теория расписаний. М.: Мир, 1975.

44. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978.

45. Ксёнз С.П. Поиск неисправностей в радиоэлектронных системах методом функциональных проб. М.: Сов. радио, 1965.

46. Ксёнз С.П., Ярцев A.M. Теория эксплуатации радиоэлектронных систем. М.: МО СССР, 1975.

47. Ксёнз С.П. Техническая диагностика и ремонтопригодность средств и комплексов связи. Л.: ВАС, 1982.

48. Кузнецов П.И., Пчелинцев I.A., Гайденко B.C. Контроль и поиск неисправностей в сложных системах. М.: Сов. радио, 1969.

49. Кук С.А. Сложность процедур доказательства теорем. Кибернетический сборник. Вып. 18. М.: Мир, 1981.

50. Литваков Б.М. Механизмы выбора, использущие множественно-графовые структуры. Автоматика и телемеханика, 1980, Je 9, с. 145-153.

51. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.

52. Михалевич B.C., Кукса А.И. Методы последовательно®; оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983.

53. Миркин Б.Г. Проблемы группового выбора. М.: Наука, 1974.

54. Методика выбора диагностических параметров для непрерывных объектов, представленных логическими моделями / Гос. комитетстандартов СМ СССР, ВНИИ НМЖ. Горький, 1977.

55. Методы параллельного микропрограммирования / Под ред. О.Л. Бандман. М.: Наука, 1981.

56. Мозгалевский A.B. Техническая диагностика (непрерывные объекты). Автоматика и телемеханика, 1978, № I; с. 145-166.

57. Мозгалевский A.B., Гаскаров Д.В. Диагностика судовой автоматики методами планирования эксперимента. Л.: Судостроение, 1977.

58. Мятлев В.Д. Теоремы и алгоритмы об одной схеме последовательного поиска дефектных элементов. В кн.: Вопросы кибернетики. Вып. 35. - М.: Сов. радио, 1977.

59. Мятлев В.Д. Групповые проверки, минимизирующие среднюю цену. В кн.: Вопросы кибернетики. Вып. 71. М.: Сов. радио, 1981.

60. Носков В.Н. 0 сложности тестов, контролирующих работу входов логических схем. В кн.: Дискретный анализ. Труды института математики СО АН СССР. Вып. 27. - Новосибирск, 1975,0.23-52.

61. Носков В.Н. О длинах минимальных единичных диагностических тестов, контролирувдих работу входов логических схем. В кн.: Дискретный анализ. Труды института математики СО АН СССР. Вып. 32. - Новосибирск, 1978, с. 40-52.

62. Ноткин Р.Г. Об одной задаче, возникающей при построении контролирующих тестов для логических сетей. Автоматика и телемеханика, 1975, № 6, с.

63. Осис Я.Я. Алгоритм нахождения оптимального подмножества параметров для контроля технического состояния сложного объекта. В кн.: Кибернетика и диагностика. Вып. 2. - Рига: Зинатые, 1968, с. 33-40.

64. Основы технической диагностики / Под ред. П.П.Пархоменко. -М.: Энергия, 1971.

65. Пархоменко П.П., Правильщиков П.А. Диагностирование программного обеспечения. Автоматика и телемеханика, 1980, № I.

66. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики. М.: Энергия, 1981.

67. Пашковский Г.С. Оптимальный выбор контролируемых параметров для систем встроенного контроля. Изв. АН СССР. Техническая кибернетика, 1980, № I, с. I0I-III.

68. Пашковский Г.С. Задачи оптимального обнаружения и поиска отказов в РЭА. М.: Радио и связь, 1981.

69. Поспелов Д.А. Логико-лингвистические модели в системах управления. М.: Энергия, 1981.

70. Разработка алгоритмов автоматизированного контроля технических комплексов с применением управляющих ЭВМ, Отчет по НИР-530 / ЛИАП: руководитель работы Петровский A.B. JS ГРУ 86300 . - Л., 1983.

71. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.

72. Романовский И.В. Алгоритмы решения экстремальных задач. -М.: Наука, 1977.

73. Руднев В.В. Системы взаимосвязанных графов и алгоритмическое программирование дискретных управляющих устройств. Автоматика и телемеханика, 1979, № 7, с. 122-129.

74. Руднев В.В. Система взаимосвязанных графов как модель сложных конечных автоматов. Автоматика и телемеханика, 1980, № 3, с. 156-163.

75. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

76. Свиридов А.П. Оптимальное планирование повторений учебного материала. Труды МЭИ, 1980, й 469, с. 85-88.

77. Сергиенко И.В., Касппшцкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наукова думка, 1981.

78. Сердаков A.C. Автоматический контроль и техническая диагностика. Киев: Техника, 1971.

79. Теория расписаний и вычислительные машины / Под ред. Э.Г.Ко^-фмана Э.Т. М.: Наука, 1984.

80. Тимонен Л.С. 0 построении оптимальных программ контроля работоспособности. Автометрия, 1966, № I, с. 75-82,

81. Тимонен Л.С. 0 построении оптимальных программ диагностики состояния сложных технических систем. Изв. АН СССР. Техническая кибернетика, 1966, № 4, с. 95-103.

82. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

83. Форд Л.Р., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966.

84. Харари Ф. Теория графов. М.: Мир, 1973.

85. Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения. В кн.: Кибернетический сборник,

86. М.: Мир, 1964, с. 202-218.

87. T^dhs. OH Computers, /976 f A ^ p У$ъ-5УЗgi HclC€ Ue-L-ík A. Cottíetti strua luj andtícihci Cish'/L^ for со/npcdu ¿¡ased tdnetvélen;

88. J. C&mpu t, -/3a$ed Instruct. f i$S>b, p. Y-У9X. Jccrdzea M. Structured rtp/^sehictiion cj-knc^ fedge petti nets as aid teaekin-^ and rei-ewejt . Mates Cctnf*<~t. f>. ôbï-fiy.

89. S3. oohthij С V-, Meiyccfq W. Сотриte/t dlajjnoiùl(r<>¿}b£j -tíÍL íieeki^ú V¿ te rc&ch , ~jt EE

90. Tottis. €>VL Completers 9-H9 roe C-2o,"H?p. HQ9

91. R(Lmahwortiuj С. V-, Uct* Y.W. R*tia$H<ty1.ùàjïiS of ssystvms, WirtL OOflCLtrrevutdeteet¿ú*z -JEBE TrCLhs.cn Comput-tnl /07-5Г л/9} p SÏC-89-ê.