The ant colony algorithm for test syntesis for digital devices.pdf Проблемы контроля и диагностирования цифровых устройств (ЦУ) относятся к числу актуальных, поскольку обеспечение высокой надежности функционирования ЦУ невозможно без их эффективного решения. Жесткие требования к надежности ЦУ диктуются постоянно возрастающей ответственностью функций, которые на них возлагаются. Это в полной мере относится, например, к ЦУ, используемым в системах управления опасными промышленными производствами (изготовление токсичных и взрывчатых веществ и т.п.), в системах обеспечения безопасности транспортных средств (авиация, железные дороги, морские суда) и т.д. Важным этапом обеспечения высокой надежности ЦУ является эффективная организация их тестового и функционального диагностирования [1]. Предлагаемая статья посвящена задаче синтеза тестов для ЦУ. Методы синтеза тестов можно условно разделить на две группы. К первой относятся сравнительно просто реализуемые методы, но вместе с тем получаемые ими тесты обнаруживают, как правило, сравнительно большую часть возможных неисправностей ЦУ, однако не все их множество. Примером может служить метод псевдослучайного синтеза тестов [1]. Ко второй группе относятся методы, более трудоемкие в реализации, но синтезируемые ими тесты способны обнаруживать не только «простые», но и «трудные» неисправности. Примером могут служить методы различающей функции и булевых производных [1]. Предлагаемый в статье метод относится именно к этой группе. В последние два-три десятилетия получили широкое распространение так называемые эволюционные алгоритмы [2, 3], оказавшиеся эффективными для решения многих практических проблем. В статье описан метод синтеза тестов, базирующийся на идее одного из таких алгоритмов, алгоритме муравьиной колонии (АМК), разработанном М. Дориго [4, 5] и детально описанном в [6, 7]. 1. Постановка задачи Пусть задано ЦУ в виде структурной схемы и множество F его возможных неисправностей. Для простоты изложения далее предполагается, что ЦУ является комбинационным, а рассматриваемые неисправности - одиночными константными. Требуется разработать АМК для синтеза тестов, позволяющий обнаруживать все неисправности из множества F. Далее эту задачу будем именовать задачей синтеза тестов (ЗСТ). Рассматриваемая задача наиболее близка к классической задаче коммивояжера (ЗК) [6], и аналогия с ней будет использована нами. В ЗСТ моделью ЦУ является неориентированный граф G = (V, E), где V - множество вершин, каждая из которых соответствует некоторому входному набору ЦУ. В множество V включаются 122 Алгоритм муравьиной колонии синтеза тестов для цифровых устройств только те входные наборы ЦУ, которые обнаруживают неисправности из F. Если p - число входов, то | F | может быть существенно меньше 2p. Множество E образуют ребра между любой парой вершин графа G. Понятно, что граф G = (V, E) является полным [8]. Заметим, что в ЗК используемый в качестве модели граф полным не является. Каждому ребру ставится в соответствие число, называемое длиной (весом), о содержательном смысле которого будет сказано ниже. В терминах описанного графа решением ЗСТ является минимальный по длине путь (маршрут) в этом графе (сумма длин всех его ребер), которому соответствует тест, обнаруживающий все неисправности из F. Отметим, что если в ЗК ее решение есть путь, проходящий через все вершины графа , то в ЗСТ минимальный по длине «тестовый» путь может и не проходить через все вершины графа. При этом, как и в ЗК, каждая вершина «тестового» пути должна посещаться только один раз. В ЗСТ это требование объясняется тем, что повторение в тесте одного и того же входного набора не увеличивает числа обнаруживаемых неисправностей ЦУ. Из сказанного выше вытекает, что хотя между ЗК и ЗСТ, несомненно, имеется аналогия, вместе с тем существующие между ними различия требуют существенной модификации АМК решения ЗК для возможности адаптации его к решению ЗСТ. 2. Описание алгоритма Далее предполагается знакомство читателя с терминологией и понятиями из области муравьиных алгоритмов хотя бы в рамках небольшой по объему публикации [6]. Процесс построения теста каждым k-м муравьем (их число выбирается заранее) является пошаговым. Он начинается с включения в тест некоторого входного набора с последующим добавлением к «текущему» тесту Ттек нового набора на каждом очередном шаге. С помощью Ттек обнаруживается некоторое множество неисправностей ЦУ, которое исключается из первоначально заданного множества неисправностей F, и в результате остается множество FtH еще не обнаруженных неисправностей. Добавление к «текущему» тесту Ттек нового набора продолжается до тех пор, пока множество F£ не окажется пустым. Перейдем теперь к содержательному описанию предлагаемого АМК, предварительно введя некоторые обозначения, сопровождаемые комментариями. F(w) - множество неисправностей из F, обнаруживаемых с использованием входного слова w. FktTтек - множество еще не обнаруженных тестом Ттек k-м муравьем неисправностей из F на итерации t; dtj (к, f) =| FXTeK ,0 ннннн, н)І - число неисправностей, не обнаруживаемых k-м муравьем на итерации t как входным набором i, так и следующим за ним в текущем тесте входным набором j. D = j ГІFHi) n F(j) |, если F(i) Ф F(j), С - большая константа, если F(i) = F(j), Dij - вес (длина) дуги (i, j) графа G). Поясним содержательный смысл Dij: чем больше множество «общих» неисправностей, обнаруживаемых наборами i и j, тем менее «привлекателен» для включения в тест после набора i входной набор j. Понятно, что вклад набора j в распознавание неисправностей из F в этом случае будет уменьшаться с ростом величины Dij. Это хорошо согласуется с используемым в АМК для ЗК понятием видимости вершин графа [6]: чем больше значение Dij, тем «дальше» вершина j от вершины i, т.е. тем хуже ее «видимость». = 1/ D - видимость, являющаяся локальной статической информацией, которая выражает естественное желание включить в качестве очередного элемента искомого теста входной набор с наибольшим вкладом в обнаружение неисправностей множества F. Отметим, что значения элементов Dij матрицы D находятся применением логического моделирования ЦУ при наличии в нем всех неисправностей множества F. 123 В.М. Соловьев, Д.В. Сперанский Самоорганизация в колонии муравьев [6] есть результат взаимодействия четырех компонентов -случайности, многократности, а также положительной и отрицательной обратных связей. Что касается многократности, в АМК для ЗСТ она реализуется за счет итерационного процесса поиска теста, осуществляемого не одним, а группой муравьев. При этом каждый муравей этой группы решает ЗСТ независимо от других. В процессе выполнения итерации каждый муравей группы решает задачу синтеза теста до конца. Упомянутый выше принцип положительной обратной связи в АМК реализуется в виде имитации предпочтения муравьем при выборе очередного ребра (входного набора) графа при построении тестового пути. Муравей может отдать предпочтение такому из альтернативных ребер, на котором концентрация феромона максимальна. Большая привлекательность для муравья такого ребра в качестве очередного звена тестового маршрута интуитивно связана с тем, что этот след феромона «укреплен» за счет перемещения по ребру многих муравьев, задействованных для решения той же задачи. Условимся далее концентрацию (количество) феромона на ребре (i, j) на итерации t обозначать как Tj(t). Откладываемый на ребрах феромон позволяет «хорошим» тестовым маршрутам сохраняться в глобальной памяти колонии муравьев. Последующие итерации АМК могут привести к улучшению таких тестовых путей. Заметим, что концентрация феромона на ребрах должна изменяться после каждой итерации АМК, что отражает приобретение муравьями опыта в поиске теста. Однако применение только положительной обратной связи может привести к ситуации, когда все муравьи двигаются одним и тем же субоптимальным (близким к оптимальному, но не оптимальным) путем. По аналогии с АМК для ЗК в нашем алгоритме будет использоваться отрицательная обратная связь, вызываемая испарением феромона. Этот процесс приводит к тому, что группа муравьев, решающая ЗСТ, одновременно исследует разные точки пространства решений и передает свой опыт через изменение ячеек глобальной памяти колонии муравьев. Такая память представляет собой совокупность значений концентрации феромона на ребрах графа G, накопленных в результате итераций АМК. Компонент случайности в нашем АМК реализуется при переходе от одного набора синтезируемого теста к следующему. По аналогии с ЗК вероятность перехода k-го муравья из вершины i в вершину j на t-й итерации имеет следующий вид: P,k (t) < [^ Г мр IК (t)]° [ца (t)]p ’ leJi ,k j (t) = о, если j e Jl k, если j g Ji,k, (1) где Jik - множество еще не использованных входных наборов ЦУ в синтезируемом тесте k-м муравьем, а и в - регулируемые параметры, задающие веса следа феромона и видимости при построении теста. Понятно, что при а = 0 концентрация феромона при выборе ребра не используется, т.е. выбор осуществляется только на основе видимости вершины j. Если же в = 0, то для выбора используется только концентрация феромона, что может привести к сваливанию тестовых путей к одному из субоптимальных. Как и в АМК, для ЗК выбор очередного входного набора должен осуществляться по правилу рулетки. При этом каждый входной набор имеет в секторе рулетки площадь, пропорциональную вероятности (1). По аналогии с ЗК формула корректировки концентрации феромона на ребре графа за счет его испарения (с параметром ре[0,1]) имеет следующий вид: x j (t +1) = (1 - р)т j (t) + Ат j (t), (2) m где Ату(t) = 1)АТуk(t), m - количество муравьев в группе (колонии), синтезирующей тест (m являетk=1 ся регулируемым параметром). 124 Алгоритм муравьиной колонии синтеза тестов для цифровых устройств Итак, в предложенном АМК для ЗСТ самоорганизация в колонии муравьев базируется на взаимодействии компонентов случайности, многократности, положительной и отрицательной обратных связей. Заключение Предложенный алгоритм расширяет область приложений эволюционных вычислений на решение важного класса задач контроля и диагностирования ЦУ. Качество получаемых с применением алгоритма муравьиной колонии результатов во многих других проблемах дает основание рассчитывать на эффективные результаты и в рассмотренной нами области.

Скачать электронную версию публикации