Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи Институт прикладной математики и механики НАН Украины Донецкий национальный технический Университет

2 Содержание Существующие подходы к задаче построения инициализирующих последовательностей; Общая схема предлагаемого подхода Избыточная генерация тестов Предварительная оценка качества тестов Выбор оптимального подмножества Симуляция отжига: основные понятия Экспериментальные данные Заключение Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

3 Построение тестов с минимальным рассеиванием тепла Основные подходы: добавление метрики в существующий алгоритмы; пересортировка векторов в уже построенном тесте; Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

4 Предлагаемый трёхэтапный подход генерация избыточных тестовых последовательностей; предварительная оценка тестов на основе дополнительной метрики; выбор оптимального подмножества последовательностей; Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

5 1. Избыточная генерация тестов Определение. Неисправность f обнаруживается (проверяется) заданной последовательностью S={s1,s2,…sn} с избыточностью r, если существует не менее чем r подпоследовательностей, таких, что каждая из них проверяет неисправность f. При этом r называется фактором избыточности. Определение. Входная тестовая последовательность S обладает полной избыточностью r относительно множества неисправностей, если каждая неисправность заданного множества проверяется данной последовательностью не менее, чем r раз. Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

6 1. Избыточная генерация тестов Этап 1 решения задачи заключается в построении входной последовательности S={s1,s2,…sn} (набора подпоследовательностей), которая обладает требуемой избыточной полнотой при фиксированной избыточности r. При этом для каждой фиксированной неисправности гарантируется существование не менее r входных подпоследовательностей, принадлежащих S таких, что каждая из них обнаруживает данную неисправность. Гарантирование избыточности для некоторой неисправности позволяет в дальнейшем в зависимости от целей задачи выбирать ту или иную из последовательностей. Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

7 1. Избыточная генерация тестов для решения задачи адаптирован существующий ГА построения тестов: - неисправность удаляется из списка, если она проверилась заданное число раз; - в итоговой последовательности фиксируются начала каждой из подпоследовательностей; Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

8 2. Оценка рассеивания тепла Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

9 2. Оценка рассеивания тепла для решения задачи адаптирован существующий алгоритм событийного моделирования последовательностных схем: - моделирование работы схемы на заданной последовательности даёт параметр «активность вентилей»; - строится файл, в котором для каждой подпоследовательности приводится список проверяемых неисправностей и параметр рассеиваемой мощности; Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

10 3. Оценка рассеивания тепла Задача комбинаторной оптимизации - решается с помощью алгоритма симуляции отжига Этап 3 основан на алгоритме СО и заключается в выборе подмножества S из S последовательностей такого, что выполняются два следующих условия: Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

11 Симуляция отжига. Основные понятия. конфигурация Ki – потенциальное решение задачи: - требуется кодирование; функция стоимости C(Ki): - как хорошо конфигурация решает задачу; - вычисление функции стоимости: декодирование и расчёт; окружение конфигурации Ki: - возмущающие операции; Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

12 эвристические константы: - параметры температуры: начальная, конечная, шаг изменения; - число итераций для каждой температуры; - распределение вероятностей принять плохие изменения: Симуляция отжига. Основные понятия. Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

13 Симуляция отжига. Основной алгоритм. Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

14 Краткое сравнение СО и ГА Обе стратегии разработаны для решения NP-полных задач; Обе стратегии используют эволюцию свойств предварительных решений: - начальные решения строятся случайно; Новые решения строятся в результате модифицирующих операций: - отбор, скрещивание и мутация в ГА; - возмущающие операции в СО; Проблема кодирования решений и восстановления свойств из кодировки; Быстро вырождаются в неполиномиальные; Используют большое количество эвристик: - предельное число итераций; модифицирующие операции и вероятности их применения; критерии остановки и т.д. Проблема построения эффективной оценочной функции. Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

15 Симуляция отжига: кодирование конфигурации - в качестве конфигурации в предлагаемом алгоритме выступает множество номеров подпоследовательностей из S, которые фактически задают входную последовательность. Симуляция отжига: возмущающие операции -удаление номера последовательности; -добавление номера последовательности; -случайная замена номера последовательности. Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

16 Симуляция отжига: оценивающая функция -Фаза 1 алгоритма: выбор подмножества с максимальной полнотой: -Фаза 2 алгоритма: минимизация рассеивания тепла: Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

17 Псевдокод алгоритма СО симуляция_отжига(описание_схемы, параметры) { K 0 =построение_начальной_конфигурации(); T i =T нач ; пока( T i >T кон ) { K пром =выбрать_конф._из_окружения(K i ); C пром =C(K пром ); если( цель_достигнута(C пром ) ) { решение=K пром ; возврат; } C i =C пром -C i ; если( C i >0 ) K i+1= K пром ; иначе K i+1= K пром с вер. P( C i )=exp(- C i /kT i ); T i+1 =обновить(T i ); } решение=K i+1 ; } Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

18 Экспериментальные данные схемаполнота теста, % уменьшение рассеивания тепла, % время работы, сек s s s s s s

19 Функциональная диаграмма системы ASMID-E Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

20 Заключение 1.Предложен новый подход построения тестовых последовательностей с минимальным рассеиванием тепловой энергии. Подход состоит из трёх последовательных этапов: построение избыточной тестовой последовательности, оценка рассеивания тепла для каждой подпоследовательности, выбор оптимального множества подпоследовательностей.. 2.Для решения задачи третьего этапа предложено использовать алгоритм симуляции отжига. 3.Эффективность предложенного подхода демонстрируется на контрольных схемах ISCAS-89, при этом среднее уменьшение рассеивания тепла составило 86.34%, достигая 93.28% в лучших случаях. Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи

21 Спасибо за внимание! Связаться с авторами можно: Иванов Дмитрий Евгеньевич: Иванов Дмитрий Рамзи Зуауи: Рамзи Эволюционный подход построения оптимизированных входных тестов Д.Е. Иванов, Р.Зуауи