Метод базирующийся на использовании критериев предпочтения

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

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

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

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

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

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

Выбрав любую проверку из множества {p_j} и выполнив ее, можно в зависимости от ее результата, который должен быть дуальным независимо от физической природы измеряемых при выполнении проверки показателей, можно разделить все множество возможных состояний, в которых может находиться объект, на два подмножества: S_j0 и S_j1 одно из которых соответствует нулевому результату j-ой проверки, другое – единичному. Поскольку порядок выполнения следующих проверок для идентификации действительного состояния объекта неизвестен, то вычислить среднюю стоимость определения любого из возможных состояний в каждом из подмножеств невозможно. Однако можно определить нижнюю границу этой стоимости

lim(p_j,S)=C_j +lim(S_j0)+lim(S_j1) (3.4)

Значения нижней границы стоимости для любой последовательности проверок определяются аналогичными выражениями, например, для последовательности проверок p_j, p_f, p_g нижняя граница стоимости будет

lim(p_j,p_f,p_g,S)=C_j +lim(p_f,S_j0)+lim(p_g,S_j1) (3.5)

Общий алгоритм поиска оптимального теста состоит в следующем.

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

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

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

Рассмотрим применение этого метода на примере.

Пусть диагностируемый объект состоит из четырех элементов. Вероятности отказов каждого из элементов, подсчитанные методами теории надежности, составляют: q₁=0.05; q₂=0.07; q₃=0.03; q₄=0.10. Максимальная кратность диагностируемых неисправностей равна двум. Исходное множество элементарных проверок содержит 12 проверок, каждая из которых характеризуется стоимостью, определяемой в относительных единицах, согласно (3.2).

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

Всего должно быть M=n+1+ диагностируемых состояний (все состояния с одной и двумя неисправностями плюс одно исправное состояние)

M=4+1+ =5+4×3/2=11

Их двоичные векторы: 1111, 0111, 1011, 1101, 1110, 0011, 0101, 0110, 1001, 1010, 1100. Вероятности этих состояний будем подсчитывать как вероятности сложных событий, каждое из которых представляет совокупность четырех независимых событий:

P_si=p₁×p₂×p₃×p₄,

где p₁, p₂, p₃, p₄ – вероятность нахождения каждого из 4-х элементов объекта в исправном или неисправном состоянии, причем вероятности исправных состояний элементов равны p_i=1-q_i, где q_i – заданные вероятности отказов элементов.

Подсчитанные таким образом вероятности состояний объекта сведены в табл. 3.1.

Таблица 3.1

Двоичные векторы состояний и их вероятности

В таблице 3.2. представлена исходная таблица состояний объекта, при составлении которой все состояния расположены и пронумерованы в порядке убывания их вероятностей, а проверки расположены и пронумерованы в порядке возрастания их стоимости.

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

1) для уменьшения средней стоимости тестирования необходимо состояния с наибольшей вероятностью идентифицировать самыми короткими тестами, а с малой – длинными;

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

Таблица 3.2.

Таблица состояний объекта

Таблица 3.3.

Исходная таблица состояний

Для уменьшения средней длины теста в соответствии с принципом Шеннона необходимо выбирать проверки в такой очередности, чтобы каждая из них разделяла возможные состояния объекта на две группы с примерно равной суммарной вероятностью. Исходя из этого первая проверка должна делить все возможные состояния объекта на две группы с примерно одинаковой вероятностью. В нашем случае вероятность исправного состояния (S₁) существенно больше суммы вероятностей всех остальных состояний. Следовательно желательно, чтобы первая проверка отделяла состояние S₁ от всех остальных. Поскольку при состоянии S₁ все проверки дают 1, наилучшей будет проверка, содержащая максимальное количество нулей, особенно в верхней части таблицы, где расположены наиболее вероятные состояния. Такой проверкой является p₄. Кроме состояния S₁ она дает 1 только для двух состояний S₉ и S₁₁ с малыми вероятностями (0.0026 и 0.0012). Да и стоимость ее не высока (31). Таким образом, не производя расчета нижних границ стоимости тестов для всех остальных проверок, можно с уверенностью считать, что первой проверкой оптимального теста должна быть проверка p₄. Она разделяет все возможные состояния объекта на две группы. Единице соответствует группа состояний (S₁, S₉, S₁₁) с суммарной вероятностью 0.7751. Нулю соответствуют все остальные состояния с суммарной вероятностью 0.2236. Рассчитаем нижнюю границу стоимости теста для данного случая. В соответствии с (3.4)

