많은 목적 지향 테스트 데이터 생성 방법들이 진화 알고리즘 (Evolutionary Algorithm, EA) 에 바탕을 두고 있습니다 . 진화 알고리즘은 자연세계의 진화과정을 모델링하여 복잡한 실세계의 문제를 해결하고자 하는 계산모델입니다 . 진화 알고리즘은 구조가 간단하고 방법이 일반적이어서 응용범위가 매우 넓으며 , 특히 적응적 탐색과 학습 및 최적화를 통한 공학적인 문제의 해결에 많이 이용되고 있습니다 . 진화 알고리즘을 이용하여 테스트 데이터를 생성하는 방법을 진화 테스팅 (Evolutionary Testing, ET) 라 합니다 .
ET 는 후보 테스트 데이터와 원하는 테스트 데이터간의 차이를 평가하기 위해 적합성 함수 (fitness function) 를 이용합니다 [3]. 예를 들면 , 어떤 프로그램에서 x==5 인 분기 조건이 참이 되게 하는 테스트 데이터를 구하는 문제를 생각해 봅니다 . 이와 같은 분기 조건은 F(x) = |5-x| 와 같은 함수로 간주합니다 . 이때 함수 F(x) 를 최소화하는 입력 데이터 x 는 분기 조건 x==5 를 참이 되게 하는 입력 값이 원하는 테스트 데이터가 됩니다 . 여기에서 분기 조건 x==5 의 분기 거리 (branch distance) 는 |5-x| 로 정의되며 해당 분기가 참이 되기 위해 얼마나 가까이 접근했는지를 나타냅니다 . 예를 들면 x 가 7 과 10 을 각각 가졌을 경우에 분기 거리는 2 와 5 가 됩니다 . 이는 x 가 7 일 때 10 인 경우 보다 분기 조건 x==5 을 참이 되게 하는 경우에 보다 더 가까이 접근했음을 의미합니다 . 만약 탐색 알고리즘이 10 을 먼저 생성하였다면 이를 감소하는 방향으로 탐색을 진행할 것입니다 .
