📄 098-101.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=098-101//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="095-097.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="101-104.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B>COMPUTER IMPLEMENTATION</B></FONT></P>
<P>The computer code for this investigation is implemented in the “C” language and consists in its current version of about 4,000 lines of code. All experiments were run on a SUN platform running UNIX. All parameters for a run are contained in a parameters file described below.
</P>
<P>The initial population is generated by a separate program, <B>randArray</B>, which simply generates a population of arrays of integers within certain bounds. For experiments here, the bounds 0…10 were used.</P>
<P>The principal program operates by reading the initial population from standard input performing the genetic algorithm according the settings in the parameters file (taken as an argument), and writing the final population to the standard output. This design is a standard UNIX approach that permits “chaining” of different variants of the algorithm into an extended algorithm and provides a convenient tool for investigation of time-varying parameters for the program as well.</P>
<P>For each generation, the following steps are performed:</P>
<DL>
<DD><B>1.</B> <B>Fitness</B> computation
<DD><B>2.</B> <B>Tournament</B> selection
<DD><B>3.</B> <B>Mutation</B>
<DD><B>4.</B> <B>Crossover</B>
</DL>
<P>After each step above, the complete population is scanned to see whether any individual has fitness less than the stopping fitness parameter. If so, the genetic algorithm terminates. If not, it continues up to a maximum (parameterized) number of generations.
</P>
<P><FONT SIZE="+1"><B><I>The Parameters File</I></B></FONT></P>
<P>The parameters file guides the operation of the genetic algorithm. It contains all problem-specific information as well as all “tuning” parameters. Each of the entries in the parameters file is described here.
</P>
<P>Population parameters:</P>
<DL>
<DD><B>•</B> <B>nrow</B> - number of rows (resources)
<DD><B>•</B> <B>ncol</B> - number of columns (services)
<DD><B>•</B> <B>npop</B> - population size
</DL>
<P><FONT SIZE="+1"><B><I>Random number seed</I></B></FONT></P>
<DL>
<DD><B>•</B> <B>seed</B> - random number seed. “0” is used to request a “current time” based seed.
</DL>
<P><FONT SIZE="+1"><B><I>Stopping parameters</I></B></FONT></P>
<DL>
<DD><B>•</B> <B>stopgen</B> - maximum number of generations to run before stopping the algorithm
<DD><B>•</B> <B>stopfit</B> - maximum value of “acceptable” fitness. Ideally, this would be “0” but for tightly constrained or overconstrained problems, setting this to a “reasonable” value aids in problem convergence.
</DL>
<P><FONT SIZE="+1"><B><I>Mutation parameters</I></B></FONT></P>
<DL>
<DD><B>•</B> <B>muprob</B> - represents the probability of individual allele mutation.
<DD><B>•</B> <B>murng</B> - represents the maximum range of mutation value possible. For example, by setting murng=10, a mutation will select a “delta” value uniformly in the range of - 10…+10 and apply it to the allele.
<DD><B>•</B> <B>mugenlarge</B> - duration (in generations) between “epochal” mutation. Every “muperiodlarge” generations a different set of mutation parameters is put into effect for a single generation.
<DD><B>•</B> <B>muproblarge</B> - the probability of individual allele mutation during the “epochal” generation. Generally this is larger than muprob.
<DD><B>•</B> <B>murnglarge</B> - the maximum range of mutation value during the “epochal” generation.
</DL>
<P><FONT SIZE="+1"><B><I>Tournament parameters</I></B></FONT></P>
<DL>
<DD><B>•</B> <B>toursize</B> - number of participants in each tournament.
<DD><B>•</B> <B>tourwin</B> - number of winners chosen in each tournament.
</DL>
<P><FONT SIZE="+1"><B><I>Fitness Parameters</I></B></FONT></P>
<P>All fitness parameters here have a default value of “1” unless otherwise specified.
</P>
<DL>
<DD><B>•</B> <B>rowsum</B> - vector of numbers representing <B>MAXIMUM</B> weighted row sums which can occur without penalty.
<DD><B>•</B> <B>rowfact</B> - vector of numbers representing multipliers for row penalty values.
<DD><B>•</B> <B>rowexp</B> - vector of numbers representing exponents applied to row penalty values.
<DD><B>•</B> <B>colsum</B> - vector of numbers representing <B>MINIMUM</B> weighted column sums which can occur without penalty.
<DD><B>•</B> <B>colfact</B> - vector of numbers representing multipliers for column penalty values.
<DD><B>•</B> <B>colexp</B> - vector of numbers representing exponents applied to column penalty values.
<DD><B>•</B> <B>cost</B> - array of numbers representing unit cost per allele in the chromosome. These are used as multipliers when computing row (resource) penalties.
<DD><B>•</B> <B>bene</B> - array of numbers representing unit benefits per allele in the chromosome. These are used as multipliers when computing column (service) penalties.
</DL>
<P><FONT SIZE="+1"><B>INVESTIGATIONS</B></FONT></P>
<P>The problem examples below are all based on the genetic algorithm formulation above. All examples can be run using the same code formulation with varying values for the problem parameters.
</P>
<P><FONT SIZE="+1"><B><I>Problem #1: Tight Constraints</I></B></FONT></P>
<P>The parameters file for this problem is shown here:
</P>
<!-- CODE //-->
<PRE>
<B>Population</B> <B>Fitness</B>
<B>nrow</B> 5 <B>rowsum</B> 25 25 25 25 25
<B>ncol</B> 5 <B>rowfact</B> 1 1 1 1 1
<B>npop</B> 100 <B>rowexp</B> 1 1 1 1 1
<B>Random Seed</B> <B>colsum</B> 25 25 25 25 25
<B>seed</B> 0 <B>colfact</B> 1 1 1 1 1
<B>colexp</B> 1 1 1 1 1
<B>Stopping</B>
<B>stopgen</B> 100
<B>stopfit</B> 0
<B>Mutation</B>
<B>muprob</B> 0.01
<B>murng</B> 5
<B>Tournament</B>
<B>dotour</B> 1
<B>toursize</B> 5
<B>tourwin</B> 1
<B>Crossover</B>
<B>xprob</B> 0.2
</PRE>
<!-- END CODE //-->
<P>The best (minimal) fitness for each generation is shown next:
</P>
<P><A NAME="Fig2"></A><A HREF="javascript:displayWindow('images/06-02.jpg',400,238)"><IMG SRC="images/06-02t.jpg"></A><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="095-097.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="101-104.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 + -