📄 249-252.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:Gauss-Legendre Integration Using Genetic Algorithms</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=12//-->
<!--PAGES=249-252//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="248-249.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="252-255.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B>A HYBRID APPROACH</B></FONT></P>
<P>A Newton-Raphson algorithm lies at the heart of the hybrid approach presented here. This method suffers from its sensitivity to the initial guess it is supplied, but it is still the most popular algorithm for solving systems of nonlinear equations. Once the neighborhood of a root has been identified, Newton’s method provides an efficient means of converging to the root, if it exists, or of spectacularly failing to converge, indicating that there is no root in the neighborhood. Thus, the focus of the hybrid scheme is to effectively locate regions in which roots are likely to exist; a problem that proves to be readily solved using a GA.
</P>
<P>Newton’s method is driven by derivative information and is derived from Taylor’s series analysis. In the solution of systems of equations, the method employs a linear model to solve the equations. A linear model of <B>f(x)</B> is of the form</P>
<P ALIGN="CENTER"><IMG SRC="images/12-07d.jpg"></P>
<P>where J is a matrix. Usually <B>a</B><SUB><SMALL>0</SMALL></SUB> = <B>f</B>(<B>x</B><SUB><SMALL>0</SMALL></SUB>), and Equation (12.6) is then the first two terms of the Taylor’s series of <B>f</B>(<B>x</B>) if the model J uses the first derivatives. We want to have <B>f</B>(<B>x</B>) = 0, and so set the model in Equation (12.6) equal to zero and solve for <B>x</B> to obtain</P>
<P ALIGN="CENTER"><IMG SRC="images/12-08d.jpg"></P>
<P>An iteration is formed from Equation (12.7) above in an obvious way. Note that an N by N system of linear equations must be solved at each iteration. Thus, such derivative-based methods can be time consuming.
</P>
<P>Newton’s method for systems of nonlinear equations uses the linear model based on the “tangent planes.” Since <B>f</B>(<B>x</B>) = 0 is N equations</P>
<P ALIGN="CENTER"><IMG SRC="images/12-09d.jpg"></P>
<P><I>y</I> = <I>f</I><SUB><SMALL>i</SMALL></SUB>(x) defines a surface. At x<SUB><SMALL>0</SMALL></SUB>, the tangent plane to the surface is</P>
<P ALIGN="CENTER"><IMG SRC="images/12-10d.jpg"></P>
<P>The matrix J is the <I>Jacobian</I> matrix</P>
<P ALIGN="CENTER"><IMG SRC="images/12-11d.jpg"></P>
<P>The linearized model employed by Newton’s method is quite effective if the initial guess of <B>x<SUB><SMALL>0</SMALL></SUB></B> is reasonably close to a root. However, the development of the coefficients required in Gauss-Legendre quadrature is such a case; after all, if the values of the coefficients are approximately known, then the value of the integral can more than likely be accurately approxmiated. Thus, in the hybrid approach proposed, a GA is employed to locate regions in which roots to the system of equations are likely to exist.</P>
<P>GAs are search algorithms based on the mechanics of natural genetics. Despite the numerous variations to Holland’s basic GA [9], the majority of evolutionary algorithms proceed as follows:</P>
<DL>
<DD><B>1.</B> generate a population of strings coded to represent potential solutions to the search problem at hand;
<DD><B>2.</B> evaluate the effectiveness or quality of the solutions represented by the strings in the current population (compute a <I>fitness function</I> value for each string);
<DD><B>3.</B> make copies of strings in proportion to the effectiveness of the solutions they represent (in proportion to their fitness function values) and combine portions of these highly fit strings according to genetic operators to produce a new population of strings (a new <I>generation</I>);
<DD><B>4.</B> repeat steps 2 and 3 until a suitable solution to the search problem has been found.
</DL>
<P>The different varieties of evolutionary algorithms occur due to the genetic operators, the definition of the coding scheme, and the fitness function. In this chapter, the genetic operators are from the <I>simple genetic algorithm</I> due to Goldberg [8]. Computer code for implementing the algorithm can be found in the reference by Goldberg [8].</P>
<P>The coding scheme for this problem is accomplished using a relatively standard coding scheme. A <I>concatenated, binary, linearly mapped coding</I> scheme is employed [8]. In this scheme, the parameters of the search problem are represented as bit strings. For example, in the two-point Gauss-Legendre problem, there exist four equations in four unknowns. The equations are presented collectively as Equation (12.3) and the unknowns are w<SUB><SMALL>1</SMALL></SUB>, w<SUB><SMALL>2</SMALL></SUB>, x<SUB><SMALL>1</SMALL></SUB>, and x<SUB><SMALL>2</SMALL></SUB>. The four parameters are each coded as binary strings according to the formula</P>
<P ALIGN="CENTER"><IMG SRC="images/12-12d.jpg"></P>
<P>where p is the parameter being coded, p<SUB><SMALL>min</SMALL></SUB> is the minimum value of the parameter (in the case of x<SUB><SMALL>i</SMALL></SUB>, the minimum value is -1, while for w<SUB><SMALL>i</SMALL></SUB>, it is 0), p<SUB><SMALL>max</SMALL></SUB> is the maximum value of the parameter (in the case of both x<SUB><SMALL>i</SMALL></SUB> and w<SUB><SMALL>i</SMALL></SUB>, the maximum values are 1), and b is the decimal value associated with a binary string of length <I>l</I>. Each of the parameters in the search problem is represented in this fashion, and then concatenated to form a single string that represents a complete solution to the problem. To achieve the accuracy required in this application, bit strings of length forty were employed.</P>
<P>The fitness function is based on identifying the zero-contours of the individual functions <I>f</I><SUB><SMALL>i</SMALL></SUB>. The fitness function to be minimized by the genetic algorithm is</P>
<P ALIGN="CENTER"><IMG SRC="images/12-13d.jpg"></P>
<P>where <I>g</I> is the fitness function to be minimized, <I>max</I>[<I>abs</I>(<I>f</I><SUB><SMALL>i</SMALL></SUB>)] is the maximum value of the absolute value of individual equations in the system <B>f</B>(<B>x</B>) = 0, and N is the number of equations in the system. This function <I>g</I> is a positive definite function that contains global minimums at each of the roots to the system of equations. Recall that a GA will not guarantee convergence to the roots of the equation, but it will rapidly locate regions in which the fitness function is minimal. For the problem of solving systems of nonlinear equations, these regions will likely contain roots to the equations or points at which the zero-contour lines approach but do not cross (false roots).</P>
<P>The hybrid approach is built around two concepts. First, once regions in which roots are likely to exist have been determined, a Newton method can quickly distinguish between “real roots” and “false roots.” If there are roots in the region, a Newton method will rapidly converge to the roots. Second, a GA can be used to rapidly determine regions in which roots are likely to exist. It does so by minimizing a fitness function that indicates promising regions in the search space. The solutions determined by the GA are used as initial guesses supplied to a Newton-Raphson method. As will be seen in the next section, the result is a hybrid scheme that is far more efficient than a Newton method alone.</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="248-249.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="252-255.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 + -