Эволюционные методы генерации тестов

Для повышения уровня "интеллекта" и эффективности современных САПР компьютерных систем, расширения их возможностей применяются различные методы искусственного интеллекта. Одним из самых перспективных направлений является использование эволюционных вычислений.

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

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

25.1 Простой генетический алгоритм

Генетические алгоритмы (ГА) [25.1], являясь одной из парадигм эволюционных вычислений, представляют собой алгоритмы поиска, построенные на принципах, сходных с принципами естественного отбора.

В соответствии с ними простой ГА использует три основных оператора: репродукция, кроссинговер, мутация. При репродукции хромосомы копируются согласно их значениям ЦФ. Копирование лучших хромосом с большими значениями ЦФ определяет большую вероятность их попадания в следующую генерацию. Оператор репродукции реализует принцип "выживания сильнейших" по Дарвину.

Самый простой (и популярный) метод реализации ОР - построение асимметричного колеса рулетки, в которой каждая хромосома имеет сектор, пропорциональный ее значению ЦФ. Например, "колесо рулетки" имеет следующий вид, представленный на рис. 25.1.

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

Оператор кроссинговера (ОК) обычно выполняется в три этапа:

Например, для родительских особей

$$A=1001 11001$$, $$B=0110 10010$$

При точке кроссинговера $$k=4$$ получаем следующие особи - потомки

$$\tilde{A}=1001 10010, \tilde{B}=0110 11001$$.

Следует отметить, что для отобранных родительских особей оператор кроссинговера выполняется с некоторой заданной вероятностью $$P_{k}$$ (обычно $$P_{k} \approx 0.5$$). То есть отобранные родители не всегда дают потомство.

Оператор мутации (ОМ) случайным образом (с небольшой вероятностью $$P_{m} \approx 0.001$$ ) изменяет произвольный ген (элемент) стринга.

Используя эти три основные оператора, популяция (множество потенциальных решений данной проблемы) эволюционирует от поколения к поколению. Эволюция такой искусственной популяции представлена на рис. 25.2.

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

25.2 Генетические алгоритмы в генерации тестов для комбинационных схем

Классический "простой" генетический алгоритм [25.1] использует двоичные стринги - строки из двоичных элементов 0,1 (например, 0011101), что делает его привлекательным для задач генерации проверяющих тестов логических схем, где решение представляется в виде двоичных наборов или их последовательностей, которые в данном случае рассматриваются как особи популяции - множества возможных решений [25.2]. На множестве решений определяется целевая (fitness) функция (ЦФ), которая позволяет оценить близость каждой особи к оптимальному решению. В случае задачи генерации тестов ЦФ прямо или косвенно должна отражать такие свойства двоичных наборов или последовательностей как число проверяемых неисправностей или изменений сигналов в схеме.

Рассмотрим простейший случай использования ГА для генерации тестов комбинационных схем[25.3]. Очевидно, особью (хромосомой) в данном случае является отдельный двоичный набор значений входных переменных $$X=(x_{1},x_{2},…, x_{n},)$$, где $$x_{i}=0,1$$ и $$n$$ равно числу входов схемы. Популяцией является множество наборов, составляющих проверяющий тест схемы. Обычно число особей в популяции пропорционально числу входов (например, $$3n$$ ) В качестве целевой (fitness) функции пока для простоты (условно) для каждого двоичного набора будем считать число проверяемых им неисправностей. Следует подчеркнуть, что значение ЦФ определяется с помощью программы логического моделирования, которая является важнейшей компонентой этого метода. Мы рассмотрим применение ГА для генерации тестов на примере схемы рис. 25.3. Для удобства в табл. 25.1 представлены все возможные 8 входных наборов со значениями сигналов на всех линиях схемы рис. 25.3.

При инициализации популяция входных векторов генерируется случайным образом. Для нашего примера рис. 25.3 начальная популяция (построенная случайно) представлена в первом столбце табл. 25.2. Во втором столбце для каждой особи - набора показаны проверяемые им одиночные константные неисправности. Очевидно, что входной набор, проверяющий большее количество неисправностей, должен иметь больше шансов попасть в тестовое множество.

