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

ВВЕДЕНИЕ.

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

1.1. Анализ функционирования систем управления техническими средствами.

1.1.1. Роль и место корабельных систем управления техническими средствами.

1.1.2. Тенденции и противоречия в процессе проведения контроля.

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

1.2. Анализ существующих методов принятия решения оператором в процессе контроля.

1.3. Особенности автоматизированного выявления отказов в системах управления техническими средствами корабля.

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

ГЛАВА 2. РАЗРАБОТКА МЕТОДА ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ КОРАБЕЛЬНЫХ СИСТЕМ УПРАВЛЕНИЯ ПРИ ОБНАРУЖЕНИИ ОТКАЗОВ.

2.1. Задачи процесса распознавания отказов.

2.2. Модель системы распознавания отказов.

2.3. Обоснование выбора алгоритма распознавания.

2.4. Оценка информативности групп признаков.

2.5. Обоснование и расчет показателя эффективности процесса распознавания отказов.

2.5.1. Постановка задачи оптимизации процесса распознавания

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

2.5.3. Вычисление интегрального показателя эффективности распознавания.

2.6. Сведение оптимизации процесса распознавания отказов к задаче покрытия.

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

ГЛАВА 3. КОМБИНАТОРНО-ЛОГИЧЕСКИЕ АЛГОРИТМЫ ФОРМИРОВАНИЯ И ПОКРЫТИЯ ТАБЛИЦЫ НАБОРОВ ПРИЗНАКОВ

3.1. Задача покрытия как задача комбинаторного типа.

3.2. Алгоритмы формирования таблицы наборов признаков.

3.2.1. Задачи, решаемые алгоритмами формирования таблицы наборов признаков.

3.2.2. Алгоритм формирования таблицы наборов признаков на основании метода декомпозиции.

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

3.3. Алгоритмы покрытия таблицы наборов признаков.

3.3.1 Алгоритм покрытия таблицы наборов признаков по столбцам.

3.3.2. Алгоритм покрытия таблицы наборов признаков по строкам.

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

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

4.1. Методика оценки комбинаторно-логических алгоритмов.

4.2. Экспериментальная проверка эффективности предложенных алгоритмов решения задачи покрытия.

4.3. Оценка эффективности алгоритма формирования таблицы наборов признаков.

4.4. Оценка эффективности алгоритма при решении задачи покрытия полученного класса таблиц.

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

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

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

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

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

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

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

Целью работы является разработка алгоритмов распознавания отказов в системах управления техническими средствами корабля, которые позволяют использовать сравнительно небольшое число контролируемых признаков ТС.

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

1) разработка моделей, обеспечивающих формальное описание процесса распознавания образов на этапе выявления отказов в корабельных систем;

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

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

Для большинства комбинаторно-логических задач существуют простые в вычислительном отношении модели определения оптимальных решений в исследуемом процессе. Однако для задач большой размерности такая возможность поиска решения является только потенциальной, так как эти модели связаны с перебором большого числа различных вариантов. В [10] показано, что для большинства задач на дискретных математических структурах они вообще отсутствуют. Это обстоятельство вынуждает отказаться от попыток построения моделей для нахождения строгих оптимальных решений и направить все усилия на решение практических задач, относящихся к классу комбинаторно-логических, на создание эвристических моделей.

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

Поставленная цель определяет следующие направления исследования:

- анализ функционирования СУ на этапе контроля и принятия решений по отказам в технических средствах корабля;

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

- разработка комбинаторно-логических алгоритмов формирования и покрытия таблицы наборов признаков; 5

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

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

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

Результаты диссертации использованы при создании программного обеспечения СУ ТС "Пурга" (в части алгоритмов сигнализации и защиты) в ФГУП НПО "Аврора", а также внедрены в учебный процесс в высших учебных заведениях Санкт-Петербурга (Военно-морской институт радиоэлектроники имени A.C. Попова, Военно-морская академия имени Н.Г. Кузнецова). Акты внедрения прилагаются к диссертации.

Выводы по главе 4

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

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

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

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

98

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

5. Предложены алгоритмы покрытия таблицы признаков «по строкам» и по «столбцам», снижающие размерность процедуры выбора совокупности наборов информативных признаков для распознавания отказов.

99

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

Практической значимостью обладают следующие результаты диссертационной работы.

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

2. Методика оценки эффективности комбинаторно-логических алгоритмов распознавания отказов путем организации вычислительного эксперимента на совокупности задач, генерируемых для предъявления оператору, и сравнения полученных результатов решения задач комбинаторно-логическими алгоритмами с покрытием таблицы признаков на основе случайного поиска и выбора' «наихудших» решений по разработанному критерию.

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

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

1. Адельсон-Вельский Г.М., Кузнецов О.П. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988. - 480с.

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

