📄 025-029.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=025-029//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="022-025.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="029-032.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B><I>Local Hill Climbing</I></B></FONT></P>
<P>A technique borrowed from the current image-calibration code is to take a “good” solution, and to try small permutation on the matrix values to get a better solution. This is done to the best performer as it is copied from one generation to the next. A GA parameter is used to set the maximum number of hill-climbing iterations, resulting in small hill-climbing steps per generation. If needed, a recurring best performer can continue to climb the same hill over many generations.
</P>
<P><FONT SIZE="+1"><B><I>Gray-Code Mapping</I></B></FONT></P>
<P>Gray-coding is commonly used with GA implementations due to the 1-bit change in neighboring gray-code values. The option to evaluate the matrix value deltas as gray-coded numbers was provided and investigated.
</P>
<P><FONT SIZE="+1"><B>EFFECT OF CHANGING GA PARAMETERS ON THIS PROBLEM</B></FONT></P>
<P>The GA implementation uses various parameters during a matrix-solution run. The effect of these parameters was studied in depth to access the parameters’ influence on the convergence and timeliness of the run. There were some unexpected observations made in this study.
</P>
<P>These studies were designed to have the GA run for about 30 seconds maximum. The resulting distance value was tracked as well as the time to run. Five runs at each setting were used to get a statistical spread of the parameter-setting effects. Rather than include pages and pages of multi-line plots, the main points of these studies are summarized. The author can be contacted for access to the detailed analysis.</P>
<P><FONT SIZE="+1"><B><I>Maximum Generations (MG) and Population Size (PS)</I></B></FONT></P>
<P>These two parameters are tightly intertwined in this problem due to the time deadline constraint; an increase in the population size will cause each generation to take longer to run. Population sizes in the range of 10 to 100 individuals were studied. Without accounting for the time factor, larger populations generally had better convergence values for a given number of generations. It was observed that the relation between MG and PS is a linear relation, where PS * MG = 1,000,000 resulted in a maximum-generation stopping time of about 30 seconds. A change in either PS or MG would yield the required value for the other. The population study was re-run with this time-normalized relationship, which showed an advantage in convergence value in a given time period to a population size of about 40 individuals. A PS of 40 requires a MG of 25,000 for 30 seconds. To achieve a 20 second time for a PS of 40, a MG of 25,000 * 2 / 3 = 17,000 (approximately) was used.
</P>
<P><FONT SIZE="+1"><B><I>Crossover Types</I></B></FONT></P>
<P>The 1-point, 2-point, and matrix-element crossover types were used with various usage weights. With 100% usage of the 1-point, or 80% or more of the matrix-element crossovers being used, the GA did not converge within the desired time. Various average mixes of these three crossover operators gave good results; there was not a clear mix which outperformed other mixes. The setting of 20%, 40%, 40% for the 1-point, 2-point, and matrix-element crossover operators proved to be a good robust setting.
</P>
<P><FONT SIZE="+1"><B><I>Number of Bits</I></B></FONT></P>
<P>The number of bits used (N) for each matrix delta value, and the resulting size of the search space had little effect on the operation of this GA. As expected, small values of N (8 or less) resulted in unacceptable results. Surprisingly, in the range from N=8 to N=64 bits, there was little difference in the performance of the GA in terms of time-to-converge and resulting distance value when finished.
</P>
<P><FONT SIZE="+1"><B><I>Maintaining the Best Performer</I></B></FONT></P>
<P>Maintaining the previous generation’s best performer in the current generation proved to be a valuable technique. Without this feature, runs were observed which would be converging, then lose the best performer and jump up a bit, continue to converge, then jump again, and so on, as depicted in Figure 2.9. While the average fitness of the population may have been continually decreasing over this entire period, the fact that the GA may be stopped at any given generation and the current best solution is to be used, made this unacceptable in a time-constrained GA.
</P>
<P><A NAME="Fig9"></A><A HREF="javascript:displayWindow('images/02-09.jpg',500,238)"><IMG SRC="images/02-09t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/02-09.jpg',500,238)"><FONT COLOR="#000077"><B>Figure 2.9</B></FONT></A> Effect of losing the best-performer on the best-of-generation solution.</P>
<P><FONT SIZE="+1"><B><I>Varying Mutation Rate and Comet-Strike Operator</I></B></FONT></P>
<P>Observation shows that increasingly introducing new genetic material into the population, and also mass introduction of new genetic material into the population, can revitalize the convergence rate in a stagnate run. Without these two mutation-type operations, runs were observed which would stagnate for many hundreds of generations. Given this tendency to favor mutation, a mutation study was undertaken to study the effect of increasing the basic single-bit mutation occurrence. Figure 2.10 shows the results of a series of runs where this mutation rate was increased, and the resulting average fitness for multiple runs is plotted. There is a trend to favor more and more chance of mutation up to a certain point (about 0.002 percent). Additional increases in mutation have a degrading effect on the GA’s performance as the system is becoming less of a GA engine and more of a random-search algorithm.
</P>
<P><A NAME="Fig10"></A><A HREF="javascript:displayWindow('images/02-10.jpg',500,384)"><IMG SRC="images/02-10t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/02-10.jpg',500,384)"><FONT COLOR="#000077"><B>Figure 2.10</B></FONT></A> Effect mutation rates on the best-of-generation solution.</P>
<P><FONT SIZE="+1"><B><I>Local Hill Climbing</I></B></FONT></P>
<P>Observation shows that this technique allowed the best performers to slide into a near-by better solution.
</P>
<P><FONT SIZE="+1"><B><I>Gray Code Mapping</I></B></FONT></P>
<P>As expected, the use of gray-code mapping had a positive effect on the generation-to-generation performance of the GA, resulting in a 9.5% better convergence value after a given number of generations. However, this is not the whole story. As discovered in implementing the gray-coding capabilities [8], the mapping from a binary integer to gray-code is a simple 1-line equation. However, the mapping from gray-code to a binary integer uses an iterative algorithm which loops on the number of bits (N). This code proved to be rather expensive to execute as was needed for each individual at each generation, and multiple times for the best performers in the local hill-climbing. While 9.5% better in average final value, the gray-code execution time was 2.2 times longer (49 S vs. 22 S for the settings used). With the emphasis on convergence value within a specific time-frame, the use of gray-coding was detrimental and was thus dropped for this problem.
</P>
<P><FONT SIZE="+1"><B><I>Use of a Matrix Subset</I></B></FONT></P>
<P>The technique of identifying a subset of the transformation matrix and only searching with nine of the sixteen matrix values proved to both allow acceptable convergence to be achieved as well as providing a time savings. Comparing using all sixteen matrix values to only using nine resulted in a 33% drop in the time-to-run, and a 23% better convergence value. Reducing the scope of the problem based on observed numerical results was beneficial.
</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="022-025.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="029-032.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 + -