GENETIC ALGORITHM IN PATH TESTING

Path testing searches the program domain for suitable test cases that covers every possible path in the software under
test SUT. However, it is generally impossible to achieve this goal, for several reasons. First, a program may contain
an infinite number of paths when the program has loops. Second, the number of paths in a program is exponential to
the number of branches in it and many of them may be unfeasible .Third, the number of test cases is too large, since
each path can be covered by several test cases.
Our algorithm works on control flow graph. CFG is a simple notation for the representation of control flow. An
independent path is any path through the program that introduces at least one new set of processing statements or a
new condition. When stated in terms of a flow graph an independent path must move along at least edge that has not
been traversed before the path is defined [5].
Genetic Algorithm:

1. Initialize the population randomly.

2. Determine the fitness of the chromosome.
3. Until done repeat:
1. Select parents.
2. Perform crossover and mutation.
3. Calculate the fitness of the new po
 Start

Create initial population in each mode

Select and reproduce best individul

Generalize new offspring by applying crossover ,

hypercrossover , mutation and hypermutation

Evaluate fitness for each individual

NO

Reach the generation size

YES

Output non - dominated individual

Stop

pulation.
4. Append it to the gene pool.
Pseudo-code

Initialize procedure GA{

Set cooling parameter = 0;
Evaluate population P(t);
While( Not Done ){
Parents(t) = Select_Parents(P(t));
Offspring(t) = Procreate(P(t));
p(t+1) = Select_Survivors(P(t), Offspring(t));
t = t + 1;
}
}

3.1 Procedure to perform path testing:-

Input- CFG of the code, assigning weights to edges of CFG – The first step of algorithm is assigning weights to
CFG. More weights are assigned to edges which are critical so to say, that are part of paths which are more error
prone.
3.1.1. Rank-based roulette wheel selection

Rank-based roulette wheel selection is the selection strategy where the probability of a chromosome being selected
is based on its fitness rank relative to the entire population. Rank-based selection schemes first sort individuals in
the population according to their fitness and then computes selection probabilities according to their ranks rather
than fitness values. Hence rank-based selection can maintain a constant pressure in the evolutionary search where it
introduces a uniform scaling across the population and is not influenced by super-individuals or the spreading of
fitness values at all as in proportional selection.
For linear rank-based selection, the biasness could be controlled through the selective pressure SP, such that and the
expected sampling rate of the best individual is SP, the expected sampling rate of the worst individual is 2-
SP.Consider n the number of individuals in the population, Pos the position of an individual in the population least
fit individual has Pos 1, the fittest individual Pos n.
3.1.2. Reproduction
In one-point or single crossover, two input data selected as potential parents by selection process exchange
substring information at a random position in the data to produce two new Data
3.1.3. Mutation
Mutation is performed on a bit-by-bit basis. Every bit of every chromosome in the offspring has an equal chance to
mutate change from ‘0’ to ‘1’ or from ‘1’ to ‘0’, and the mutation occurs according to a mutation probability pm,
which is also an adjustable parameter [6][7].
. CONCLUSION & FUTURE SCOPE

Here presents a method for optimizing computer software effectiveness that is testing determining the absolute most
critical course clusters in a program. We do that by building size this is certainly adjustable Algorithms that optimize
and choose the program road groups which are weighted prior to the criticality of the path. Exhaustive software
testing is seldom feasible given that it becomes intractable even for medium sized software. The Genetic Algorithms
additionally outperforms the search that is exhaustive regional search strategies. In conclusion, by examining the
most critical routes first, we get a far more way that is effective method evaluating which often helps to refine
energy and value estimation within the examination phase. Our experiments performed up to now derive from fairly
tiny examples and much more research should be carried out with bigger instances which can be commercial. Future
research will involve contrasting GA selected paths in bigger test information and refining that is further method
provided. This research would help in generating software that is numerous instances. Additionally, since GA may
be used independently for just about any issue and it is a field this is certainly emerging this has great significance
for people.
Our work this is certainly future is towards performing more complex experiments using some real programs
determine the effectiveness of our method .We are going to use our recommended approach for generating the
necessary paths to cover other control-flow and data-flow criteria. Then, we will use GA for creating test data for
address all of the basis test paths. In inclusion, our future work will direct to make use of another method this is
certainly search-based as Practical Swarm Optimization Algorithm to create test routes for many control-flow and
data-flow criteria and compare the performance of GA with the performance of PSO in producing test paths.
REFERENCES
[1] BindiaTarika, Review on Software Testing Techniques, International Journal on Recent and Innovation Trends
in Computing and Communication, Volume 2, Issue 1,2014
[2] Gaurav Kumar Srivastav, Dileram Bansal, Manoj Kumar Sharma, Overview on Software Testing Methodology,
International Journal of Engineering and Technical Research, Special Issue,2014
[3] Jinkal Javia, Arpita Gupta, Sapan Gandhi, Optimization in Software Testing using Genetic
Algorithm ,International Journal of Scientific & Engineering Research, Volume 5, Issue 7, 2014
[4] AbhishekSinghal, Swati Chandna, Abhay Bansal, Optimization of Test Cases Using Genetic
Algorithm ,International Journal of Emerging Technology and Advanced Engineering , Volume 2, Issue 3,2012
[5] Praveen Ranjan Srivastava and Tai-hoon Kim ,Application of Genetic Algorithm in Software
Testing ,international Journal of Software Engineering and Its Applications Volume 3,Issue 4,2009
[6] Rakesh Kumar, Surjeet Singh, Girdhar Gopal, Automatic Test Case Generation Using Genetic Algorithm,
International Journal of Scientific & Engineering Research, Volume 4, Issue 6,2013
[7] Chayanika Sharma, Sangeeta Sabharwal, Ritu Sibal ,Software Testing Techniques using Genetic Algorithm,
IJCSI International Journal of Computer Science Issues, Volume 10, Issue 1,2013
[8] S. Keshavarz and Reza Javidan, Software Quality Control Based on Genetic Algorithm International Journal of
Computer Theory and Engineering, Volume 3,Issue 4,2011
[9] Poonam Saini, Sanjay Tyagi, Test Data Generation for Basis Path Testing Using Genetic Algorithm and Clonal
Selection Algorithm, International Journal of Science and Research (IJSR),Volume 3 Issue 6,2014
[10] Moheb R. Girgis, Automatic Test Data Generation for Data Flow Testing, Using a Genetic Algorithm, Journal
of Universal Computer Science, volume 11, Issue 6,2005
[11] Mark Last, Shay Eyal, and Abraham Kandel, Effective Black-Box Testing with Genetic Algorithms,
Department of Computer Science and Engineering, Ben-Gurion University of the Negev, Beer-Sheva,Israel,2005
[12] Arvinder Kaur et al., A Genetic Algorithm for Regression Test Cases Prioritization Using Code Coverage,
International Journal on Computer Science and Engineering, Volume 3,Issue 5,2011
[13] R.Krishnamoorthi and S.A.Sahaaya ,Arul Mary, Regression Test Suite Prioritization using Genetic Algorithms,
International Journal of Hybrid Information Technology, Volume 2,Issue 3, 2009