3. Алексеев А.Г. Алгоритм решения задачи о покрытии. Изв. АН СССР. Техническая кибернетика, N5,1980, с. 12-16.

4. Архангельский Е.А. Методы оценки эффективности корабельных систем управления. Л.: BMA, 1985. 12с.

5. Баишев В.М. Методы распознавания в обработке сведений радиоэлектронной разведки. СПб.: BMA им. Н.Г. Кузнецова, 1999. 116с.

6. Буреев В.А. Методы сокращения вычислительных затрат в задачах распознавания изображений. Зарубежная радиоэлектроника, 1980, N4, с.52-75.

7. Вадзинский Р.Н. Математическая статистика. СПб.: BMA, 1993. 317с.

8. Вапник В.И., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). М.: Наука, 1974. - 416с.

9. Волгин Н.С. Применение методов теории вероятностей в оперативно-тактической области. Л.: BMA, 1983. 180с.

10. Ю.Волгин Н.С., Махров И.В., Юровский В.А. Исследование операций. Л.: BMA, 1981.-280с.

11. П.Гасов В.М., Меньков A.B., Шигин A.B. Системное проектирование взаимодействия человека с техническими средствами. М.: Высшая школа, 1991.- 142с.

12. П.Гасов В.М., Соломонов Л.А. Инженерно-психологическое проектирование взаимодействия человека с техническими средствами. М.: Высшая школа, 1990,- 127с.

13. Гвардейцев М.И., Морозов В.П., Розенберг В.Я: Специальное математическое обеспечение управления. М.: Сов. радио, 1978. - 512с.

14. Головкин Б.А. Машинное распознавание и линейное программирование. -М.: "Советское радио", 1973. 100с.150

15. Горелик А.Л., Скрипкин В.А. Некоторые вопросы построения систем распознавания. М.: Советское радио, 1974. - 224с.

16. Горелик А.Л., Скрипкин В.А. Методы распознавания. М.: Высшая школа, 1977.-221с.

17. Горелик А.Л. и др. Современное состояние проблемы распознавания: Некоторые аспекты. М.: Радио и связь, 1985. - 160с.

18. Грешилов A.A. Как принять наилучшее решение в реальных условиях. М.: Радио и связь, 1991. - 320с.

19. Губинский А.И., Евграфов В.Г. Эргономическое проектирование судовых систем управления. Л.: "Судостроение", 1977. - 224с.

20. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981.-432с.

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

22. Давришев М.А. Применение теории распознавания при выявлении отказов в корабельных АСУ. Деп. в ЦВНИ МО, №ДР В4323, серия Б, вып. 51. - 15 с.

23. Давришев М.А. Метод организации и использования системы централизованного контроля корабельных АСУ. Деп. в ЦВНИ МО, №ДР -В4322, серия Б, вып. 51. 17 с.

24. Давришев М.А. Организация информационной поддержки оператора системы централизованного контроля корабля. //Гироскопия и навигация, 1998, №3,-с. 25-28.

25. Давришев М.А. Организация многоуровневых вычислительных комплексов. //В сб. тезисов докладов 4-й межведомственной НТК «Проблемные вопросы сбора, обработки и передачи информации», СПб: Военно-морской инженерный университет, 1999.

26. Давришев М.А. Автоматизация распознавания отказов в корабельных системах на основе системы централизованного контроля. //Тезисы доклада на 4-й международной конференции "Моринтех", СПб., 2001 г.

27. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. -512с.

28. Емельянов C.B., Ларичев О.И. Многокритериальные методы принятия решений. М.: Знание, 1985 - 32с.

29. Журавлев Ю.И. Локальные алгоритмы вычисления информации I //Кибернетика, 1965, N1, с.12-19.

30. Журавлев Ю.И. Локальные алгоритмы вычисления информации II //Кибернетика, 1966, N2, с. 1 -11.

31. Журавлев Ю.И., Финкелыптейн Ю.Ю. Локальные алгоритмы для задач линейного целочисленного программирования. В кн.: Проблемы кибернетики -М.: Наука, 1965, вып. 14, с. 289-295.32.3акревский А.Д. Логический синтез каскадных схем. М.: Наука, 1981. -414с.

32. Информационно-управляющие человеко-машинные системы: исследование, проектирование, испытание. Справочник. М.: Машиностроение, 1993. -528с.

33. Искусственный интеллект. Кн.1. Системы общения и экспертные системы: Справочник. М.: Радио и связь, 1990. - 464с.

34. Кожухаров А.Н., Петрикеева Т.Г., Черняк Л.Е. Алгоритмы и модели управления в технических организационных системах. //Проблемы исследования операций и организационного управления. 1976. Вып. 10, с.52-58.

35. Кожухаров А.Н., Петрикеева Т.Г., Черняк Л.Е. Эвристическая модель принятия решений при подготовке рукописей к изданию //Проблемы исследования операций и организационного управления. 1976. Вып. 12, с.9-12.

