УДК 681.518

УСКОРЕНИЕ РАБОТЫ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

ПРИ ПОСТРОЕНИИ ТЕСТОВ.

Д.Е. Иванов, Ю.А. Скобцов.

Введение. Проблема построения тестов для последовательностных устройств является одной из самых сложных в технической диагностике. В последнее время разработан ряд методов построения тестовых наборов, позволяющих добиться высокой полноты тестов, как для комбинационных, так и для последовательностных схем. Все они могут быть условно разделены на три группы. К первой относятся структурные методы, являющиеся расширением для последовательностных схем метода ветвей и границ [1]. Результаты такого подхода сильно зависят от эвристик, используемых при направлении поиска.  К существенным недостаткам метода относятся сложность реализации и плохая практическая применимость к большим схемам. Во вторую группу включаются методы, основанные на символьном моделировании [2]. Их суть заключаются в получении и обработке булевых функций, реализующих схему. Методы символьного моделирования (также как и методы первой группы) являются алгоритмами и показывают хорошие результаты для небольших и средних схем. Однако они практически полностью неприменимы для схем, содержащих более двух десятков триггеров. Третья группа методов основана на псевдослучайной генерации тестовых наборов и дальнейшей их модификации с учётом моделирования (исправного или с неисправностями) [3]. Распространение этой группы методов обусловлено появлением быстрых программ моделирования с неисправностями [4].

Предложенный Голдбергом в [5] генетический подход хорошо зарекомендовал себя при решении задач переборного типа с NP полным решением. Используемый в данном подходе генетический алгоритм относится к третьей группе методов построения тестов. Показывая сопоставимые с детерминированными методами результаты, он является гораздо более простым по структуре и в реализации. В данной статье обсуждаются некоторые практические методы, реализованные в алгоритме построения тестовых наборов для последовательностных схем, которые позволяют существенно повысить скорость работы генетического алгоритма. Статья имеет следующую структуру. Во втором разделе кратко описана адаптация генетического алгоритма к проблеме построения тестов последовательностных схем. В третьем разделе представлены программы моделирования, используемые в алгоритме. В четвёртом разделе описывается способ построения новой популяции, позволяющий избежать повторного вычисления оценочной функции для особей, в неё без изменения. В заключительной части приведены результаты машинных экспериментов, проведённых с программной реализацией алгоритма на контрольных схемах из международного каталога ISCAS-89.

Генетический алгоритм. Для решения проблемы генерации тестов в последнее время получили распространение генетические алгоритмы [6]. Применительно к проблеме генерации тестов суть генетического алгоритма заключается в следующем. В начальный момент времени (обычно случайным образом) генерируется ряд тестовых последовательностей - популяция (рис.1). Каждая последовательность называется особью и является частичным решением проблемы. Далее на основании некоторых критериев вычисляется оценочная функция каждой особи (тестовой последовательности), характеризующая относительную способность решения поставленной проблемы. Обычно для вычисления оценочной функции используется моделирование с неисправностями, реже – исправное моделирование. Из текущего поколения особей строится следующее с целью либо найти решение, либо улучшить оценку каждой особи. Цель данной операции – получение особей в популяции, обладающих новыми свойствами. Новое поколение строится следующим образом. Из популяции случайным образом выбираются две особи. Вероятность выбора особи полагается пропорциональной оценочной функции. Копии выбранных особей сразу помещаются в новую популяцию. После этого к данным особям применяются модифицирующие операции. Обычно используют два вида таких операций: скрещивание и мутацию. Скрещивание производится в одной или нескольких точках (рис.2). Далее с некоторой вероятностью в двух новых особях происходит мутация битов: ноль изменяется на 1 и наоборот, после чего модифицированные особи помещаются в новую популяцию. Так происходит до тех пор, пока в новой популяции не наберётся необходимое число особей. Порождение новых популяций прекращается, когда найдено удовлетворительное решение, либо произведено вычисление заранее заданного числа поколений.

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

На основе описанного выше подхода авторами был разработан и реализован алгоритм генерации тестов для последовательностных схем. Структурно он состоит из трёх фаз. В фазе 1 из списка непроверенных неисправностей необходимо выбрать одну целевую неисправность, которая может быть активизирована, т.е. значения сигналов в исправной и неисправной схемах распространяются на внешние псевдовыходы. Для достижения этой цели используется псевдослучайная генерация последовательностей и дальнейшее моделирование с неисправностями на данных последовательностях. В фазе 1 используется программа моделирования неисправных схем, описанная в [7]. Основной в данном алгоритме является фаза 2, цель которой с помощью генетического алгоритма улучшить активизирующую последовательность, полученную в фазе 1, чтобы она стала проверяющей для  целевой неисправности. Фаза 3 используется для удаления из списка тех неисправностей, которые обнаруживаются построенной в фазе 2 последовательностью. Общая структура алгоритма в виде псевдокода представлена ниже.

