Разработка и анализ методов идентификации, основанных на зависимых проверках

• Автор: Бобков, Александр Ильич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Ленинград
• Количество страниц: 216 c. : ил

ВВЕДЕНИЕ. Л

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

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

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

1.3. Задача идентификации состояния объекта

по результатам зависимых проверок 1.9

Выводы. .

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

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

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

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

2.4. Идентификация состояния объекта, представляемого
графом типа диаграммы Хассе.
Выводы.
3. ПОСТРОЕНИЕ АЛГОРИТМОВ НЕПОЛНОЙ ИДЕНТИШШЩ
СОСТОЯНИЯ ОБЪЕКТА. .
3.1. Уровневый алгоритм пороговой классификации
состояний. 7
3.2. Многопороговая бинарная классификация состояний 7
3.3. Приближенный алгоритм многолороговой
бинарной классификации. ,
2.
ИССЛЕДОВАНИЕ ПРИМЕНЕНИЯ МЕТОДА ВЕТВЕЙ И ГРАНИЦ И
МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ЗАДАЧАХ
ИДШИФЙКАШ СОСТОЯНИЯ ОБЪЕКТА
4.1. Алгоритм ветвей и границ
4.2. Алгоритм динамического программирования
Выводы
ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ РАЗРАБОТАННЫХ
АЛГОРИТМОВ ИДЕНТИФИКАЦИИ
5.1. Диагностирование аппаратуры системы
автоматического управления при кратных
отказах
5.2. Построение системы контроля знаний
5.3. Диагностирование объекта с аппаратурной
избыточностью
Выводы 1М
ЗАКЛЮЧЕНИЕ 1Ъ
ЛИТЕРАТУРА


Хотя алгоритмы ветвей и границ обычно являются более эффективными, чем полный перебор, все же их требования в вычислительных ресурсах растут как экспоненты или полиномы высокой степени от размера задачи. При использовании МВГ можно специально сократить объем используемой памяти при условии, что конечный результат не обязательно должен быть точным. Крайним случаем такого подхода является полный отказ от возвращений; для этого нужно просто продвигаться по ветви вглубь в направлении наименьшей нижней оценки вплоть до получения после »V шагов полного решения [] . Такая процедура называется МВГ «без возвратов". Она требует вычисления нижних оценок для 0( к. Поскольку размеры множеств вершин заранее ограничены, то лишняя информация просто отбрасывается. Однако обязательно хранится наименьшая нижняя оценка, связанная с отброшенными вершинами. Это позволяет получить нижнюю оценку решения в момент завершения. Такая нижняя оценка совместно с верхней оценкой, вычисленной для лучшего полного решения, используется для обеспечения точности решения. Другим ограничивающим фактором может стать время вычислений. Если в ситуации, когда превышается отведенное время счета, мы тлеем полное решение, то оно совместно о наименьшей нижней оценкой для вершин из активного множества определяет границы точности нашего решения. К приближенным алгоритмам относятся такие эвристические алгоритмы. Здесь иногда можно найти оценки характеристик для наихудшего случая, но дальнейшее увеличение объема вычислений не приводит, вообще говоря, к улучшению или к получению оптимального решения. Однако, эвристические процедуры при всей своей произвольности и слабости могут быть с успехом использованы в МВГ как средство получения начальных решений и верхних оценок. Этот метод называют поиском в локальной окретсности, естественным отбором, эвристическим программированием, локальным поиском и поиском в окрестности 1ЪЧ9ЦЪ 9 . Идея таких алгоритмов состоит в обследовании некоторой окрестности данного решения и в восприятии всех улучшений по мере их отыскания. Данный процесс продолжается до тех пор, пока все возможности по улучшению решения в данной окрестности не окажутся исчерпанными. В работе [. Для приближенного решения задачи идентификации можно использовать МВГ с ограниченными возвратами. Дцея МВТ при построении дерева решений заключается в следующем. Если для каждой ветви дерева ветвлений можно определить нижние границы значений критерия, то нужно развивать лишь ту ветвь, которая имеет на каждом шаге лучшее (в данном случае минимальное) зпачение оценки-прогноза. Так как реальные значения целевой функции обычно выше найденных нижних границ, то на каждом шаге ветвления дальнейший прогноз развиваемой ветви может оказаться хуже аналогичного прогноза для других, ранее отброшенных вариантов. В этом случае следует возвратиться к ним, т. Решение задачи идентификации на основе ЮГ было описано в [] , где процедура определения нижних границ значений целевой функции следовала из теории вопросников [б. Основным результатом ТВ является формулировка и доказательство системы правил, позволяющих уменьшить цену обхода вопросника. Пусть имеется некоторый вопросник, позволяющий идентифицировать М состояний ОД. Тогда, отвлекаясь от физического смысла процесса, описываемого вопросником, можно пытаться уменьшить цену его обхода. Так, если возможно, например, перераспределение цен вопросов или весов их так, чтобы вопрос с более высоким весом имел бы более низкую цену и наоборот, то цена обхода вопросника уменьшится. Последовательно применяя другие правила преобразования, получим вопросник, цену обхода которого уже нельзя уменьшить никакими перестановками. Это и йудет оптимальный, как правило, нереализуемый вопросник. Значение средней цены обхода такого вопросника и предлагается использовать в качестве значений оценок при построении программ идентификации МВГ. В терминах ТВ программы идентификации называются оптимальными реализуемыми вопросниками. Строятся они следующим образом. Пусть решено первым применять вопрос .