📄 029-032.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:Image-Calibration Transformation Matrix Solution Using 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=2//-->
<!--PAGES=029-032//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="025-029.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="032-034.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B>GA RESULTS</B></FONT></P>
<P>The sixteen test images were used to test the performance of the GA code. Each image was used as the reference, with the GA mapping the other sixteen images into the image-space of the reference. This provided a sampling of 256 different image mappings, including each image being used as a reference for itself, which should result in a transformation being the identity matrix.
</P>
<TABLE WIDTH="100%" BORDER><CAPTION ALIGN=LEFT><B>Table 2.7</B> Parameters used for the GA.
<TR>
<TD WIDTH="80%">Number of bits for each delta value
<TD WIDTH="20%">10
<TR>
<TD>Use gray-code encoding
<TD>False
<TR>
<TD>Maximum generation
<TD>17,000
<TR>
<TD>Population size
<TD>40
<TR>
<TD>Percent chance of 1-point crossover
<TD>20%
<TR>
<TD>Percent chance of 2-point crossover
<TD>40%
<TR>
<TD>Percent chance of matrix-element crossover
<TD>40%
<TR>
<TD>Percent chance of mutation
<TD>0.0002%
<TR>
<TD>Number of no-change generations before comet-hit
<TD>20
<TR>
<TD>Hill-climbing iterations per generation
<TD>50
</TABLE>
<P><FONT SIZE="+1"><B><I>Parameter Notes</I></B></FONT></P>
<P>The choice of 17,000 generations was chosen to give an average time of about 20 seconds if the GA did not converge.
</P>
<P><FONT SIZE="+1"><B><I>Test-case Details</I></B></FONT></P>
<P>After a study of the problem, the originally stated target of 0.1 for the distance value was not required. A value of 0.4 is within the acceptable range for this problem. To provide a fair comparison, the original algorithm was also run with this relaxed distance target; with a resulting average per-run time of 20.0 seconds-with every value below the specified 0.4 figure. It should be noted that the time variance in the original method was very small; each run took the same time within a 10% tolerance.
</P>
<P>The 256 test-case transformations were run ten times each, for a total of 2560 GA-based transformations. Table 2.8 shows the results looking at CPU time, GA generations, and the final fitness-function value (the sum of the distances squared). This value is considered by itself, and also as the best and the worst for each of the ten runs for an image pair.</P>
<TABLE WIDTH="100%" BORDER><CAPTION ALIGN=LEFT><B>Table 2.8</B> Summary of results from the GA run.
<TR>
<TH WIDTH="40%" ALIGN="LEFT">Measure
<TH WIDTH="20%" ALIGN="LEFT">Minimum
<TH WIDTH="20%" ALIGN="LEFT">Average
<TH WIDTH="20%" ALIGN="LEFT">Maximum
<TR>
<TD>CPU Time
<TD>0.09 S
<TD>13.5 S
<TD>39.9 S
<TR>
<TD>Generations
<TD>62
<TD>11,359
<TD>17,000
<TR>
<TD>(Sum of Distances)<SUP><SMALL>2</SMALL></SUP>
<TD>0.143
<TD>0.664
<TD>2.89
<TR>
<TD>Best of 10 Sums
<TD>0.143
<TD>0.40
<TD>0.99
<TR>
<TD>Worst of 10 Sums
<TD>0.40
<TD>1.07
<TD>2.89
</TABLE>
<P>Another look at the resulting data, Figure 2.11, shows the number of runs resulting in ranges of distance values; the tallest bar is in the range from 0.3 to 0.4.
</P>
<P><A NAME="Fig11"></A><A HREF="javascript:displayWindow('images/02-11.jpg',500,249)"><IMG SRC="images/02-11t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/02-11.jpg',500,249)"><FONT COLOR="#000077"><B>Figure 2.11</B></FONT></A> Distance results of the 2560 test-case runs.</P>
<P>Examining the data as a whole, the GA algorithm ran in 9.6 hours versus 14.2 hours for the non-GA method. This is a reduction of 32% in time. The final values achieved did not fare as well, with an average convergence value of 0.664, 66% higher than the specified 0.4 value. As seen in Figure 2.11, over 1,028 runs achieved the 0.4 goal, with 50 of them jumping from above 0.4 to below 0.3 in a single generation-thus 42% of the runs achieved the specified 0.4 goal. The remaining 1,482 runs (58%) did not achieve the 0.4 goal, and are distributed in value ranges in decreasing amounts, with a single run at the largest final value of 2.89.
</P>
<P>Looking at select individuals, there were some GA runs which finished in less than 100 mS. Figure 2.12 shows that 17.5% of the runs completed in less than 2.0 seconds and 29% of the runs completed in less than 4.0 seconds. The majority of the runs, 59%, completed in the range of 19.5 to 20.5 seconds. These results indicate that, if “lucky”, the GA algorithm will converge in a few seconds, but once the 2.0 second mark is passed, the chance that the GA will converge decreases, until at about 20 seconds the maximum generation count is reached. This timing spread results in an average run time of 13.5 seconds, with two groups: one around 2.0 seconds and a tighter group at 20 seconds.</P>
<P><A NAME="Fig12"></A><A HREF="javascript:displayWindow('images/02-12.jpg',500,278)"><IMG SRC="images/02-12t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/02-12.jpg',500,278)"><FONT COLOR="#000077"><B>Figure 2.12</B></FONT></A> Time results of the 2560 test-case runs.</P>
<P>The correlation between Figures 2.11 and 2.12 is that the 1,078 runs which achieved the distance goal in Figure 2.11 are spread out from 0 to 19 seconds in Figure 2.12, and the 1,482 runs around 20 seconds in Figure 2.12 are spread out above the distance of 0.4 in Figure 2.11. This led to the idea of implementing a Total-Comet-Strike every 4.0 seconds (0.2 * the maximum-generations), to take advantage of a completely fresh gene-pool, thinking that maintaining the best performer overshadowed a new comet-strike generated population and remaining in the area of the local minimum already found. This is essentially running five sequential GAs with MG = MG/5, with the run terminating if any of these sub-runs reaches the convergence value. Preliminary results implementing this additional capability look very promising, with an initial result over thirty-five runs as presented in Table 2.9. All three averages, CPU time, generations, and distance value, have improved from 2.1 to 6.4 percent. The downside is that the maximum distance value has grown to 4.8.
</P>
<TABLE WIDTH="100%" BORDER><CAPTION ALIGN=LEFT><B>Table 2.9</B> Summary of results from the GA run.
<TR>
<TH WIDTH="40%" ALIGN="LEFT">Measure
<TH WIDTH="20%" ALIGN="LEFT">Minimum
<TH WIDTH="20%" ALIGN="LEFT">Average
<TH WIDTH="20%" ALIGN="LEFT">Maximum
<TR>
<TD>CPU Time
<TD>1.37 S
<TD>12.9 S
<TD>20.9 S
<TR>
<TD>Generations
<TD>1139
<TD>10,628
<TD>17,000
<TR>
<TD>(Sum of Distances)<SUP>2</SUP>
<TD>0.32
<TD>0.64
<TD>4.8
</TABLE>
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="025-029.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="032-034.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 + -