В работе [1] рассматривается еще один возможный способ организация словаря неисправностей, в котором для каждого технического состояния сохраняется часть полной реакции устройства в этом состоянии на диагностический тест, выделенная с помощью некоторого шаблона, который именуется маской.
Назовем точкой проверки пару номер тестового воздействия:номер выхода. Тогда маской $$h$$ назовем любую совокупность точек проверки.
Пусть имеется некоторое разбиение множества $$S$$ и пусть $$S_j$$ - элементы этого разбиения. Поставим в соответствие каждому подмножеству $$S_j$$ некоторую маску $$h_j$$. Множество всех $$h_j$$ обозначим через $$H$$. Построим по списку полных реакций (СПР) и множеству масок $$H$$ таблицу следующим образом. Каждая строка таблицы соответствует техническому состоянию. Содержимое строки таблицы, соответствующей состоянию $$s_i\in S_j$$, будут составлять значения точек проверки из $$h_j$$, взятые из строки СПР, соответствующей $$s_i$$, в порядке их следования в СПР. Построенную таким образом таблицу будем называть (по аналогии с [1]) словарем полной реакции, построенный по маскам из $$H$$, и обозначать $$СПР_H$$. Маску $$h_j$$ будем называть индивидуальной маской для каждого состояния из $$S_j$$, а множество $$H$$ - множеством индивидуальных масок.
Например, построим СПР для СПР из табл. 27.5, если $$S_1=\{s_0\}$$, $$S_2=\{s_1\}$$, $$S_3=\{s_2\}$$, $$S_4=\{s_3,s_4\}$$, $$S_5=\{s_5\}$$, $$S_6=\{s_6\}$$, $$S_7=\{s_7\}$$, $$S_8=\{s_8\}$$, а элементы множества $$H$$: $$h_1=\{1:1,1:2,2:1\}$$, $$h_2=\{1:2,2:1\}$$, $$h_3=\{1:1,3:1\}$$, $$h_4=\{1:2,3:1,3:2\}$$, $$h_5=\{3:1,3:2,4:1\}$$, $$h_6=\{4:1\}$$, $$h_7=\{3:1,3:2\}$$, $$h_8=\{1:1,3:1\}$$. Элементы СПР, выбираемые с помощью масок из $$H$$, выделены прямоугольниками в СПР в табл. 29.1, а сам словарь неисправностей $$СПР_H$$ приведен в табл. 29.2.
| $$ \pi_{27} $$ | $$ \pi_1$$ | $$ \pi_3$$ | $$ \pi_29$$ | |
|---|---|---|---|---|
| $$s_0$$ | 11 | 00 | 11 | 10 |
| $$s_1$$ | 10 | 10 | 11 | 10 |
| $$s_2$$ | 00 | 00 | 11 | 10 |
| $$s_3$$ | 00 | 00 | 00 | 10 |
| $$s_4$$ | 01 | 00 | 00 | 10 |
| $$s_5$$ | 01 | 00 | 01 | 10 |
| $$s_6$$ | 01 | 00 | 01 | 00 |
| $$s_7$$ | 10 | 00 | 10 | 10 |
| $$s_8$$ | 11 | 11 | 11 | 10 |
| $$s_0$$ | 110 |
|---|---|
| $$s_1$$ | 01 |
| $$s_2$$ | 01 |
| $$s_3$$ | 000 |
| $$s_4$$ | 100 |
| $$s_5$$ | 011 |
| $$s_6$$ | 0 |
| $$s_7$$ | 010 |
| $$s_8$$ | 11 |
Заметим, что представление диагностической информации в виде $$СПР_H$$ предполагает наличие полной таблицы СПР, а также множества масок $$H$$ и указания соответствия между $$s_i$$ и $$h_j$$.
Содержательно выделение информации с помощью маски можно пояснить следующим образом. Полную СПР будем интерпретировать как прямоугольную таблицу с пронумерованными строками и столбцами. В каждой клетке СПР, находящейся на пересечении $$i$$-ой строки и $$j$$-го столбца, находится двоичная последовательность длины $$k$$ , где $$k$$ - число выходов диагностируемого ЦУ.Эта последовательность есть реакция ЦУ в состоянии$$ s_i$$ на $$j$$-ый тестовый набор. Тогда маска $$h_i$$ соответствует "окошечкам" в сплошном битовом шаблоне $$i$$-ой строки, которые следует "прорезать" , чтобы увидеть выделяемые этой маской биты реакции ЦУ на диагностический тест.
В процессе диагностирования предполагается получение выходной реакции объекта диагностирования на диагностический тест, после чего на эту реакцию накладываются поочередно маски $$h_j$$, а результат наложения сравнивается со значениями в $$СПР_H$$ для всех $$s_i\in S_j$$. Те из $$s_i$$, для которых произошло совпадение, заносятся в СПН.
Пусть в рассматриваемом примере объект находится в техническом состоянии $$s_6$$. В этом случае выходная реакция объекта - $$01 00 01 00$$. Ни одна из масок, кроме $$h_6$$, не приведет к занесению в СПН ни одного состояния. После наложения маски $$h_6$$ будет получена последовательность 0 и в СПН будет внесено состояние $$s_6$$. Результат диагностирования объекта есть СПН, равный $$\{s_6\}$$.
Очевидно, что если СПР обладает свойством различения всех неисправностей, то найдется множество индивидуальных масок таких, что $$СПР_H$$ будет обладать свойством различения всех неисправностей.
Если множество $$H$$ содержит только одну маску для всех технических состояний из $$S$$, то такую маску называют единой (общей) маской.
Рассмотрим, например, диагностический тест для схемы $$С17$$ и множество $$H$$, содержащее одну маску$$ h=\{1:2,2:1,3:1,3:2,,4:1\}$$. В этом случае $$СПР_H$$ будет выглядеть так, как показано в табл. 29.3.
| $$s_0$$ | 10111 |
|---|---|
| $$s_1$$ | 01111 |
| $$s_2$$ | 00111 |
| $$s_3$$ | 00001 |
| $$s_4$$ | 10001 |
| $$s_5$$ | 10011 |
| $$s_6$$ | 10010 |
| $$s_7$$ | 00101 |
| $$s_8$$ | 11111 |
Использование единой маски имеет некоторые преимущества в процессе диагностирования объекта. Действительно, если используется единая маска , то при получении выходной реакции устройства можно сразу отфильтровывать с использованием маски $$h$$ последовательность выходных значений и не сохранять при этом всю выходную реакцию. Более того, после получения очередного "отфильтрованного" с помощью маски выходного значения можно сразу формировать и вносить изменения в СПН. Сначала в СПН вносятся все технические состояния объекта, но при получении очередного бита информации происходит удаление из СПН состояний, не соответствующих значению данного бита.
Что касается объема сокращенного с помощью масок словаря неисправностей, то в случае единой маски его величина равна $$|S|M$$, где $$M$$ - количество точек проверок, составляющих маску. В случае сокращения ДИ с помощью множества индивидуальных масок объем словаря составит
$$ (|S|+|H| -2)b' + M'\cdot(log_2{m} + log_2{|\tau|})+|S|log_2|H|+M''$$где $$b'$$ - количество бит, необходимых для отделения данных по одному техническому состоянию от остальной информации, $$M'$$ - суммарное количество точек проверки по всем маскам в множестве $$H$$, $$M''$$ - суммарное количество точек проверки по всем маскам, с учетом их кратности.
Заметим, что с помощью масок можно проводить сокращение ДИ, представленной также и в виде ТН. В этом случае элементом маски $$h$$ выступает не точка проверки, а номер тестового вектора, информация об обнаружении неисправности которого заносится в сокращенную таблицу. Таблицу, построенную в результате сокращения ТН с помощью набора масок $$H$$, будем называть таблицей неисправностей, построенной по маскам из $$H$$,и обозначать через $$TH_H$$.
В связи со сказанным выше, подход к сокращению ДИ при помощи масок приводит к необходимости исследования задач поиска различных масок. Остановимся на этом немного подробнее.
Так, в работе [1] формулируются три задачи, касающиеся сокращения ДИ с помощью масок:
Сформулированные задачи принято называть задачами минимизации ДИ при помощи масок [2,3]. В работах [3,4,5,6] рассматриваются методы точного аналитического решения первой, а в работе [6] еще и второй из сформулированных задач.
В ряде случаев для решения задач минимизации применимы методы, предложенные для оптимизации безусловных алгоритмов диагностирования [7].
В работе [3] сформулирована еще одна задача - задача оптимизации: для множества $$S$$ определить разбиение $$S_1,\ldots,S_l$$ и набор масок $$H=\{h_1,\ldots,h_l\}$$, чтобы объем $$СПР_H$$ не превышал заданной величины $$Z$$ и изменение разрешающей способности диагностирования с помощью $$СПР_H$$ по отношению к разрешающей способности диагностирования с использованием СПР было минимальным. Здесь же рассматриваются варианты точного аналитического решения этой задачи.
В работах [3,8] отмечается, что предложенные варианты точных решений задач поиска масок связаны с частичным перебором, и требуют большого объема вычислений. При значительном увеличении количества неисправных модификаций, характерного для современных устройств, а также при увеличении длины диагностического теста такие варианты решений становятся неприемлемыми из-за больших временных затрат. Выходом из сложившейся ситуации является замена точного решения приближенным. В тех же работах, а также в работе [2], предлагаются методы приближенного решения задачи минимизации и оптимизации объема $$СПР_H$$, когда $$H$$ - множество индивидуальных масок.
Каждый из упомянутых выше
Имеющийся опыт исследования многих оптимизационных прикладных задач показывает, что для их решения эффективным математическим аппаратом являются генетические алгоритмы (ГА). В лекции 25 была показана полезность ГА и их приемлемость с точки зрения временных затрат применительно к решению задач синтеза тестов. Далее мы убедимся, что и для различных модификаций задач поиска масок ГА также дают прекрасные результаты.
В дальнейшем изложении предполагается, что читатель знаком с содержанием лекции 25, где были определены основные понятия и термины,используемые в
Кратко напомним необходимые нам сведения о ПГА, содержащем следующие этапы:
На первом этапе создаются особи начальной популяции. Создание начальной популяции осуществляется, как правило, произвольным образом, в большинстве случаев особи формируются из случайных данных. Это позволяет осуществить разброс по пространству поиска, т. е. в данном случае этап создания начальной популяции подобен методу случайного поиска.
На втором этапе отбора для каждой особи определяется ее приспособленность, оцениваемая с помощью фитнес-функции. Напомним, что фитнес-функция есть мера качества решения. Затем с помощью оператора селекции осуществляется отбор. Отбор кандидатов (особей) для участия в процессе репродукции производится по принципу: чем выше приспособленность особи, тем выше вероятность ее участия в процессе скрещивания. Этап отбора представляет собой аналог дарвиновского выживания сильнейших применительно к особям.
Существуют различные варианты методов селекции, которые различаются как алгоритмическими характеристиками (вычислительная сложность, требования к памяти), так и такими специфическими для ГА характеристиками, как давление отбора, уменьшение разнообразия, наличием элитизма и т. д. Давление отбора - это отношение вероятности отбора лучшей особи к средней вероятности отбора всех особей. Явление уменьшения разнообразия вследствие применения отбора заключается в том, что оператор селекции исключает из дальнейшего использования особи, которые не были отобраны. Принцип элитизма заключается в сохранении некоторого количества наиболее приспособленных особей для их безусловного участия в процессе репродукции.
На третьем этапе осуществляется скрещивание отобранных на предыдущем этапе особей с помощью оператора скрещивания. Обычно данный оператор из двух особей (родительских) производит двух новых потомков. Создание новых особей осуществляется путем обмена соответствующих генов родительских особей. Полученные особи формируют новую популяцию или, говоря иначе, новое поколение.
На четвертом этапе осуществляется
В качестве условия окончания процесса эволюции может выступать факт наличия в популяции особи, чье значение функции приспособленности удовлетворяет некоторым пороговым значениям. В этом случае такая особь принимается в качестве решения. Альтернативным вариантом условия окончания может быть заранее определенное предельное число этапов эволюции (длина жизненного цикла популяции). При такой постановке в качестве решения принимается особь из последнего поколения с наилучшей приспособленностью.
Применение ГА требует подходящего выбора способа кодирования решения, представленного в виде
Остановимся на определении структуры
Отметим, что большая часть практически работающих ГА базируется на предположении, что
Хромосому, представляющую маску $$h$$, будем представлять в виде битовой последовательности $$\eta(h)$$ длины $$m|\tau|$$:
$$ \eta(h)=\eta_1(h)\eta_2(h)\ldots\eta_{m|\tau|}(h) $$Здесь $$m$$ - количество выходов устройства, $$\tau$$ - применяемый тест.
Для каждой точки проверки $$i$$:$$j$$ из маски $$h$$ значение $$\eta_s(h)$$ в (4.1), где $$s=m(i-1)+j$$, полагается равным 1. Все остальные разряды в $$\eta(h)$$ полагаются равными нулю.
Объемом маски будем считать величину
$$ |h|\stackrel{def}{=}\sum\limits_{i=1}^{m|\tau|}{\eta_i(h)}$$Назовем маску $$h$$ полной, если $$\eta_i(h)=1$$ для всех $$i=1,\ldots,m|\tau|$$. Введем в рассмотрение величину
$$V(h)=\cfrac{|h|}{m|\tau|}$$которая равна доле объема $$h$$ от объема полной маски.
Таким образом, среди всех битовых строк длины $$m|\tau|$$ ПГА будет отыскивать такую, которая обеспечивает экстремум целевой функции и о которой будет сказано ниже. В теории ГА эту функцию называют фитнес-функцией.
Маски порождают используемую ДИ и, тем самым, соответствующее множество СПН. Для оценки эффективности диагностирования с использованием порожденной ДИ будем применять значение ожидаемой глубины диагностирования
$$\rho_1=\cfrac{1}{|s|}\sum\limits_s{|S_j|^2},$$где $$S$$- множество состояний ЦУ, $$S_j$$- список подозреваемых неисправностей. Обозначим через $$\rho_2(h)$$ значение ожидаемой глубины диагностирования с использованием ДИ, порожденной маской $$h$$.
Теперь обратимся к задаче минимизации ДИ. Для ее решения с применением ПГА будем использовать следующую фитнес-функцию:
$$ d_1(\eta(h))=C\cdot(\rho_2(h)-1)+V(h)$$где $$C$$ - достаточно большая константа.
Поясним содержательный смысл функции (29.3). Ее значение естественно трактовать как оценку трудоемкости поиска неисправности в ЦУ, которая очевидно будет складываться из величины, пропорциональной средней длине СПН (первое слагаемое) и величины, пропорциональной размеру пространства поиска для определения неисправности, присутствующей в тестируемом ДУ. Множитель $$C$$ в (29.3) введен для того, чтобы обеспечить заданную глубину диагностирования $$\mu_0$$. Исходя из содержательного смысла фитнес-функции (29.3), искомым решением рассматриваемой задачи будет такая маска, которая доставит минимум упомянутой функции.
Соображения, аналогичные только что приведенным, применительно к задаче оптимизации ДИ приводит к следующей фитнес-функции:
$$ d_2(\eta(h))=C_1\cdot(\rho_2(h)-1)+C_2\cdot|V(h)-Z|$$где $$C_1$$ и $$C_2$$ - достаточно большие константы.
Исходя из содержательного смысла функции (29.4) ясно, что решением задачи оптимизации ДИ будет такая маска, которая доставит минимум этой функции.
Можно упростить вид последней фитнес-функции если ограничить пространство поиска маски только лишь масками заданного объема $$Z$$. Тогда в качестве фитнес-функции можно принять функцию
$$d_3(\eta(h))=\rho_2(h)$$Упрощение фитнес-функции влечет за собой изменение в операторах кроссовера и
Содержательный смысл минимизации функции $$d_3$$ очевиден - при постоянном объеме маски проводится минимизация ожидаемой глубины диагностирования.
Решение задачи минимизации ДИ с помощью индивидуальных масок можно осуществить двумя способами. Первый из них заключается в разработке ГА для поиска индивидуальной маски одного конкретного технического состояния ДУ, второй - в разработке ГА для одномоментного поиска множества индивидуальных масок всей рассматриваемой совокупности технических состояний ДУ.
Для обоих способов решения задачи структура
где $$\eta(h_i)$$ определены соотношением (29.1), $$F$$- множество рассматриваемых неисправностей.
Очевидно, что только второй способ организации
Рассмотрим сначала первый способ решения задачи минимизации ДИ.
Итак, при данном способе один запуск
Введем в рассмотрение функцию $$\rho_6(i,h)$$, возвращающую число технических состояний, неотличимых от состояния $$s_i$$ при использовании ДИ, отфильтрованной с помощью маски $$h$$.
Теперь можем определить фитнес-функцию для
Как видно из сравнения (29.3) и (29.7), функция $$d_4$$ отличается от функции $$d_1$$ только применением $$\rho_6(i,h)$$ вместо $$\rho_2(h)$$.
Для второго способа решения задачи минимизации построим ГА, аналогичный тому, что был построен для поиска единой маски. Обобщим этот алгоритм для использования набора масок $$H$$ вместо одной единой маски $$h$$.
Сначала введем в рассмотрение, по аналогии с (29.2), величину
$$V(H)=\cfrac{1}{m|\tau|(|F|+1)}\sum\limits_{h\in H}{|h|}$$Данная величина определяет долю объема ДИ, отфильтровываемой с помощью набора масок $$H$$ из общего объема ДИ.
Обозначим $$\rho_2(H)$$ значение ожидаемой глубины диагностирования при использовании ДИ, порожденной набором индивидуальных масок $$H$$.
В таком случае, по аналогии с (29.3), используя битовые последовательности $$H(H)$$ вместо $$\eta(h)$$, можно определить фитнес-функцию для решения с применением ПГА задачи минимизации:
$$ d_5(H(H))=C\cdot(\rho_2(H)-1)+V(H)$$Проводя такую же аналогию, что и в предыдущем случае, но применительно к задаче оптимизации, приходим к следующей фитнес-функции:
$$ d_6(H(H))=C_1\cdot(\rho_2(H)-1)+C_2\cdot|V(H)-Z|$$И так же, как нами было произведено упрощение функции до функции , можно преобразовать функцию при условии ограничения пространства поиска особями заданного объема. Фитнес-функция в таком случае примет вид:
$$d_7(H(H))= \rho_2(H)$$Из построения функций $$d_4$$, $$d_5$$, $$d_6$$ и $$d_7$$ ясно, что решением исследуемых задач будут те
Отметим, что во всех численных экспериментах, проведенных для оценки эффективности сконструированных ПГА, начальная популяция формировалась из особей, генерируемых с использованием датчиков случайных величин. Что касается размера популяции, то он подбирался опытным путем с целью ускорения сходимости к искомому решению.
На втором этапе ПГА, связанном с подбором (селекцией) особей для скрещивания, были опробованы различные методы: турнирный отбор, отбор отсечением, пропорциональный отбор, а также отбор линейным и экспоненциальным ранжированием, описанные, например, в [9].
На третьем этапе, связанном с репродукцией особей, опробовались операторы одноточечного, многоточечного, однородного и булева кроссовера.
Что касается
На пятом этапе ПГА для формирования следующего поколения из особей текущего поколения, а также полученных после скрещивания потомков, был использован метод элитного отбора.
Наконец, в качестве условий окончания процесса работы сконструированных простых ГА использовался критерий достижения заданного предельного числа этапов эволюции (длины жизненного цикла популяции).
Материал, представленный выше, помимо упомянутых в этой лекции работах, базируется также на статье [10].
Маска для диагностической информации - шаблон, накладываемый на строки полной диагностической информации, позволяющий отфильтровывать из реакций проверяемого ЦУ на тест только заранее определенные в ДИ позиции .
Простой генетический алгоритм поиска маски- алгоритм, оперирующий с совокупностью различных шаблонов масок, представленных в виде хромосом. Поиск маски основан на применении к начальному множеству (популяции) шаблонов операторов кроссовера,
В лекции описан подход к сокращению ДИ с использованием масок. Сформулированы различные модификации задач поиска масок и описан простой
В работе [1] рассматривается еще один возможный способ организация словаря неисправностей, в котором для каждого технического состояния сохраняется часть полной реакции устройства в этом состоянии на диагностический тест, выделенная с помощью некоторого шаблона, который именуется маской.
Назовем точкой проверки пару номер тестового воздействия:номер выхода. Тогда маской $$h$$ назовем любую совокупность точек проверки.
Пусть имеется некоторое разбиение множества $$S$$ и пусть $$S_j$$ - элементы этого разбиения. Поставим в соответствие каждому подмножеству $$S_j$$ некоторую маску $$h_j$$. Множество всех $$h_j$$ обозначим через $$H$$. Построим по списку полных реакций (СПР) и множеству масок $$H$$ таблицу следующим образом. Каждая строка таблицы соответствует техническому состоянию. Содержимое строки таблицы, соответствующей состоянию $$s_i\in S_j$$, будут составлять значения точек проверки из $$h_j$$, взятые из строки СПР, соответствующей $$s_i$$, в порядке их следования в СПР. Построенную таким образом таблицу будем называть (по аналогии с [1]) словарем полной реакции, построенный по маскам из $$H$$, и обозначать $$СПР_H$$. Маску $$h_j$$ будем называть индивидуальной маской для каждого состояния из $$S_j$$, а множество $$H$$ - множеством индивидуальных масок.
Например, построим СПР для СПР из табл. 27.5, если $$S_1=\{s_0\}$$, $$S_2=\{s_1\}$$, $$S_3=\{s_2\}$$, $$S_4=\{s_3,s_4\}$$, $$S_5=\{s_5\}$$, $$S_6=\{s_6\}$$, $$S_7=\{s_7\}$$, $$S_8=\{s_8\}$$, а элементы множества $$H$$: $$h_1=\{1:1,1:2,2:1\}$$, $$h_2=\{1:2,2:1\}$$, $$h_3=\{1:1,3:1\}$$, $$h_4=\{1:2,3:1,3:2\}$$, $$h_5=\{3:1,3:2,4:1\}$$, $$h_6=\{4:1\}$$, $$h_7=\{3:1,3:2\}$$, $$h_8=\{1:1,3:1\}$$. Элементы СПР, выбираемые с помощью масок из $$H$$, выделены прямоугольниками в СПР в табл. 29.1, а сам словарь неисправностей $$СПР_H$$ приведен в табл. 29.2.
| $$ \pi_{27} $$ | $$ \pi_1$$ | $$ \pi_3$$ | $$ \pi_29$$ | |
|---|---|---|---|---|
| $$s_0$$ | 11 | 00 | 11 | 10 |
| $$s_1$$ | 10 | 10 | 11 | 10 |
| $$s_2$$ | 00 | 00 | 11 | 10 |
| $$s_3$$ | 00 | 00 | 00 | 10 |
| $$s_4$$ | 01 | 00 | 00 | 10 |
| $$s_5$$ | 01 | 00 | 01 | 10 |
| $$s_6$$ | 01 | 00 | 01 | 00 |
| $$s_7$$ | 10 | 00 | 10 | 10 |
| $$s_8$$ | 11 | 11 | 11 | 10 |
| $$s_0$$ | 110 |
|---|---|
| $$s_1$$ | 01 |
| $$s_2$$ | 01 |
| $$s_3$$ | 000 |
| $$s_4$$ | 100 |
| $$s_5$$ | 011 |
| $$s_6$$ | 0 |
| $$s_7$$ | 010 |
| $$s_8$$ | 11 |
Заметим, что представление диагностической информации в виде $$СПР_H$$ предполагает наличие полной таблицы СПР, а также множества масок $$H$$ и указания соответствия между $$s_i$$ и $$h_j$$.
Содержательно выделение информации с помощью маски можно пояснить следующим образом. Полную СПР будем интерпретировать как прямоугольную таблицу с пронумерованными строками и столбцами. В каждой клетке СПР, находящейся на пересечении $$i$$-ой строки и $$j$$-го столбца, находится двоичная последовательность длины $$k$$ , где $$k$$ - число выходов диагностируемого ЦУ.Эта последовательность есть реакция ЦУ в состоянии$$ s_i$$ на $$j$$-ый тестовый набор. Тогда маска $$h_i$$ соответствует "окошечкам" в сплошном битовом шаблоне $$i$$-ой строки, которые следует "прорезать" , чтобы увидеть выделяемые этой маской биты реакции ЦУ на диагностический тест.
В процессе диагностирования предполагается получение выходной реакции объекта диагностирования на диагностический тест, после чего на эту реакцию накладываются поочередно маски $$h_j$$, а результат наложения сравнивается со значениями в $$СПР_H$$ для всех $$s_i\in S_j$$. Те из $$s_i$$, для которых произошло совпадение, заносятся в СПН.
Пусть в рассматриваемом примере объект находится в техническом состоянии $$s_6$$. В этом случае выходная реакция объекта - $$01 00 01 00$$. Ни одна из масок, кроме $$h_6$$, не приведет к занесению в СПН ни одного состояния. После наложения маски $$h_6$$ будет получена последовательность 0 и в СПН будет внесено состояние $$s_6$$. Результат диагностирования объекта есть СПН, равный $$\{s_6\}$$.
Очевидно, что если СПР обладает свойством различения всех неисправностей, то найдется множество индивидуальных масок таких, что $$СПР_H$$ будет обладать свойством различения всех неисправностей.
Если множество $$H$$ содержит только одну маску для всех технических состояний из $$S$$, то такую маску называют единой (общей) маской.
Рассмотрим, например, диагностический тест для схемы $$С17$$ и множество $$H$$, содержащее одну маску$$ h=\{1:2,2:1,3:1,3:2,,4:1\}$$. В этом случае $$СПР_H$$ будет выглядеть так, как показано в табл. 29.3.
| $$s_0$$ | 10111 |
|---|---|
| $$s_1$$ | 01111 |
| $$s_2$$ | 00111 |
| $$s_3$$ | 00001 |
| $$s_4$$ | 10001 |
| $$s_5$$ | 10011 |
| $$s_6$$ | 10010 |
| $$s_7$$ | 00101 |
| $$s_8$$ | 11111 |
Использование единой маски имеет некоторые преимущества в процессе диагностирования объекта. Действительно, если используется единая маска , то при получении выходной реакции устройства можно сразу отфильтровывать с использованием маски $$h$$ последовательность выходных значений и не сохранять при этом всю выходную реакцию. Более того, после получения очередного "отфильтрованного" с помощью маски выходного значения можно сразу формировать и вносить изменения в СПН. Сначала в СПН вносятся все технические состояния объекта, но при получении очередного бита информации происходит удаление из СПН состояний, не соответствующих значению данного бита.
Что касается объема сокращенного с помощью масок словаря неисправностей, то в случае единой маски его величина равна $$|S|M$$, где $$M$$ - количество точек проверок, составляющих маску. В случае сокращения ДИ с помощью множества индивидуальных масок объем словаря составит
$$ (|S|+|H| -2)b' + M'\cdot(log_2{m} + log_2{|\tau|})+|S|log_2|H|+M''$$где $$b'$$ - количество бит, необходимых для отделения данных по одному техническому состоянию от остальной информации, $$M'$$ - суммарное количество точек проверки по всем маскам в множестве $$H$$, $$M''$$ - суммарное количество точек проверки по всем маскам, с учетом их кратности.
Заметим, что с помощью масок можно проводить сокращение ДИ, представленной также и в виде ТН. В этом случае элементом маски $$h$$ выступает не точка проверки, а номер тестового вектора, информация об обнаружении неисправности которого заносится в сокращенную таблицу. Таблицу, построенную в результате сокращения ТН с помощью набора масок $$H$$, будем называть таблицей неисправностей, построенной по маскам из $$H$$,и обозначать через $$TH_H$$.
В связи со сказанным выше, подход к сокращению ДИ при помощи масок приводит к необходимости исследования задач поиска различных масок. Остановимся на этом немного подробнее.
Так, в работе [1] формулируются три задачи, касающиеся сокращения ДИ с помощью масок:
Сформулированные задачи принято называть задачами минимизации ДИ при помощи масок [2,3]. В работах [3,4,5,6] рассматриваются методы точного аналитического решения первой, а в работе [6] еще и второй из сформулированных задач.
В ряде случаев для решения задач минимизации применимы методы, предложенные для оптимизации безусловных алгоритмов диагностирования [7].
В работе [3] сформулирована еще одна задача - задача оптимизации: для множества $$S$$ определить разбиение $$S_1,\ldots,S_l$$ и набор масок $$H=\{h_1,\ldots,h_l\}$$, чтобы объем $$СПР_H$$ не превышал заданной величины $$Z$$ и изменение разрешающей способности диагностирования с помощью $$СПР_H$$ по отношению к разрешающей способности диагностирования с использованием СПР было минимальным. Здесь же рассматриваются варианты точного аналитического решения этой задачи.
В работах [3,8] отмечается, что предложенные варианты точных решений задач поиска масок связаны с частичным перебором, и требуют большого объема вычислений. При значительном увеличении количества неисправных модификаций, характерного для современных устройств, а также при увеличении длины диагностического теста такие варианты решений становятся неприемлемыми из-за больших временных затрат. Выходом из сложившейся ситуации является замена точного решения приближенным. В тех же работах, а также в работе [2], предлагаются методы приближенного решения задачи минимизации и оптимизации объема $$СПР_H$$, когда $$H$$ - множество индивидуальных масок.
Каждый из упомянутых выше
Имеющийся опыт исследования многих оптимизационных прикладных задач показывает, что для их решения эффективным математическим аппаратом являются генетические алгоритмы (ГА). В лекции 25 была показана полезность ГА и их приемлемость с точки зрения временных затрат применительно к решению задач синтеза тестов. Далее мы убедимся, что и для различных модификаций задач поиска масок ГА также дают прекрасные результаты.
В дальнейшем изложении предполагается, что читатель знаком с содержанием лекции 25, где были определены основные понятия и термины,используемые в
Кратко напомним необходимые нам сведения о ПГА, содержащем следующие этапы:
На первом этапе создаются особи начальной популяции. Создание начальной популяции осуществляется, как правило, произвольным образом, в большинстве случаев особи формируются из случайных данных. Это позволяет осуществить разброс по пространству поиска, т. е. в данном случае этап создания начальной популяции подобен методу случайного поиска.
На втором этапе отбора для каждой особи определяется ее приспособленность, оцениваемая с помощью фитнес-функции. Напомним, что фитнес-функция есть мера качества решения. Затем с помощью оператора селекции осуществляется отбор. Отбор кандидатов (особей) для участия в процессе репродукции производится по принципу: чем выше приспособленность особи, тем выше вероятность ее участия в процессе скрещивания. Этап отбора представляет собой аналог дарвиновского выживания сильнейших применительно к особям.
Существуют различные варианты методов селекции, которые различаются как алгоритмическими характеристиками (вычислительная сложность, требования к памяти), так и такими специфическими для ГА характеристиками, как давление отбора, уменьшение разнообразия, наличием элитизма и т. д. Давление отбора - это отношение вероятности отбора лучшей особи к средней вероятности отбора всех особей. Явление уменьшения разнообразия вследствие применения отбора заключается в том, что оператор селекции исключает из дальнейшего использования особи, которые не были отобраны. Принцип элитизма заключается в сохранении некоторого количества наиболее приспособленных особей для их безусловного участия в процессе репродукции.
На третьем этапе осуществляется скрещивание отобранных на предыдущем этапе особей с помощью оператора скрещивания. Обычно данный оператор из двух особей (родительских) производит двух новых потомков. Создание новых особей осуществляется путем обмена соответствующих генов родительских особей. Полученные особи формируют новую популяцию или, говоря иначе, новое поколение.
На четвертом этапе осуществляется
В качестве условия окончания процесса эволюции может выступать факт наличия в популяции особи, чье значение функции приспособленности удовлетворяет некоторым пороговым значениям. В этом случае такая особь принимается в качестве решения. Альтернативным вариантом условия окончания может быть заранее определенное предельное число этапов эволюции (длина жизненного цикла популяции). При такой постановке в качестве решения принимается особь из последнего поколения с наилучшей приспособленностью.
Применение ГА требует подходящего выбора способа кодирования решения, представленного в виде
Остановимся на определении структуры
Отметим, что большая часть практически работающих ГА базируется на предположении, что
Хромосому, представляющую маску $$h$$, будем представлять в виде битовой последовательности $$\eta(h)$$ длины $$m|\tau|$$:
$$ \eta(h)=\eta_1(h)\eta_2(h)\ldots\eta_{m|\tau|}(h) $$Здесь $$m$$ - количество выходов устройства, $$\tau$$ - применяемый тест.
Для каждой точки проверки $$i$$:$$j$$ из маски $$h$$ значение $$\eta_s(h)$$ в (4.1), где $$s=m(i-1)+j$$, полагается равным 1. Все остальные разряды в $$\eta(h)$$ полагаются равными нулю.
Объемом маски будем считать величину
$$ |h|\stackrel{def}{=}\sum\limits_{i=1}^{m|\tau|}{\eta_i(h)}$$Назовем маску $$h$$ полной, если $$\eta_i(h)=1$$ для всех $$i=1,\ldots,m|\tau|$$. Введем в рассмотрение величину
$$V(h)=\cfrac{|h|}{m|\tau|}$$которая равна доле объема $$h$$ от объема полной маски.
Таким образом, среди всех битовых строк длины $$m|\tau|$$ ПГА будет отыскивать такую, которая обеспечивает экстремум целевой функции и о которой будет сказано ниже. В теории ГА эту функцию называют фитнес-функцией.
Маски порождают используемую ДИ и, тем самым, соответствующее множество СПН. Для оценки эффективности диагностирования с использованием порожденной ДИ будем применять значение ожидаемой глубины диагностирования
$$\rho_1=\cfrac{1}{|s|}\sum\limits_s{|S_j|^2},$$где $$S$$- множество состояний ЦУ, $$S_j$$- список подозреваемых неисправностей. Обозначим через $$\rho_2(h)$$ значение ожидаемой глубины диагностирования с использованием ДИ, порожденной маской $$h$$.
Теперь обратимся к задаче минимизации ДИ. Для ее решения с применением ПГА будем использовать следующую фитнес-функцию:
$$ d_1(\eta(h))=C\cdot(\rho_2(h)-1)+V(h)$$где $$C$$ - достаточно большая константа.
Поясним содержательный смысл функции (29.3). Ее значение естественно трактовать как оценку трудоемкости поиска неисправности в ЦУ, которая очевидно будет складываться из величины, пропорциональной средней длине СПН (первое слагаемое) и величины, пропорциональной размеру пространства поиска для определения неисправности, присутствующей в тестируемом ДУ. Множитель $$C$$ в (29.3) введен для того, чтобы обеспечить заданную глубину диагностирования $$\mu_0$$. Исходя из содержательного смысла фитнес-функции (29.3), искомым решением рассматриваемой задачи будет такая маска, которая доставит минимум упомянутой функции.
Соображения, аналогичные только что приведенным, применительно к задаче оптимизации ДИ приводит к следующей фитнес-функции:
$$ d_2(\eta(h))=C_1\cdot(\rho_2(h)-1)+C_2\cdot|V(h)-Z|$$где $$C_1$$ и $$C_2$$ - достаточно большие константы.
Исходя из содержательного смысла функции (29.4) ясно, что решением задачи оптимизации ДИ будет такая маска, которая доставит минимум этой функции.
Можно упростить вид последней фитнес-функции если ограничить пространство поиска маски только лишь масками заданного объема $$Z$$. Тогда в качестве фитнес-функции можно принять функцию
$$d_3(\eta(h))=\rho_2(h)$$Упрощение фитнес-функции влечет за собой изменение в операторах кроссовера и
Содержательный смысл минимизации функции $$d_3$$ очевиден - при постоянном объеме маски проводится минимизация ожидаемой глубины диагностирования.
Решение задачи минимизации ДИ с помощью индивидуальных масок можно осуществить двумя способами. Первый из них заключается в разработке ГА для поиска индивидуальной маски одного конкретного технического состояния ДУ, второй - в разработке ГА для одномоментного поиска множества индивидуальных масок всей рассматриваемой совокупности технических состояний ДУ.
Для обоих способов решения задачи структура
где $$\eta(h_i)$$ определены соотношением (29.1), $$F$$- множество рассматриваемых неисправностей.
Очевидно, что только второй способ организации
Рассмотрим сначала первый способ решения задачи минимизации ДИ.
Итак, при данном способе один запуск
Введем в рассмотрение функцию $$\rho_6(i,h)$$, возвращающую число технических состояний, неотличимых от состояния $$s_i$$ при использовании ДИ, отфильтрованной с помощью маски $$h$$.
Теперь можем определить фитнес-функцию для
Как видно из сравнения (29.3) и (29.7), функция $$d_4$$ отличается от функции $$d_1$$ только применением $$\rho_6(i,h)$$ вместо $$\rho_2(h)$$.
Для второго способа решения задачи минимизации построим ГА, аналогичный тому, что был построен для поиска единой маски. Обобщим этот алгоритм для использования набора масок $$H$$ вместо одной единой маски $$h$$.
Сначала введем в рассмотрение, по аналогии с (29.2), величину
$$V(H)=\cfrac{1}{m|\tau|(|F|+1)}\sum\limits_{h\in H}{|h|}$$Данная величина определяет долю объема ДИ, отфильтровываемой с помощью набора масок $$H$$ из общего объема ДИ.
Обозначим $$\rho_2(H)$$ значение ожидаемой глубины диагностирования при использовании ДИ, порожденной набором индивидуальных масок $$H$$.
В таком случае, по аналогии с (29.3), используя битовые последовательности $$H(H)$$ вместо $$\eta(h)$$, можно определить фитнес-функцию для решения с применением ПГА задачи минимизации:
$$ d_5(H(H))=C\cdot(\rho_2(H)-1)+V(H)$$Проводя такую же аналогию, что и в предыдущем случае, но применительно к задаче оптимизации, приходим к следующей фитнес-функции:
$$ d_6(H(H))=C_1\cdot(\rho_2(H)-1)+C_2\cdot|V(H)-Z|$$И так же, как нами было произведено упрощение функции до функции , можно преобразовать функцию при условии ограничения пространства поиска особями заданного объема. Фитнес-функция в таком случае примет вид:
$$d_7(H(H))= \rho_2(H)$$Из построения функций $$d_4$$, $$d_5$$, $$d_6$$ и $$d_7$$ ясно, что решением исследуемых задач будут те
Отметим, что во всех численных экспериментах, проведенных для оценки эффективности сконструированных ПГА, начальная популяция формировалась из особей, генерируемых с использованием датчиков случайных величин. Что касается размера популяции, то он подбирался опытным путем с целью ускорения сходимости к искомому решению.
На втором этапе ПГА, связанном с подбором (селекцией) особей для скрещивания, были опробованы различные методы: турнирный отбор, отбор отсечением, пропорциональный отбор, а также отбор линейным и экспоненциальным ранжированием, описанные, например, в [9].
На третьем этапе, связанном с репродукцией особей, опробовались операторы одноточечного, многоточечного, однородного и булева кроссовера.
Что касается
На пятом этапе ПГА для формирования следующего поколения из особей текущего поколения, а также полученных после скрещивания потомков, был использован метод элитного отбора.
Наконец, в качестве условий окончания процесса работы сконструированных простых ГА использовался критерий достижения заданного предельного числа этапов эволюции (длины жизненного цикла популяции).
Материал, представленный выше, помимо упомянутых в этой лекции работах, базируется также на статье [10].
Маска для диагностической информации - шаблон, накладываемый на строки полной диагностической информации, позволяющий отфильтровывать из реакций проверяемого ЦУ на тест только заранее определенные в ДИ позиции .
Простой генетический алгоритм поиска маски- алгоритм, оперирующий с совокупностью различных шаблонов масок, представленных в виде хромосом. Поиск маски основан на применении к начальному множеству (популяции) шаблонов операторов кроссовера,
В лекции описан подход к сокращению ДИ с использованием масок. Сформулированы различные модификации задач поиска масок и описан простой
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.