lim(p₄,S)=C₄ +lim(S₄₀)+lim(S₄₁)=31×0.9987+lim(S₄₀)+lim(S₄₁).

Рис. 3.1. Дерево решений после первого шага

Рассмотрим возможные варианты дальнейшего решения. Оптимальное разделения группы состояний (S₁, S₉, S₁₁) состоит в отделении состояния S₁ от двух остальных. Для этого следующая проверка должна давать нули при состояниях S₉ и S₁₁. Таких проверок три: p₅, p₆ и p₇. Из них минимальная стоимость у проверки p₅. Ее и выбираем. Далее остается лишь разделить состояния S₉ и S₁₁, для чего пригодны проверки p₁, p₂, p₉, p₁₀, p₁₁ и p₁₂. Из них, очевидно, надо выбрать проверку p₁, как обладающую минимальной стоимостью. Следовательно:

lim(S₄₁)=C₅(p₁+p₉+p₁₁)+C₁(p₉+p₁₁)=35×0.7751+22×0.0038=27.21

Вторую подгруппу также необходимо разделить на подгруппы с примерно одинаковыми суммарными вероятностями (т.е. вероятность каждой подгруппы должна быть близка к 0.2236/2=0.1118). Здесь возможны два варианта:

1) первая подгруппа образована только одним состоянием S₂ ( =0.0857), а вторая – всеми остальными (åp=0.1379);

2) первая подгруппа состоит из двух состояний S₂ и S₃ с суммарной вероятностью 0.1439, а вторая – из всех остальных с суммарной вероятностью 0.0797. Теперь посмотрим на сколько это реализуемо с помощью имеющихся проверок. Рассмотрение таблицы состояний показывает, что ни тот, ни другой вариант не реализуемы. Наиболее близкие к первому варианту дают проверки p₃, p₇, p₈, p₁₀, p₁₁ и p₁₂, а ко второму – p₁, p₂, p₅, p₆, p₉. Проанализируем их.

Проверка p₃ разделяет вторую группу на следующие подгруппы (S₂, S₅, S₈) åp=0.1126, (S₃, S₄, S₆, S₇, S₁₀) åp=0.1110.

Проверка p₇ разделяет вторую группу на подгруппы: (S₂, S₆, S₇, S₈, S₁₀) åp=0.1012 и (S₃, S₄, S₅) åp=0.1224.

Проверка p₈ делит на подгруппы: (S₂, S₄, S₆, S₁₀) åp=0.1342 и (S₃, S₅, S₇, S₈) åp=0.0894.

Проверка p₁₀ делит на группы: (S₂, S₄, S₅, S₆, S₇) åp=0.16 и (S₃, S₈, S₁₀) åp=0.063.

Проверка p₁₁ делит на подгруппы: (S₂, S₄, S₆, S₁₀) åp=0.1342 и (S₃, S₅, S₇, S₈) åp=0.0894.

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

Из рассмотренных вариантов решений наилучшим является решение с выбором в качестве второй проверки p₃. Во-первых, она дает разделение второй группы состояний на подгруппы с практически одинаковой вероятностью (0.1126 и 0.1110), а во-вторых, она имеет минимальную стоимость из всех остальных рассмотренных решений. Приняв это решение, получаем

lim(S₄₀)=C₃(p₂+p₃+p₄+p₅+p₆+p₇+p₈+p₁₀)+lim(S₄₃₀)+lim(S₄₃₁).

В итоге дерево решений после второго шага будет иметь вид

Рис. 3.2. Дерево решений после второго шага.

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

Перейдем к рассмотрения третьего шага для правой группы. После второго шага мы получили две подгруппы: (S₃, S₄, S₆, S₇, S₁₀) åp=0.111 и (S₂, S₅, S₈) åp=0.1126. Третий шаг должен поделить каждую из них на две части с примерно равными вероятностями (примерно равными 0.055).

Для левой подгруппы желательно отделить S₃ (p₃=0.058) от всех остальных, причем нельзя использовать проверки p₄ и p₃, т.к. они уже использованы в этой ветви дерева (проверки p₅ и p₁ при условном алгоритме использовать можно, т.к. они использовались в других ветвях дерева, при безусловном алгоритме и их использовать было бы нельзя, но мы ориентируемся на условный алгоритм как наиболее экономичный). Такая проверка только одна p₉.

С ней могут конкурировать лишь более дешевые проверки, при которых к S₃ добавляются маловероятные состояния. Сюда можно отнести проверки p₁, при которой к S₃ добавляются состояния S₆ и S₁₀ и p₂, при которой добавляется лишь одно состояние S₇. Поэтому следует рассмотреть два варианта: p₉ и p₂.