Поэтому на начальном этапе в качестве фитнеcc-функции можно взять $$h=F_{d}*s$$, где $$F_{d}$$ - число (вновь) проверяемых неисправностей и $$s$$ - "премия" за каждую проверенную неисправность (в нашем примере $$s=10$$). В реальной системе генерации тестов $$F_{d }$$определяется с помощью моделирования неисправностей. Очевидно, лучший входной набор (011 или 101) с максимальным значением фитнеcc-функции $$h=F_{d}*s$$ должен быть включен в тест. Пусть для определенности это будет набор (101). Далее для генерации популяции следующего поколения необходимо применить генетические операторы кроссинговера и мутации.

При одноточечном кроссинговере случайно выбирается точка скрещивания с вероятностью $$P\approx 0.5$$ и производится обмен фрагментами хромосом после точки скрещивания. Например, для двух родительских особей (0Ѕ11) (1Ѕ01) с точкой к=1 получаем два потомка - наборы (0Ѕ01) (1Ѕ11).

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

После выполнения операторов кроссинговера полученные потомки с вероятностью $$P_{m}$$ подвергаются мутации, которая может быть выполнена различными способами. В простейшем случае для каждой особи случайно выбирается позиция и с малой вероятностью от $$Р_{m}=0,01$$ до $$Р_{m}=0,001$$ выполняется инвертирование значения переменной в выбранной позиции.

Каждую особь популяции нового поколения необходимо оценить с помощью фитнесс-функции, которая в общем случае (кроме начальной популяции) должна в первую очередь учитывать число вновь проверенных данным набором неисправностей. Допустим, что после второго шага в текущее тестовое множество включены два входных набора (101,011), которые проверяют (и не проверяют неисправности, показанные в табл. 25.3) и текущая популяция входных наборов (кандидатов на включение в тест) представлена в табл. 25.4.

Заметим, что далее мы используем фитнесс-функцию $$h= F_{d}*s+ F_{n}*r$$ , где $$F_{n}$$ - число вновь проверенных неисправностей и $$F_{d}$$ - число ранее проверенных неисправностей $$s$$ соответствующим тестовым набором. Здесь $$r=10$$ - премия за каждую вновь проверенную неисправность и $$s=1$$ - премия за каждую ранее проверенную неисправность. В соответствие с данными табл. 25.4 тестовый набор (110) должен быть включен в тестовую последовательность поскольку он имеет максимальное значение фитнесс-функции. В следующей табл. 25.5 ситуация показана для текущего тестового множества, которое состоит из трех наборов и имеет только две непроверяемые неисправности.

Аналогично можно показать, что на следующем шаге тестовый набор (010) должен быть включен в тест, поскольку он проверяет последнии непроверенные неисправности $$x_{1}\equiv 1, x_{3}\equiv 1$$. Укрупненный генетический алгоритм на основе описанного подхода представлен псевдокодом рис. 25.5.

Здесь на этапе инициализации генерируется множество неисправностей, и выполняются другие вспомогательные операции. Обычно наборы начальной популяции генерируются случайным образом, но если априорная доступная информация о хороших кандидатах в тест, то она может быть использована. Оценка значений фитнесс-функции выполняется на основе данных логического моделирования с неисправностями. Заметим, что в описанном выше подходе генетический алгоритм на каждом шаге решает локальную проблему поиска особи - следующего входного набора для включения его в тест в отличие от классичекого ГА, где особь представляет глобальное решение проблемы (весь тест).

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

25.3 ГА в генерации тестов последовательностных схем

Использование ГА при генерации проверяющих тестов является естественным развитием псевдослучайных методов генерации тестов. Одним из первых применений ГА в технической диагностике цифровых схем (ЦС) является построение на их основе генераторов тестовых последовательностей. Суть задачи заключается в поиске двоичной входной последовательности, которая для каждой неисправности из заданного множества дает различные выходные значения сигналов в исправной и неисправной схемах. Как правило, рассматриваются одиночные константные неисправности.

Поскольку значения сигналов внешних выходов при функционировании ЦС данного типа зависят не только от значений сигналов на его внешних входах, а и от состояний триггеров, то при генерации тестов таких ЦС с применением ГА в качестве особи используется тестовая последовательность, которая представляется двоичной таблицей (рис. 2.8 а). Число столбцов таблицы определяется числом входов схемы, а число строк - длиной тестовой последовательности. Популяция состоит из фиксированного числа тестовых последовательностей, возможно, различной длины (рис. 2.8 б). Для выбранного таким образом представления особей и популяций применяются генетические операторы скрещивания и мутации [25.3].

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