генерация_тестов(схема)

{

while(не достигнута заданная полнота)

{

цель=активизировать_неисправность();                                                          // Фаза 1

if( цель == НЕТ_НЕИСПРАВНОСТИ )

  goto конец;

последовательность=GA:_генерация_тестовой_последовательности(цель) //Фаза 2

if( последовательность != НЕТ_ПОСЛЕДОВАТЕЛЬНОСТИ )

моделирование_с_неисправностями( последовательность );                   // Фаза 3

else // не смогли найти тестовую последовательность для целевой неисправности

 отметить_неисправность_как_непроверяемую();

}          // конец while – достигнута заданная полнота

конец:

}               // конец алгоритма

Программы моделирования и вычисление оценочных функций. Для повышения быстродействия алгоритма построения тестов в программную реализацию интегрированы две программы параллельного моделирования с неисправностями. Первая программа [7] используется в фазе 1 для проверки активизации произвольной неисправности случайно сгенерированной последовательностью. На данном этапе мы рассматриваем только потенциальных кандидатов на тестовую последовательность, поэтому удалять неисправности, которые они обнаруживают, из списка неисправностей не нужно. Это достигается введением в программу моделирования «пробного» режима. После моделирования в таком режиме мы будем знать, сколько неисправностей проверилось данной тестовой последовательностью из заданного списка неисправностей, но сам список не изменится. В списках неисправных элементов состояний ([7]) хранятся значения сигналов псевдовыходов неисправной схемы. Поэтому, если данный список для произвольной неисправности не пуст, значит её влияние распространилось на внешние псевдовыходы, или, другими словами, произошла её активизация. «Пробный» режим моделирования с неисправностями применяется в фазе 1 алгоритма. При этом моделирование может выполняться либо до активизации первой неисправности из списка ещё непроверенных, либо на всех особях-кандидатах. В первом случае в качестве целевой выбирается активизированная неисправность. Во втором случае, если активизировано несколько неисправностей, возможно применение некоторых критериев. Например, в качестве целевой выбрать ту неисправность, в присутствии которой в схеме наблюдается наибольшая активность, либо влияние неисправности которой распространилось на большее число псевдовыходов, либо применить комбинацию данных критериев. Возможно также адаптировать для этой цели генетический алгоритм, что позволит выбирать самую активную неисправность. При этом оценочные функции будут аналогичны используемым в фазе 2 (см. ниже).

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

Самым ресурсоёмким этапом генетического алгоритма, определяющим время его работы, является вычисление оценочных функций. В нашем алгоритме качество тестовой последовательности оценивается как мера отличия значений сигналов в исправной и неисправной схемах. Данная оценка основывается на предположении, что, чем выше активность в неисправной схеме производит неисправность, тем легче она может быть обнаружена. Для вычисления оценочной функции используется вторая программа моделирования с неисправностями, реализующая алгоритм «параллельного моделирования по тестовым наборам», и написанная специально для работы с генетическим алгоритмом построения тестов. Суть данного алгоритма заключается в следующем. Во всех битах машинного слова моделируется одна и та же неисправность: целевая неисправность фазы 2 алгоритма, но на каждый разряд подаётся своя тестовая последовательность-особь. Таким образом реализуется параллельное по особям популяции моделирование, а каждый разряд машинного слова используется для вычисления оценочной функции отдельной особи, что позволяет за один проход произвести вычисление оценочной функции сразу для всех особей в популяции. Происходит это следующим образом. После моделирования очередного тестового вектора происходит вычисление оценочной функции текущего вектора по формуле:

                                                 

В качестве веса выбирается мера наблюдаемости элемента схемы, вычисляемая на этапе предварительной обработки схемы.

Если текущий тестовый вектор обнаружил целевую неисправность, то его позиция показывает эффективную длину последовательности, а её остаток отбрасывается. После того как для последовательности, моделируемой в определённом разряде, достигнута эффективная длина или произведено моделирование на последнем наборе вычисляется оценочная функция всей последовательности:

Применение данного алгоритма существенно повышает скорость вычисления оценочных функций особей в популяции, а, следовательно, и скорость работы алгоритма в целом. Недостатком такого подхода является ограниченное число особей в популяции: не более 32, что обусловлено разрядностью инструментальной ЭВМ. Однако это ограничение несущественно, поскольку число особей в популяции (МАХ_ОСОБЕЙ) обычно выбирается гораздо меньше: 16 или 24 особи.

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

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