36. Крэлти Дж., Кумбс М. Экспертные системы: концепции и примеры. М.: Финансы и статистика, 1987. - 191с.

37. Компьютер и задача выбора. М.: Наука, 1989. - 208с.

38. Крамер Г. Математические методы статистики. М.: Наука, 1978. 210с.

39. Кузин Е.С. и др. Интеллектуализация ЭВМ. М.: Высшая школа, 1989. -158с.

40. Кубанов Г.П. Распознавание в системах автоконтроля. М.: Машиностроение, 1973. - 424с.

41. Кузюрин H.H. Асимптотическое исследование задачи о покрытии. В кн.: Проблемы кибернетики, вып.37. -М.: Наука, 1980, с. 19-56.

42. Леридан Т.Б., Феррелл У.Р. Системы человек-машина: Модели обработки информации, управления и принятия решений человеком-оператором. М.: Машиностроение, 1980.-400с.

43. Ларичев О.И. Принятие решений как научное направление: методологические проблемы. Системные исследования. М.: Наука, 1982. - 324с.

44. Ларичев О.И. Объективные модели и субъективные решения. М.: Наука, 1987.-235с.

45. Ларичев О.И. Анализ процессов принятия человеком решений при альтернативах, имеющих оценки по многим критериям //Автоматика и телемеханика, 1981,N8,cl5-18.

46. Ларичев О.И., Поляков O.A. Человеко-машинные процедуры решения многокритериальных задач математического программирования //Экономика и математические методы, т. 16, 1980, N1, с.23.

47. Мелихов А.Н., Берштейн Л.С., Коровин С.Я. Ситуационные советующие системы с нечеткой логикой. М.: Наука. 1990. - 272с.

48. Обработка и представление данных в человеко-машинных системах. М.: Наука, 1988- 150с.

49. Отчет по НИР. Применение системы централизованного контроля в интересах автоматизации процесса распознавания образов в корабельных системах. / Шифр 4126, 1 этап, BMA им. Н.Г. Кузнецова, инв. № 31467, 1999, 33 с.

50. Отчет по НИР. Методы повышения эффективности системы централизованного контроля. / Шифр 4126, 2 этап, BMA им. Н.Г. Кузнецова, инв. №31472, 2000,-35 с.153

51. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. -М.: Мир, 1985. 512с.

52. Патрик Э. Основы теории распознавания образов. М.: Сов.радио, 1980. -408с.

53. Попов Э.В. Экспертные системы. Решение информационных задач в диалоге с ЭВМ. М.: Наука, 1987. - 288с.

54. Поспелов Д.А. Ситуационное управление: теория и практика. М.: Наука, 1986-288с.

55. Построение экспертных систем. -М.: Мир, 1987. 441с.

56. Проблемы принятия решения. М.: Наука, 1976. - 320с.

57. Распознавание образов: состояние и перспективы. /К. Верхаген, Р. Дейн, Ф. Грун и др. М.: Радио и связь, 1985. - 104с.

58. Реальность и прогнозы искусственного интеллекта. М.: Мир, 1987. - 247с.

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

60. Рыбаков Ф.И. Системы эффективного взаимодействия человека и ЭВМ. М.: Радио и связь, 1985. - 200с.

61. Скугарев В.Д., Федулов A.A., Щербаков О.В. Автоматизированные системы управления. М.: Воениздат, 1981. - 287с.

62. Современное состояние теории исследования операций. М.: Наука, 1979. -464с.

63. Taxa X. Введение в исследование операций. Кн.1. М.: Мир, 1985. - 479с.

64. Taxa X. Введение в исследование операций. Кн.2. -М.: Мир, 1985. 496с.

65. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978. -412с.

66. Уинстон П. Искусственный интеллект. -М.: Мир, 1980. 519с.

67. Флейшман С.Б. Эффективное применение метода непоследовательного динамического программирования в комбинаторной оптимизации //Автоматика и телемеханика, N2, 1988, с.76-85.

68. Фомин Я.А., Тарловский Г.Р. Статистическая теория распознавания образов. -М.: Радио и связь, 1986.-264с.

69. Фу К. Последовательные методы в распознавании образов и обучении машин. М.: Наука, 1971. - 256с.

70. Фукунага К. Введение в статистическую теорию распознавания образов. -М.: Наука, 1979.-367с.

71. Человеко-машинные системы и комплексы принятия решений. Тезисы докладов. Таганрог: Академия наук СССР, 1989. - 206с.1. УТВЕРЖДАЮ»

72. Председателя начальника СО-20 Прикота A.C.

73. Председатель комиссии: Начальник С0-20 Члены комиссии:

74. Начальник лаборатории 2032 Главный конструктор1. Прикот A.C.7.v Нахимов В.Н. Шереметьев Ю.Н.