Классический одноточечный кроссинговер. В этом случае двоичная таблица интерпретируется одной двоичной строкой, которая получается в результате последовательной конкатенации ("склеивания") строк. Поскольку в оперативной памяти таблица представляется именно в таком виде, то этот тип кроссинговера имеет простую реализацию. Отметим, что часто используемый на практике оператор горизонтального кроссинговера,представленного на рис.2.\9, является частным случаем одноточечного кроссинговера.

Горизонтальный кроссинговер, где случайно выбирается момент времени $$k$$ (точка скрещивания) и родительские последовательности обмениваются подпоследовательностями после строки $$k$$, что показано на рис. 25.7а).

Вертикальный кроссинговер, представленный на рис. 25.7б), где обмен между родительскими особями производится случайно выбранными столбцами. Напомним, что столбец соответствует входной последовательностим, подаваемой на один вход схемы. Все "нестыковки" в данных операциях, которые образуются из-за различной длины участвующих особей, заполняются случайным образом. Также следует отметить, что при такой реализации длина особей-потомков могут как уменьшаться, так и увеличиваться. (рис 25.7) Операции горизонтального и вертикального скрещивания ГА

Свободный вертикальный кроссинговер представлен на рис. 25.8 и выполняется следующим образом. Для каждой строки $$k$$ (входного набора) родительських двоичных таблиц определяется своя точка скрещивания $$t_{k}$$. Затем каждая пара строк (двоичных входных наборов) обменивается подстроками после точки скрещивания $$t_{k}$$ , что показано на рис. 25.8. Отметим, что данная модификация является обобщением приведенного ранее вертикального кроссинговера (рис. 25.7). (рис 25.8) Свободный вертикальный кроссинговер

Однородный кроссинговер отличается от предыдущих видов. Здесь каждый ген потомка создается путем копирования соответствующего гена из первого или второго родителя, то есть каждая позиция потенциально является точкой кроссинговера. Для этого случайным образом генерируется двоичная маска кроссинговера той же длины (с тем числом бит), что у хромосом родителей. Четность бита маски показывает родителя, из которого копируется ген потомка. Для определенности допустим, что 1 соответствует первому родителю, а 0 - второму. На рис. 25.9 показана схема выполнения этого типа кроссинговера на конкретном примере. Каждый бит потомка копируется из 1-го или 2-го родителя в соответствии со значением этого бита маски. (рис 25.9) Однородный кроссинговер

Таким образом, здесь потомок содержит смесь генов из каждого родителя.

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

Итак, скрещивание реализуется в виде приведенных независимых операций скрещивания, выбор в процессе работы, между которыми, происходит с вероятностью $$P_{1}, P_{2},…, P_{6}$$, где значения $$P_{i }$$подбираются экспериментально и $$P_{1}+ P_{2}+ P_{3}+ P_{4}+ P_5+P_6=1$$.

Далее, как обычно к полученным потомкам применяются операторы мутации. Здесь также производится выбор одной из возможных операций:

Выбор между тремя операторами мутации также производится случайно с вероятностями $$P_{мут}_{1}$$ и $$P_{мут}_{2}$$ с распределением $$0<P_{мут}_{1}<P_{мут}_{2}<1$$.

25.4 Проблемно-ориентированные фитнесс-функции для генерации тестов

Поскольку целью генерации тестов является построение последовательности, на которой максимально отличаются значения сигналов в исправной и неисправной схемах, то качество тестовой последовательности (fitness-функция) оценивается как мера отличия значений сигналов в исправной и неисправной схемах. В программных системах генерации тестов используются различные fitness-функции, зависящие от следующих основных параметров, которые приведены в табл. 25.6.

Помимо них характеристики алгоритмов генерации тестов существенно зависят от стандартных параметров ГА таких как мощность популяции, вероятности репродукции, кроссинговера и мутации, числа поколений и т.д.

В системе CRIS [25.6] используется техника иерархического моделирования, сокращающая затраты памяти и позволяющая обрабатывать схемы большой размерности. Здесь применяется традиционный ГА, в котором популяции эволюционируют посредством операторов мутации и кроссинговера. В качестве особи берется последовательность входных наборов. Система CRIS основывается прежде всего на непрерывной мутации данной входной тестовой последовательности и анализе мутировавших наборов путем моделирования, в основном, исправных схем с целью определения тестового множества. Данная система показала хорошие результаты при построении тестов с высоким уровнем покрытия неисправностей в комбинационных и последовательностных схемах большой размерности. Однако данный подход имеет существенный недостаток - "ручную" подстройку параметров ГА для каждой схемы.

Система GATEST [25.4] ориентирована на последовательностные логические схемы и основана на двухуровневом ГА: на нижнем уровне с помощью ГА строятся входные наборы, а далее ГА применяется для генерации входных последовательностей на основе полученных наборов. Соответственно, на нижнем уровне особью является входной вектор, а на верхнем - входная последовательность. В ГА применяются различные виды операторов кроссинговера: одноточечный, двухточечный, однородный. Первый уровень в свою очередь подразделяется на три фазы. Таким образом, в целом, метод образуют четыре фазы, которые определяют соответствующие различные оценочные функции:

В фазах 2-4 оценка особей выполняется с помощью моделирования неисправностей, что несколько замедляет работу GATEST. Система успешно применялась к последовательностным устройствам достаточно большой размерности и строила тесты в тех случаях, где детерминированный метод HITEC [25.1] не мог построить тесты. К недостаткам можно также отнести то, что разработчики вручную подбирают многие параметры ГА, включая размерность алфавита, размер популяции, уровень мутации.

Интересным является подход, представленный в работе [25.7] системой DIGATE. Он состоит из двух фаз:

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

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

В другой системе [25.5] GATTO в качестве особей также выбраны входные последовательности. Основное внимание авторы алгоритма уделяют определению эффективной оценочной функции, как меры удаленности особи от искомого оптимума. Особи оцениваются с помощью моделирования неисправностей из соображений увеличения активности неисправности в схеме (чем больше количество линий, на которых значения в исправной и неисправной схемах различны, тем больше вероятность обнаружения неисправности). Поэтому оценочная функция определяется тремя эвристическими параметрами: взвешенное количество вентилей с разными значениями в исправном и неисправном устройствах; взвешенное количество триггеров с разными значениями в исправном и неисправном устройствах; длина последовательности-особи, параметр $$L$$ используется для получения компактной тестовой последовательности. В качестве весов первых двух параметров используются соответствующие значения наблюдаемости. Таким образом, оценочная функция есть $$h_7=\max_s{L^i*h(v_i)}$$, где $$s$$ - особь-последовательность, $$v_i $$ - $$i$$-й вектор последовательности, $$h(v_i)$$ - сумма нормализованных первых двух параметров.

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

В системе АСМИД-Е [25.1] для повышения быстродействия алгоритма построения тестов в программную реализацию интегрированы две программы параллельного моделирования с неисправностями. Первая программа реализует параллельный по неисправностям метод моделирования и используется в фазе 1 для проверки активизации произвольной неисправности случайно генерированной последовательностью.

Для вычисления оценочной функции используется вторая программа моделирования с неисправностями, реализующая алгоритм "параллельного моделирования по тестовым наборам", и написанная специально для работы с генетическим алгоритмом построения тестов. После моделирования очередного тестового вектора происходит вычисление оценочной функции текущего вектора по формуле: $$h(v)=c_1N_d(v)+c_2T_d(v)$$, где $$v$$ - текущий входной набор. В качестве весов используются меры наблюдаемости схемы, вычисляемые на этапе предварительной обработки схемы. После того как для входной последовательности, моделируемой в определённом разряде, достигнута эффективная длина или произведено моделирование на последнем наборе вычисляется оценочная функция всей последовательности:

где $$s$$ - анализируемая последовательность; $$v_i$$ - вектор из рассматриваемой последовательности, $$i$$ - позиция вектора в последовательности, $$f$$ - заданная неисправность, $$LH$$ - предварительно заданная константа в диапазоне $$0<LH\le 1$$, благодаря которой предпочтение отдаётся более коротким последовательностям. Применение данного алгоритма существенно повышает скорость вычисления оценочных функций особей в популяции, а, следовательно, и скорость работы алгоритма в целом.

Наиболее эффективным является метод построения тестов, объединяющий преимущества структурного детерминированного и генетического алгоритмов генерации. При этом этапы внесения влияния неисправности и активизации путей до внешних выходов схемы выполняется детерминированным методом с применением многозначных алфавитов, а этап доопределения - поиска значений входов схемы, обеспечивающих требования, полученные на первых этапах, выполняется с помощью ГА. Перспективным является также использование параллельных ГА, в которых используются несколько популяций решений, которые параллельно эволюционируют, в основном, независимо друг от друга. Но время от времени между ними производится обмен лучшими решениями, который может выполняться по различным схемам. Сама природа задачи построения тестов является иерархической, поэтому в ней целесообразно использовать иерархические ГА, где на каждом уровне иерархии применяется свой ГА.

25.5 Реализация генетического алгоритма генерации тестов

Общий подход к тестированию заключается в следующем. Процесс генерации тестов содержит три фазы. Цель первой фазы - активизация неисправности, т.е. распространение рассогласования сигнала на псевдовыходы. На начальном этапе, когда необходимо как можно быстрее активизировать и проверить большее число неисправностей, используется псевдослучайный метод генерации тестовых последовательностей. На втором этапе для повышения эффективности процесса активизации неисправностей используется генетический алгоритм. После того, как в первой фазе активизирована какая-либо неисправность, необходимо улучшить полученную активизирующую последовательность так, чтобы она стала проверяющей. Для этого во второй фазе также используется генетический алгоритм. Фаза 2 является ядром всего алгоритма. После выполнения второй фазы в случае успешного результата - построения тестовой последовательности, необходимо произвести моделирование с неисправностями на данной последовательности (фаза три), чтобы обнаружить все неисправности, которые она проверяет. Укрупненный алгоритм в виде псевдокода представлен на рис. 25.10. Здесь переменная режим показывает, каким способом ведётся активизация неисправности: значение 0 соответствует псевдослучайному метод, 1 - генетическому алгоритму. Переменная метод показывает цель, для которой используется генетический алгоритм. При этом значение 0 соответствует активизации неисправности, а 1 - построению теста для активизированной неисправности.

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

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

где $$s$$ - анализируемая последовательность; $$v_{i}$$ - вектор из рассматриваемой последовательности, $$i$$ - позиция вектора в последовательности, $$f$$ - заданная неисправность, $$L$$ - предварительно заданная константа в диапазоне $$0<L\le 1$$, благодаря которой предпочтение отдаётся более коротким последовательностям. Здесь оценочная функция одного вектора из последовательности имеет вид:

где $$с_{1}$$ константа нормирования, равная отношению числа вентилей схемы к числу триггеров; $$f_{1}(v,f)$$ и $$f_{2}(v,f) $$ эвристические функции, определяющие:

В качестве веса выбирается мера наблюдаемости элемента схемы, вычисляемая на этапе предварительной обработки схемы. В алгоритме используется виды скрещивания, описанные выше, выбор между которыми производится случайно При горизонтальном скрещивании случайным образом в последовательностях-родителях выбираются точки разреза $$x_{1}$$ и $$x_{2}$$. Первый потомок получается соединением векторов первого родителя от начала последовательности до точки деления $$x_{1}$$ и второго родителя от точки деления $$x_{2}$$ до конца последовательности. Второй потомок получается аналогично при перемене мест первого и второго родителя. Вертикальное скрещивание производится не по наборам теста, а по входным сигналам схемы. Для получения потомка необходимо взять первый столбец из таблицы - теста первого родителя и случайным образом определить, будет ли он столбцом первого или второго потомка. Легко заметить, что при горизонтальном пересечении длина последовательностей-особей может, как уменьшаться, так и увеличиваться, тогда, как при вертикальном скрещивании длина обоих потомков станет равной длине большего из родителей. При этом все "пустоты", получаемые из-за разности длин заполняются случайными битами.