newP=Ж; // промежуточная популяция

for( k=0 ; k<ЧИСЛО_НОВЫХ_ОСОБЕЙ ; k++ ) {

выбрать_две_последовательности_s₁_в_P();

newP=newPÈs₁;

применить_операцию_скрещивания_к_s₁();//генерируются две особи s₂

применить_операцию_мутации_к_s₂_c_вероятностью_P_m();

newP=newPИs₂;

}

вычислить_оценочные_функции_особей_из_newP();

P=( лучшие MAX_ОСОБЕЙ из newP )

где MAX_ОСОБЕЙ - размер популяции, P - текущая и новая популяция, newP - промежуточная популяция, P_m - заданная вероятность мутации.

Рассмотрим недостатки этого подхода. Для того, чтобы узнать какие особи являются лучшими в промежуточной популяции (newP), необходимо вычислить оценочные функции особей этой популяции. При этом вычисление оценочных функций производится для всей промежуточной популяции. Таким образом вычисление для старых особей будет проведено повторно. Дополнительно, если размер промежуточной популяции (МАХ_ОСОБЕЙ + ЧИСЛО_НОВЫХ_ОСОБЕЙ) превышает 32 особи, то вычисление оценочных функций всех особей в новой популяции необходимо организовать два (или более) вызовов программы моделирования, что связано с разрядностью инструментальной ЭВМ.

Чтобы избежать указанных недостатков, предлагается следующий механизм порождения новой популяции, который также основан на параллельном вычислении оценочных функций. После выбора двух особей в качестве родителей они остаются в предыдущей популяции P. В промежуточную популяцию newP после операций скрещивания и мутации будут помещены их потомки, тогда как сами родители – нет. Далее для получения нового поколения путём выбора лучших особей из старой популяции P и промежуточной newP необходимо будет вычислить оценочные функции только для особей из newP. Это выполняется с помощью программы параллельного моделирования, описанной в предыдущем разделе. При этом также эффективно будут использованы все разряды машинного слова, поскольку число особей в промежуточной популяции newP равно МАХ_ОСОБЕЙ и обычно не превышает 32. Псевдокод данной реализации записан ниже.

newP=Ж;

for( k=0 ; k<МАХ_ОСОБЕЙ; k++ ) {

выбрать_две_последовательности_s₁_в_P();

применить_операцию_скрещивания_к_s₁(); // генерируются две особи s₂

применить_операцию_мутации_к_s₂_c_вероятностью_P_m();

newP=newPИs₂;

}

вычислить_оценочные_функции_особей_из_newP(); // только МАХ_ОСОБЕЙ

P=( лучшие MAX_ОСОБЕЙ из newP и P)

Заметим также, что при таком способе построения новой популяции:

- гарантировано не будут утеряны особи с высокой оценочной функцией, которые тем не менее не были выбраны в качестве родителей новых особей;

- вероятность выбора особей с высокой оценочной функцией в качестве родителя повышается в МАХ_ОСОБЕЙ раз, поскольку они не удаляются из предыдущей популяции.

Экспериментальные данные. Алгоритм построения тестовых последовательностей на основе генетической стратегии и предложенные методы были реализованы программно на языке программирования С++ в среде визуального программирования C++ Builder. Программа генерации тестовых наборов вошла составной частью в автоматизированную систему моделирования и диагностики АСМИД-Е. Система АСМИД-Е разработана в Институте прикладной математики и механики НАН Украины и выполняет следующие функции: 1) графический или текстовый ввод описания моделируемого устройства; 2) синтаксический анализ описания, необходимый для выявления ошибок подготовки данных; 3) трансляцию описания ЦУ во внутреннюю структуру данных; 4) логическое моделирование исправных ДУ на входных воздействиях, заданных пользователем; 5) генерацию тестов; 6) логическое моделирование неисправных ДУ с целью анализа полноты тестовых наборов.

Апробация работы алгоритма проводилась на схемах из международного каталога ISCAS-89 [8]. Данный каталог содержит набор последовательностных схем с различными характеристиками, предложенных в качестве стандарта для апробации новых методов моделирования и построения тестов. При проведении машинных экспериментов использовалась следующая стратегия. Генерация тестовых наборов проводилась в среде АСМИД-Е с помощью программы, реализующей генетический алгоритм построения тестовых наборов. Данные о наблюдаемости линий схемы вычислялись на этапе трансляции описания схемы статистическим методом [9] и считались известными программе генерации тестов. Программа выполнялась со следующими значениями параметров: число особей в популяции МАХ_ОСОБЕЙ=16, число поколений МАХ_ПОКОЛЕНИЙ=16, вес позиции вектора в тесте LH=0.98, вероятность мутации одиночного бита Р_{мутации}=0.5%. Результаты работы программы: полнота полученных тестовых наборов, время генерации и длина тестов приведены в табл. 1. В общем можно отметить, что программа показывает высокие эксплутационные характеристики, обладая преимуществами простоты реализации и надёжности.

