📄 059-062.html
字号:
<HTML>
<HEAD>
<META name=vsisbn content="0849398010">
<META name=vstitle content="Industrial Applications of Genetic Algorithms">
<META name=vsauthor content="Charles Karr; L. Michael Freeman">
<META name=vsimprint content="CRC Press">
<META name=vspublisher content="CRC Press LLC">
<META name=vspubdate content="12/01/98">
<META name=vscategory content="Web and Software Development: Artificial Intelligence: Other">
<TITLE>Industrial Applications of Genetic Algorithms:Software Test Data Generation from a Genetic Algorithm</TITLE>
<!-- HEADER -->
<STYLE type="text/css">
<!--
A:hover {
color : Red;
}
-->
</STYLE>
<META NAME="ROBOTS" CONTENT="NOINDEX, NOFOLLOW">
<!--ISBN=0849398010//-->
<!--TITLE=Industrial Applications of Genetic Algorithms//-->
<!--AUTHOR=Charles Karr//-->
<!--AUTHOR=L. Michael Freeman//-->
<!--PUBLISHER=CRC Press LLC//-->
<!--IMPRINT=CRC Press//-->
<!--CHAPTER=4//-->
<!--PAGES=059-062//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="054-059.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="063-066.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B>FITNESS FUNCTION</B></FONT></P>
<P>This chapter investigates two fitness functions. The first is described in Watkins [3] and is simply the reciprocal of the number of times a given path was executed. Throughout this chapter, the author has termed Watkins’ method the Inverse Path Probability (IPP) algorithm to help the reader keep track of the two fitness functions evaluated. The other fitness function is derived from the inverse probability of traversing the last code block in a path and is termed the Last Block Traversal Probability with Bonus, or LBTPB. Most of the work presented compares the performance of the IPP and LBTPB algorithms.
</P>
<P>An early alternative to the LBTPB algorithm was derived from calculating traversal probabilities for all edges in the control graph, which trace out the path of execution through the MUT. This produced fitness ratings similar to the probability of executing the last block of code in a given path. The LBTPB algorithm works well for trityp-easy because all paths will terminate with node 88, 95, 102, or 108. The LBTPB algorithm would fare worse if trityp-easy only had one common terminal code block while traversing unique portions of the module earlier in the MUT. This is not as serious an issue as it may seem because the LBTPB algorithm should be capable of being extended to reward unique nodes all along the path.</P>
<P>The path taken through the MUT represents the phenotype of that particular set of test data. The control graph was loaded into a graph data structure implemented as an adjacency list when the GA was initialized. (In the proposed utility, the parser would analyze the MUT and provide control graph initialization information to the genetic algorithm.) Counters in the control graph data structure were used to keep track of how many times each node and edge was traversed. Fitness was calculated after all individual sets of test data making up the population were evaluated.</P>
<P>The relationship between nodes of a graph is often described using the terms of parent and child. Parent nodes have directed edges to child nodes. Additional fitness was given to those sets of test data traversing a parent node having an untraversed child. This fitness bonus helps the genetic algorithm to search for unexplored sections of the MUT. Runs of the genetic algorithm using LBTPB fitness started out with a complete control graph, providing the knowledge needed to provide the bonus. Runs evaluating the IPP fitness algorithm built up the control graph as new nodes were discovered. The IPP algorithm was not made aware of the structure of the MUT and provided no bonus.</P>
<P>The following example illustrates how fitness was awarded. Figure 4.3 shows a sample code fragment and its control graph. The numbers next to the control graph’s edges represent traversal counts for that edge. In this example, test cases executing node 16 have not yet been found, making its traversal count zero. However, paths containing node 12, which is the parent to node 16, will receive the fitness bonus. A bonus value of 5 was used in these calculations. The following examples show how the LBTPB fitness may be calculated for the path 1-6-28 and a population size of 16.</P>
<P>The LBTPB algorithm yields a fitness of 2 for the path 1-6-28. The last node in the path (28) was traversed eight times.</P>
<P ALIGN="CENTER"><IMG SRC="images/04-01d.jpg"></P>
<P>The IPP fitness algorithm yields a much higher fitness of 8 for the same path.
</P>
<P ALIGN="CENTER"><IMG SRC="images/04-02d.jpg"></P>
<P>The IPP fitness algorithm yields a much higher fitness of 8 for the same path.
</P>
<P ALIGN="CENTER"><IMG SRC="images/04-03d.jpg"></P>
<P>Thus, for the same path, the IPP algorithm provides a high fitness of 8 while the LBTPB algorithm provides a low fitness of 2. This is an important trait of the LBTPB algorithm: it does not reward paths executing common sections of code. In this example, node 28 is shared among four paths: 1-6-28, 1-12-28, 1-12-16-28, and 1-22-28. For these four paths, fitness should be based on traversal counts of nodes 6, 12, 16, and 22. This matches well with the goal of this chapter - producing a set of test data executing every line of code at least once, without spending the tester’s time on redundant tests. Note that the LBTPB algorithm only looks at the last node. Future work will extend this fitness algorithm to reward traversal of unique nodes throughout the control graph, not just the terminal nodes.
</P>
<P>The two algorithms provide similar fitness scores for the path 1-12 (after LBTPB awards its bonus). Since node 12 is a parent to the untraversed node 16, paths including node 12 (paths 1-12 and 1-12-28) receive a fitness bonus. For path 1-12 the LBTPB fitness is calculated as:</P>
<P ALIGN="CENTER"><IMG SRC="images/04-04d.jpg"></P>
<P>The fitness bonus helps the genetic algorithm find untraversed sections of the module under test because descendants of test cases (GA individuals) which include such parent nodes have the best chance of finding untraversed child nodes. Table 4.2 summarizes fitness information for all paths in Figure 4.3.
</P>
<P><A NAME="Fig5"></A><A HREF="javascript:displayWindow('images/04-05.jpg',500,573)"><IMG SRC="images/04-05t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/04-05.jpg',500,573)"><FONT COLOR="#000077"><B>Figure 4.3a</B></FONT></A> Code example for fitness calculation.</P>
<P><A NAME="Fig6"></A><A HREF="javascript:displayWindow('images/04-06.jpg',350,521)"><IMG SRC="images/04-06t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/04-06.jpg',350,521)"><FONT COLOR="#000077"><B>Figure 4.3b</B></FONT></A> Control graph for fitness calculation.</P>
<TABLE WIDTH="100%" BORDER>
<CAPTION ALIGN=LEFT><B>Table 4.2</B> Comparison of IPP and LBTPB fitness.
<TR>
<TH WIDTH="15%" VALIGN="TOP" ALIGN="LEFT">Path
<TH WIDTH="5%" VALIGN="TOP" ALIGN="LEFT">#
<TH WIDTH="15%" VALIGN="TOP" ALIGN="LEFT">IPP
<TH WIDTH="15%" ALIGN="LEFT">LBTPB Before Bonus
<TH WIDTH="15%" VALIGN="TOP" ALIGN="LEFT">Bonus
<TH WIDTH="15%" VALIGN="TOP" ALIGN="LEFT">Total LBTPB
<TR>
<TD>1-6
<TD>3
<TD>5.33
<TD>3.2
<TD>0
<TD>3.2
<TR>
<TD>1-6-28
<TD>2
<TD>8.0
<TD>2.0
<TD>0
<TD>2.0
<TR>
<TD>1-12
<TD>2
<TD>8.0
<TD>3.2
<TD>5
<TD>8.2
<TR>
<TD>1-12-28
<TD>3
<TD>5.33
<TD>2.0
<TD>5
<TD>7.0
<TR>
<TD>1-12-16
<TD>0
<TD>N/A
<TD>N/A
<TD>N/A
<TD>N/A
<TR>
<TD>1-12-16-28
<TD>0
<TD>N/A
<TD>N/A
<TD>N/A
<TD>N/A
<TR>
<TD>1-22
<TD>3
<TD>5.33
<TD>2.67
<TD>0
<TD>2.67
<TR>
<TD>1-22-28
<TD>3
<TD>5.33
<TD>2.0
<TD>0
<TD>2.0
</TABLE>
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="054-059.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="063-066.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<hr width="90%" size="1" noshade>
<div align="center">
<font face="Verdana,sans-serif" size="1">Copyright © <a href="/reference/crc00001.html">CRC Press LLC</a></font>
</div>
<!-- all of the reference materials (books) have the footer and subfoot reveresed -->
<!-- reference_subfoot = footer -->
<!-- reference_footer = subfoot -->
</BODY>
</HTML>
<!-- END FOOTER -->
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -