В статье рассматриваются подход генерации тестов, основанный на генетических алгоритмах. Алгоритм разработан таким образом, что он позволяет прямое сравнение с псевдослучайными методами генерации тестовых воздействий. Экспериментальные результаты полученные по критериям ISCAS'85 [6] показывают, что предложенный алгоритм дают значительно лучшие результаты, чем аналогичный подходы опубликованные в работе [1]. Кроме того, тесты генерируемые с помощью данного алгоритма более компактны.
В данной работе мы представляем подход генерации тестов улучшенный с помощью генетических алгоритмов. В разделе 2 даётся описание алгоритма. Раздел 3 содержит экспериментальные результаты, которые показывают, что генетический подход превосходит подход основанный на генерации псевдослучайных последовательностей. По данным экспериментов, наш подход позволяет достичь лучшего покрытий и более компактного размера, чем тест CRIS генетический алгоритм, описанный в работе в работе [1].
Джон Холланд, основатель генетических алгоритмов, указал способность простых представлений (битовые строки) кодировать сложные структуры и способность несложных преобразований значительно улучшения эти тесты [3]. Он показал, что используя соответствующие структуры управления, можно быстро улучшить характеристики генерируемых тестов (при определенных преобразованиях), и заставить их изменятся на техже законах, на которых проходит эволюция животного мира. Важным результатом подчёркивает Холланд, что даже в больших и сложных проблемных областях, при определенных условиях, генетические алгоритмы будут, как правило, показывать оптимальные или близкие к ним результаты.
Для решения проблемы с точки зрения генетических алгоритмов необходимо описать следующие компоненты:
1) хромосомное представление решений проблемы
2) способ создания начальной популяции решений
3) функции оценки, которая играет роль окружающей среды, оценки качества решений с точки зрения их "годности"
4) генетические операторы, которые изменяют структуру "потомков" в период размножения
5) значения параметров, которые используются генетическим алгоритмом в ходе работы (численность населения, вероятности применения генетических операторов)
С точки зрения генетических алгоритмов, одно из возможных решений проблемы называется «особь». Также, как существует множество разных людей в обществе, существует и большое количество путей решения проблемы (1 более оптимальный, чем другие). Все решения, в совокупности образуют популяцию (множество). В контексте генерации тестов, один тест вектор, будет индивидуален , а набор тестовых векторов будет соответствовать популяции.
Первоначально, генерируется случайный набор тестовых векторов. Этот набор в дальнейшем обрабатывается системой, подвергается изменению. Такой способ инициализации, когда начальная популяция задаётся случайно, хорошо подходит для исследования. Переход от случайной популяции к хорошо популяции лучше соответствующей заданным условиям, позволяет лучше показать превосходства данного алгоритма, так как полученные в итоге тестовые вектора были получены с помощью алгоритма, а с помощью начальной инициализации. Полученное в результате множество, также может быть обработано с помощью данного алгоритма, для улучшения заданных свойств.
Оценка (fitness функция) позволяет оценить пригодность члена множества, для решения поставленной задачи. Лучшее решение будет получать более высокий балл. Функция оценки направляет населения к прогрессу, потому что хорошие решения (с высокой оценкой) будут отобраны во время процесса выбора решения, а решения с низкой оценкой будут отброшены. Для оценки пригодности тестов используется моделирование. Вектор с лучшими показателями отбирается и сохраняется для дальнейшей обработки. Тот факт, что из всей популяции отбирается один тест вектор, с лучшими показателями, гарантирует минимальный размер тестовой последовательности.
Так как в ходе эволюции решения начинают сходиться, то разница между fitness функциями может быть очень мала. Оптимальные решения не могут иметь значительную разницу при вычислении fitness функции от них. Алгоритм используем квадратичные значения для fitness функции, чтобы усилить разницу между ними.
Выбор необходим для нахождения двух (или более) кандидатов на скрещивание. На основе показателей качества (веса), будут выбраны лучшие вектора из всего тестового набора. Для выбора используется механизм, схожий с механизмом рулетки. Количество слотов в рулетке будет равно численности популяции. Размер гнезда рулетки пропорционален значению fitness функции для данного вектора. Это означает, что вектора с лучшими показателями будут иметь более высоки шансы быть выбранными. Если предположить, что размер популяции N, а N четное число, то существует N / 2 пар для скрещивания. Кандидаты в паре будет определяться, путём двукратного запуска рулетки. За один запуск определяется один кандидат. При таком выборе схемы может случиться, что же кандидат отбирается в два раза. Получение одинаковых генов является уместной ситуацией в данном случае. Это всего лишь означает, что выбранный вектор имеет хорошие показатели , и его характеристики должны перейти в новое поколение.
Обмен соответствующим генетическим материалом от двух хромосом родителей позволить полезным генам переходить в следующее поколение. Скрещивание является ключевым достоинством генетического алгоритма. Родители с наиболее успешными показателями чаще передают свои гены следующему поколению. Полезные свойства обоих родителей учитываются в генах вектора потомка.
Выбранная с помощью рулетки пара создаёт два новых вектора потомка, это происходит следующим образом: 1) определяется случайная позиция m в тестовом векторе, генерируя случайное число от 1 до L, при условии, что L длина вектор теста. 2) первые m бит от первого вектора кандидата копируются в первый новый вектор 3) первые m бит от второго вектора кандидата копируются во второй новый вектор 4) биты m + 1 ... L от первого вектора кандидата, копируются во второй новый вектор (в биты m + 1...L) 5) биты m + 1 ... L от второго вектора кандидата копируются в первый новый вектор (в биты m+1...L)
Случайные мутации вносят изменения в хромосомный набор вектора, и иногда эти изменения оказываются полезными для особи. Без мутации рано или поздно все особи в популяции станут одинаковыми, и это не позволит протекание прогресса . Популяция будем стремиться к локальному максимуму.
В целях поощрения разнообразия тестовых векторов и покрытия ими большего числа ошибок, мутации будут введены при операции скрещивания. Для каждого нового вектора, каждый бит может бить проинвертирован с определенной вероятностью р. Кроме того, можно использовать стратегию, при которой выбирается не вероятность, а позиция в которой точно произойдёт мутация, т.е. p = 1 для этой позиции. Это должно уменьшить количество вычислений. Однако эксперименты показали что это также снижает количество покрываемых ошибок. Таким образом, этот метод не рекомендован к использованию. Шаги 2.2 – 2.5 повторяются, пока все ошибки из списка ошибок не будут найдены или не будет достигнут предопределенный предел количества поколений. Испытание поколения также заканчивается, если достигнут максимум количества холостых векторов, не покрывающих ни одну неисправность. Количество таких векторов зависит от размера схемы и равна (Количество входов / const), где const постоянная задаваемая пользователем. Чем меньше значение const, тем более подробно мы будем искать. В текущей реализации, тест поколения работает в два этапа, с разной частотой мутаций.
1) В первом этапе, когда ещё существует много невыявленных ошибок и fitness функция для вектора в основном больше нуля, частота мутаций меньше (р = 0,1).
2) На втором этапе, когда остается только несколько незамеченных ошибок и ни один из векторов популяции не определяет их, невозможно сказать, какой вектор на самом деле лучше. В таком случае вероятность мутаций увеличивается (р = 0,5) для обеспечения большего разнообразия в популяции, что может позволить найти непокрытые ранее ошибки.
Эксперименты были отчасти призваны показать, насколько генетический подход лучше, чем псевдослучайный. Для того, чтобы достичь этого, генерация псевдослучайных тестов была проведена при тех же условиях. Численность популяции при испытании генетического алгоритма была установлена равной 32. Это компромисс между скоростью и количеством охвата ошибок. В каждом поколении, один вектор из 32 выбран в окончательный тестовый набор. Генератор случайных тест работал таким же образом. Он создает модели в упаковках по 32 вектора. Лучший вектор из пакета (на основе результатов моделирования) будет выбран, если он обнаруживает некоторые ранее не обнаружены ошибки. Таким образом, мы можем сравнить эти два метода адекватно. Сравнение выполнено с использованием пакета Turbo tester [8]. Эксперименты проводились с использованием схем ISCAS'85. Первые эксперименты показали, что меньшая длинна теста сгенерированного с помощью генетического алгоритма покрывает большее количество ошибок, по сравнению с псевдослучайным тестированием. Что касается трудно тестируемых схем c2670 и c7552, генетический метод отлавливает на 118 неисправностей больше чем псевдослучайные тесты в случае c2670 и на 33 ошибки больше в случае c7552. Время тестирования простых схем c432 и c499 с помощью псевдослучайного тестирования было немного короче.
Эффективность генетических алгоритмов проявляется в случае схем, которые имеют большое количество входов. Мы сравнили полученные результаты с теми, которые получены в работе [2]. Сравнение показало, что для схем c7552 и c2670 были найдены все ошибки, но для этого потребовалось почти в два раза меньше векторов тестов.
Кроме того, наши результаты были сопоставлены с генетическим подходом, описанным в работе [1]. Ключевой особенностью того метода является схема мониторинга деятельности. Простой подход приводимые здесь обнаруживает все неисправности за меньшее время для всех схем и генерирует в 1,6 - 6,5 раз меньше векторов, чем метод [1]. Для схем c2670 и c7552,сравнение некорректно, потому что в [1] генерации тестов была прекращена слишком рано.
[1] D. G. Saab, Y. G. Saab, J. A. Abraham, “CRIS: A test Cultivation Program for Sequential VLSI Circuits”, Intl. Conf. Computer-Aided Design, Nov. 1992, pp. 216-219.
[2] I. Pomeranz, S. M. Reddy, “On improving Genetic Optimization based Test Generation”, Proc. of European Design and Test Conference 1997, pp. 506-511
[3] J.H. Holland, “Adaptation in Natural and Artificial Systems”, University of Michigan Press, 1975
[4] E. M. Rudnick, J. H. Patel, G. S. Greenstein, T. M. Niermann “Sequential Circuit Generation in a Genetic Framework”, 31st ACM/IEEE Design Automation Conference
[5]Goldberg “Genetic algorithms”, Addison-Wesley USA,1991
[6] F. Berglez, H. Fujiwara, “A Neutral Netlist of 10 Combinational Benchmark Circuits and a Target Translator in Fortran”, Proc. of the Int. Test Conf., pp. 785-794, 1985.
[7] S. R. Ladd, “Genetic Algorithms in C++”, M&T Books, 1996
[8] R.Ubar, J.Raik, P.Paomets, E.Ivask, G.Jervan, A.Markus. “Low-Cost CAD System for Teaching Digital Test”, .Microelectronics Education. World Scientific Publishing Co. Pte. Ltd. pp. 185-188, Grenoble, France, Feb. 1996