Механизм мутации обеспечивает появление новых генов в особях. Он применяется с заранее заданной вероятностью $$P_{m}$$ к результатам операции скрещивания. В алгоритме применяется три приведенные выше вида мутации, выбор между которыми происходит случайно.

Остановимся теперь подробнее на фазах алгоритма. Целью 1-й фазы является определение неисправности, которая может быть активизирована. При этом значения сигналов в присутствии неисправности, отличные от значений исправной схемы, могут быть распространены на внешние псевдовыходы. Для этого производится моделирование неисправностей для нескольких последовательностей. После этого выбирается лучшая из последовательностей. Если она активизировала какую-либо неисправность, то эта неисправность выбирается в качестве целевой неисправности и происходит переход во вторую фазу алгоритма. В начале работы алгоритма в качестве лучшей последовательности выбирается та, которая обнаружила больше неисправностей. При этом, за несколько проходов моделирования строится тест для большинства легко тестируемых неисправностей. На более поздних этапах в качестве лучшей последовательности выбирается та, которая активизировала наибольшее число неисправностей или произвела наибольшую активность сигналов (изменений) в схеме. Для этой цели также используется генетический алгоритм. При этом оценочные функции будут аналогичны тем, которые используются в фазе 2, поскольку несут ту же смысловую нагрузку. Метод активизации неисправностей в алгоритме показывает переменная режим. Длина последовательностей в фазе 1 в начальный момент считается заданной, а далее полагается равной длине проверяющей последовательности, сгенерированной в фазе 2 алгоритма.

Целью 2-й фазы является улучшение активизирующей последовательность таким образом, чтобы она стала проверяющей для целевой неисправности. Эта фаза является ключевой в алгоритме. Её псевдокод приведён на рис. 25.11. Здесь $$P$$ - текущая популяция, которая в начальный момент инициализируется особями из фазы 1 алгоритма, $$newP $$- следующее поколение, $$s$$ - две новых последовательности, получаемых в результате операции скрещивания. Вычисление новых популяций производится ограниченное число раз (MAX_ПОКОЛЕНИЙ). Если за это время тестовая последовательность не найдена, то целевая неисправность отмечается, как непроверяемая и больше не может быть вновь выбрана в качестве цели генетического алгоритма.

Поиск_проверяющей_последовательности(неисправность-цель)
\{
  for( i=0 ; i<MAX_ПОКОЛЕНИЙ ; i++)
  \{
    for( каждой особи s в популяции P )
      вычислить_оценку(s, f );
    newP=*;
    for( k=0 ; k<ЧИСЛО_НОВЫХ_ОСОБЕЙ ; k++ )
    \{
      выбрать_две_последовательности_в_P();
      применить_операцию_скрещивания();//генерируются две особи 
      применить_операцию_мутации_к_s_c_вероятностью_P_{m}();
      newP=newP*s;
    \}
    P=(лучшие MAX_ОСОБЕЙ из newP и P )
    for( каждой особи s в популяции P )
      if( s обнаруживает f )
        return s;
  \}
  return( НЕТ_ПОСЛЕДОВАТЕЛЬНОСТИ )
\}

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

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

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

Ключевые термины:

Генетический алгоритм - алгоритм поиска решения, основанный на принципах, сходных с принципами естественного отбора..

Особь - потенциальное решение рассматриваемой проблемы.

Популяции - множество особей - потенциальных решений.

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

Мутация - генетический оператор, где с малой вероятностью случайно изменяется значение гена.

Фитнесс-функция - характеризует качество потенциального решения проблемы.

Краткие итоги

В лекции рассмотрено применение генетического алгоритма к решению задачи построения проверяющих тестов.

В разделе 25.1 изложены основные понятия простого генетического алгоритма, определены основные генетические операторы репродукции, кроссинговера и мутации.

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

Раздел 25.3 описывает применение ГА для построения тестов последовательностной схемы. Здесь в качестве особе выступает тестовая последовательность и генетические операторы кроссинговера и мутации определены над двоичными таблицами.

В разделе 25.4 приведены основные виды фитнесс-функций, которые используются для оценки качества потенциальных решений при построении проверяющих тестов.

Раздел 25.5 посвящен вопросам реализации генетического алгоритма построения проверяющих тестов, изложены основные этапы генерации тестов.

Вопросы и упражнения