Литература.

1.        Niermann T., Patel J.H. HITEC: A Test Generation Package for Sequential Circuits // Proc. European Design Automation Conf.- 1991.- p.214-218.

2.        Sellers F.F., Hsiao M.Y., Bearnson L.W. Analysing errors with the boolean difference // IEEE Transactions on Computers.- 1967.- №5.- p.675-680.

3.        Lisanke R., Brgles F., Degens A..J., Gregory D. Testability-driven random test pattern generation // IEEE Trans. Computer-Aided Design.- 1987.- №6.- p.1082-1087.

4.        Cheng W.T., Patel J.H. PROOFS: A Super Fast Fault Simulator for Sequential Circuits. // Proc. The European Conference on Design Automation.– 1990.– p.475-479.

5.        Goldberg D.E., Genetic Algorithm in Search, Optimization, and Machine Learning.- Addison-Wesley.- 1989.

6.        Rudnick E.M., Holm J.G., Saab D.G., Patel J.H., Application of Simple Genetic Algorithm to Sequential Circuit Test Generation // Proc. European Design & Test Conf.- 1994.- p.40-45.

7.        Иванов Д.Е., Скобцов Ю.А., Параллельное моделирование неисправностей для последовательностных схем // «Искусственный интеллект».- 1999.- №1.- с.44-50.

8.        Brgles F., Bryan D., Kozminski K. Combinational profiles of sequential benchmark circuits // International symposium of circuits and systems, ISCAS-89.– 1989.– p.1929-1934.

9.        Барашко А.С., Скобцов Ю.А, Сперанский Д.В., Моделирование и тестирование дискретных устройств.- К.: Наукова Думка, 1992.- 288с.

Таблица 1. Экспериментальные данные работы генетического алгоритма.

  

УДК 681.518

Ускорение работы генетических алгоритмов при построении тестов.

Д.Е.Иванов, Ю.А.Скобцов.

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

УДК 681.518

Прискорення роботи генетичних алгоритмів при побудові тестів.

Д.Е.Іванов, Ю.О.Скобцов.

Розглядається проблема побудови тестів для синхронних послідовністних схем за допомогою генетичного алгоритму. Заснована на моделюванні генетична стратегія побудови тестів показує порівнювані з детермінованими методами результати, володіючи рядом переваг: прозорість стратегії та простота реалізації. Пропонуються методи, що дозволяють підвищити швидкість генетичного алгоритму: оптимізований спосіб побудови нової популяції та паралельне обчислення оцінюючих функцій.

UDC 681.518

Speed up of the genetic algorithms in the test generation.

D.E. Ivanov, Y.A. Skobtsov.

It is considered the problem of the test generation for the synchronous sequential circuits with help of the genetic algorithm. This test generation strategy is based on the fault simulation, but demonstrate the comparable with deterministic strategy results and have clear and simple implementation. There are proposed the methods that able to speed up of the genetic algorithm: an optimized way of the construction of the new population and parallel calculation of the fitness function.

Сведения об авторах

1.      ФИО: Иванов Дмитрий Евгеньевич.

2.      Домашний адрес: , 83017, Донец-17,

бул. Шевченко, 60, кв. 25.

3.      Место работы: Институт прикладной математики и механики

НАН Украины.

4.      Рабочий адрес: 83114, Донецк-114,

ул. Р.Люксембург, 74, ИПММ НАН Украины.

5.      Должность: инженер.

6.      Степень: нет.

7.      Звание: нет.

8.      Телефоны: (0622) 51-01-47 (служебный).

9.      Факс: (0622) 55-22-65.

10.  E-mail: ivanov@iamm.ac.donetsk.ua

1.      ФИО: Скобцов Юрий Александрович.

2.      Домашний адрес: 83112, г. Донецк-112, ул. Туполева, 15, кв. 73.

3.      Место работы: Институт прикладной математики и механики

НАН Украины.

4.      Рабочий адрес: 83114, Донецк-114,

ул. Р.Люксембург, 74, ИПММ НАН Украины.

5.      Должность: зав. отделом теории управляющих систем.

6.      Степень: доктор технических наук.

7.      Звание: доцент.

8.      Телефоны: (0622) 55-50-82 (служебный), (0622) 66-91-39 (домашний).

9.      Факс: (0622) 55-22-65.

10.  E-mail: skobtsov@iamm.ac.donetsk.ua