📄 022-025.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=022-025//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="020-022.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="025-029.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>The data calculated in Table 2.6 shows the effect of increasing the number of bits used in the delta coding. A simple linear mapping from the minimum to the maximum value for each matrix location is used. The concern here is that if N is too small, then a good T21 cannot be found because, as the delta is incremented from one possible value to the next possible value, the requisite value is bypassed.
</P>
<TABLE WIDTH="100%" BORDER><CAPTION ALIGN=LEFT><B>Table 2.6</B> Resulting coarseness calculated for different numbers of bits.
<TR>
<TH WIDTH="12%" ALIGN="LEFT" ROWSPAN="2" VALIGN="TOP">Range
<TH ALIGN="LEFT" COLSPAN="7">Coarseness
<TR>
<TH WIDTH="13%" ALIGN="LEFT">N=4
<TH WIDTH="12%" ALIGN="LEFT">N=8
<TH WIDTH="13%" ALIGN="LEFT">N=12
<TH WIDTH="12%" ALIGN="LEFT">N=16
<TH WIDTH="13%" ALIGN="LEFT">N=20
<TH WIDTH="12%" ALIGN="LEFT">N=24
<TH WIDTH="13%" ALIGN="LEFT">N=28
<TR>
<TD>0.031
<TD>0.002
<TD>8.1E-06
<TD>1.9E-09
<TD>3.0E-14
<TD>2.8E-20
<TD>1.7E-27
<TD>6.4E-36
<TR>
<TD>0.0197
<TD>0.001
<TD>5.1E-06
<TD>1.2E-09
<TD>1.9E-14
<TD>1.8E-20
<TD>1.0E-27
<TD>4.0E-36
<TR>
<TD>0.0001
<TD>9.6E-06
<TD>3.7E-08
<TD>9.1E-12
<TD>1.4E-16
<TD>1.3E-22
<TD>7.9E-30
<TD>2.9E-38
<TR>
<TD>0.078
<TD>0.005
<TD>2.0E-05
<TD>4.9E-09
<TD>7.6E-14
<TD>7.2E-20
<TD>4.3E-27
<TD>1.6E-35
<TR>
<TD>0.033
<TD>0.002
<TD>8.7E-06
<TD>2.1E-09
<TD>3.2E-14
<TD>3.1E-20
<TD>1.8E-27
<TD>6.8E-36
<TR>
<TD>0.0001
<TD>6.8E-06
<TD>2.6E-08
<TD>6.5E-12
<TD>1E-16
<TD>9.5E-23
<TD>5.7-30
<TD>2.1E-38
<TR>
<TD>6.9
<TD>0.46
<TD>0.018
<TD>4.4E-07
<TD>6.7E-12
<TD>6.4E-18
<TD>3.8E-25
<TD>1.4E-33
<TR>
<TD>7.8
<TD>0.52
<TD>0.020
<TD>4.9E-07
<TD>7.6E-12
<TD>7.2E-18
<TD>4.3E-25
<TD>1.6E-33
<TR>
<TD>0.044
<TD>0.0029
<TD>1.1E-05
<TD>2.8E-09
<TD>4.2E-14
<TD>4.0E-20
<TD>2.4E-27
<TD>9.0E-36
</TABLE>
<P>To allow the needed value to be approximated to an acceptable degree, the number of bits-per-value can be increased. Increasing N, however, will increase the search-space of the problem. Given nine matrix values to search on, for each 1-bit increase in N, there is a 2<SUP>9</SUP>, or 512 times increase in the size of the search space. To allow the GA to converge in a reasonable time, the search space should be kept small.</P>
<P><FONT SIZE="+1"><B>GA OPERATORS AND TECHNIQUES</B></FONT></P>
<P>In additional to the usual reproduction, crossover, and mutation GA operators [6], additional GA operators and techniques were designed and implemented for this specific problem. The entire set of GA operators implemented for this problem follow:
</P>
<P><FONT SIZE="+1"><B><I>Crossover</I></B></FONT></P>
<P>A simple 1-point crossover, as shown in Figure 2.5, is used which swaps the alleles (bit-patterns) in two selected parents at a given bit position. This bit position can be chosen anywhere within the strings, within a delta value as well as between delta values.
</P>
<P><A NAME="Fig5"></A><A HREF="javascript:displayWindow('images/02-05.jpg',500,72)"><IMG SRC="images/02-05t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/02-05.jpg',500,72)"><FONT COLOR="#000077"><B>Figure 2.5</B></FONT></A> Single point crossover.</P>
<P><FONT SIZE="+1"><B><I>Two-Point Crossover</I></B></FONT></P>
<P>A 2-point crossover, as shown in Figure 2.6, is used which swaps the alleles in two selected parents between two given bit positions. These bit positions can be chosen anywhere within the strings, within a delta value as well as between delta values. For this crossover, the string is considered to wrap back on itself in a ring-like fashion, which results in this 2-point crossover swapping a selection of the ring for two selected parents.
</P>
<P><A NAME="Fig6"></A><A HREF="javascript:displayWindow('images/02-06.jpg',500,72)"><IMG SRC="images/02-06t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/02-06.jpg',500,72)"><FONT COLOR="#000077"><B>Figure 2.6</B></FONT></A> Two-point crossover.</P>
<P><FONT SIZE="+1"><B><I>Matrix-Element Crossover</I></B></FONT></P>
<P>Wallet, et al. [3] inspired the use a matrix-element crossover operator, as seen in Figure 2.7. Their technique of selecting a contiguous sub-region of the 4×4 matrix was expanded to select a number of matrix elements which were related for this specific problem. Templates in the code were designed to define different matrix elements to be used for the eight different matrix-element crossovers possibilities desired. When the matrix-element crossover was selected, one of these templates was then selected and used to accomplish the crossover.
</P>
<P><A NAME="Fig7"></A><A HREF="javascript:displayWindow('images/02-07.jpg',500,106)"><IMG SRC="images/02-07t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/02-07.jpg',500,106)"><FONT COLOR="#000077"><B>Figure 2.7</B></FONT></A> Matrix-element crossover.</P>
<P>The matrix-element crossover swaps selected matrix elements between two selected parents. These swaps are done on full N-bit matrix elements within the strings and does not mix string values within a given matrix element. Figure 2.8 shows the eight matrix-element templates implemented here. The odd templates fit within the Wallet scheme, while the even-numbered templates show the extension to the Wallet scheme. The templates correspond to transformation operators: (1) Z rotation, (2) Z rotation with homogeneous coordinate scaling, (3) X and Y translation, (4) X and Y translation and perspective, (5) X and Y perspective, (6) X and Y scaling, (7) X and Y perspective with homogeneous coordinate scaling, and (8) X, Y, and Z scaling with homogeneous coordinate scaling.
</P>
<P><A NAME="Fig8"></A><A HREF="javascript:displayWindow('images/02-08.jpg',500,256)"><IMG SRC="images/02-08t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/02-08.jpg',500,256)"><FONT COLOR="#000077"><B>Figure 2.8</B></FONT></A> Eight matrix-element crossover templates.</P>
<P><FONT SIZE="+1"><B><I>Maintaining the Best Performer</I></B></FONT></P>
<P>Similar to De Jong’s generation-gap idea, the best performer of each generation is copied as-is to the next generation. This guarantees that the solution as found by the GA will not get worse over time. This approach is known as elitist selection.
</P>
<P><FONT SIZE="+1"><B><I>Varying Mutation Rate</I></B></FONT></P>
<P>The classic GA implementation uses a fixed mutation-rate. Being concerned with a timely solution, GA stagnation was studied very closely. GA stagnation is defined as the number of generations in which the best performer remains the same, as guaranteed above. One stagnation related solution was to impose an increasing mutation rate (Ms), which is the product of the no-change generation count (NC) and the mutation rate (MR): Ms = NC * MR. This results in ever-increasing chances for mutation to change the best performer in a positive direction.
</P>
<P><FONT SIZE="+1"><B><I>Comet-Strike Operator</I></B></FONT></P>
<P>Another GA stagnation operation is, as coined by Robert Dain [7], the Comet-Strike. The analogy is that of a comet striking the earth, which reeks havoc with the ecosystem and destroys all but the most robust of life. Following the comet-strike, new species evolve. The GA equivalent is to maintain the best performer and re-initialize the remaining population. The comet-strike operator is invoked when the no-change generation count (NC) goes above a set threshold and the average/minimum value is less than M (the bulk of the population consists of similar genetic material).
</P>
<P><FONT SIZE="+1"><B><I>Total-Comet-Strike Operator</I></B></FONT></P>
<P>A total-comet-strike operator is a re-initialization of the entire population. For this problem, and possibly other real-time GA problems, this operator allows the GA run to result in a better solution at the end of the imposed time-limit.
</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="020-022.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="025-029.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 + -