📄 107-110.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=107-110//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="104-107.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="../ch07/111-113.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B><I>Problem #4: Service Isolation</I></B></FONT></P>
<P>As discussed above, there are a wide variety of issues which must be considered by the service provisioner. Maximizing service benefits and minimizing resource costs are generally important. However, other issues are also important. Here we consider the problem of service isolation.
</P>
<P>In order to model this problem using a genetic algorithm, a modification to the fitness function was made. In addition to the row and column penalties assessed as described above, an additional section was added to the parameters file as the following shows.</P>
<!-- CODE //-->
<PRE>
<B>Parameters File</B>
<B>Population</B> <B>Fitness</B>
<B>nrow</B> 10 <B>rowsum</B> 55 55 55 55 55 55 55 55 55 55
<B>ncol</B> 10 <B>rowfact</B> 10 10 10 10 10 10 10 10 10 10
<B>npop</B> 100 <B>rowexp</B> 1 1 1 1 1 1 1 1 1 1
<B>Random Seed</B> <B>colsum</B> 50 50 50 40 40 40 40 40 40 40
<B>seed</B> 0 <B>colfact</B> 50 50 50 10 10 10 10 10 10 10
<B>colexp</B> 1 1 1 1 1 1 1 1 1 1
<B>Stopping</B>
<B>stopgen</B> 4000 <B>Isolation Factor</B>
<B>stopfit</B> 0 1 1 1 1 1 1 1 1 1 1
<B>stopfitalt</B> 0 1 1 1 1 1 1 1 1 1 1
<B>Mutation</B> 1 1 1 1 1 1 1 1 1 1
<B>muprob</B> 0.05 0 0 0 0 0 0 0 0 0 0
<B>murng</B> 5 0 0 0 0 0 0 0 0 0 0
<B>mugenlarge</B> 20 0 0 0 0 0 0 0 0 0 0
<B>muproblarge</B> 0.2 0 0 0 0 0 0 0 0 0 0
<B>murnglarge</B> 2 0 0 0 0 0 0 0 0 0 0
<B>Tournament</B> 0 0 0 0 0 0 0 0 0 0
<B>dotour</B> 1
<B>toursize</B> 3
<B>tourwin</B> 1
<B>Crossover</B>
<B>xprob</B> 0.2
</PRE>
<!-- END CODE //-->
<P>Here, an array, <B>isofact</B>, captures the inter-service isolation factors desired. These factors act as multipliers and are applied whenever two services share a common resource. For the example shown, all factors are “1” for Services #1 .. #3 and “0” otherwise. This causes a penalty to be assessed whenever any of these services share resources with any other services.</P>
<P>This problem is studied here both because it is an important “real world” constraint, and because it adds an interesting epistasis to the problem domain. In addition to “competing” for resources, certain (high priority) services are forced to be separated from each other.</P>
<P>This example took 1,288 generations to arrive a zero penalty solution, shown here.</P>
<TABLE WIDTH="100%" BORDER><TR>
<TH ALIGN="LEFT" WIDTH="15%">
<TH ALIGN="LEFT" WIDTH="9%">Sv #1
<TH ALIGN="LEFT" WIDTH="8%">Sv #2
<TH ALIGN="LEFT" WIDTH="8%">Sv #3
<TH ALIGN="LEFT" WIDTH="8%">Sv #4
<TH ALIGN="LEFT" WIDTH="8%">Sv #5
<TH ALIGN="LEFT" WIDTH="8%">Sv #6
<TH ALIGN="LEFT" WIDTH="8%">Sv #7
<TH ALIGN="LEFT" WIDTH="8%">Sv #8
<TH ALIGN="LEFT" WIDTH="8%">Sv #9
<TH ALIGN="LEFT" WIDTH="12%">Sv #10
<TR>
<TD>Res #1
<TD>0
<TD>0
<TD>0
<TD>1
<TD>4
<TD>19
<TD>8
<TD>3
<TD>14
<TD>2
<TR>
<TD>Res #2
<TD>0
<TD>0
<TD>0
<TD>22
<TD>0
<TD>0
<TD>5
<TD>6
<TD>2
<TD>9
<TR>
<TD>Res #3
<TD>0
<TD>0
<TD>0
<TD>9
<TD>14
<TD>7
<TD>2
<TD>7
<TD>10
<TD>1
<TR>
<TD>Res #4
<TD>0
<TD>0
<TD>0
<TD>0
<TD>15
<TD>0
<TD>3
<TD>23
<TD>6
<TD>6
<TR>
<TD>Res #5
<TD>0
<TD>0
<TD>0
<TD>8
<TD>5
<TD>9
<TD>15
<TD>1
<TD>8
<TD>0
<TR>
<TD>Res #6
<TD>0
<TD>0
<TD>0
<TD>13
<TD>9
<TD>5
<TD>3
<TD>0
<TD>7
<TD>7
<TR>
<TD>Res #7
<TD>50
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
<TR>
<TD>Res #8
<TD>0
<TD>0
<TD>0
<TD>13
<TD>3
<TD>0
<TD>8
<TD>2
<TD>2
<TD>15
<TR>
<TD>Res #9
<TD>0
<TD>0
<TD>50
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
<TR>
<TD>Res #10
<TD>0
<TD>54
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
<TD>0
</TABLE>
<P>The solution found by the genetic algorithm shows that the isolation strategy has been achieved: Service #1 uses only Resource #7, Service #2 uses only Resource #10, and Service #3 uses only Resource #9.
</P>
<P><FONT SIZE="+1"><B>CONCLUSION</B></FONT></P>
<P>A genetic algorithm approach to an industrial decision problem, resource provisioning, has been considered. A flexibly parametrized program has been developed to investigate the problem for small-to-medium size examples. The genetic algorithm approach is shown to be feasible and matches human intuition for small examples. The genetic algorithm always found a reasonable solution in a reasonable number of generations. It did not always find an optimal solution in problems where an optimal solution was known to exist.
</P>
<P>The algorithm was applied in two basic cases. Two different extensions of the algorithm were also studied. One extension showed that simultaneously considering multiple cost and benefit factors is feasible within the same problem approach. A separate extension showed that adding a highly non-linear component to the fitness (penalty) function could also be handled easily within the same framework.</P>
<P><FONT SIZE="+1"><B>REFERENCES</B></FONT></P>
<DL>
<DD><B>1</B> Goldberg, D. (1989). <I>Genetic algorithms in search, optimization and machine learning</I>. Reading, MA: Addison-Wesley.
<DD><B>2</B> <I>Genetic Algorithms Digest</I>: <A HREF="http://www.aic.nrl.navy.mil/galist">http://www.aic.nrl.navy.mil/galist</A>.
<DD><B>3</B> Michalewicz, Z. (1992). <I>Genetic algorithms + data structures = evolution Programs</I>. New York: Springer-Verlag.
<DD><B>4</B> Cox, L.A., Davis, L., Qiu, Y. (1991). Dynamic anticipatory routing in circuit-switched telecommunications networks. In Davis, L. (Ed.), <I>Handbook of genetic algorithms</I>.
<DD><B>5</B> Davis, L., Coombs, S. (1987). Genetic algorithms and communication link speech design: Theoretical considerations, constraints and operators. In <I>Genetic Algorithms and Their Applications, Proceedings of the Second International Conference on Genetic Algorithms</I>, Cambridge, MA: MIT Press.
<DD><B>6</B> Surry, P., Radcliffe, N. (1995). A Multi-objective approach to constrained optimization of gas supply networks: The COMOGA method. In Fogarty, T. (Ed.), <I>AISB-EC-95</I>.
<DD><B>7</B> Michalewicz, Z. (1995). A survey of constraint handling techniques in evolutionary computation methods. In McDonnell, J., Reynolds, R., Fogel, D. (Ed.) <I>Evolutionary Programming IV</I>, Cambridge, MA: MIT Press.
</DL>
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="104-107.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="../ch07/111-113.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 + -