📄 101-104.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:Genetic Algorithms for Constrained Service Provisioning</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=6//-->
<!--PAGES=101-104//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="098-101.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="104-107.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
</P>
<P><FONT SIZE="+1"><B><I>Discussion for Problem #1</I></B></FONT></P>
<P>This problem is small (five resources, five services) and simple (all resources and services are interchangeable). The interesting part is that the sum of the resource constraints is equal to the sum of the service constraints. Since the resource constraints are <B>maxima</B> and the service constraints are <B>minima</B>, equality of their sum means that, for a zero penalty solution, all constraints must be met exactly. Since the number of constraints (10: one for each row, one for each column) is far less than the number of variables (25 alleles per chromosome), this problem is, in general, solvable. However, the solution space can be thought of as a “thin” (15-dimensional) hyperplane in 25-dimensional space. This is actually a rather small “target” for the genetic algorithm to hit!</P>
<P>The genetic algorithm was able to find a zero penalty solution in 64 generations. The solution found is shown here:</P>
<TABLE WIDTH="100%" BORDER><TR>
<TH WIDTH="20%" ALIGN="LEFT">
<TH WIDTH="15%" ALIGN="LEFT">Svc #1
<TH WIDTH="15%" ALIGN="LEFT">Svc #2
<TH WIDTH="15%" ALIGN="LEFT">Svc #3
<TH WIDTH="15%" ALIGN="LEFT">Svc #4
<TH WIDTH="20%" ALIGN="LEFT">Svc #5
<TR>
<TD>Res #1
<TD>2
<TD>7
<TD>7
<TD>1
<TD>8
<TR>
<TD>Res #2
<TD>6
<TD>2
<TD>8
<TD>8
<TD>1
<TR>
<TD>Res #3
<TD>3
<TD>6
<TD>2
<TD>5
<TD>9
<TR>
<TD>Res #4
<TD>10
<TD>2
<TD>8
<TD>3
<TD>2
<TR>
<TD>Res #5
<TD>4
<TD>8
<TD>0
<TD>8
<TD>5
</TABLE>
<P>This problem turns out to be “easy” for the genetic algorithm. It was performed as a feasibility test for the general approach described in this chapter.
</P>
<P><FONT SIZE="+1"><B><I>Problem #2: Unequal Resources and Services</I></B></FONT></P>
<P>The parameters file for this problem are shown here:
</P>
<!-- CODE //-->
<PRE>
<B>Parameters File</B>
<B>Population</B> <B>Fitness</B>
<B>nrow</B> 6 <B>rowsum</B> 30 30 30 30 30 30
<B>ncol</B> 6 <B>rowfact</B> 1 1 1 1 1 1
<B>npop</B> 100 <B>rowexp</B> 1 1 1 1 1 1
<B>Random Seed</B> <B>colsum</B> 60 60 60 60 60 60
<B>seed</B> 0 <B>colfact</B> 1 1 1 1 1 1
<B>colexp</B> 1 1 1 1 1 1
<B>Stopping</B>
<B>stopgen</B> 2000 <B>Cost</B>
<B>stopfit</B> 0 1 1 1 2 2 2
1 1 1 2 2 2
<B>Mutation</B> 1 1 1 2 2 2
<B>muprob</B> 0.01 2 2 2 1 1 1
<B>murng</B> 5 2 2 2 1 1 1
<B>mugenlarge</B> 10 2 2 2 1 1 1
<B>muproblarge</B> 0.2
<B>murnglarge</B> 2 <B>Beneft</B>
1 1 1 1 1 1
<B>Tournament</B> 2 2 2 2 2 2
<B>dotour</B> 1 3 3 3 3 3 3
<B>toursize</B> 3 3 3 3 3 3 3
<B>tourwin</B> 1 2 2 2 2 2 2
1 1 1 1 1 1
<B>Crossover</B>
<B>xprob</B> 0.2
</PRE>
<!-- END CODE //-->
<P>The best (minimal) fitness for each generation is shown below:
</P>
<P><A NAME="Fig3"></A><A HREF="javascript:displayWindow('images/06-03.jpg',400,229)"><IMG SRC="images/06-03t.jpg"></A></P>
<P><FONT SIZE="+1"><B><I>Discussion for Problem #2</I></B></FONT></P>
<P>The problem size is almost the same as for Problem #1 (six resources and six services) but, in this problem, it is much more difficult to “see ”a solution by inspection. The genetic algorithm quickly comes near to a solution after about 300 generations (penalty 10) and thereafter, does not find further improvement.
</P>
<P>This problem was “rigged” so that both the cost and benefits matrices (shown above) have unequal entries. Examining the <B>cost</B> array for resources, we see that resources #1 … #3 are more efficient for providing services #1 … #3. Similarly, resources #4 … #6 are more efficient for providing services #4 … #6.</P>
<P>The <B>bene</B> (benefits) array is also biased. Services #3 and #4 provide the most benefit per unit of resource with other services diminishing in value per resource used. Putting this together, it makes most sense (to a person!) to provide most of services #1 … #3, with resource #3 and most of services #4 … #6 with resource #4.</P>
<P>The solution found by the genetic algorithm is shown here:</P>
<TABLE WIDTH="100%" BORDER><TR>
<TH ALIGN="LEFT" WIDTH="15%">
<TH ALIGN="LEFT" WIDTH="14%">Svc #1
<TH ALIGN="LEFT" WIDTH="14%">Svc #2
<TH ALIGN="LEFT" WIDTH="14%">Svc #3
<TH ALIGN="LEFT" WIDTH="14%">Svc #4
<TH ALIGN="LEFT" WIDTH="14%">Svc #5
<TH ALIGN="LEFT" WIDTH="15%">Svc #6
<TR>
<TD>Res #1
<TD>7
<TD>6
<TD>7
<TD>4
<TD>0
<TD>0
<TR>
<TD>Res #2
<TD>6
<TD>11
<TD>7
<TD>3
<TD>0
<TD>0
<TR>
<TD>Res #3
<TD>9
<TD>10
<TD>13
<TD>0
<TD>0
<TD>0
<TR>
<TD>Res #4
<TD>0
<TD>0
<TD>0
<TD>13
<TD>15
<TD>10
<TR>
<TD>Res #5
<TD>6
<TD>0
<TD>0
<TD>2
<TD>6
<TD>10
<TR>
<TD>Res #6
<TD>2
<TD>2
<TD>0
<TD>7
<TD>5
<TD>10
</TABLE>
<P>The genetic algorithm has approximately duplicated the “experienced provisioners” solution. This solution is not “ideal” (zero penalty) but there is no obvious (to this author!) way to improve the solution.
</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="098-101.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="104-107.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 + -