При выборе проверки p₉ образуются подгруппы (S₃) p₃=0.058 и (S₄, S₆, S₇, S₁₀) åp=0.053. Причем ее стоимость 50.

При выборе проверки p₂ образуются подгруппы (S₃, S₇) åp=0.0625 и (S₄, S₆, S₁₀) åp=0.0485, причем ее стоимость 25, т.е. вдвое меньше.

Совершенно очевидно, что более выгодным является второй вариант.

Теперь обратимся к правой группе. Здесь надо искать проверку, отделяющую S₂ от состояний S₅ и S₈.

Это обеспечивают проверки p₆, p₈ и p₁₁. Выбираем из них самую дешевую p₆. В результате от правой группы состояний отделяется состояние S₂ с вероятностью p₂=0.0857 и остается подгруппа (S₅, S₈) с суммарной вероятностью åp=0.0269.

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

Рис. 3.3. Дерево решений (правая ветвь) после третьего шага.

Итак после третьего шага у нас остались три висячих вершины (недостроенных решений): (S₃, S₇) и (S₅, S₆) и отделить S₄ от (S₆, S₁₀), причем для достройки левой ветви дерева (рис. 3.3) нельзя использовать проверки p₄, p₃ и p₂, а для достройки правой ветви – p₄, p₃ и p₆.

Для разделения пары (S₃, S₇) наиболее дешевой является проверка p₁.

Для разделения пары (S₅, S₈) – тоже проверка p₁ (она используется в другой ветви, поэтому ее можно использовать и здесь).

И, наконец, для отделения S₄ от (S₆, S₁₀) тоже пригодна проверка p₁.

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

И, наконец, на пятом шаге остается лишь разделить пару состояний (S₆, S₁₀), причем нельзя использовать проверки p₄, p₃, p₂ и p₁. Самой дешевой из возможных является проверка p₅.

В итоге получается полное дерево решений, отображенное на рис. 3.4.

Рис. 3.4. Полное дерево решений условных тестов.

Как видно из рис. 3.4 самый короткий тест, состоящий всего из двух проверок, соответствует самому вероятному состоянию (S₁ – исправному состоянию), а самый длинный, состоящий из пяти проверок, состояниям S₁₀ и S₆ с суммарной вероятностью 0.0079.

Можно подсчитать среднюю длину теста:

И, наконец, можно определить среднюю стоимость тестирования объекта

p₁(Cp₄+Cp₅)+(p₉+p₁₁)(Cp₄+Cp₅+Cp₁)+

+(Cp₄+Cp₃+Cp₂+Cp₁)(p₃+p₇+p₄)+Cp₄+Cp₃+Cp₂+Cp₁+Cp₅)

(p₆+p₁₀)+(Cp₄+Cp₃+Cp₆)p₂+(Cp₄+Cp₃+Cp₆+Cp₁)(p₅+p₈)=0.7751×

(31+35)+0.0038×(31+35+22)+(31+27+25+22)×0.0625+(31+27+25+22)×0.0406+(31+27+25+22+35)×0.0079+(31+27+38)×0.0857+

(31+27+38+22)×0.0269=51.157+0.3344+6.5625+4.263+1.106+8.227+3.1742=74.824

Сопоставим эту стоимость со стоимостями всех возможных тестовых последовательностей

С(p₄+p₅)=31+35=66

С(p₄+p₅+p₁)=31+35+22=88

С(p₄+p₃+p₆)=31+27+38=96

С(p₄+p₃+p₂+p₁)=31+27+25+22=105

С(p₄+p₃+p₂+p₁+p₅)=105+35=140

С(p₄+p₃+p₆+p₁)=31+27+38+22=118

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

Опознавателями состояний являются последовательность и результаты произведенных проверок, которые легко определяются из дерева решений:

S₁®p₄(1)-p₅(1); S₇®p₄(0)-p₃(1)-p₂(1)-p₁(0);

S₂®p₄(0)-p₃(0)-p₆(0); S₈®p₄(0)-p₃(0)-p₆(1)-p₁(0);

S₃®p₄(0)-p₃(1)-p₂(1)-p₁(1); S₉®p₄(1)-p₅(0)-p₁(1);

S₄®p₄(0)-p₃(1)-p₂(0)-p₁(0); S₁₀®p₄(0)-p₃(1)-p₂(0)-p₁(1)-p₅(1);

S₅®p₄(0)-p₃(0)-p₆(1)-p₁(1); S₁₁®p₄(1)-p₅(0)-p₁(0).

S₆®p₄(0)-p₃(1)-p₂(0)-p₅(0);

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