Тестирование софта - статьи
ce076b8f

Простейший алгоритм


Рассмотрим простейший генетический алгоритм для решения задачи 1. В качестве множества кандидатов возьмём множество Σ; в качестве оценочной функции возьмём метрику тестового покрытия

для заданной тестируемой системы S. Условием останова будет наличие в текущем поколении решения
, удовлетворяющего критерию . Структуру представления кандидатов, а также операторы кроссовера и мутации мы пока уточнять не будем.

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

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

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

Содержание раздела